CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에 해야 하는 일을 스레드 단위로 CPU에 할당한다.
프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정하며 CPU 스케줄링 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready queue)에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.
CPU 스케줄링 알고리즘은 크게 비선점형(non-preemptive) 방식와 선점형(preemptive) 방식으로 이루어져 있다.
1. 비선점형 방식(non-preemptive)
비선점형 방식(non-preemptive)는 프로세스가 스스로 CPU 소유권을 포기하는 방식이며 강제로 프로세스를 중지하지 않기 떄문에 컨텍스트 스위칭(Context Switching)으로 인한 부하가 적다.
1-1. 비선점형 방식의 종류
FCFS(First Come, First Served)
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상(convoy effect)가 발생하는 단점이 있다.
SJF(Shortest Job First)
실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧다. 하지만 실제로는 실해 시간을 알 수 없기 때문에 과거의실행했던 시간을 토대로 추측해서 사용한다.
우선순위
기존 SJF를 보완한 알고리즘으로써 오래된 작업일수록 우선순위를 높이는 방법을 사용해 보완한 알고리즘
2. 선점형 방식(preemptive)
선점형 방식(preemptive)는 현대 운영체제가 쓰는 방식으로서 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.
2-1. 선점형 방식의 종류
라운드 로빈(RR, Round Robin)
현대 컴퓨터가 쓰는 선점형 알고리즘 스케줄링 방법으로서 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(Ready Queue)의 뒤로 보내는 알고리즘을 의미한다.
주의해야할 점은 할당 시칸이 너무 크게 하면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드(=비용)이 커진다.
일반적으로는 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.
라운드 로빈 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로 사용된다.
SRF(Shortest Remaining Time First)
프로세스 중에서 남은 실행 시간이 가장 짧은 프로세스를 우선적으로 실행하는 방식으로서, 작업을 진행하는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘을 의미한다.
다단계 큐(Multilevel Queue)
CPU 스케줄링 알고리즘 중 하나로 프로세스를 우선순위에 따라 여러 개의 큐로 분리하여 각각의 큐에 다른 스케줄링 방식을 적용하는 방식이다.
각 큐는 서로 다른 프로세스 그룹을 처리하며, 각 큐의 프로세스는 독립적으로 스케줄링되고 프로세스 그룹에 따라 우선순위와 처리 방법을 다르게 적용하기 때문에, 우선순위가 높은 작업을 먼저 처리할 수 있다.
