CPU 스케줄러는 CPU 스케줄링 알고리즘을 바탕으로 프로세스에서 해야 하는 작업들을 스레드 단위로 CPU에 할당한다.
즉, CPU 스케줄링 알고리즘에 따라 어떤 프로그램에 'CPU 소유권'을 부여할 것인지 결정한다.
이 알고리즘은 CPU 이용율을 높게, 주어진 시간에 최대한 많은 일을 하도록, 준비 큐에 있는 프로세스는 최대한 적게, 응답 시간은 짧게 설정하는 것을 목표로 하고 있다.
1. 비선점형 방식
프로세스가 스스로 CPU 소유권을 포기하는 방식으로, 강제로 프로세스를 중지하지 않는다.
- FCFS 알고리즘 : 가장 먼저 온 것은 먼저 처리하는 알고리즘이다. 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리게 되는 단점이 있다.
- SJF 알고리즘 : 실행 시간이 가장 짧은 프로세스부터 실행하는 알고리즘이다. 하지만 실행시간이 긴 프로세스가 오랫동안 실행되지 않는 Starvation 현상이 발생한다는 단점이 존재한다.
- 우선순위 알고리즘 : SJF의 Starvation 현상을 방지하기 위해 오래된 프로세스일수록 우선순위를 부여하는 알고리즘이다.
2. 선점형 방식
현대 운영체제가 사용하고 있는 방식으로, 지금 실행중인 프로세스를 강제로 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식이다.
- 라운드 로빈(RR) 알고리즘 : 모든 프로세스에 동일하게 할당 시간을 부여하고 그 시간안에 끝나지 않으면 다시 준비 큐에 넣는 알고리즘이다.
- SRF 알고리즘 : 중간에 실행 시간이 더 짧은 프로세스가 들어와도 기존 프로세스을 모두 마치고 다음 프로세스를 실행하는 SJF 알고리즘과 달리, 중간에 실행 시간이 더 짧은 프로세스가 들어오면 기존 프로세스를 중단시키고 해당 프로세스를 실행하는 알고리즘이다.
- 다단계 큐 알고리즘 : 우선순위에 따른 준비 큐를 여러 개 사용하고, 각 큐마다 서로 다른 스케줄링 알고리즘을 적용한 알고리즘이다.