스케줄링 알고리즘

FCFS(First-Come-First-Served)

이름 그대로 CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받습니다. 요청한 순서대로 처리됩니다. 만약 버스트 시간이 긴 프로세스가 요청을 앞서 했다면 평균 대기 시간이 길어집니다. 프로세스들이 처리 시간이 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 합니다. 비선점형입니다.

 

SJF(Shortest-Job-First)

최단 작업 우선 알고리즘입니다. CPU는 가장 작은 버스트를 가진 다음 프로세스에 할당됩니다. 프로세스 전체의 길이가 아니라 CPU의 버스트의 길이에 의해 스케줄링이 되기 때문에 Shortest-next-CPU-burst 알고리즘이라는 용어가 더 적합합니다. SJF 스케줄링 알고리즘은 프로세스들에 대해 최소 평균 대기 시간을 가진다는 점에서는 최적이지만, CPU의 버스트 길이를 알 수 없어 단기 CPU 스케줄링 수준에서는 구현할 수 없습니다.

 

SJF는 선점형이거나 비선점형입니다. 프로세스가 실행되는 동안 새로운 프로세스가 준비 완료 큐에 도착하는 상황을 가정해봅시다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다 더 짧은 CPU 버스트를 가질 때 선점형 SJF는 프로세스를 선점하고, 비선점형 SJF는 대기합니다. 선점형 SJF 알고리즘을 SRF(Shortest Remaining Time First) 스케줄링이라고도 합니다.

 

Priority Scheduling

SJF 알고리즘은 우선순위 알고리즘의 한 종류입니다. CPU는 우선순위가 가장 높은 프로세스에게 할당됩니다. 우선순위가 같은 프로세스는 FCFS 순서로 스케줄됩니다. 우선순위 스케줄링은 선점형일 수도 있고 비선점형일 수도 있습니다. 우선순위 스케줄링의 문제는 영원히 CPU를 할당받지 못하는 프로세스가 생길 수 있다는 점입니다. 우선순위가 낮은 프로세스가 대기 중인 상황에서 우선순위가 높은 프로세스들이 꾸준히 들어올 수 있기 때문입니다. 이에 대한 해결은 aging입니다. 일정 시간이 지날 때마다 우선순위를 높이는 방법입니다.

 

Round-Robin Scheduling

라운드 로빈 스케줄링은 시분할 시스템에 맞게 디자인됐습니다. FCFS와 비슷하지만 time quantum 혹은 time slice마다 프로세스를 선점합니다. FCFS의 선점형 버전(preemptive version)입니다. FCFS는 시스템의 효율을 떨어뜨릴 확률이 높기 때문에 시간 할당량을 정해 CPU를 프로세스에 골고루 분배하는 방식입니다. 윈도우와 리눅스는 priority + RR 방식입니다. 할당되는 시간이 클 경우 FCFS와 비슷해지고 시간이 작으면 컨텍스트 스위칭으로 인한 오버헤드가 커지기 때문에 적당한 시간 할당량을 정하는 것이 중요합니다. CPU의 버스트의 80 퍼센트는 시간 할당량보다 짧은 게 좋습니다.