CPU 스케줄러
스케줄링 대상은 Ready Queue에 있는 프로세스들이다.
FCFS(First Come First Served)
특징
- 먼저 온 순서대로 처리
- 비선점형(Non-Preemptive) 스케줄링: 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
문제점
- convoy effect: CPU burst가 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
SJF(Shortest Job First)
특징
- CPU burst time이 짧은 프로세스에게 선 할당
- 비선점형(Non-Preemptive) 스케줄링
문제점
- starvation: SJF는 CPU burst time가 짧은, 즉 priority가 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 따라서 priority가 높은 프로세스가 계속 들어온다면, priority가 낮은 프로세스는 CPU를 할당받을 수 없게 된다.
SRTF(Shortest Remaining Time First)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
- 선점형(Preemptive) 스케줄링: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
문제점
- starvation
- CPU burst time이 예측되어야 한다
부적절한 예측은 최적의 average waiting time으로 이어질 수 없다.
Priority Scheduling
특징
- 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
- 선점형 스케줄링(Preemptive) 방식: 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.
- 비선점형 스케줄링(Non-Preemptive) 방식: 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.
문제점
- starvation
- 무기한 봉쇄(Indefinite blocking): 실행 준비는 되어있으나 CPU를 사용못하는 프로세스를 CPU가 무기한 대기하는 상태
해결책
- aging: 시간이 지남에 따라 프로세스의 priority를 높여준다.
Round Robin
특징
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다.
- 할당 시간이 지나면 프로세스는 선점(preemption)당하고 ready queue에 들어간다.
- RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
- RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.
장점
- Response time이 빨라진다.
n개의 프로세스가 ready queue에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. - 프로세스가 기다리는 시간이 CPU 를 사용할 만큼에 비례한다.
공정한 스케줄링이라고 할 수 있다.
주의할 점
설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적(time sharing)에는 이상적이지만 잦은 context switch로 overhead가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.
Reference
https://github.com/JaeYeopHan/Interview_Question_for_Beginner
JaeYeopHan님의 자료를 참조했습니다.
