3.4 CPU 스케줄링 알고리즘

스터디를 함께 진행했음

CPU 스케줄링 알고리즘 : CPU 스케줄러가 준비 큐에 있는 프로세스나 스레드 중 어떤 작업에 CPU를 할당할지 결정하는 알고리즘

CPU 스케줄링 알고리즘은 CPU 이용률, 처리량, 대기 시간, 응답 시간, 반환 시간을 기준으로 평가할 수 있다.

1. 비선점형(non-preemptive) : 한 번 CPU를 할당받은 프로세스가 종료되거나 I/O 요청 등으로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗지 못하는 방식. 컨텍스트 스위칭으로 인한 부하가 적다.
   1. FCFS(First Come First Served) : 먼저 온 것을 먼저 처리하는 방식. 긴 작업이 먼저 도착하면 짧은 작업들이 뒤에서 오래 기다리는 convoy effect가 발생할 수 있다.
   2. SJF(Shortest Job First) : 실행 시간이 가장 짧은 것을 먼저 처리하는 방식. 실행 시간이 긴 작업이 계속 밀리는 starvation이 발생할 수 있다.
   3. 우선순위 스케줄링 : 우선순위가 높은 작업을 먼저 처리하는 방식. 우선순위가 낮은 작업이 계속 밀리는 starvation이 발생할 수 있고, 이를 방지하기 위해 오래 기다린 작업의 우선순위를 aging으로 높일 수 있다.
2. 선점형(preemptive) : 운영체제가 현재 실행 중인 프로세스의 CPU 사용권을 강제로 회수하고 다른 프로세스에 CPU를 할당할 수 있는 방식. 현대 운영체제에서 주로 사용한다.
   1. 라운드 로빈(RR, Round Robin) : 각 작업에 동일한 시간 할당량(time quantum)을 주고, 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 보내는 방식. 시간 할당량이 너무 작으면 컨텍스트 스위칭 비용이 커지고, 너무 크면 FCFS와 비슷해진다.
   2. SRTF(Shortest Remaining Time First, SRT) : 남은 실행 시간이 가장 짧은 작업을 먼저 수행하는 방식. 실행 중인 작업보다 남은 시간이 더 짧은 작업이 들어오면 기존 작업을 중단하고 새 작업을 수행한다.
   3. 다단계 큐 : 우선순위에 따른 큐를 여러 개 두고, 큐마다 라운드 로빈이나 FCFS 같은 서로 다른 스케줄링 알고리즘을 적용하는 방식. 큐 사이의 작업 이동이 안 되기 때문에 유연성이 떨어진다는 특징이 있다.