[OS]CPU 스케줄링 알고리즘

* CPU 스케줄러 : CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당

프로그램이 실행될 때, CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정

목표 : CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정

 

 

1. 선점형 방식(preemptive) :  지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식, 현재 운영체제가 쓰는 방식

1) 라운드 로빈(RR, Round Robin) : 우선순위 스케줄링의 일종, 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시준비 큐의 뒤로 가는 알고리즘

2) SRF : 중간에 실행 시간이 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘

cf. SJF (Shortest Remaining Time First) : 중간에 실행 시간이 더 짧은 작업이 들어와도, 기존 짧은 작업을 모두 수행하고 그다음 짧은 작업을 이어나감

3) 다단계 큐 : 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘(라운드 로빈이나 FCFS등)을 적용한 것 

 

2. 비선점형 방식(non-preemptive) : 프로세스가 스스로 CPU 소유권을 포기하는 방식, 강제로 프로세스를 중지하지 않음

-> 컨텍스트 스위칭으로 인한 부하가 적음

1) FCFS (First Come, First Served) : 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

2) SJF (Shortest Job First) : 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

3) 우선순위 : SJF의 단점을 보완한 알고리즘

 

* SRF vs. SJF