CPU 스케줄링은 준비완료 큐에 있는 어는 프로세스에 CPU를 할당할 것인지를 결정하는 문제를 다룬다. 그리고 이러한 문제를 다루는 여러가지 CPU스케줄링 알고리즘들이 있다.

▦ FCFS 스케줄링(First Come, First Served Scheduling)

가장 간단한 CPU 스케줄링 알고리즘이다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. FIFO 큐로 쉽게 구현하고 관리할 수 있다. 그러나 이 알고리즘 하에서 프로스세스들의 평균 대기 시간은 가끔 대단히 길 수 있다. 시간 0에 도착한 다음의 프로세스 집합을 생각해보자.(CPU 버스트 시간 단위는 밀리초이다)

프로세스(버스트시간)

P1(24)

P2(3)

p3(3)

프로세스들이 P1, P2, P3 순으로 도착하고 FIFO 서비스를 받는다면, P1의 대기시간(0), P2의 대기시간(24), P3의 대기시간(27)의 평균 대기시간은 (0 + 24 + 27)/3 = 17 밀리초이다. 그러나 프로세스들이 P2, P3, P1 순으로 도착하면 평균 대기시간은 (0 + 3 + 6)/3 = 3 밀리초이다.

일반적으로 FCFS 스케줄링 정책 하에서 평균 대기시간은 최소가 아니며, CPU 버스트 시간이 크게 변할 경우 평균 대기시간도 상당히 변한다.

▦ SJF 스케줄링(Shortest Job First Scheduling)

이 알고리즘은 각 프로세스에 그것의 다음 CPU 버스트 길이를 연관시킨다. CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에게 CPU를 할당한다. 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면, 순위를 정하기 위해 FCFS 스케줄링을 적용한다. 이 스케줄링은 프로세스 전체길이(CPU 버스트 시간, I/O 처리 시간 등)가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링이 되는 것을 유의하기 바란다.

프로세스(버스트시간)

P1(6)

P2(8)

P3(7)

P4(3)

SJF 스케줄링을 이용하면 위의 프로세스들은 P4 → P1 → P3 → P2의 순서로 스케줄링 될것이다. P4의 대기시간(0), P1의 대기시간(3), P3의 대기시간(9), P2의 대기시간(16)의 평균 대기시간은 (0 + 3 + 9 + 16)/4 = 7 밀리초이다. 만일 FCFS 스케줄링을 사용했다면 평균 대기시간은 10.25 밀리초가 되었을 것이다.

SJF 스케줄링 알고리즘은 주어진 프로세스들의 집합에 대해 최소의 평균 대기시간을 가진다는 점에서 최적임이 증명 가능하다. 그러나 SJF 알고리즘의 실제 어려움은 다음 CPU 요청의 길이를 파악하는 것이다. SJF 알고리즘이 최적이긴 하지만 단기 CPU 스케줄링 수준에서는 구현될 수 없으며, 한가지 접근 방식은 다음 CPU 버스트의 길이를 특정한 방법으로 추정하여, SJF 스케줄링과 근사한 방법을 사용하는 것이다.

비선점 SJF 스케줄링 알고리즘은 현재 CPU가 할당된 프로세스의 잔여 버스트 시간보다 더 짧은 CPU 버스트 시간을 갖는 새로운 프로세스가 준비완료 큐에 도착하여도 현재 CPU가 할당된 프로세스를 완료한 후에 새로 들어온 프로세스가 선택되어지지만, 선점형 SJF 스케줄링 알고리즘은 현재 CPU가 할당된 프로세스를 준비완료 큐로 보내고 새로 들어온 더 짧은 길이의 버스트 시간을 갖는 프로세스를 CPU에 할당할 것이다. 예를 들어 다음의 네 프로세스들을 생각해보자.

프로세스(도착시간, 버스트 시간)

P1(0, 8)

P2(1, 4)

P3(2, 9)

P4(3, 5)

선점형 SJF 스케줄링 알고리즘 하에서 프로세스들의 실행 순서와 버스트 길이, 시작 시간은 다음과 같다.

P1(1, 0) → P2(4, 1) → P4(5, 5) → P1(7, 10) → P3(9, 17)

프로세스 P1은 준비완료 큐에 있는 유일한 프로세스이므로 시간 0에 시작된다. 프로세스 P2는 시간 1에 도착한다. 프로세스 P1의 잔여시간(7)이 프로세스 P2가 요구하는 시간(4)보다 크기 때문에 프로세스 P1은 선점되고 프로세스 P2가 스케줄 된다. 프로세스 P3는 시간 2에 도착하지만, 프로세스 P2의 잔여시간(3)보다 프로세스 P3가 요구하는 시간(9)보다 작기 때문에 선점은 일어나지 않으며 나머지 경우도 마찬가지이다.

P1의 대기시간(10 - 1), P2의 대기시간(1 - 1), P3의 대기시간(17 - 2), P4의 대기시간(5 -3)의 평균 대기시간은 26/4 = 6.5 밀리초로 비선점형 SJF 스케줄링의 평균 대기시간 7.75 밀리초보다 작다.

▦ 우선순위 스케줄링(Priority Scheduling)

SJF 알고리즘은 우선순위 스케줄링 알고리즘의 특별한 경우이다. 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다. 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄된다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다. 예를 들어 시간제한, 메모리 요구, 열린 파일 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율 등이 우선순의의 계산에 사용된다. 외부적 우선순위는 프로세스의 중요성, 지불되는 비용 등 운영체제 외부적 기준에 의해 결정된다.

우선순위 스케줄링 알고리즘의 주요 문제는 무한봉쇄(indefinite blocking) 또는 기아상태(starvaion)이다. 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 있는데, 이때 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다. 낮은 우선순위의 프로세스들을 무한히 봉쇄하는 문제에 대한 한 해결 방안은 노화(aging)으로, 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법이다.

▦ 라운드 로빈 스케줄링(Round Robin Scheduling)

라운드 로빈 스케줄링 알고리즘은 시분할 시스템을 위해 설계되었다. FCFS 스케줄링과 유사하지만 프로세스들 사이를 옮겨 다니기 위해서 선점이 추가되며, 시간 할당량(time quantum)이라고 하는 작은 단위의 시간을 정의하는데 일반적으로 10에서 100 밀리초 사이다. 준비완료 큐는 환형 큐(circular queue)로 설계되며, CPU 스케줄러는 준비완료 큐를 돌아가면서 시간 할당량 동안 프로세스들에게 CPU를 할당하고 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후 프로세스를 디스패치(dispatch)한다.

프로세스를 스케줄할 때 두 가지 경우 중 하나가 발생한다. 첫번째, CPU 버스트가 시간 할당량보다 작을 경우 프로세스 자신이 CPU를 자발적으로 방출하며, 스케줄러는 준비완료 큐에 있는 다음 프로세스로 진행한다. 두번째, CPU 버스트가 시간 할당량보다 긴 경우 타이머가 끝이 나고 운영체제는 인터럽트를 유발한다. 문맥교환이 일어나고 실행하던 프로세스는 준비완료 큐의 꼬리에 넣어진다. 그 후 CPU 스케줄러는 준비완료 큐의 다음 프로세스를 선택한다.

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면 RR 정책은 FIFO와 같다. 시간 할당량이 매우 적다면 RR방식은 프로세서 공유(processor sharing)라 불리며, 이론적으로는 n개의 프로세들이  실제 프로세서의 1/n 속도로 실행되는 자신의 프로세서를 가지고 있는 것처럼 보인다. 그러나 소프트웨어에서는 RR 스케줄링의 성능에 문맥교환의 영향을 고려해야 할 필요가 있다. 너무 작은 시간할당량은 문맥교환 빈도를 높여 프로세스 집합의 평균 총처리시간을 증가시킬 것이기 때문이다.

▦ 다단계 큐 스케줄링(Multilevel Queue Scheduling)

포어그라운드(foreground) 대화형 프로세스들과 백그라운드(background) 일괄처리 프로세스들은 일반적으로 구분을 한다. 이들 두 타입의 프로세스는 응답시간에 대한 요구사항이 다르기 때문에 스케줄링 또한 다를 것이기 때문이다. 이처럼 단단계 큐 스케줄링은 프로세스의 특성에 기반하여 준비완료 큐를 다수의 별도 큐로 나누어 관리하며, 각 큐는 자신의 스케줄링 알고리즘을 갖고 있다. 예를들어 포어그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있고, 백그라운드 큐는 FCFS 알고리즘에 의해 스케줄 될 수 있는 것이다. 추가로 큐 사이에 스케줄링이 반드시 있어야 하며, 일반적으로 고정된 우선순위의 선점형 스케줄링으로 구현된다. 예를 들어 포그라운드 큐는 백그라운드 큐보다 절대적인 우선순위를 갖을 수 있음을 말한다.

▦ 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 영구적으로 하나의 큐에 할당되며, 프로세스들은 큐 사이를 이동하지 않는다. 이러한 방식은 스케줄링 부담이 적은 장점이 있으나 융통성이 적다. 다단계 피드백 큐 스케줄링 알고리즘은 프로세스가 큐들 사이로 이동할 수 있으며, 프로세스들을 상이한 CPU 버스트 성격에 따라서 구분한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위의 큐로 이동되는 식이다. I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣고, 긴 프로세스는 낮은 우선순위 큐에 넣어지게 된다. 노화(aging)을 통해 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다.

▦ 실시간 스케줄링(Real Time Scheduling)

실시간 컴퓨팅은 두 가지 타입으로 나누어진다. 경성(hard) 실시간 시스템은 중요한 작업을 보장된 시간 내에 완료할 것을 요구한다. 일반적으로 프로세스는 작업완료나 I/O 수행에 필요한 시간의 양을 제출하고, 스케줄러는 프로세스가 정해진 시간에 완료되는 것이 보장될 경우 그 프로세스를 받아들이며, 불가능할 경우 요청을 거절한다. 이러한 보장은 스케줄러가 각 타입의 운영체제 기능을 수행하는 데 얼마만큼의 시간이 쇼요될 지를 정확하게 파악할 것을 요구하며, 각 연산의 최대 소요시간을 보장해야 한다.

연성(soft) 실시간 컴퓨팅은 경성 실시간 컴퓨팅에 비해 덜 제한적이며, 중요한 프로세스들이 다소 덜 중요한 프로세스에 비해서 높은 우선순위를 가질 것을 요구한다.

연성 실시간 시스템의 요구사항은 다음과 같다.

1. 우선순위 스케줄링을 제공해야 하며, 실시간 프로세스들이 가장 높은 우선순위를 가져야 하고, 실시간 프로세들의 우선순위는 시간이 지남에 따라 낮아져서는 안된다. 이런 성질을 가지도록 보장하기 위해 실시간 프로세스는 프로세스 노화를 허용하지 않는다.

2. 디스패치 지연을 최소화해야 된다. 디스패치 지연을 줄이기 위해서는 시스템 호출이 선점되는 것을 허용할 필요가 있으며, 이러한 목적을 달성하기 위해 시스템 호출에 선점 지점(preemption point)을 삽입하고 그 호출이 높은 우선순위의 프로세스가 실행할 필요가 있는지 검사하도록 한다. 선점지점은 커널 자료가 변경될 수 없는 곳에만 놓여질 수 있다. 또 다른 방법은 커널 전체를 선점 가능하도록 하는 것이다. 올바른 동작을 보장받기 위해서는 모든 커널 자료구조는 여러가지 동기화 기법을 사용하여 반드시 보호되어야 한다. 이 방법으로 갱신되고 있는 커널자료가 높은 우선순위의 프로세스에 의해 변경되는 것을 방지할 수 있기 때문에 커널은 항상 선점할 수 있다. 높은 우선순위의 프로세스가 현재 낮은 우선순위의 프로세스에 의해 접근되고 있는 커널 자료를 변경할 필요가 있을 경우 높은 우선순위 프로세스는 낮은 우선순위의 프로세스가 끝나기를 기다려야 하며, 낮은 우선순위 프로세스가 그 자원을 사용 완료할 때까지 높은 우선순위를 상속하였다가 종료될 때 원래의 값으로 복귀시키는 방법이 있다.