공룡책 5장 CPU 스케줄링

이 글은 공룡책으로 유명한 운영체제 9판을 가지고 작성한 글입니다.

다르거나 이상한 점이 있다면 댓글로 알려주시면 감사하겠습니다.

---

CPU 스케줄링은 다중 프로그램 운영체제의 기본입니다. 운영체제는 CPU를 프로세스들 간에 교환함으러써, 컴퓨터를 보다 생산적으로 만듭니다.

앞서 스레드를 소개했는데, 스레드를 지원하는 운영체제에서는 실질적으로 운영체제는 프로세스가 아니라 커널 수준 스레드를 스케줄 합니다. 그러나 "프로세스 스케줄링"과 "스레드 스케줄링" 용어는 상호 교환적으로 사용됩니다. 이 번엔 일반적인 스케줄링 개념을 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우엔 스레드 스케줄링이라 명명하겠습니다.

---

기본 개념

단일 처리기 시스템에서 한 순간에 오직 하나의 프로세스만이 실행될 수 있습니다. 나머지 프로세스는 CPU가 자유 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 합니다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있습니다. 다중 프로그래밍에 대한 기본 아이디어는 기본적으로 간단합니다. 하나의 프로세스는 전형적으로 어떤 입출력 요청이 완료되기를 기다려야만 할 때까지 실행됩니다. 이렇게 되면 단순한 컴퓨터 시스템에선 CPU는 그저 놀고 있게 됩니다. 이러한 모든 대기 시간은 낭비되며, 어떤 유용한 작업도 수행하지 못합니다.

다중 프로그래밍에서는, 이러한 시간을 생산적으로 활용하려고 시도합니다. 어느 한 순간에 다수의 프로세스들을 메모리 내에 유지하고, 어떤 프로세스가 대기해야 할 경우엔 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당합니다. 이러한 패턴은 계속되며, 하나의 프로세스가 대기해야 할 때마다, 다른 프로세스가 CPU 사용을 양도 받습니다.

이러한 종류의 스케줄링은 운영체제의 기본적인 기능입니다. 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄이 됩니다. 물론 CPU는 중요한 컴퓨터 자원 중의 하나이기에 CPU의 스케줄링은 운영체제 설계의 핵심이 됩니다.

CPU-입출력 버스트 사이클

프로세스 실행은 CPU 실행과 입출력 대기의 사이클로 구성됩니다. 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 합니다. 프로세스 실행은 CPU 버스트(burst)로 시작됩니다. 뒤이어 입출력 버스트가 발생하고, 그 뒤를 이어 또 다른 CPU 버스트가 발생하며, 이어 또 다른 입출력 버스트로 진행됩니다. 이렇게 계속 사이클이 만들어지면서 실행을 종료하기 위한 시스템 요청과 함께 끝이 납니다.

입출력 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가질 것입니다. CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가질 수 있습니다. 이러한 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는 데 매우 중요할 것입니다.

CPU 스케줄러

CPU가 휴식 상태가 될 때마다, 운영체제는 Ready Queue에 있는 프로세스들 중 하나를 선택해 실행해야 합니다. 선택 절차는 단기 스케줄러(또는, CPU 스케줄러)에 의해 수행됩니다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여 이들 중 하나에게 CPU를 할당합니다.

Ready Queue는 반드시 선입 선출(FIFO) 방식이 아니어도 됩니다. 여러 가지 스케줄링 알고리즘들을 고려할 때 알게 되지만, Ready Queue는 선입 선출 큐, 우선순위 큐, 트리 또는 단순히 순서가 없는 연결 리스트로도 구현할 수 있습니다. 그러나 개념적으로 볼 때 Ready Queue에 있는 모든 프로세스들은 CPU에서 실행될 기회를 기다리며 대기하고 있습니다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)들입니다.

선점 스케줄링(Preemptive Scheduling)

CPU 스케줄링 결정은 다음의 네 가지 상황 하에서 발생할 수 있습니다.

• 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (예를 들어 입출력 요청이 들어왔을 때)
• 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (예를 들어 인터럽트가 발생할 때)
• 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (예를 들어 입출력 종료 시)
• 프로세스가 종료할 때

상황 1과 4의 경우, 스케줄링 면에서는 선택의 여지가 없습니다. 실행을 위해서 새로운 프로세스가 반드시 선택되어야 합니다. (준비 완료 큐에 하나라도 존재할 경우) 그러나 상황 2와 3을 위해서는 선택의 여지가 있습니다.

상황 1과 4에서만 스케줄링이 발생할 경우, 이러한 스케줄링 방법을 비선점(non-preemptive), 협조적(cooperative)라고 합니다. 그렇지 않으면, 선점(preemptive)합니다. 비선점 스케줄링에서는 CPU가 한 프로세스에 할당되면, 프로세스가 종료하든지 또는 대기 상태로 전환해 CPU를 반납할 때 까지 CPU를 점유합니다.

선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있습니다. 두 프로세스가 자료를 공유하는 경우를 고려해봅시다. 한 프로세스가 자료를 갱신하고 있다가 선점되어 두 번째 프로세스가 실행 가능한 상태가 될 수 있습니다. 이때 두 번째 프로세스가 데이터를 읽으려고 할 때, 데이터의 일관성은 이미 깨진 상태입니다. 이러한 문제는 동기화 문제로 또 포스팅을 하도록 하겠습니다.

선점은 또한 운영체제 커널 설계에 영향을 줍니다. 시스템 호출을 처리할 동안, 커널은 한 프로세스를 위한 활동으로 바쁠 수 있습니다. 그러한 활동은 중요한 커널 자료(입출력 큐와 같은) 변경을 포함할 수 있습니다. 만일 이러한 변경 도중에 해당 프로세스가 선점되고, 커널이 동일한 구조를 읽거나 또는 변경할 필요가 있을 경우 어떤 일이 발생할까요? 아마 혼란이 계속해서 일어날 것입니다. 대부분의 경우엔 문맥 교환(Context Switching)이 수행하기 전에 시스템 호출이 완료되거나 입출력 요구에 따른 Block이 일어나기를 기다리는 방법을 사용합니다.

정의에 의하면 인터럽트는 어느 시점에서건 일어날 수 있고, 커널에 의해서 항상 무시될 수는 없기 때문에, 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 합니다. 운영체제는 거의 항상 인터럽트를 받아들일 필요가 있는데, 그렇지 않으면 입력을 잃어버리거나 또는 출력이 겹쳐서 쓰여질 수 있습니다. 따라서 이러한 코드 부분은 다수 프로세스가 병행으로 접근할 수 없도록 그 진입점에서 인터럽트를 불능화하고, 출구에서 인터럽트를 다시 가능하해야합니다. 인터럽트 불능화는 자주 발생해서는 안 되고, 아주 적은 수의 명령어들만 포함하여야 합니다.

디스패처

CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처(dispatcher)입니다. 디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈입니다. 디스패처는 다음과 같은 작업을 합니다.

• 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

딧패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 최고로 빨리 수행되어야 합니다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)라고 합니다.

---

스케줄링 기준

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가지고 있으며 한 부류의 프로세스들을 다른 부류보다 더 선호할 수 있습니다. 특정 상황에서 어떠한 알고리즘을 선택하려면 다양한 알고리즘들의 서로 다른 특성을 반드시 고려해야 합니다.

CPU 스케줄링 알고리즘을 비교하기 위해 여러 기준이 제시되었습니다.

• CPU 이용률(utilization) : 저희는 가능한 CPU를 최대한 빠르게 유지하기를 원합니다. CPU가 실제로 몇 퍼센트 이용되고 있는지를 판단하고, 이 이용률을 최대화 해야합니다.
• 처리량(throughput) : CPU가 프로세스를 수행하느라 바쁘다면, 작업이 진행되고 있는 것입니다. 작업량 측정의 한 방법은 단위 시간당 온료된 프로세스의 개수로, 이를 처리량(throughput)이라 합니다. 긴 프로세스인 경우엔 이 비율은 시간당 한 프로세스가 될 수 있고, 짧은 트랜잭션인 경우 처리량은 초당 10개의 프로세스가 될 수 있습니다.
• 총 처리 시간(turnaround time) : 프로세스를 실행하는 데 소요된 시간입니다. 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 합니다. 총처리 시간은 메모리에 들어가기 위해 기다리며 소비한 시간, Ready Queue에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한 시간입니다.
• 대기 시간(waiting time) : CPU 스케줄링 알고리즘은 프로세스가 실행하거나 입출력을 하는 시간의 양에 영향을 미치지 않습니다. 스케줄링 알고리즘은 단지 프로세스가 Ready Queue에서 대기하는 시간의 양에만 영향을 줍니다. 대기 시간은 Ready Queue에서 대기하며 보낸 시간의 합입니다.
• 응답 시간(response time) : 대화식 시스템에서, 총처리 시간은 최선의 기준이 아닐 수도 있습니다. 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간입니다. 응답 시간이라고 하는 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는 데 걸리는 시간이 아닙니다.

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직합니다. 대부분의 경우, 평균 측정 시간을 최적화하려고 합니다. 그러나 어떤 경우엔 평균보다는 최소값 또는 최대값을 최적화하는 것이 바람직할 수 있습니다. 예를 들어 모든 사용자들이 좋은 서비스를 얻도록 보장하기 위해, 우리는 최대 응답 시간을 최소화하려고 할 수 있습니다.

대화식 시스템의 경우 평균 응답 시간을 최소화하기보다는 응답 시간의 변동폭을 최소화하는 것이 중요합니다.

이어서 CPU 스케줄링 알고리즘에선 수백 개의 CPU 버스트와 입출력 버스트들의 열을 갖는 많은 수의 프로세스를 고려해야하지만, 설명을 위해 프로세스당 단지 하나의 CPU 버스트를 고려하겠습니다.

---

스케줄링 알고리즘

CPU 스케줄리은 Ready Queue에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룹니다. 여러가지 다른 CPU 스케줄링 알고리즘이 존재합니다. 그러한 스케줄링 알고리즘에 대해서 자세히 알아봅시다.

선입 선출 스케줄링(First Come, First-Served Scheduling, FIFO)

가장 간단한 CPU 스케줄링 알고리즘은 선입 선처리 스케줄링 알고리즘입니다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받습니다. 선입 선처리 정책의 구현은 선입선출 큐로 쉽게 관리할 수 있습니다. 프로세스가 Process Queue에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결합니다. CPU가 자유 상태가 되면, Ready Queue의 앞부분에 있는 프로세스에게 할당됩니다. 이 실행 상태의 프로세스는 이어 Ready Queue에서 제거됩니다. 선입 선처리를 위한 코드는 작성하기 쉽고 이해하기가 쉽습니다.

부정적인 측면은 선입 선처리 정책 하에서 평균 대기 시간이 대단히 길어질 수 있습니다. 시간 0에 도착한 다음의 프로세스 집합을 생각해봅시다. 여기서 CPU 버스트 시간의 길이는 밀리초입니다.

프로세스	버스트 시간
P1	24
P2	3
P3	3

프로세스들이 P1, P2, P3 순으로 도착하고, 선입 선처리 순으로 서비스 받는다면, 다음의 평균 대기 시간은 (0 + 24 + 27)/3 = 17밀리초입니다. 그러나 프로세스들이 P2, P3, P1 순으로 도착하면, 평균 대기 시간은 (6 + 0 + 3)/3 = 3밀리초입니다. 이러한 감소는 상당히 큽니다.

그러므로 선입 선처리 정책 하에서 평균 대기 시간은 일반적으로 최소가 아니며, 프로세스 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있습니다.

혹여나 CPU 중심 프로세스와 입출력 중심 프로세스가 같이 운용이 된다면, 입출력 중심 프로세스는 항상 CPU 중심 프로세스가 일을 마칠 때까지 비효율적인 대기가 계속 될 수 있습니다. 이렇듯 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 합니다.

선입 선처리 스케줄링 알고리즘은 비선점형입니다. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하든지 또는 입출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유합니다. 선입 선처리 시엔 멀티 태스킹(시분할) 시스템에서 문제가 됩니다. 그 이유는 멀티태스킹 시스템에서는 각 사용자가 규칙적인 간격으로 CPU의 몫을 얻는 것이 매우 중요합니다. 한 프로세스가 지나치게 오랫 동안 CPU를 점유한다면 손해가 크게 발생합니다.

최단 작업 우선 스케줄링(Shortest-Job-First Schduling, SJF)

CPU 스케줄링의 다른 접근 방법은 최단 작업 우선 알고리즘입니다. 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관합니다. CPU가 이용 가능해지면 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당합니다. 두 프로세스가 동일한 길이의 CPU 버스트를 가지면 선입 선처리 스케줄리을 적용하면 됩니다. 이 스케줄리은 프로세스의 전체 길이가 아니라 다음 CPU 버스트 길이에 의해 스케줄링 되기 때문에, 최단 다음 CPU 버스트 알고리즘 용어가 더 적합합니다. 대부분의 사람들과 교과서가 SJF라고 명명하기에 저희도 SJF를 사용하겠습니다.

하나의 예로 밀리초 단위의 CPU 버스트 길이를 가진 다음과 같은 프로세스들의 집합을 고려해봅시다.

프로세스	버스트 시간
P1	6
P2	8
P3	7
P4	3

SJF 스케줄링을 이용하여 이들의 평균 대기 시간을 정해보겠습니다.

프로세스 P4의 대기시간 0, P1의 대기시간 3, P3의 대기시간 9, P2의 대기시간 16 밀리초가 되니 평균 대기 시간은 (3 + 16 + 9 + 0)/4 = 7밀리초가 됩니다. 평균 대기 시간이었으면, 10.25밀리초가 됩니다.

SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가질 수 있기에 최적임이 증명 가능합니다.

하지만, 어려운 점은 다음 CPU 요청의 길이를 파악하는 것입니다. 왜냐면 다음 CPU 버스트의 길이를 알 수 있는 방법이 없습니다. 한 가지 접근 방식은 SJF 스케줄링과 근사한 방법을 사용하는 것입니다. 다음 CPU 버스트의 길이를 알 수 없으나, 그 값을 예측할 수는 있습니다. 우리는 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 예상합니다. 그러므로 다음 CPU 버스트 길이의 근사 값을 계산해, 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택하게 됩니다.

SJF 알고리즘은 선점형이거나 비선점형일 수 있습니다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 Ready Queue에 도착하면 선택이 발생합니다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수 있습니다. 선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용합니다. 선점형 SJF 알고리즘은 최소 잔여 시간 우선 스케줄링이라고 불립니다.

예를 들어 다음의 네 프로세스들을 생각해봅시다.

프로세스	도착시간	버스트 시간
P1	0	8
P2	1	4
P3	2	9
P4	3	5

프로세스들이 위에 보인 시간에 Ready Queue에 도착하고, 선점형 SJF 스케줄링을 실행하면 다음과 같이 진행이 됩니다.

우선 P1이 먼저 도착했기에 0에 시작합니다. P2는 시간1에 도착하고 P1은 CPU를 넘겨주게 됩니다.(남은 시간 7)

P2는 버스트 시간이 가장 짧기 때문이 나머지 P2, P3가 도착해도 계속 진행하고 끝냅니다

P2가 끝나면 Ready Queue에 있는 나머지 프로세스 중 가장 짧은 프로세스인 P4를 끝내고 그 다음으로 P1을 끝내고 P3를 끝내면서 모든 프로세스 처리가 완료됩니다. ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 6.5밀리초에 완료됩니다.

비선점형인 경우 7.75밀리초가 됩니다.

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

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우입니다. 왜냐면 CPU가 가장 우선순위를 가졌기 때문입니다.

우선순위는 내부적 또는 외부적으로 정의될 수 있습니다. 내부적으론 측정 가능한 양이 존재합니다. 시간 제한, 메모리 요구, 열린 파일의 수 등등입니다. 외부적 우선 순위는 비용, 정치적 요인 등이 존재합니다.

우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있습니다. 프로세스가 Ready Queue에 도착하면 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교합니다. 선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점합니다. 비선점형 우선순위 스케줄링 알고리즘은 단순히 Ready Queue의 머리 부분에 새로운 프로세스를 넣습니다.

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking), 기아 상태(starvation)입니다. 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주될 수 있습니다. 죽 우선 순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스들은 영원히 대기해야 할 수 있습니다. 한 가지 해결 방안으론 노화(Aging)이 있습니다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 것입니다.

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

라운드 로빈(RR) 스케줄링 알고리즘은 멀티 태스킹 시스템을 위해 설계되었습니다. 이는 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가됩니다. 시간 할당량(time quantum), 시간 조각(time slice)이라고 하는 작은 단위의 시간을 정의합니다. 시간 할당량은 일반적으로 10에서 100밀리초 동안입니다. Ready Queue는 원형 큐(circular queue)로 동작합니다. CPU 스케줄러는 Ready Queue를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당합니다.

라운드 로빈 스케줄링을 구현하기 위해, 우리는 다시 Ready Queue가 선입 선출 큐로 동작하게 만듭니다. 새로운 프로세스들은 Ready Queue의 꼬리에 추갇됩니다. CPU 스케줄러는 Ready Queue에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머(timer)를 설정한 후, 프로세스를 디스패치(dispatch)합니다.

두 가지 경우 중 하나가 발생한 것입니다. 첫 번째는 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 수 있습니다. 이 경우엔 프로세스 자신이 CPU를 자발적으로 돌려주며서 스케줄러는 그 후 Ready Queue에 있는 다음 프로세스로 진행할 것입니다. 두 번째는 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우로, 타이머가 끝나고 운영체제에게 인터럽트를 발생할 것입니다. 문맥 교환이 일어나고, 실행하던 프로세스는 Ready Queue의 꼬리에 넣어집니다. 그 후 CPU 스케줄러는 Ready Queue의 다음 프로세스를 선택할 것입니다.

종종 RR 정책 하에서 평균 대기 시간은 깁니다. 아래의 예를 보도록 하겠습니다.

프로세스	버스트 시간
P1	24
P2	3
P3	3

시간 할당량을 4밀리초로 한다면 P1은 처음의 4밀리초를 사용합니다. 이 프로세스는 20밀리초를 더 필요하기 때문에 Ready Queue 꼬리 부분으로 가고 P2가 CPU를 차지합니다. P2와 P3는 4밀리초가 필요하지 않기 때문에 둘 다 3밀리초에 완료되고 CPU는 20밀리초를 가진 P1에게 할당됩니다. 따라서 평균 대기 시간은 P1는 (10 - 4 = 6밀리초), P2는 4밀리초, P3는 7밀리초를 기다리게 되면서 평균 대기 시간은 17/3 = 5.66밀리초입니다.

라운드 로빈 스케줄링 알고리즘에서는, 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당받는 프로세스는 없습니다. 만일 CPU 버스트가 한 번의 시간 할당량을 초과하면, 프로세스는 선점되고 Ready Queue로 되돌아갑니다. 따라서 RR 스케줄링 알고리즘은 선점형입니다.

Ready Queue에 n개의 프로세스가 있고 시간 할당량이 q이면, 각 프로세스는 최대 q 시간 단위의 덩어리로 CPU 시간의 1/n을 얻습니다.

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받습니다. 시간 할당량이 크면 RR 정책은 선입 선처리 정책과 같습니다. 이와 반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥교환(Context Switching)을 야기합니다. 그만큼 프로세스의 실행이 느려집니다.

그러므로 저희는 시간 할당량이 문맥 교환 시간에 비해 더 클 것을 원합니다. 문맥 교환 시간이 시간 할당량의 10퍼센트에 근접한다면, 이상적인 시간입니다.

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

프로세스들이 쉽게 상이한 그룹으로 분류될 수 있는 상황을 위해 스케줄링 알고리즘의 또 다른 클래스가 고안되었습니다. 일반적으로 포그라운드(foreground, 대화형) 프로세스들과 백그라운드(background, 일괄처리) 프로세스들을 구분합니다. 이들 두 유형의 프로세스는 응답 시간에 대한 요구 사항이 다르기 때문에, 스케줄링 요구 또한 다를 것입니다. (I/O 프로세스, CPU 프로세스를 생각하시면 됩니다)

다단계 큐 스케줄링 알고리즘은 Ready Queue를 다수의 별도의 큐로 분류합니다. 일반적으로 프로세스들은 메모리 크기, 프로세스의 우선순위 혹은 프로세스 유형과 같은 프로세스의 특성에 따라 한 개의 큐에 영구적으로 할당됩니다. 각 큐는 자신의 스케줄링 알고리즘을 갖고 있습니다. 예를 들어 포그라운드와 백그라운드 프로세스들을 위해 별도의 큐를 사용할 수 있습니다.

포그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있고, 반면에 백그라운드 큐는 선입 선처리 알고리즘에 의해 스케줄 될 수 있습니다.

추가로, 큐와 큐 사이에도 스케줄링이 반드시 있어야 하며, 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현됩니다. 예를 들어 포그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위를 가질 수 있습니다.

이제 5개의 큐를 가진 다단계 큐 스케줄링 알고리즘의 예를 살펴봅시다. 각 큐는 다음과 같은 우선순위를 갖습니다.

1. 시스템 프로세스
2. 대화형 프로세스
3. 대화형 편집 프로세스
4. 일괄처리 프로세스
5. 학생 프로세스

각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가집니다. 예를 들어 시스템 프로세스, 대화형 프로세스, 그리고 대화형 편집 프로세스를 위한 큐들이 모두 비어 있지 않으면, 일괄처리 큐에 있는 프로세스는 실행될 수 없습니다. 일괄처리 프로세스가 실행되고 있는 중에 대화형 편집 프로세스가 Ready Queue에 들어가면, 일괄처리 프로세스는 선점될 것입니다.

다른 가능성은 큐들 사이에 시간을 나누어 사용하는 것입니다. 각 큐는 CPU 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있습니다. 예를들어 포그라운드 큐는 자신의 프로세스들 사이에서 RR 스케줄리을 위해 CPU 시간의 80%가 주어지고, 백그라운드 큐는 CPU 시간의 20%를 받아 자신의 프로세스들에게 선입 선처리 방식으로 줄 수 있습니다.

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

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당됩니다. 예를 들어서 포그라운드와 백그라운드 프로세스를 위해 별도의 큐가 있을 경우, 프로세스들은 한 큐에서 다른 큐로 이동하지 않습니다. 왜냫면 프로세스들이 포그라운드와 백그라운드의 특성을 바꾸지 않기 때문입니다. 이러한 방식은 스케줄링 오버헤드가 장점이 있으나 융통성이 적습니다.

대조적으로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용합니다. 프로세스들을 CPU 버스트 성격에 따라서 구분합니다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동됩니다. 이 방법에서는 입출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣습니다. 마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있습니다. 이러한 노화(aging) 형태는 기아 상태를 예방합니다.

예를 들어 번호가 0에서 2까지의 세 개의 큐를 가진 다단계 피드백 큐 스케줄러를 생각해 봅시다. 스케줄러는 처음에 큐 0의 모든 프로세스들을 실행시킵니다. 큐 0이 비어있을 때만 큐 1에 있는 프로세스들을 실행시킵니다. 마찬가지로 큐 0과 1이 비어있을 때만 큐 2에 있는 프로세스들이 실행됩니다. 큐 1에 도착한 프로세스는 큐 2에있는 프로세스를 선점합니다. 큐 1에 있는 프로세스는 큐 0에 도착한 프로세스에 의해 선점될 것입니다.

Ready Queue로 들어오는 프로세스는 큐 0에 넣어집니다. 큐 0에 있는 프로세스는 8밀리초의 시간 할당량이 주어집니다. 만약 프로세스가 이 시간 안에 끝나지 않는다면 큐 1의 꼬리로 이동됩니다. 큐 0이 비어 있다면, 큐 1의 머리에 있는 프로세스에게 16밀리초의 시간 할당량이 주어집니다. 이 프로세스가 완료되지 않는다면, 선점되어 큐 2에 넣어집니다. 큐 0과 큐 1이 비어 있을 때만 큐 2에 있는 프로세스들이 선입 선처리 방식으로 실행됩니다.

이 스케줄링 알고리즘은 CU 버스트가 8밀리초 이하인 모든 프로세스에게 최고의 우선순위를 부여합니다. 이러한 프로세스는 빨리 CPU를 할당받아서, CPU 버스트를 끝내고 다음의 입출력 버스트로 갑니다. 8밀리초 이상 24밀리초 이하가 필요한 프로세스들은, 더 짧은 프로세스들보다는 낮은 우선순위를 받지만, 역시 서비스를 빨리 받습니다. 긴 프로세스는 자동적으로 큐 2로 가게 되며, 큐 0과 큐 1이 사용하지 않는 CPU 주기에 선입 선처리 방식으로 처리됩니다.

일반적으로, 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의됩니다.

1. 큐의 개수
2. 각 큐를 위한 스케줄링 알고리즘
3. 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
4. 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
5. 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐로 결정하는 방법

다단계 피드백 큐 스케줄러의 정의에 의하면 이 스케줄링 알고리즘은 가장 일반적인 CPU 스케줄링 알고리즘입니다. 이 알고리즘은 설계 중인 특정 시스템에 부합하도록 구성 가능합니다. 그러나 불행하게도 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수들의 값을 선정하는 특정 방법이 필요하기 때문에 또한 가장 복잡한 알고리즘이기도 합니다.

---

요약

CPU 스케줄링은 Ready Queue로부터 대기 중인 프로세스를 선택해 CPU를 할당하는 작업입니다. CPU는 디스패처에 의해 선택된 프로세스에게 할당됩니다.

선입 선처리(FCFS) 스케줄링은 가장 단순한 스케줄링 알고리즘이지만, 짧은 프로세스들이 매우 긴 프로세스딜이 끝날 때까지 기다려야 하는 경우를 유발합니다. 최소 작업 우선 스케줄링(SJF)은 최적임이 증명 가능하며, 가장 짧은 대기 시간을 제공합니다. SJF 스케줄링을 구현하는 일은 어려운데, 이는 다음 CPU 버스트의 길이를 예측하기 어렵기 때문입니다. SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우로 후자는 CPU를 단순히 최고 우선순위의 프로세스에게 할당합니다. 우선순위와 SJF 스케줄링은 모두 기아 상태를 겪을 수 있습니다. 노화(aging)는 기아 상태를 예방하는 기법입니다.

라운드 로빈(RR) 스케줄리은 시분할(대화형) 시스템에 더 적합합니다. 라운드 로빈 스케줄링은 Ready Queue에 있는 첫 번째 프로세스에게 q시간 단위 동안 CPU를 할당합니다. 여기서 q는 시간 할당량입니다. q시간 단위 이후에, 프로세스가 CPU를 양도하지 않았다면, CPU를 선점하고 프로세스는 Ready Queue의 꼬리로 이동합니다. 주요 문제는 시간 할당량을 선택하는 것입니다. 시간 할당량이 너무 크면, 라운드 로빈 스케줄링은 선입 선처리 스케줄링으로 격하되고, 만약 시간 할당량이 너무 적으면, 문맥 교환 시간으로 나타나는 스케줄링 오버헤드가 지나치게 커지게 됩니다.

선입 선처리 알고리즘은 비선점형입니다. 라운드 로빈 알고리즘은 선점형입니다. SJF와 우선 순위 알고리즘은 선점형일 수도 있고 비선점형일 수도 있습니다. 다단계 큐 알고리즘들은 다양한 클래스의 프로세스들에 대해 상이한 알고리즘을 사용하도록 허용합니다. 가장 보편적인 모델은 라운드 로빈 스케줄링을 사용하는 전위 대화형 큐와 선입 선처리 스케줄링을 사용하는 후위 일괄처리 큐입니다. 다단계 피드백 큐는 프로세스들을 한 큐에서 다른 큐로 이동하는 것을 허용합니다.

실시간 시스템은 마감시간 이내에 결과가 나와야만 하는 컴퓨터 시스템입니다. (이 글에선 다루지 않았습니다) 마감시간이 지난 후의 결과는 아무 소영이 없습니다. 경성 실시간 시스템은 실시간 태스크들이 마감시간 이내에 수행될 것이라는 사실을 반드시 보장해야 합니다. 연성 실시간 시스템은 제약이 더 적은 시스템으로 다른 태스크들보다 실시간 태스크에게 더 높은 스케줄링 우선순위를 부여합니다.

스케줄링 알고리즘의 다양성 대문에 알고리즘들을 선택하기 위한 방법을 가질 필요가 있습니다. 분석적 방법은 알고리즘 성능을 결정하는데 수학적 분석을 이용합니다. 모의 실험 방법은 대표적인 견본이 되는 프로세스들에 대해 스케줄링 알고리즘을 흉내 내어 얻어지는 성능을 계산하여 결정합니다. 그러나 모의실험은 실제 시스템의 근사치만을 알려줄 뿐입니다. 스케줄링 알고리즘의 평가 중 유일하게 믿을 수 있는 방법은 실제 시스템에 알고리즘을 구현하고 실세계 환경에서의 성능을 감시하는 것입니다.

---

이상 공룡책 5장 CPU 스케줄링이었습니다. ^_^