3.2 Process Scheduling

 다중 프로그래밍의 목적은 CPU 활용률을 극대화하기 위해 언제나 어떤 프로세스가 실행 중이어야 한다는 것이다. 반면에 time sharing으 목적은 CPU 코어를 프로세스 간에 자주 전환하여 사용자가 각 프로그램이 실행되는 동안 사용자가 동시에 여러 작업을 수행하는 것처럼 보이게 하여, 각 프로그램이 실행되는 동안 입력을 제공하고 출력을 확인할 수 있도록 하는 것이다.

 이 두 목표를 달성하기 위해서 process scheduler 는 각 프로그램이 실행을 위해 사용 가능한 프로세스를 선택한다. 각 CPU 코어는 한 번에 하나의 프로세스만 실행할 수 있다. 단일 CPU 코어 시스템의 경우 한 번에 하나의 프로세스만 실행되므로, 여러 코어 시스템은 한 번에 여러 프로세스를 실행할 수 있다. 단일 CPU 코어 시스템의 경우 한 번에 하나의 프로세스만 실행되므로, 다중 코어 시스템은 한 번에 여러 프로세스를 실행할 수 있다. 코어보다 더 많은 프로세스가 있는 경우 초과 프로세스는 코어가 비어 있고(할당이 안되어 있어서 자기 차례의 실행이 올때까지 기다리는 상태), 다시 스케줄링 될 때 까지 기다려야 한다. 현재 메모리에 있는 프로세스의 수를 degree of multiprogramming 이라고 한다.

 다중 프로그래밍과 타임 쉐어링의 목표를 균형있게 유지하기 위해서는 프로세스의 일반적인 동작도 고려해야 한다. 일반적으로 대부분의 프로세스는 I/O-bound 또는 CPU-bound로 설명할 수 있다. I/O-bound process는 계산보다 I/O를 수행하는 시간이 더 많은 프로세스 이다. 반면에 CPU-bound process는 드물게 I/O 요청을 생성하고, 계산을 수행하는 데 더 많은 시간을 사용한다.

• 다중 프로그래밍의 목적은 CPU 활용률을 극대화 하는 것
• 시분할 시스템의 목적은 프로세스 간에 자주 전환을 하여 각 프로그램들이 실행되는 동안 입력과 출력을 할 수 있도록 하는 것
• 코어보다 많은 프로세스가 있을 경우 초과되는 프로세스는 코어가 비어있음, 재스케줄링을 기다려야 함
• 메모리에 있는 프로세스의 수를 degree of multiprogramming이라고 함
• 프로세스는 I/O-bound process, CPU-bound process 두가지로 간주될 수 있다.
• I/O-bound process는 I/O를 수행하는 시간이 더 많은 프로세스이다.
• CPU-bound process는 계산을 수행하는데 더 많은 시간을 사용한다.

 

3.2.1 Scheduling Queues

 프로세스가 시스템에 진입(RAM에 진입)하게 되면, CPU 코어에서 실행되기 위해 ready 상태가 되고 그 후에 ready queue에 넣어진다. 이 큐는 일반적으로 linked-list 형태로 된다. 준비 큐의 헤더는 list에서 첫번째 PCB에 대한 포인터를 포함하고, 각 PCB에는 준비 큐에서 다음 PCB를 가르키는 포인트 필드가 포함되게 된다.

 하나의 큐만이 아니라 다른 큐도 포함된다. 프로세스가 CPU 코어를 할당 받으면 일정 시간 동안 실행되다가 결국 중단되거나 특정 이벤트 발생을 기다리게 된다.

 예를 들어 CPU를 할당 받은 프로세스가 디스크와 유사한 장치에 I/O request을 수행하는 경우를 가정해보자. 장치는 프로세서보다 헤비하고 느리게 실행되므로, 프로세스는 I/O가 사용 가능해질 때까지 기다려야한다. 이 I/O 가 사용 가능하다는 특정 이벤트가 발생할 때까지 기다리는 프로세스들은 모두 wait queue에 배치된다.

 프로세스 스케줄링을 나타내는 위 그림에서, 원은 큐를 제공하는 resource을 나타내며, 화살표는 시스템에서 프로세스의 흐름을 나타낸다. 새 프로세스는 처음에 준비 큐에 넣는다. 그곳에서 실행되기 위해 선택/배치될 때까지 기다린다. 프로세스가 CPU 코어를 할당받고 실행 중일 때, 여러 이벤트가 발생할 수 있다.

• 프로세스가 I/O 요청을 보낼 수 있고, 그런 다음 I/O wait queue 에 배치될 수 있다
• 프로세스가 새로운 자식 프로세스를 생성하고, 자식의 종료를 기다리는 동안 wait queue에 배치될 수 있다.
• 프로세스가 인터럽트로 인해 강제로 코어에서 제거되어 interrupt wait queue에 배치되게 된다.
• 프로세스는 시간 조각이 만료되어 ready queue에 다시 넣을 수도 있다.

 첫번째, 두번째의 경우에 프로세스가 최종적으로 waiting state 에서 ready state 로 전환되고, 그 다음 ready queue 에 다시 넣는다. 프로세스는 종료될 때까지 이러한 주기를 반복하며, 그 때 모든 큐에서 제거되고 해당 PCB 및 리소스가 해제가 된다.

• 프로세스가 RAM에 올려져 실행되기 위해 ready state를 가짐
• ready state 가 되고 ready queue(linked list)에 배치
• ready queue에는 PCB에 대한 포인터, 다음 PCB를 가르키는 포인터 가 있음
• ready queue에서 기다리는 프로세스 들은 자신의 차례에 CPU 코어를 할당 받게되고, 이때 다양한 이벤트가 발생됨
• I/O request의 경우, I/O 장치가 가용할 때까지 기다려야 하기에 이 이벤트가 발생할 때까지 프로세스들은 모두 I/O wait queue에 배치됨
• Create child process는 자식 프로세스를 생성하고, 자식의 종료를 기다리는 동안 child termination wait queue에 배치됨
• Wait for an Interrupt는 강제로 코어에서 제거되고 interrupt wait queue에 배치된다.
• Time slice expired는 실행 가능한 시간이 끝난 경우로 시분할 시스템에서 각 프로세스에게 CPU의 할당 시간을 정해두고 해당 시간이 끝나면 CPU 제어를 반환하고 다시 ready queue로 가서 기다림

 

3.2.2 CPU Scheduling

 프로세스는 life cycle 전체를 ready queue와 다양한 wait queue 사이를 이동하며, CPU scheduler의 역할은 ready queue에 있는 프로세스 중에서 선택을 통해 CPU 코어를 할당해주는 것이다. CPU scheduler는 CPU를 새로운 프로세스에게 빈번히 할당해야 한다. I/O-bound process는 I/O 요청을 기다리는 동안 몇 밀리초 만에 실행될 수 있다. CPU-bound process는 CPU 코어를 더 오래 사용해야 하지만, 스케줄러는 코어를 긴 시간동안 한 프로세스에게 할당할 가능성이 적다. 대신에 다른 프로세스를 실행하도록 강제로 CPU 를 제거하고 다른 프로세스를 스케줄링한다. 따라서 CPU 스케줄링은 일반적으로 최소 100밀리초마다 실행되지만, 일반적으로 훨씬 더 자주 실행된다.

 일부 운영 체제에는 swapping 이라는 중간 형태의 스케줄링이 있다. swapping 이라는 처리는 메모리에서 프로세스를 제거하고, degree of multiprogramming을 줄일 수 있는 행위다. 그 후에 프로세스는 다시 메모리에 도입되고, 실행은 이전에 남아 있던 곳에서 계속할 수 있다. 이 방법이 swapping이다. 현재 상태를 저장하기 위해 메모리에서 디스크로 swapped out이 될 수도 있고, 나중에 디스크에서 메모리로 swapped in도 될 수 있다. 스왑은 메모리가 과부하되고 해제되어야 할 때에만 필요하다.

• 프로세스는 ready queue의 프로세스 중 선택을 하여 CPU 코어를 할당해주는 일을 함
• 여기서 I/O-bound process는 I/O 요청을 기다리는 동안 몇(1~10) 밀리초만에 실행됨
• 하지만 CPU-bound process는 CPU를 오래 붙잡기 때문에 적당한 시간을 두어 다른 프로세스에게 양보해야함(보통 100 밀리초마다 실행됨, 지금은 훨씬 더 자주 실행).
• swapping 은 중간 형태의 스케줄링으로 메모리 과부하 혹은 interrupt 와 같은 강제로 CPU 반환을 하게 되었을때 수행됨
• swapping 은 메모리에서 프로세스를 제거하고, degree of multiprogramming을 줄임
• swapping은 swapped out(메모리 → 디스크, context를 저장하고) 이후에 swapped in(디스크 → 메모리)을 수행할 수 있게 된다.

 

3.2.3 Context Switch

  인터럽트는 운영체제가 CPU 코어를 현재 작업에서 변경하여 커널 루틴을 실행하게 만든다. 이러한 작업은 일반적인 운영체제에서 자주 발생한다. 인터럽트가 발생되면 시스템은 CPU 코어에서 실행중인 프로세스의 현재 컨텍스트를 저장해야 한다(PCB에 있을 것임). 그렇게 하면 처리가 완료될 때, 해당 컨텍스트를 복원할 수 있고, 프로세스를 일시 중지한 다음 다시 실행을 거기서부터 할 수 있을 것이다. 컨텍스트는 프로세스의 PCB 데이터 구조에 표시된다. 일반적으로 현재 CPU 코어의 현재 상태를 저장(state save)하고(커널/사용자 모드에서), 그런 다음 작업을 계속하기 위해 상태를 복원(state restore)한다.

 CPU 코어를 다른 프로세스로 전환하려면 현재 프로세스의 상태를 저장하고 다른 프로세스의 상태를 복원해야 한다. 이 작업을 Context Switch(Swapping이랑은 다름, Swapping은 메모리 관리 기술이며, 프로세스 전체 상태를 저장하고 불러오지만, Context Switch는 시분할 시스템에서만 발생하고, CPU 의 제어권을 전환하는 작업이고 CPU 레지스터, 실행 상태 등의 작은 것만 저장하고 복구함, 따라서 Swapping은 RAM과 Disk 간의 작업, Context Switch는 CPU와 RAM 간의 작업임)라고 하며, 위의 그림이 이 내용을 설명해주고 있다. Context Switch가 발생하면, 커널은 이전 프로세스의 컨텍스트를 해당 PCB에 저장하고 실행할 새로운 프로세스의 저장된 컨텍스트를 로드한다. 컨텍스트 스위치 작업이 시스템에 추가적인 부하를 일으키는데, 이는 원래 원하던 작업을 수행하는게 아니라 불필요한 작업을 수행하게 되고, 스위치 시간은 시스템 리소스를 소비하는 순수한 오버헤드로 간주되게 된다. 스위칭 속도는 메모리 속도, 복사해야 하는 레지스터의 수, 특수 명령어의 존재 와 같은 기계에 따라 다르다. 기본적으로 마이크로초의 시간이 걸린다.

• CPU 코어를 현재 작업에서 다른 커널 루틴의 작업으로 변경하게 만드는 행위를 Context Switch라고 함
• Swapping이랑 Context Switch는 서로 다른 작업임
• Context Switch 가 발생하면, 커널은 이전 프로세스의 컨텍스트를 PCB에 저장함
• 그 다음 커널이 실행할 새로운 프로세스의 저장된 컨텍스트를 로드