CPU Scheduling, Scheduler

geonmyung·2020년 8월 25일

Scheduling의 목적

만약 단일 처리 시스템이라면 실행 중인 프로세스가 입출력을 요청하면, 이 프로세스가 실행을 모두 마칠 때까지 사용하던 자원을 대기해야 하므로 효율이 떨어진다. 하지만 다중 처리 시스템에서는 여러 프로세스를 동시에 메모리에 올려놓고 실행 중인 프로세스가 입출력을 요청한다면, 운영체제가 자원을 회수하여 다른 프로세스에게 할당한다.
좋은 스케줄링은 CPU가 쉬지 않고 돌 수 있도록 해준다!

처리량 최대화
자원 활용도 최대화
무기한 연기 회피
오버헤드 최소화

1. CPU Scheduling

실행 준비가 된(Ready queue에 있는) 프로세스 중에서 하나를 선택하여 CPU를 할당하는 것
- 위의 의미을 다시 세분화하면 Dispatch와 스케줄링으로 나눌 수 있는데,
  프로세스를 고르는 작업을 스케줄링, 선택한 프로세스에 CPU를 할당하여 running으로 바꾸는 것을 Dispatch라고 한다.
- +) Dispatch를 하는 것을 Dispatcher, Dispatch하는데 걸리는 시간을 Dispatch latency라고 부른다.
CPU 스케줄링이 발생하는 상황
1) running -> waiting (입출력 요청, event wait)
2) running -> ready (인터럽트 발생)
3) waiting -> ready (입출력 완료, event completion)
4) terminated (프로세스 수행 완료)

1), 4)번은 프로세스가 자발적으로 CPU를 내려놓은 것이다. -> 스스로 반납할 때까지 계속 사용하도록 허용하는 방식 -> Non-preemptive scheduling
2), 3)번은 실행 중인 프로세스로부터 CPU를 빼앗고 다른 프로세스에게 할당해 줄 수 있는 방식 -> Preemptive scheduling

프로세스 상태

new : 프로세스가 만들어진 상태
running : 프로세스가 실제로 도는 상태
waiting : I/O 나 다른 이벤트가 발생하기를 기다리는 상태(= "이제부터 너에게도 CPU를 줄게!"라고 결정되면 ready 상태가 된다.)
ready : CPU만 받으면 바로 일할 수 있는 상태(= 실행 준비가 다 된 상태에서 기다리는 것)
terminated : 프로세스가 종료된 상태

프로세스 스케줄링 큐 (Scheduling queue)

Job queue : 현재 시스템 내에 있는 모든 프로세스의 집합
Ready queue : 현재 메모리 내에 있으면서 CPU를 받아 실행되기를 기다리는 프로세스의 집합
Device queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

상태 전이 : 이 프로세스의 프로세스 포인터 블록 포인터를 이 큐에서 저 큐로 옮기는 것
(프로세스 포인터 블록은 엄청나게 무거워서 프로세스를 들어서 옮기는 것이 아니라 그걸 가리키는 포인터를 만들어줘 포인터만 옮겨준다.)

큐잉 도표 (Queueing diagram)

프로세스 스케줄링의 공통적인 표현 방식

2. Scheduler의 종류

운영체제에서는 다양한 스케줄러를 이용하여 프로세스를 관리한다.
둘 이상의 프로세스가 적절히 실행되도록 컨트롤 해준다.
실행 준비가 되어 CPU를 할당해줄 프로세스를 메모리에서 선택한다.
프로세스를 스케줄링 해준다.

Long-term scheduler (job scheduler)

한정된 메모리에 프로세스들이 한꺼번에 메모리에 올라올 때, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool에 저장되어 있는 프로세스 중, 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정한다.

메모리와 디스크 사이의 스케줄링을 담당
프로세스에 memory(+리소스) 할당(admit)
degree of multiprogramming 제어 (= 현재 돌고 있는 프로세스의 개수 조절)
프로세스의 상태 (new -> ready)

Short-term scheduler (CPU scheduler)

CPU Scheduling을 한다!!!
CPU와 메모리 사이의 스케줄링 담당
Ready queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정 -> 프로세스에 CPU 할당
매우 빈번하게 실행된다 -> 그래서 한 번 실행 할 때 걸리는 시간(overhead)을 줄여야 한다.
프로세스의 상태 (ready -> running -> waiting(block) -> ready)

Medium-term scheduler (Swapper)

메모리가 부족하여 프로세스(프로세스 이미지)를 통째로 들어서 하드 디스크로 보내버린다 (Swap)
프로세스에게서 memory를 deallocate
근데 어떤 프로세스를 들어서 옮길까? -> 가장 좋은 후보는 suspend 된 것. 사용자가 멈추라고 했으니까 CPU를 줄 필요가 없다. -> 하지만 suspend 된 놈이 없다면? -> 그걸 고르는게 medium term scheduling이라고 한다.
프로세스의 상태 (ready -> suspended)