Search
Duplicate

운영체제/ CPU 스케줄링

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

기본 개념

단일 처리기 시스템에서는 한 순간에 오직 하나의 프로세스만이 실행될 수 있다. 나머지 프로세스는 CPU가 자유 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 한다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화 하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.
다중 프로그래밍에 대한 기본 아이디어는 비교적 간단하다. 하나의 프로세스는 전형적으로 어떤 입출력 요청이 완료되기를 기다려야 할 때까지 실행된다. 이렇게 되면 단순한 컴퓨터 시스템에서 CPU는 그저 놀고 있게 된다. 이러한 모든 대기 시간은 낭비되며, 어떤 유용한 작업도 수행하지 못한다.
다중 프로그래밍에서는 우리는 이러한 시간을 생상적으로 활용하려고 시도한다. 어느 한 순간에 다수의 프로세스들을 메모리 내에 유지한다. 어떤 프로세스가 대기해야 할 경우 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.
이러한 패턴은 계속된다. 하나의 프로세스가 대기해야 할 때마다 다른 프로세스가 CPU 사용을 양도받을 수 있다.
이러한 종류의 스케줄링은 운영체제의 기본적인 기능이다. 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄 된다. 물론 CPU는 중요한 컴퓨터 자원 중 하나이다. 따라서 CPU의 스케줄링은 운영체제 설계의 핵심이 된다.

CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)

CPU 스케줄링의 성공은 프로세스들의 다음과 같은 관찰된 성질에 의해 좌우된다. 프로세스 실행은 CPU 실행과 입출력 대기의 사이클로 구성된다. 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 한다.
프로세스 실행은 CPU 버스트(burst)로 시작된다. 뒤이어 입출력 버스트가 발생하고 그 뒤를 이어 또 다른 CPU 버스트가 발생하며 이어 또 다른 입출력 버스트 등으로 진행된다.
결국 마지막 CPU 버스트는 또 다른 입출력 버스트가 뒤따르는 대신 실행을 종료하기 위한 시스템 요청과 함께 끝난다. (그림 5.1)
이들 CPU 버스트들의 지속 시간을 광범위하게 측정하였다. 이들은 프로세스마다 그리고 컴퓨터마다 상당히 변화가 크지만 그림 5.2에 보인 바와 유사한 빈도수 곡선을 갖는 경향이 있다. 이 곡선은 일반적으로 지수형 또는 초지수형(hyperexponential)으로 특성화된다.
짧은 CPU 버스트가 많이 있으며, 긴 CPU 버스트는 적다. 입출력 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가질 것이다. CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가질 수 있다. 이러한 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는데 매우 중요할 수 있다.

CPU 스케줄러(CPU Scheduler)

CPU가 유휴 상태가 될 때마다 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행해야 한다. 선택 절차는 단기(short term) 스케줄러(또는 CPU 스케줄러)에 의해 수행된다.
스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여 이들 중 하나에게 CPU를 할당한다.
준비 완료 큐는 반드시 선입 선출(FIFO) 방식의 큐가 아니어도 되는 것에 유의해야 한다. 여러 가지 스케줄링 알고리즘들을 고려할 때 알게 되겠지만, 준비 완료 큐는 선입 선출 큐, 우선순위 큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있다.
그러나 개념적으로 볼 때 준비 완료 큐에 있는 모든 프로세스들은 CPU에서 실행될 기회를 기다리며 대기하고 있다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB) 들이다.

선점 스케줄링(Preemptive Scheduling)

CPU 스케줄링은 다음의 네 가지 상황에서 발생할 수 있다.
1.
한 프로세스가 실행 상태에서 대기 상태로 전환될 때(예컨대 입출력 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait를 호출할 때)
2.
프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(예컨대 인터럽트가 발생할 때)
3.
프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(예컨대 입출력의 종료 시)
4.
프로세스가 종료할 때
상황 1과 4의 경우 스케줄링 면에서는 선택의 여지가 없다. 실행을 위해 새로운 프로세스(준비 완료 큐에 하나라도 존재할 경우)가 반드시 선택되어야 한다. 그러나 상황 2와 3을 위해서는 선택의 여지가 있다.
상황 1과 4에서만 스케줄링이 발생할 경우 우리는 이러한 스케줄링 방법을 비선점(non-preemptive) 또는 협조적(cooperative)이라고 한다. 그렇지 않으면 그것은 선점(preemptive)이라고 한다.
비선점 스케줄링 하에서는 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지 또는 대기 상태로 전환해 CPU를 방출할 때까지 CPU를 점유한다.
이 스케줄링 방법은 Windows 3.1에서 사용되었다. Windows 95에서 선점 스케줄링이 도입되고 그 이후 버전의 Windows 운영체제는 선점 스케줄링을 사용해오고 있다.
Mac OS X 운영체제는 선점 스케줄링을 사용한다. 이전 버전의 Macintosh 운영체제는 협조적 스케줄링을 사용하였다. 이 협조적 스케줄링 방법은 timer와 같은 특수 하드웨어를 요구하지 않기 때문에 특정 기종에서 채택될 수 있는 유일한 방법이다.
불행하게도 선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다. 두 프로세스가 자료를 공유하는 경우를 고려하자. 한 프로세스가 자료를 갱신하고 있는 동안 선점되어 두 번째 프로세스가 실행 가능한 상태가 될 수 있다. 이때 두 번째 프로세스가 데이터를 읽으려고 할 때 데이터의 일관성은 이미 깨진 상태이다.
이러한 문제점에 대해 6장에서 상세하게 논의한다.
선점은 또한 운영체제 커널 설계에 영향을 준다. 시스템 호출을 처리할 동안 커널은 한 프로세스를 위한 활동으로 바쁠 수 있다. 그러한 활동(입출력 큐와 같은) 중요한 커널 자료 변경을 포함할 수 있다.
만일 이렇나 변경 도중에 해당 프로세스가 선점되고, 커널(또는 디바이스 드라이버) 이 동일한 구조를 읽거나 또는 변경할 필요가 있을 경우 어떤 일이 발생할까? 혼란이 계속해서 일어날 것이다.
대부분의 UNIX 버전을 포함하여 몇몇 운영체제들은 문맥교환을 수행하기 전에 시스템 호출이 완료되거나 입출력 요구에 따른 봉쇄가 일어나기를 기다리는 방법을 사용한다. 커널 자료구조가 비일관적인 상태에 있을 동안 커널이 해당 프로세스를 선점하지 않기 때문에 이러한 방법은 커널 구조를 단순하게 만든다.
불행하게도 이러한 커널 실행 모델은 주어진 시간 안에 태스크의 실행이 완료되어야 하는 실시간 컴퓨팅을 지원하기에는 좋은 모델이 아니다. 5.6절에서 실시간 시스템의 스케줄링 요구조건에 대해 탐구한다.
정의에 의하면 인터럽트는 어느 시점에서건 일어날 수 있고, 커널에 의해 항상 무시될 수는 없기 때문에 인터럽트에 의해 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.
운영체제는 거의 항상 인터럽트를 받아들일 필요가 있는데, 그렇지 않으면 입력을 잃어버리거나 또는 출력이 겹쳐서 쓰여질 수 있다. 따라서 이러한 코드 부분은 다수 프로세스가 병행으로 접근할 수 없도록 그 진입점에서 인터럽트를 불능화하고, 출구에서 인터럽트를 다시 가능화 한다. 인터럽트 불능화는 자주 발생해서는 안 되고 아주 적은 수의 명령어들만 포함하여야 한다.

디스패처(Dispatcher)

CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처(dispatcher)이다. 디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이며 다음과 같은 작업을 포함한다.
문맥을 교환하는 일
사용자 모드로 전환하는 일
프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일
디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 최고로 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연(dispatch latency)라고 한다.

스케줄링 기준

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가지고 있으며 한 부류의 프로세스들을 다른 분류보다 더 선호할 수 있다. 특정 상황에서 어떠한 알고리즘을 선택하려면 우리는 다양한 알고리즘들의 서로 달느 특성을 반드시 고려해야 한다.
CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었다. 비교하는데 사용되는 특성에 따라 최선의 알고리즘을 결정하는데 큰 차이가 발생한다. 사용되는 기준은 다음을 포함한다.
CPU 이용률(utilization)
우리는 가능한 CPU를 최대한 바쁘게 유지하기를 원한다. 개념상으로 CPU 이용률은 0에서 100%까지 이른다. 실제 시스템에서는 40% —부하가 적은 시스템의 경우— 에서 90% —부하가 큰 시스템의 경우— 까지의 범위를 가져야 한다.
처리량(throughput)
CPU가 프로세스를 수행하느라고 바쁘다면 작업이 진행되고 있는 것이다. 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이것을 처리량(throughput)이라고 한다.
긴 프로세스인 경우에는 이 비율은 시간당 한 프로세스가 될 수 있고, 짧은 트랜잭션인 경우 처리량은 초당 10개의 프로세스가 될 수도 있다.
총처리 시간(turnaround time)
특정한 프로세스의 입장에서 보면 중요한 기준은 그 프로세스를 실행하는데 소요된 시간일 것이다. 프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 한다.
총처리 시간은 메모리에 들어가기 위해 기다리며 소비한 시간, 준비 완료 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한 시간이다.
대기 시간(waiting time)
CPU 스케줄링 알고리즘은 프로세스가 실행하거나 입출력을 하는 시간의 양에 영향을 미치지는 않는다. 스케줄링 알고리즘은 단지 프로세스가 준비 완료 큐에서 대기하는 시간의 양에만 영향을 준다. 대기 시간은 준비 완료 큐에서 대기하면서 보낸 시간의 합이다.
응답 시간(response time)
대화식 시스템(interactive system)에서 총처리 시간은 최선의 기준이 아닐 수도 있다. 프로세스가 어떤 출력을 매우 일찍 생성하고 앞서의 결과가 사용자에게 출력되는 사이에 새로운 결과를 얻으려고 연산을 계속하는 경우가 종종 있다.
따라서 또 다른 기준은 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간이다. 응답 시간이라고 하는 이 기준은 응답이 시작되는데까지 걸리는 시간이지 그 응답을 출력하는데 걸리는 시간은 아니다. 총처리 시간은 일반적으로 출력 장치의 속도에 의해 제한된다.
CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다. 대부분의 경우 평균 측정 시간을 최적화하려고 한다. 그러나 어떤 경우에는 평균보다는 최솟값 또는 최댓값을 최적화하는 것이 바람직할 때도 있다.
연구자들은 대화식 시스템의 경우에는 평균 응답 시간을 최소화하기보다는 응답 시간의 변동폭(variance)를 최소화하는 것이 중요하다고 제시하고 있다.
합리적이고 예측 가능한 응답 시간을 가진 시스템이 평균 속도는 빠르지만 변동폭이 큰 시스템보다 더 바람직한 것으로 생각될 수 있다. 그러나 변동폭을 최소화하는 CPU 스케줄링 알고리즘에 대한 연구는 거의 없다.

스케줄링 알고리즘

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

선입 선처리 스케줄링(First-Come, First-Served Scheduling)

가장 간단한 CPU 스케줄링 알고리즘은 선입 선처리(FCFS) 스케줄링 알고리즘이다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리할 수 있다.
프로세스가 준비 완료 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다. CPU가 자유 상태가 되면, 준비 완료 큐의 앞부분에 있는 프로세스에게 할당된다.
이 실행 상태의 프로세스는 이어 준비 완료 큐에서 제거된다. 선입 선처리를 위한 코드는 작성하기 쉽고 이해하기 쉽다.
부정적인 측면으로 선입 선처리 정책 하에서 평균 대기 시간은 종종 대단히 길 수 있다. 시간 0에 도착한 다음 프로세스 집합을 생각해 보자. 여기서 CPU 버스트 시간의 길이는 밀리초 단위이다.
프로세스
버스트 시간
P1
24
P2
3
P3
3
프로세스들이 P1, P2, P3 순으로 도착하고 선입 선처리 순으로 서비스 받는다면 다음의 Gantt 차트에 보인 결과를 얻는다. Gantt 차트는 참여한 각 프로세스의 시작 시간과 종료 시간을 포함하여 특정 스케줄 기법을 도시하는 막대형 차트이다.
프로세스 P1의 대기시간은 0밀리초이며, P2는 24밀리초이고, P3은 27밀리초이다. 그러므로 평균 대기 시간은 (0 + 24 + 27) / 3 = 17밀리초이다.
그러나 프로세스들이 P2, P3, P1 순으로 도착하면 결과는 다음 Gantt 차트와 같다.
평균 대기 시간은 (6 + 0 + 3) / 3 = 3밀리초이다. 이러한 감소는 상당히 큰 것이다.
그러므로 선입 선처리 정책 하에서 평균 대기 시간은 일반적으로 최소가 아니며 프로세스 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있다.
추가로 동적 상황에서 선입 선처리 스케줄링의 성능을 고려해 보자. 우리는 하나의 CPU 중심(CPU-bound) 프로세스와 많은 수의 입출력 중심 프로세스를 갖는다고 가정하자. 프로세스들이 시스템에서 진행함에 따라 다음의 시나리오가 발생할 수 있다.
CPU 중심 프로세스가 CPU를 할당 받아서 점유한다. 그 동안 다른 모든 프로세스들은 입출력을 끝내고 준비 완료 큐로 이동하여 CPU를 기다릴 것이다. 프로세스들이 준비 완료 큐에서 기다린느 동안 입출력 장치들은 쉬고 있다.
마침내 CPU 중심 프로세스가 자신의 CPU 버스트를 끝내고 입출력 장치로 이동한다. 모든 입출력 중심의 프로세스들은 매우 짧은 CPU 버스트를 갖고 있기 땜누에 CPU 작업을 신속하게 끝내고 다시 입출력 큐로 이동한다. 이 시점에서 CPU가 쉬게 된다.
그러면 CPU 중심 프로세스는 다시 준비 완료 큐로 이동해 CPU를 할당받는다. CPU 중심 프로세스가 끝날 때까지 다른 모든 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.
선입 선처리 스케줄링 알고리즘은 비선점형이라는 것을 주의하라. 일단 CPU가 한 프로세스에 할당되면 그 프로세스가 종료하든지 또는 입출력 처리를 요구하든지 하여 CPU를 방출할 떄까지 CPU를 점유한다.
선입 선처리 알고리즘은 특히 시분할 시스템에서 문제가 되는데 그 이유는 시분할 시스템에서는 각 사용자가 규칙적인 간격으로 CPU의 몫을 얻는 것이 매우 중요하기 때문이다. 한 프로세스가 지나치게 오랜 동안 CPU를 점유하게 허용하는 것은 손해가 클 것이다.

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

CPU 스케줄링의 다른 접근 방법은 최단 작업 우선(SJF) 알고리즘이다. 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. CPU가 이용 가능해지면 가장 ㅈ가은 다음 CPU 버스트를 가진 프로세스에게 할당한다.
두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면 순위를 정하기 위해 선입 선처리 스케줄링을 적용한다.
이 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링이 되기 때문에 최단 다음 CPU 버스트(shortest-next-CPU-burst) 알고리즘이라는 용어가 더 적합하다.
하나의 예로 밀리초 단위의 CPU 버스트 길이를 가진 다음과 같은 프로세스들의 집합을 고려해 보자.
프로세스
버스트 시간
P1
6
P2
8
P3
7
P4
3
SJF 스케줄링을 이용하면 우리는 이들 프로세스를 다음 Gantt 차트와 같이 스케줄 할 것이다.
평균 대기시간은 (3 + 16 + 9 + 0) / 4 = 7밀리초이다. 비교 차원에서 만일 선입 선출 스케줄링을 사용한다면 평균 대기 시간은 10.25 밀리초가 되었을 것이다.
SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적임이 증명 가능하다.
짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가되는 것보다 더 많이 줄일 수 있다. 결과적으로 평균 대기 시간이 줄어든다.
SJF 알고리즘의 실제 어려움은 다음 CPU 요청의 길이를 파악하는 것이다. 일괄처리 시스템에서 장기 스케줄링을 위해서는 사용자가 작업을 제출할 때 지정한 처리 시간 제한을 이용할 수 있다. 이러한 경우 사용자들이 처리 시간 제한을 정확하게 예상하도록 하는 동기가 된다.
왜냐하면 시간이 짧을수록 신속한 응답을 기대할 수 있지만 너무 짧으면 시간-초과 오류가 발생하게 되어 사용자는 작업을 다시 제출해야 하기 때문이다. SJF 스케줄링은 장기 스케줄링에서 자주 사용된다.
SJF 알고리즘이 최적이긴 하지만 단기 CPU 스케줄링 수준에서는 구현할 수 없다. 단기 스케줄링에서는 다음 CPU 버스트의 길이를 알 수 있는 방법이 없다.
한 가지 접근 방식은 SJF 스케줄링과 근사한 방법을 사용하는 것이다. 다음 CPU 버스트의 길이를 알 수는 없으나 그 값을 예측할 수는 있을 것이다. 우리는 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 기대한다. 그러므로 다음 CPU 버스트의 길이의 근사 값을 계산해 가장 좋은 예상 CPU 버스트를 가진 프로세스를 선택한다.
다음 CPU 버스트는 일반적으로 측정된 이전 CPU 버스트들의 길이를 지수(exponential) 평균 한 것으로 예측한다. 지수 평균을 다음과 같이 정의할 수 있다.
tnt_{n}nn번째 CPU 버스트의 길이라 하고 τn+1\tau_{n+1}은 다음 CPU 버스트에 대한 예측 값이라고 하자. 그러면 0α10 \leq \alpha \leq 1α\alpha에 대해 다음을 정의한다.
τn+1=αtn+(1α)τn\tau_{n+1} = \alpha t_{n} + (1 - \alpha)\tau_{n}
tnt_{n} 값은 최근의 정보를 가지며, τn\tau_{n}은 과거의 역사를 저장한다. 매개변수 α\alpha는 우리의 예측에서 최근의 값과 이전 값의 상대적인 무게를 제어한다.
만약 α=0\alpha = 0이라면 τn+1=τn\tau_{n+1} = \tau_{n}이며, 최근의 역사는 아무 영향이 없다(현재 조건들이 일시적인 것으로 간주된다.)
만약 α=1\alpha = 1이라면 τn+1=tn\tau_{n+1} = t_{n}이며 단지 가장 최근의 CPU 버스타만 중요시된다(역사는 오래되고 관계가 없는 것으로 간주된다)
보다 일반적으로 α=12\alpha = {1 \over 2}이라면 최근의 역사와 과거의 역사가 같은 무게를 갖는다.
그림 5.3은 α=12\alpha = {1 \over 2}이고 τ0=10\tau_{0} = 10일 때의 지수 평균을 보여준다.
지수 평균(exponential average)의 동작 특성을 이해하기 위해, 우리는 τn\tau_{n}을 대치해 τn+1\tau_{n+1}에 대한 공식을 다음과 같이 확장할 수 있다.
τn+1=αtn+(1α)αtn1+...+(1α)jαtnj+...+(1α)n+1τ0\tau_{n+1} = \alpha t_{n} + (1 - \alpha) \alpha t_{n-1} + ... + (1-\alpha)^{j} \alpha t_{n-j} + ... + (1 - \alpha)^{n + 1} \tau_{0}
일반적으로 α\alpha(1α)(1 - \alpha)가 모두 1보다 작거나 같기 때문에, 각 후속 항(term)은 그 전항 보다 가중치가 작게 된다.
SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 완료 큐에 도착하면 선택이 발생한다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다.
선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다. 선점형 SJF 알고리즘은 때때로 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고 불린다.
예컨대 다음 네 프로세스들을 생각해 보자. 여기서 CPU 버스트 시간은 밀리초 단위이다.
프로세스
도착시간
버스트 시간
P1
0
8
P2
1
4
P3
2
9
P4
3
5
프로세스들이 위에 보인 시간에 준비 완료 큐에 도착하고, 표시된 버스트 시간을 요구한다면 결과로 얻어지는 선점형 SJF 스케줄은 다음의 Gantt 차트로 묘사될 수 있다.
이 예에서 평균 대기 시간은 ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 26 / 4 = 6.5밀리초이다. 비선점형 SJF 스케줄링은 평균 대기 시간이 7.75밀리초가 될 것이다.

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

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다. 우선순위가 각 프로세스들에게 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.
우선순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄된다. SJF 알고리즘은 우선순위(pp)가 (예상되는) 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘이다. CPU 버스트가 클수록 우선순위가 낮으며, 그 역도 성립한다.
우리가 높은 우선순위와 낮은 우선순위에 의해 스케줄링을 논의하고 있음에 유의하라. 우선순위는 일반적으로 0-7 또는 0-4095까지 같은 일정 범위의 수가 사용된다. 그러나 0이 최상위 또는 최하위 우선순위인가에 대해서 일반적인 합의는 없다.
어떤 시스템에서는 낮은 값이 낮은 우선순위를 나타내고 다른 시스템에서는 높은 우선순위를 나타낼 수 있다.
하나의 예로 다음 프로세스들의 집합이 시간 0에 P1, P2, … , P6 순서로 도착하고 CPU 버스트 시간의 단위를 밀리초로 가정한다.
프포세스
버스트 시간
우선순위
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2
우선순위 스케줄링을 이용해 다음의 Gantt 차트와 같이 이들 프로세스들을 스케줄하게 될 것이다.
평균 대기 시간은 8.2 밀리초이다.
우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다.
예컨대 시간 제한, 메모리 요구, 열린 파일의 수, 평균 입출력 버스트의 평균 CPU 버스트에 대한 비율 등이 우선순위의 계산에 사용된다.
외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 타입과 양, 그 작업을 후원하는 부서 그리고 정치적인 요인 등과 같은 운영체제 외부적 기준에 의해 결정된다.
우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다. 프로세스가 준비 완료 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교한다.
선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다. 비선점형 우선순위 스케줄링 알고리즘은 단순히 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다.
우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아상태(starvation)이다. 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주될 수 있다.
우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다. 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수도 있다.
일반적으로 두 가지 경우 중 하나가 발생한다. 그 프로세스가 결국 실행되거나 —시스템 부하가 마침내 적어진 일요일 오전 2시에—, 컴퓨터 시스템이 결국 크래시하여 아직 끝나지 않은 우선순위가 낮은 프로세스들을 잃어버린다. —소문에 의하면 1973년에 MIT에서 IBM 7094를 폐쇄했을 때, 1967년에 입력된 낮은 우선순위의 프로세스가 아직도 수행되지 못하고 있는 것을 발견했다고 한다.
낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한 가지 해결 방안은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
예컨대 우선순위가 127(낮음)에서 0(높음)까지의 범위라면 우리는 매 15분마다 대기 중인 프로세스의 우선순위를 1씩 증가시킬 수 있을 것이다.
결국에는 초기의 우선순위가 127이었던 프로세스도 최고 우선순위가 되어 실행될 것이다. 127인 우선순위가 0으로 노화하는데는 32시간 밖에 걸리지 않는다.

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

라운드 로빈(RR) 스케줄링 알고리즘은 특별히 시분할 시스템을 위해 설계되었다. 이는 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.
시간 할당량(time quantum) 또는 시간 조각(time slice)이라고 하는 작은 단위의 시간을 정의한다.
시간 할당량은 일밙거으로 10에서 100밀리초이다. 준비 완료 큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당한다.
라운드 로빈 스케줄링을 구현하기 위해 우리는 다시 준비 완료 큐가 선입 선출 큐로 동작하게 만든다. 새로운 프로세스들은 준비 완료 큐의 꼬리에 추가된다.
CPU 스케줄러는 준비 완료 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머(timer)를 설정한 후, 프로세스를 디스패치(dispatch) 한다.
두 가지 경우 중 하나가 발생할 것이다.
첫 번째는 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 수 있다. 이 경우에 프로세스 자신이 CPU를 자발적으로 방출할 것이다. 스케줄러는 그 후 준비 완료 큐에 있는 다음 프로세스로 진행할 것이다.
두 번째는 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량 보다 긴 경우로 타이머가 끝나고 운영체제에게 인터럽트를 발생할 것이다. 문맥 교환이 일어나고 실행하던 프로세스는 준비 완료 큐의 꼬리에 넣어진다. 그 후 CPU 스케줄러는 준비 완료 큐의 다음 프로세스를 선택할 것이다.
종종 RR 정책 하에서 평균 대기 시간은 길다. 시간 0에 도착하는 아래 프로세스들의 집합을 생각해 보자. CPU 버스트 시간의 단위는 밀리초이다.
만일 우리가 시간 할당량을 4밀리초로 한다면, 프로세스 P1은 처음 4밀리초를 사용한다.
이 프로세스는 20밀리초가 더 필요하기 때문에 이 프로세스는 첫 번째 시간 할당량 이후에 선점되고 CPU는 큐에 있는 다음 프로세스인 P2에 할당된다. 프로세스 P2는 4밀리초를 필요로 하지 않기 때문에, 시간 할당량이 끝나기도 전에 종료한다.
CPU는 이어 다음 프로세스인 P3에게 할당된다. 일단 각 프로세스가 한 번의 시간 할당량을 받으면, CPU는 다음의 시간 할당량을 P1에게 하당한다. 라운드 로빈 스케줄의 결과는 다음과 같다.
프로세스
버스트 시간
P1
24
P2
3
P3
3
이 스케줄에 따르는 평균 대기시간은 P1은 6밀리초(10-4), P2는 4밀리초, P3은 7밀리초를 기다리므로 17/3 = 5.66 밀리초이다.
라운드 로빈 스케줄링 알고리즘에서는 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당 받는 프로세스는 없다.
만일 프로세스의 CPU 버스트가 한 번의 시간 할당량을 초과하면 프로세스는 선점되고 준비 완료 큐로 되돌아간다. 따라서 RR 스케줄링 알고리즘은 선점형이다.
준비 완료 큐에 n개의 프로세스가 있고 시간 할당량이 q이면, 각 프로세스는 최대 q시간 단위의 덩어로로 CPU 시간의 1/n을 갖는다.
각 프로세스는 자신의 다음 시간 할당량이 할당될 때까지 (n-1) x q 시간 이상을 대기하지는 않는다.
예컨대 5개의 프로세스가 있고 시간 할당량이 20밀리초라면 각 프로세스는 매 100밀리초마다 최대로 20밀리초를 할당받을 것이다.
RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우 시간 할당량이 매우 크면 RR 정책은 선입 선처리 정책과 같다. 이와 반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥 교환을 야기한다.
그러므로 우리는 시간 할당량이 문맥 교환 시간에 비해 더 클 것을 원한다. 문맥 교환 시간이 시간 할당량의 10%에 근접한다면 CPU 시간의 약 10%는 문맥 교환에 사용될 것이다.
실제로 대부분의 현대 운영체제들은 10-100밀리초 범위의 시간 할당량을 가지고 있다. 문맥 교환을 하는데 걸리는 시간은 보통 10마이크로초 미만이다. 따라서 문맥 교환 시간은 시간 할당량의 작은 부분을 차지한다.
총처리 시간(turnaround time) 또한 시간 할당량의 크기에 좌우된다. 그림 5.5에서 보는 바와 같이 한 프로세스 집합의 평균 총처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지는 않는다.
일반적으로 대부분의 프로세스들이 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면 평균 총처리 시간은 개선된다. 예컨대 각각 10시간 단위를 가진 세 개의 프로세스들이 있고 시간 할당량이 1시간 단위라면 평균 총처리 시간은 29이다. 시간 할당량이 10이라면 평균 총처리 시간은 20으로 떨어진다.
문맥 교환 시간이 추가된다면 더 많은 문맥 교환이 요구되기 떄문에 더 작은 시간 할당량에 대해서는 평균 총처리 시간이 증가된다.
시간 할당량이 문맥 교환 시간에 비해 커야 하지만 너무 커서는 안 된다. 앞서 지적한 것처럼 시간 할당량이 너무 크다면 RR 스케줄링은 선입 선처리 정책으로 퇴보한다. 경험으로 CPU 버스트의 80%는 시간 할당량보다 짧아야 한다.

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

프로세스들이 쉽게 상이한 그룹으로 분류될 수 있는 상황을 위해 스케줄링 알고리즘의 또 다른 클래스가 고안되었다. 예컨대 일반적으로 포그라운드(foreground) (대화형) 프로세스들과 백그라운드(background) (일괄처리) 프로세스들을 구분한다.
이들 두 유형의 프로세스는 응답 시간에 대한 요구 사항이 다르기 때문에 스케줄링 요구 또한 다를 것이다. 게다가 포그라운드 프로세스들은 백그라운드 프로세스들보다 높은 우선순위를 가질 수 있다.
다단계 큐 스케줄링 알고리즘은 준비 완료 큐를 다수의 별도의 큐로 구분한다 (그림 5.6)
일반적으로 프로세스들은 메모리 크기, 프로세스의 우선순위 혹은 프로세스 유형과 같은 프로세스의 특성에 따라 한 개의 큐에 영구적으로 할당된다.
각 큐는 자신의 스케줄링 알고리즘을 갖고 있다. 예컨대 포그라운드와 백그라운드 프로세스들을 위해 별도의 큐를 사용할 수 있다. 포그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있고 백그라운드 큐는 선입 선처리 알고리즘에 의해 스케줄 될 수 있다.
추가로 큐와 큐 사이에 스케줄링도 반드시 있어야 하며 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다. 예컨대 포그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위를 가질 수 있다.
5개의 큐를 가진 다단계 큐 스케줄링 알고리즘의 예를 보자 각 큐는 다음과 같은 우선순위를 갖는다.
1.
시스템 프로세스
2.
대화형 프로세스
3.
대화형 편집 프로세스
4.
일괄처리 프로세스
5.
학생 프로세스
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.
예컨대 시스템 프로세스, 대화형 프로세스 그리고 대화형 편집 프로세스를 위한 큐들이 모두 비어 있지 않으면 일괄 처리 큐에 있는 프로세스는 실행될 수 없다. 일괄처리 프로세스가 실행되고 있는 중에 대화형 편집 프로세스가 준비 완료 큐에 들어가면 일괄처리 프로세스는 선점될 것이다.
다른 가능성은 큐들 사이에 시간을 나누어 사용하는 것이다. 각 큐는 CPU 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다.
예컨대 포그라운드, 백그라운드 큐의 예에서 포그라운드 큐는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 CPU 시간의 80%가 주어지고, 백그라운드 큐는 CPU 시간의 20%를 받아 자신의 프로세스들에게 선입 선처리 방식으로 줄 수 있다.

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

다단계 큐 스케줄링 알고리즘에서 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.
예컨대 포그라운드와 백그라운드 프로세스를 위해 별도의 큐가 있으 ㄹ경우 프로세스들은 한 큐에서 다른 큐로 이동하지 않는다. 왜냐면 프로세스들이 포그라운드와 백그라운드의 특성을 바꾸지 않기 때문이다.
이러한 방식은 스케줄링 오버헤드가 장점이 있으나 융통성이 적다.
대조적으로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
아이디어는 이렇다. 프로세스들을 CPU 버스트 성격에 따라 구분한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위 큐로 이동된다. 이 방법에서는 입출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.
마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 이러한 노화(aging) 형태는 기아 상태를 예방한다.
예컨대 번호가 0에서 2까지인 세 개의 큐를 가진 다단계 피드백 큐 스케줄러를 생각해 보자. (그림 5.7)
스케줄러는 처음에 큐 0의 모든 프로세스들을 실행시킨다. 큐 0이 비어있을 때만 큐 1에 있는 프로세스들을 실행 시킨다. 마찬가지로 큐 0과 1이 비어 있을 때만 큐 2에 있는 프로세스들이 실행된다.
큐 1에 도착한 프로세스는 큐 2에 있는 프로세스를 선점하고, 큐 1에 있는 프로세스는 큐 0에 도착한 프로세스에 의해 선점될 것이다.
준비 완료 큐로 들어오는 프로세스는 큐 0에 넣어진다. 큐 0에 있는 프로세스는 8밀리초의 시간 할당량이 주어진다. 만약 프로세스가 이 시간 안에 끝나지 않는다면 큐 1의 꼬리로 이동된다.
큐 0이 비어 있다면, 큐 1의 머리에 있는 프로세스에게 16밀리초의 시간 할당량이 주어진다. 이 프로세스가 완료되지 않는다면 선점되어 큐 2에 넣어진다.
큐 0과 1이 비어 있을 때만 큐 2에 있는 프로세스들이 선입 선처리 방식으로 실행된다.
이 스케줄링 알고리즘은 CPU 버스트가 8밀리초 이하인 모든 프로세스에게 최고의 우선순위를 부여한다. 이러한 프로세스는 빨리 CPU를 할당받아서 CPU 버스트를 끝내고 다음 입출력 버스트로 간다.
8밀리초 이상 24밀리초 이하가 필요한 프로세스들은 더 짧은 프로세스들보다는 낮은 우선순위를 받지만, 역시 서비스를 빨리 받는다.
긴 프로세스는 자동적으로 큐 2로 가게되며, 큐 0과 큐 1이 사용하지 않는 CPU 주기에 선입 선처리 방식으로 처리된다.
일반적으로 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.
큐의 개수
각 큐를 위한 스케줄링 알고리즘
한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법
다단계 피드백 큐 스케줄러의 정의에 의하면 이 스케줄링 알고리즘은 가장 일반적은 CPU 스케줄링 알고리즘이다.
이 알고리즘은 설계 중인 특정 시스템에 부합하도록 구성 가능하다. 그러나 불행하게도 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수들의 값을 선정하는 특정 방법이 필요하기 때문에 또한 가장 복잡한 알고리즘이기도 하다.

스레드 스케줄링

4장에서 프로세스 모델에 스레드를 도입하면서 사용자 수준과 커널 수준 스레드를 구별하였다. 이 둘을 지원하는 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.
사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
CPU 상에서 실행되기 위해 LWP를 통한 간접적인 방식일지라도 사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 사상되어야 한다.

경쟁 범위(Contention Scope)

사용자 수준과 커널 수준 스레드의 차이 중 하나는 그들이 어떻게 스케줄 되느냐에 있다. 다대일과 다대다 모델을 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP 상에서 스케줄 된다.
이렇나 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스-경쟁 범위(process-contention scope, PCS)로 알려져 있다.
우리가 스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP 상에서 스케줄 한다고 말하는 경우 스레드가 실제로 CPU 상에서 실행 중이라는 것을 의미하지 않는다. 실제로 CPU 상에서 실행되기 위해서는 운영체제가 커널 스레드를 물리적인 CPU로 스케줄 하는 것을 필요로 한다.
CPU 상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템-경쟁 범위(system-contention scope, SCS)를 사용한다.
SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템 상의 모든 스레드 사이에서 일어난다. Windows, Linux 및 Solaris 같은 일대일 모델을 사용하는 시스템은 오직 SCS만 사용하여 스케줄 한다.
전형적으로 PCS는 우선순위에 따라 행해진다. 즉 스케줄러는 가장 높은 우선순위를 가진 실행 가능한 프로세스를 선택한다. 사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정되고 스레드 라이브러리에 의해 조정되지 않는다.
그러나 몇몇 스레드 라이브러리는 프로그래머가 스레드의 우선순위를 변경하는 것을 허용한다. PCS는 통산 더 높은 우선순위의 스레드를 위하여 현재 실행 중인 스레드를 선점한다는 것을 주의해야 한다. 그러나 같은 우선순위의 스레드들 사이에는 시간 조각에 대한 보장은 없다.

Pthread 스케줄링

4.3.1절에서 Pthreads의 스레드 생성을 소개하면서 POSIX Pthread 프로그램의 예를 제공하였다. 이제는 스레드를 생성하면서 PCS 또는 SCS를 지정할 수 있는 POSIX Pthreads API를 갖오한다. Pthreads는 다음과 같은 범위 값을 구분한다.
PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하여 스레드를 스케줄한다.
PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용하여 스레드를 스케줄한다.
다대다 모델을 구현하는 시스템에서는 PTHREAD_SCOPE_PROCESS 정책이 사용자 수준 스레드를 가용한 LWP로 스케줄한다.
LWP의 개수는 스레드 라이브러리에 의해 유지되고 아마도 스케줄러 액티베이션 기법이 사용될 수도 있다.
다대다 시스템에서 PTHREAD_SCOPE_SYSTEM 스케줄링 정책은 각 사용자 수준 스레드를 LWP를 생성하고 바인드 하게 될 것이고 결과적으로 일대일 모델을 사용하게 된다.
Pthread IPC는 경쟁 범위 정책의 정보를 얻어내고 지정하기 위하여 다음과 같은 두 함수를 제공한다.
pthread_attr_setscope(pthread_attr_t *attr, int scope)
pthread_attr_getscope(pthread_attr_t *attr, int *scope)
두 함수의 첫 번째 매개변수는 스레드를 위한 속성 집합을 가리키는 포인터를 저장한다. pthread_attr_setscope()의 두 번째 매개변수로는 경쟁 범위가 어떻게 지정되는가를 가리키는 PTHREAD_SCOPE_SYSTEM 또는 PTHREAD_SCOPE_PROCESS 값이 전달된다.
pthread_attr_getscope() 함수의 경우에 이 두 번째 매개변수는 경쟁 범위의 현재 값을 저장할 int 값을 가리키는 포인터를 저장한다. 만일 오류가 발생하면 각 함수들은 0이 아닌 값을 반환한다.
아래 코드는 Pthread 스케줄링 API를 설명한다. 이 프로그램은 기존의 경쟁 범위를 결정하고 그 값을 PTHREAD_SCOPE_PROCESS 값으로 지정한다. 그런 후에 SCS 스케줄링 정책을 사용하여 실행 될 5개의 스레드를 생성한다.
어떤 시스템에서는 오직 특정 경쟁 범위 값만이 허용된다는 것을 주의하라. 예컨대 Linux와 Mac OS X 시스템은 PTHREAD_SCOPE_SYSTEM 만을 허용한다.
#include <pthread.h> #include <stdio.h> #define NUM_THREADS 5 int main(int argc, char *argv[]) { int i, scope; pthread_t tid[NUM_THREADS]; pthread_attr_t attr; /* get the default attributes */ pthread_attr_init(&attr); /* first inquire on the current scope */ if (pthread_attr_getscope(&attr, &scope) != 0) fprintf(stderr, "Unable to get scheduling scope\n"); else { if (scope == PTHREAD_SCOPE_PROCESS) printf("PTHREAD_SCOPE_PROCESS"); else if (scope == PTHREAD_SCOPE_SYSTEM) printf("PTHREAD_SCOPE_SYSTEM"); else fprintf(stderr, "Illegal scope value.\n"); } /* set the scheduling algorithm to PCS or SCS */ pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); /* create the threads */ for (int i = 0; i < NUM_THREADS; i++) pthread_create(tid[i], &attr, runner, NULL); /* now join on each thread */ for (int i = 0; i < NUM_THREADS; i+) pthread_join(tid[i], NULL); } /* Each thread will begin control in this function */ void *runner(void *param) { /* do some work */ pthread_exit(0); }
C

다중 처리기 스케줄링

지금까지 논의는 단일 처리기를 가진 시스템에서 CPU를 스케줄하는 문제에 주안점을 두었다. 만일 여러 개의 CPU가 사용 가능하다면, 부하 공유(load sharing)가 가능해진다. 그러나 스케줄링 문제는 그에 상응하여 더욱 복잡해진다.
많은 가능성들이 시도되었으며, 우리가 단일 처리기 CPU 스케줄링에서 보았던 것처럼 여기에도 최상의 해결책은 없다.

다중 처리기 스케줄링에 대한 접근 방법(Approaches to Multiple-Processor Scheduling)

다중 처리기 시스템의 CPU 스케줄링에 관한 한 가지 해결 방법은 주 서버(master server)라는 하나의 처리기가 모든 스케줄링 결정과 입출력 처리 그리고 다른 시스템의 활동을 취급하게 하는 것이다.
다른 처리기들은 다만 사용자 코드만을 수행한다. 이러한 비대칭 다중 처리(asymmetric multiprocessing)는 단지 한 처리기만 시스템 자료구조를 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다.
두 번째 해결 방법은 대칭 다중 처리(symmetric multiprocessing, SMP)를 사용하는 것인데, 이 방식에서는 각 처리기가 독자적으로 스케줄링 한다.
모든 프로세스는 공동의 준비 완료 큐에 있거나 각 처리기 마다 가지고 있는 사유의 준비 완료 큐에 있게 된다. 어쨌든 스케줄링은 각 처리기의 스케줄러가 준비 완료 큐를 검사해서 실행할 프로세스를 선택함으로써 진행된다.
6장에서 보겠지만 여러 개의 처리기가 공동 자료 구조를 접근하고 갱신하려고 한다면 스케줄러는 신중하게 프로그램 되어야 한다. 서로 다른 2개의 처리기가 같은 프로세스를 선택하지 않아야 하며 프로세스들이 큐에서 사라지지 않는다는 것을 보장해야 한다. Windows, Linux, Mac OS X를 포함한 거의 모든 현대 운영체제들은 SMP를 지원한다.

처리기 친화성(Processor Affinity)

프로세스가 특정 처리기에서 실행 중일 때 캐시 메모리에 어떤 일이 벌어지는가 고려해 보자.
처리기에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다. 그 결과 프로세스에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족된다.
이제 프로세스가 다른 처리기로 이주한다면 어떤 일이 벌어지는가 고려하자. 첫 번째 처리기의 캐시 메모리 내용은 무효화 되어야 하고 두 번째 처리기는 다시 채워져야 한다.
캐시를 무효화 하고 다시 채우는 작업은 비용이 많이 들기 때문에 대부분의 SMP 시스템은 한 처리기에서 다른 처리기의 이주를 피하고 대신 같은 처리기에서 프로세스를 실행시키려고 한다.
이 현상을 처리기 친화성(processor affinity)라고 알려져 있으며, 즉 프로세스가 현재 실행 중인 처리기에 친화성을 가진다는 것을 의미한다.
처리기 친화성은 다수의 형태를 띤다. 운영체제가 동일한 처리기에서 프로세스를 실행시키려고 노력하는 정책을 가지고 있지만 보장하지는 않을 때, 연성 친화성(soft affinity)을 가진다고 한다.
이 경우에 운영체제는 프로세스를 특정 처리기에서 실행시키려고 노력은 하지만 프로세스가 처리기 사이에서 이주하는 것이 가능하다.
이와 대조적으로 Linux 같은 몇몇 시스템은 강성 친화성(hard affinity)을 지원하는 시스템 호출을 제공하는데 이 시스템 호출을 통하여 프로세스는 자신이 실행될 처리기 집합을 명시할 수 있다.
많은 시스템들은 연성 친화성과 강성 친화성을 모두 지원한다. 예컨대 Linux는 연성 친화성을 구현하고 있지만 강성 친화성을 지원하는 sched_setaffinity() 시스템 호출도 제공하고 있다.
시스템의 주 메모리 구조가 처리기 친화성 이슈에 영향을 줄 수 있다. 그림 5.9는 비균등 메모리 접근(Non-Uniform Memory Access, NUMA) 특성을 가지는 구조를 도시하고 있다. 이 구조에서는 CPU가 주 메모리의 일부분을 접근할 때 다른 부분보다 빠르게 접근하게 된다.
통상 CPU와 메모리가 합쳐진 보드를 사용하는 시스템에서 나타나는 구조이다. 보드의 CPU는 같은 보드의 메모리를 다른 보드의 메모리 보다 더 빠르게 접근할 수 있다.
운영체제의 스케줄러와 메모리 배치 알고리즘이 연동해서 동작한다면, 특정 CPU와 친화성을 가지는 프로세스는 그 CPU가 장착된 보드 상의 메모리에 할당될 수 있다.
이 사례는 또한 운영체제는 교과서에서 설명된 것처럼 종종 명확하게 정의되고 구현되지 않는다는 사실을 보여준다. 오히려 운영체제의 영역 간의 강한 구분선은 성능과 신뢰성을 최적화 하기 위해 두 영역 사이의 연결을 만드는 알고리즘을 갖는 약한 구분선이라고 할 수 있다.

부하 균등화(Load Balancing)

SMP 시스템에서 처리기가 하나 이상이라는 것을 최대한 활용하려면 부하를 모든 처리기에게 균등하게 배분하는 것이 매우 중요하다.
그렇지 않으면 몇몇 프로세서들은 과부하가 걸리게 되고 이런 CPU의 처리 순서를 기다리는 프로세스가 많아지더라도 일부 프로세서는 유휴 상태에 있게 된다.
부하 균등화(load balancing)는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도한다. 부하 균등화는 통상 각 처리기가 실행할 프로세스를 위한 자기 자신만의 큐를 가지고 있는 시스템에서만 필요한 기능이라는 것을 주의해야 한다.
공통의 실행 큐만 있는 시스템에서는 한 처리기가 쉬게 되면 곧바로 공통 큐에서 새로운 프로세스를 선택하여 실행하기 때문에 부하 균등화는 종종 필요하지 않다.
그러나 SMP를 지원하는 대부분의 현대 운영체제들은 각 처리기가 자신만의 큐를 가지고 있다는 사실도 역시 주의해야 한다.
부하 균등화를 위해서는 push 이주(migration)과 pull 이주 방식의 두 가지 일밙거인 접근법이 있다.
Push 이주에서는 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 쉬고 있거나 덜 바쁜 처리기로 프로세스르 이동(또는 push) 시킴으로써 부하를 재분배한다.
Pull 이주 방식은 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull 할 때 일어난다. Push와 pull 이주는 상호 배타적일 필요는 없으며 실제로는 부하 균등화 시스템에서 종종 병렬적으로 구현된다.
예컨대 Linux 스케줄러와 FreeBSD 시스템에서 가용한 ULE 스케줄러는 두 방식을 모두 구현한다.
흥미롭게도 부하 균등화는 종종 5.5.2절에서 설명한 처리기 친화성의 이익에 상충한다. 즉 같은 처리기에서 프로세스를 실행시키려는 이점은 프로세스가 그 처리기의 캐시 메모리에 존재하는 데이터를 활용하는 것이다.
그러나 프로세스를 한 처리기에서 다른 처리기로 pulling 또는 pushing 함으로써 이 이점을 없애게 된다. 시스템 공학에서 종종 그렇듯 어떤 정책이 최선이냐 하는 점에 관한 절대적인 규칙은 없다.
따라서 몇몇 시스템에서는 쉬고 있는 처리기는 바쁜 처리기에서 언제나 프로세스를 pull 한다. 그리고 다른 시스템에서는 불균형한 상태가 일정 문턱 값(threshold)을 넘을 때만 프로세스를 이주 시킨다.

다중코어 프로세서(Multicore Processors)

SMP 시스템은 다수의 물리 처리기를 제공함으로써 다수의 스레드가 동시에 실해오디게 한다. 그러나 컴퓨터 하드웨어의 최근 관행은 하나의 물리적인 칩 안에 여러 개의 처리기 코어를 장착하는 것이다. 우리는 이런 구조를 다중코어 프로세서(multicore processor)라고 한다.
각 코어는 구조적인 상태를 유지하고 있어서 운영체제 입장에서는 별개의 물리 처리기처럼 보이게 된다. 다중코어 프로세서를 사용하는 SMP 시스템은 각 프로세서가 자신의 물리 칩을 가지는 시스템에 비해 속도가 빠르고 적은 전력을 소모한다.
다중코어 프로세서는 스케줄링 문제를 복잡하게 한다. 어떻게 이러한 일이 생길 수 있는지 생각해 보자.
연구자들은 프로세서가 메모리를 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비한다는 것을 발견하였다. 메모리 멈춤(memory stall)이라고 알려진 이러한 상황은 캐시 미스(캐시 메모리에 접근하려는 데이터가 겂음) 등의 여러 원인 때문에 발생한다.
그림 5.10은 메모리 중단을 묘사하고 있다. 이 시나리오에서 프로세서는 메모리로부터 데이터가 가용해지기를 기다리면서 50%까지 시간을 허비하게 된다.
이 상황을 타개하기 위해서 최근 하드웨어 설계에서는 둘 또는 그 이상의 하드웨어 스레드가 각 코어에 할당될 수 있는 다중 스레드 프로세서 코어를 구현한다. 이 구조에서는 한 스레드가 메모리를 기다리면서 멈추면 코어는 다른 스레드로 전환할 수 있다.
그림 5.11은 스레드 0과 스레드 1이 번갈아 가며 수행되는 이중 프레드 프로세서 코어를 도시하고 있다.
운영체제의 관점에서 각 하드웨어 스레드는 소프트웨어 스레드를 실행할 수 있는 논리 프로세서로 보인다. 따라서 이중스레드, 이중코어 시스템에서는 4개의 논리 프로세서가 운영체제에게 제공된다.
UltraSPARC T3 CPU는 칩당 열여섯 개의 코어와 코어당 8개의 하드웨어 스레드를 가진다. 운영체제의 관점에서 128개의 논리 프로세서가 있는 것처럼 보인다.
일반적으로 처리기를 다중스레드와 하는데에는 거친(coarse-grained) 다중스레딩과 세밀한(fine-grained) 다중스레딩의 2가지 방법이 있다.
거친 다중 스레딩에서는 스레드가 메모리 멈춤과 같은 긴 지연시간을 가진 사건이 발생할 때까지 한 처리기에서 수행된다. 긴 지연시간을 가진 사건에 의한 지연 때문에 처리기는 다른 스레드를 실행하게 된다.
그러나 프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야 하기 때문에 스레드간 교환은 비용이 많이 든다. 이 새로운 스레드가 실행을 싲가하게 되면 자신의 명령어들로 파이프라인을 채우기 시작한다.
세밀한(또는 교차) 다중스레딩은 보통 명령어 주기의 명령어 주기 종료 시점과 같은 더 정밀한 시점에서 스레드 교환이 일어난다. 그러나 세밀한 시스템의 구조적 설계는 스레드 교환을 위한 회로를 포함한다. 그 결과 스레드간 교환의 비용이 적어진다.
다중스레드 다중코어 프로세서는 사실상 두 단계의 스케줄링이 필요하다는 것에 주의해야 한다.
어느 소프트웨어 스레드가 각 하드웨어 스레드(논리 프로세서)에서 실행되어야 하는지를 운영체제가 결정해야 하는 것이 한 단계이다. 이 단계의 스케줄링에서는 운영체제는 5.3절에서 설명한 스케줄링 정책들과 같은 임의의 정책을 사용할 수 있다.
두 번째 단계의 스케줄링에서는 각 코어가 어떤 하드웨어 스레드를 실행시킬지를 지정해야 한다. 이 경우 채택할 많은 정책들이 존재한다. 앞서 언급한 UltraSPARC T3 프로세서는 8개의 하드웨어 스레드를 각 코어에 스케줄하기 위해 간단한 라운드 로빈 알고리즘을 사용한다.
다른 예인 Interl Itanium은 코어 당 2개의 하드웨어-관리 스레드를 가진 이중코어 프로세서이다. 각 하드웨어 스레드는 0에서 7까지의 동적 urgency 값을 할당받는다. 여기서 0은 가장 낮은 긴겁성을 의미하고 7은 가장 높은 긴급성을 의미한다.
Itanium 프로세서는 스레드 교환을 야기하는 5개의 다른 사건을 구분한다. 이 중 한 사건이 발생하면 스레드-교환 회로가 두 세르드의 긴급성을 비교하여 높은 urgency 값을 가지는 스레드를 프로세서 코어에서 실행하게 한다.

실시간 CPU 스케줄링

실시간 운영체제에서 CPU를 스케줄링 할 때는 특별한 쟁점을 고려해야 한다. 일반적으로 연성(soft) 실시간 시스템과 경성(hard) 실시간 시스템으로 구분한다.
연성 실시간 시스템은 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 연성 실시간 시스템은 오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장한다.
경성 실시간 시스템은 더 엄격한 요구조건을 만족시켜야 한다. 태스크는 반드시 마감시간까지 서비스를 받아야 하며 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과를 낳는다.

지연 시간 최소화(Minimizing Latency)

실시간 시스템의 사건-중심의 특성을 생각해 보자. 시스템은 일반적으로 실시간으로 발생하는 사건을 기다린다. 사건은 타이머가 만료되었을 때처럼 소프트웨엊거으로 발생하기도 하고, 원격으로 제어되던 장치가 방해물을 만났을 때와 같이 하드웨어적으로 발생하기도 한다.
사건이 발생하면 시스템은 가능한 빨리 그에 응답을 하고 그에 맞는 동작을 수행해야 한다. 사건 지연 시간은 사건이 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 말한다. (그림 5.12)
일반적으로 사건이 다르면 그에 따른 지연 시간 역시 다르다.
다음의 두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.
인터럽트 지연시간
디스패치 지연시간
인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말한다.
인터럽트가 발생하면 운영체제는 우선 수행 중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정한다. 해당 인터럽트 서비스 루틴(ISR)을 사용하여 인터럽트를 처리하기 전에 현재 수행 중인 프로세스의 상태를 저장해 놓아야만 한다. 이러한 작업들을 모두 수행하는데 걸리는 시간이 인터럽트 지연시간이다. (그림 5.13)
실시간 태스크가 즉시 수행될 수 있도록 인터럽트 지연시간을 최소화하는 것은 실시간 운영체제에게 매우 중요한 일이다. 사실 경성 실시간 시스템에서는 인터럽트 지연시간을 최소로 해야 할 뿐만 아니라 엄격한 요구조건을 만족시키기 위하여 정해진 시간보다 작아야 한다.
인터럽트 지연시간에 영향을 주는 요인 중 하나는 커널 데이터 구조체를 갱신하는 동안 인터럽트가 불능케 되는 시간이다. 실시간 운영체제는 인터럽트 불능 시간을 매우 짧게 하여야 한다.
디스패치 지연 시간은 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 싲가하게 하는데 걸리는 시간을 말한다.
CPU를 즉시 사용해야 하는 실시간 태스크가 있다면 실시간 운영체제는 이 지연 시간을 최소화해야 한다. 디스패치 지연 시간을 최소화하는 가장 효과적인 방법은 선점형 커널이다.
그림 5.14를 보면 디스패치 지연 시간의 구성을 표혐하고 있다. 디스패치 지연 시간의 충돌 단계는 다음의 두 가지 요소로 구성되어 있다.
1.
커널에서 동작하는 프로세스에 대한 선점
2.
높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출
예컨대 Solaris에서는 선점 불가능 상태의 디스패치 지연 시간이 100밀리초를 넘는다. 그러나 선점 가능상태에서는 1밀리초 미만으로 줄어든다.

우선순위 기반의 스케줄링(Priority-Based Scheduling)

실시간 운영체제에서 가장 중요한 기능은 실시간 프로세스가 CPU를 필요로 할 때 바로 응답을 해주는 것이다. 따라서 실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원해야만 한다.
우선순위 기반의 스케줄링 알고리즘은 각각의 프로세스의 중요성에 따라 그 우선순위를 부여한다. 더 중요한 태스크가 그렇지 않은 태스크들보다 더 높은 우선순위를 갖게 된다.
또한 스케줄러가 선점 기법을 제공한다면 현재 CPU를 이용하고 있는 프로세스가 더 높은 우선순위를 갖는 프로세스에게 선점될 수도 있다.
앞서 Linux, Windows, Solaris 운영체제의 연성 실시간 스케줄링의 사례를 살펴보았다. 이러한 시스템들은 실시간 프로세스들에게 가장 높은 스케줄링 우선권을 부여한다.
예컨대 Windows에는 32개의 우선순위가 존재하는데, 가장 높은 순위인 16에서 31의 값이 실시간 프로세스들에게 할당되어 있다. Solaris와 Linux 역시 비슷한 우선순위 기법을 가지고 있다.
그러나 선점 및 우선순위 기반의 스케줄러를 제공하는 것은 단지 연성 실시간 기능을 제공하는 것에 불과하다. 경성 실시간 시스템에서는 실시간 태스크가 마감시간 내에 확실히 수행되는 것을 보장해야만 하며, 그렇기 때문에 부가적인 스케줄링 기법이 필요하다.
개별 스케줄러에 대해 자세히 알아보기 전에 스케줄 될 프로세스들의 특성들을 정의할 필요가 있다. 첫 번째로 프로세스들은 주기적이다. 즉 프로세스들은 일정한 간격으로 CPU를 필요로 한다.
각각의 주기 프로세스들은 CPU 사용권을 얻었을 때마다 고정된 수행 시간 t, CPU로부터 반드시 서비스를 받아야 하는 마감시간 d와 주기 p가 정해져 있다.
수행시간, 마감시간, 주기의 관계는 0tdp0 \leq t \leq d \leq p이다. 주기 태스크의 실행 빈도는 1p{1 \over p}이다.
그림 15.5는 주기 프로세스의 실행에 대해 설명하고 있다. 스케줄러는 이들 주기, 마감 시간, 수행 시간 사이의 관계를 이용하여 마감시간과 주기적 프로세스의 실행 빈도에 따라서 우선순위를 정한다.
이런 형식의 스케줄링에서 일반적이지 않은 것은 프로세스가 자신의 마감시간을 스케줄러에게 알려야만 할 수도 있다는 것이다. 따라서 승인 제어(admission-control) 알고리즘을 이용해서 스케줄러는 마감시간 이내에 완수할 수 있는 프로세스는 실행을 허락하고 그렇지 못한 경우에는 요구를 거절한다.

Rate-Monotonic 스케줄링

Rate-monotonic 스케줄링 알고리즘은 선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄한다. 낮은 우선순위의 프로세스가 실행 중에 있고 높은 우선순위의 프로세스가 실행 준비가 되면 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 선점한다.
각각의 주기 태스크들은 시스템에 진입하게 되면 주기에 따라 우선순위가 정해진다. 주기가 짧은 태스크는 높은 우선순위가 주기가 길면 낮은 우선순위가 배정된다. 이 정책은 CPU를 더 자주 필요로 하는 태스크에게 더 높은 우선순위를 주려는 원리에 기반을 두고 있다.
더욱이 rate-monotonic 스케줄링은 주기 프로세스들의 처리 시간은 각각의 CPU 버스트와 같다고 가정한다. 즉 프로세스가 CPU를 차지한 시간은 각각의 CPU 버스트 시간과 같다.
예컨대 두 개의 프로세스 P1, P2가 있다고 할 때, P1의 주기는 50, P2의 주기는 100이라고 하자. 즉 P1 = 50, P2 = 100이다. P1의 수행시간 T1=20, P2의 수행시간 T2 = 35이다. 각 프로세스의 마감시간은 다음 주기가 시작하기 전까지이다.
먼저 두 프로세스가 모두 마감시간을 충족시키도록 스케줄링 가능한지 생각해 보아야 한다.
각 프로세스의 CPU 이용률, 즉 주기에 대한 수행 시간 T1/P1을 구해보면 P1의 CPU 이용률은 20/50 = 0.4이고, P2의 CPU 이용률은 35/100 = 0.35이다. 총 CPU 이용률은 75%가 된다. 따라서 두 프로세스 모두 마감시간을 충족시키고도 여유시간이 있을 것으로 보인다.
P2의 우선순위가 P1보다 높다고 가정하자. 두 프로세스의 수행 모습이 그림 5.16에 표현되어 있다.
그림에서 보듯이 P2가 먼저 수행을 시작해 시간 35에 수행을 끝낸다. 이때 P1이 시작해서 시간 55에 수행을 끝낸다. 그러나 P1의 마감시간이 50이기 때문에 스케줄러는 P1의 마감시간을 만족시키지 못한다.
Rate-monotonic 스케줄을 사용하면 P1의 주기가 P2의 주기보다 짧기 때문에 P1의 우선순위가 P2의 우선순위보다 높다. 이 스케줄링 정책을 적용했을 때, 두 프로세스의 수행 모습이 그림 5.17에 표현되어 있다.
P1이 먼저 수행하여 시간 20에 끝낸다. 따라서 첫 번째 마감시간을 만족시킨다. 바로 P2가 수행을 시작해서 시간 50까지 수행을 끝낸다.
이 때 5밀리초의 CPU 할당 시간이 남아 있기는 하지만 P1에게 선점된다. P1은 시간 70까지 수행하고 스케줄러는 다시 P2를 수행시킨다. P2는 75에 수행을 끝내고, 자신의 첫 번째 마감시간을 만족시킨다.
시스템은 시간 100까지 유휴 시간을 갖다가 P1이 다시 스케줄된다.
Rate-monotonic 스케줄링 기법이 스케줄 할 수 없는 프로세스 집합의 경우 정적 우선순위를 이용하는 다른 알고리즘들 역시 스케줄 할 수 없는 측면에서 최적(optimal)이라고 할 수 있다. 이 스케줄링 기법을 이용해서 스케줄 할 수 없는 프로세스 집합에 대해 알아보자.
P1 = 50의 주기를 갖고, T1 = 25인 수행 시간을 갖는 프로세스 P1이 있다고 하자. 프로세스 P2는 P2 = 80의 주기를 갖고 T2 = 35의 수행 시간을 갖는다고 하자.
P1이 더 짧은 주기를 갖기 때문에 rate-monotonic 스케줄링 기법은 P1에게 더 높은 우선순위를 부여한다. 두 프로세스의 전체 CPU 이용률을 계산해 보면 (25/50) + (35/80) = 0.94로 CPU에 6%의 여유를 가지고 모두 스케줄할 수 있을 것으로 보인다.
그림 5.18에 프로세스 P1과 P2의 스케줄이 Gantt 차트로 표현되어 있다. P1이 먼저 시작하여 시간 25까지 수행되고 다음 P2가 수행을 시작하여 시간 50까지 수행 후 P1에게 선점된다.
P2는 아직 10밀리초의 CPU 할당시간이 남아 있다. P1이 시간 75까지 수행되고, P2는 시간 80에 자신의 마감시간을 충족시키지 못한다.
Rate-monotonic 스케줄링 기법은 최적이기는 하지만 많은 제약을 가지고 있다. CPU 이용률은 한계가 있기 때문에 CPU 자원을 최대화해서 사용하는 것은 불가능하다. N개의 프로세스를 스케줄하는데 있어 최악의 경우 CPU 이용률은 2(21N1)2(2^{{1 \over N}}-1)이다.
시스템에 한 개의 프로세스만 존재한다면 CPU 이용률은 100%이다. 그러나 프로세스의 수가 증가함에 따라 69%까지 떨어진다. 두 프로세스가 존재할 경우 CPU 이용륭은 약 83%가 한계이다.
그림 5.16과 5.17에서 스케줄 되었던 두 프로세스의 CPU 이용률을 합하면 75%이다. 따라서 이 경우 rate-monotonic 스케줄링 알고리즘은 마감시간을 만족시키도록 스케줄하는 것을 보장한다.
그림 5.18에서 스케줄 된 두 프로세스의 경우 CPU 이용률이 94%에 근접했기 때문에 rate-monotonic 스케줄링 알고리즘은 두 프로세스가 마감시간을 만족시킬지 여부를 보장할 수 없다.

Earliest-Deadline-First 스케줄링

Earliest-deadline-first(EDF) 스케줄링 기법은 마감시간에 따라 우선순위를 동적으로 부여한다. 마감시간이 빠를수록 우선순위는 높아지고 늦을수록 낮아진다.
EDF 정책에서는 프로세스가 실행가능하게 되면 자시느이 마감시간을 시스템에 알려야 한다. 우선순위는 새로 실행가능하게 된 프로세스의 마감시간에 맞춰서 다시 조정된다. 이 점이 우선순위가 고정되어 있는 rate-monotonic 스케줄링 기법과 다른 점이다.
EDF 스케줄링을 설명하기 위해 rate-monotonic 스케줄링 기법에서 마감시간을 만족시키지 못했던 그림 5.18의 두 프로세스를 다시 스케줄 해 보자.
EDF 스케줄 기법을 사용하여 이 두 프로세스를 스케줄한 모습이 그림 5.19에 표현되어 있다. 처음에는 프로세스 P1의 마감시간이 더 빠르기 때문에 P1의 우선순위는 P2의 우선순위보다 높다. 프로세스 P2는 P1의 CPU burst가 끝난 후 수행을 시작한다.
그러나 rate-monotonic 스케줄링에서는 시간 50의 다음 주기에 P1이 P2를 선점했던 것과 달리 EDF 스케줄링에서는 P2가 계속 수행된다. P2의 마감시간(시간 80)이 P1의 마감시간(시감 100)보다 더 빠르기 때문에 이젠 P2의 우선순위가 더 높다. 따라서 P1, P2 모두 첫 번째 마감시간을 만족 시킨다.
프로세스 P1은 시간 60에 다시 수행을 싲가해서 시간 85에 두 번째 CPU 할당을 끝낸다. 시간 100 이내이기 때문에 두 번째 마감시간 역시 만족시킨다. P2는 다시 수행을 시작하고 다음 주기인 시간 100에 P1에게 선점된다. P1의 마감시간(시간 150)이 P2의 마감시간(시감 160)보다 빠르기 때문이다.
시간 125에 P1은 CPU 할당량을 완수하고, P2가 수행을 시작하여 시간 145에 끝나게 되어 마감시간을 만족시킨다. 시간 150까지 시스템은 유휴 시간을 갖고 다시 P1이 스케줄 되어 수행을 시작한다.
Rate-monotonic 알고리즘과 달리 EDF 스케줄링 알고리즘은 프로세스들이 주깆거일 필요도 없고, CPU 할당 시간도 상수 값으로 정해질 필요가 없다. 그러나 프로세스가 실행가능해질 때 자신의 마감시간을 스케줄러에게 알려줘야 한다.
EDF가 매력적인 이유는 이론적으로 최적이라는 것이다. 이론적으로 모든 프로세스가 마감시간을 만족시키도록 스케줄할 수 있고 CPU 이용률 역시 100%가 될 수 있다.
그러나 실제로는 프로세스 사이 또는 인터럽트 핸들링 때의 문맥 교환 비율 떄문에 100%의 CPU 이용률은 불가능하다.

일정 비율의 몫 스케줄링(Proportionate Share Scheduling)

일정 비율의 몫 스케줄러는 모든 응용들에게 T개의 시간 몫을 할당하여 동작한다. 한 개의 응용이 N개의 시간 몫을 할당받으면, 그 응용은 모든 프로세스 시간 중 N/T 시간을 할당받게 된다.
예컨대 T = 100인 시간 몫이 있다고 할 때, 3개의 프로세스 A, B, C에게 이를 나누어 할당한다고 가정하자. A는 50 몫, B는 15 몫, C는 20 몫을 할당 받았다고 할 때, 일정 비율의 몫 스케줄링 기법은 A가 모든 처리기 시간의 50%를, B가 15%를, C가 20%를 할당 받는 것이다.
일정 비율의 몫 스케줄러는 응용이 시간 몫을 할당받는 것을 보장하는 승인 제어 정책과 함께 동작해야만 한다. 승인 제어 정책은 사용 가능한 충분한 몫이 존재할 때, 그 범위 내의 몫을 요구하는 클라이언트들에게만 실행을 허락한다.
위의 예에서 총 100개에서 50 + 15 + 20 = 85개의 몫만 할당되었다. 새로운 프로세스 D가 30몫을 요구하면 승인 제어기는 D의 시스템 진입을 거부한다.

POSIX 실시간 스케줄링

POSIX는 실시간 컴퓨팅 용으로 POSIX.1b라는 확장을 제공한다. 이 절에서는 실시간 스레드 스케줄링과 관련된 POSIX API에 관해 알아본다. POSIX는 다음과 같이 실시간 스레드를 위하여 두 개의 스케줄링 클래스를 정의한다.
SCHED_FIFO
SCHED_RR
SCHED_FIFO는 FIFO 큐를 사용하여 먼저 온 것을 먼저 서비스하는 정책에 따라 스레드를 스케줄한다. 따라서 FIFO 큐의 앞에 있는 가장 높은 우선순위의 실시간 스레드는 종료되거나 블록(block) 될 때까지 CPU를 할당 받는다.
SCHED_RR은 라운드 로빈 정책을 사용하며, 같은 우선순위의 스레드들에게 시간 할당량을 제공하는 것을 제외하면 SCHED_FIFO와 비슷하다.
POSIX는 SCHED_OTHER라는 다른 스케줄링 클래스 역시 제공하기는 하지만 그 구현은 시스템마다 다르다.
POSIX API는 스케줄링 정책에 관한 정보를 지정하고 얻어내는 다음과 같은 두 개의 함수를 제공한다.
pthread_attr_getsched_policy(pthread_attr_t *attr, int *policy)
pthread_attr_setsched_policy(pthread_attr_t *attr, int policy)
두 함수의 첫 번째 인자는 스레드의 속성 집합에 대한 포인터이다. 두 번째 인자는 현재의 스케줄링 정책이거나 SCHED_FIFO, SCHED_RR, SCHED_OTHER와 같은 정책을 표현하는 정수 값읻.ㅏ 두 함수 모두 에러가 발생하면 0이 아닌 값을 반환한다.
아래 코드에 이런 API를 사용하는 POSIX Pthread 프로그램이 나와있다. 이 프로그램은 현재의 스케줄링 정책을 얻어내고 그런 후 SCHED_FIFO로 스케줄링 알고리즘을 지정한다.
#include <pthread.h> #include <stdio.h> #define NUM_THREADS 5 int main(int argc, char *argv[]) { int i, policy; pthread_t tid[NUM_THREADS]; /* the thread identifier */ pthread_attr_t attr; /* set of attributes for the thread */ /* get the default attributes */ pthread_attr_init(&attr); /* get the current scheduling policy */ if (pthread_attr_getschedpolicy(&attr, &policy) != 0) fprintf(stderr, "Unable to get scheduling scope\n"); else { if (policy == SCHED_OTHER) printf("SCHED OTHER\n"); else if (policy == SCHED_RR) printf("SCHED_RR\n"); else if (policy == SCHED_FIFO) printf("SCHED_FIFO\n"); } /* set the scheduling policy - FIFO, RR, or OTHER */ if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0) fprintf(stderr, "unable to set scheduling policy to SCHED_OTHER\n"); /* create the threads */ for (int i = 0; i < NUM_THREADS; i++) pthread_create(tid[i], &attr, runner, NULL); /* now join on each thread */ for (int i = 0; i < NUM_THREADS; i+) pthread_join(tid[i], NULL); } /* Each thread will begin control in this function */ void *runner(void *param) { /* do some work */ pthread_exit(0); }
C

운영체제 사례들

사례: Linux 스케줄링

Linux의 프로세스 스케줄링은 흥미로운 역사를 가지고 있다. 버전 2.5전까지는 전통적인 UNIX 스케줄링 알고리즘의 변형을 사용하였다. 하지만 이 알고리즘은 SMP 시스템을 염두에 두고 설계되지 않았기 때문에 다중 처리기 시스템을 충분히 지원하지 않는다. 매우 많은 프로세스가 실행되는 시스템에서는 저조한 성능을 보인다.
버전 2.5에서 이 스케줄러는 분석, 수정되어 시스템에 존재하는 태스크 개수와 상관없이 항상 상수 시간에 실행되는 O(1)이라고 알려진 스케줄링 알고리즘이 포함되었다. 이 새로운 스케줄러는 또한 처리기 진화 정책과 처리기 사이의 부하를 균등하게 하는 기능 등 SMP를 위한 향상된 지원을 제공한다.
실제 운용 면에서 O(1) 스케줄러는 SMP 시스템에서 출중한 성능을 보이지만 데스크톱 컴퓨터 시스템에서 나타나는 대화형 프로세스에 대해서는 느린 응답을 보인다.
2.6 커널을 개발하는 동안 스케줄러는 다시 개선되었고, 2.6.23 커널부터 완벽한 공평 스케줄러(Completely Fair Scheduler, CFS)가 Linux 시스템의 디폴트 스케줄링 알고리즘이 되었다.
Linux 스케줄러는 각 클래스 별로 특정 우선순위를 부여받는 스케줄링 클래스에 기반을 두고 동작한다. 다른 스케줄링 클래스를 사용하여 시스템과 프로세스의 요구조건에 따라 커널은 다른 스케줄링 알고리즘을 수용할 수 있다.
예컨대 Linux 서버를 위한 스케줄링 기준은 Linux를 운영하는 이동장치를 위한 기준과는 다를 수 있다. 다음에 실행될 태스크를 결정하기 스케줄러는 높은 우선순위 클래스에 속한 가장 높은 우선순위의 태스크를 선택한다.
표준 Linux 커널은 (1) CFS 스케줄링 알고리즘을 사용하는 디폴트 스케줄링 클래스와 (2) 실시간 스케줄링 클래스의 두 스케줄링 클래스를 구현한다. 여기서 각 클래스에 대해 논의하며 이 외에 새로운 클래스가 추가될 수 있다.
CFS 스케줄러는 상대 우선순위에 상응하는 시간 할당량의 길이가 정해져 있는 경직된 규칙을 사용하지 않고 각 태스크에게 CPU 처리시간의 비율을 할당한다. 이 비율은 각 태스크에게 할당된 nice 값에 기반을 두고 계산된다.
Nice 값은 -20부터 19까지의 범위를 가지며, 값이 적을수록 우선순위는 높아진다. 적은 nice 값의 태스크는 높은 nice 값의 태스크 보다 더 큰 비율의 CPU 처리 시간을 할당받는다. Nice 값은 0을 디폴트값으로 가진다
CFS는 이산 값을 가지는 시간 할당량을 사용하지 않고 대신에 목적 지연시간(targeted latency)을 찾는다. 목적 지연시간은 다른 모든 수행 가능한 태스크가 적어도 한 번씩은 실행할 수 있는 시간 간격을 나타낸다.
CPU 시간의 비율은 이 목적 지연시간의 값으로부터 할당된다. 목적 지연시간은 디폴트값과 최소값을 가지며, 시스템 상에 활성 태스크의 개수가 일정 임계값보다 많아지면 증가할 수 있다.
CFS는 직접 우선순위를 할당하지 않는다. 그보다 CFS는 각 태스크 별로 vruntime이라는 변수에 태스크가 실행된 시간을 기록하여 가상 실행 시간을 유지한다. 이 가상 실행 시간은 태스크의 우선순위에 기반을 둔 감쇠 지수(decay factor)와 관련된다.
낮은 우선순위 태스크는 높은 우선순위 태스크보다 감쇠율이 높다. 보통 우선순위의(nice 값이 0) 태스크의 경우 가상 실행시간은 실제 물리적 실행 시간과 같다.
따라서 디폴트 우선순위의 태스크가 200ms 동안 실행된다면 vruntime 값도 역시 200ms가 될 것이다. 그러나 낮은 우선순위의 태스크가 200ms 동안 실행된다면 vruntime 값은 200ms보다 클 것이다. 마찬가지로 높은 우선순위의 태스크가 200ms 동안 실행된다면 vruntime은 200ms 보다 작을 것이다.
다음에 실행될 태스크를 선택하려면 스케줄러는 단순히 가장 작은 vruntime 값을 가진 태스크를 선택한다. 게다가 실행 가능하게 된 높은 우선순위 태스크는 낮은 우선 순위 태스크를 선점할 수 있다.
CFS 스케줄러가 어떻게 동작하는지 검토해 보자. 두 태스크가 같은 nice 값을 가진다고 가정하자. 한 태스크는 입출력 중심이고 다른 하나는 CPU 중심 태스크이다.
보통 입출력 중심 태스크는 추가의 입출력을 위하여 짧은 시간 실행되고 봉쇄되고 CPU 중심 태스크는 처리기 위에서 실행될 기회를 얻을 때마다 시간 주기를 전부 소진하려고 한다.
따라서 결국에는 입출력 중심 태스크의 vruntime 값은 CPU 중심 태스크의 vruntime 값보다 작아지게 되어 입출력 중심 태스크가 CPU 중심 태스크보다 우선순위가 높아지게 된다. 이 상황에서 입출력 중심 태스크가 실행 가능해지면 현재 실행 중인 CPU 중심 태스크를 선점하게 된다.
또한 Linux는 5.6.6절에서 설명한 것처럼 POSIX 표준을 사용하여 실시간 스케줄링을 구현한다. SCHED_FIFO 또는 SCHED_RR 실시간 정책을 사용하여 스케줄 된 태스크는 보통의 태스크 보다 높은 우선순위를 받고 실행된다.
Linux는 실시간 태스크에게 할당해주는 우선순위 영역과 보통의 태스크에게 할당해 주는 영역 등 두 개의 별도 영역을 사용한다. 실시간 태스크는 0부터 99 사이의 범위에서 정적 우선순위를 부여받고, 보통의 태스크는 100에서 139까지의 영역에서 부여받는다.
이 두 영역은 하나의 전역 우선순위 구조로 사상되는데, 전역 영역에서는 수치 상 작은 값이 상대적으로 높은 우선순위를 나타낸다. 보통 태스크들은 nice 값에 기반을 둔 우선순위가 할당되는데, -20은 우선순위 100에 +19는 139에 사상된다. 이 구조가 그림 5.21에 나와 있다.

CFS 성능

Linux CFS 스케줄러는 실행할 다음 태스크를 선택하기 위한 효율적인 알고리즘을 제공한다. 모든 실행 가능한 태스크는 키값으로 vruntime 값을 이용하는 균형이진 탐색 트리인 적-백 트리 형태로 관리된다. 이 트리가 아래 도시되어 있다.
태스크가 실행 가능해지면 트리에 추가된다. 트리의 태스크가 실행 가능해지지 않게 되면(예컨대 입출력을 기다리는 동안 봉쇄되면) 트리에서 제거된다.
일반적으로 더 적은 처리 시간이 주어진(vruntime 값이 더 작은) 태스크는 트리의 왼편으로 이동하면, 더 많은 처리 시간이 주어진 태스트는 오른편에 있게 된다.
이진 탐색 트리의 특성에 따라 가장 왼쪽의 노드가 가장 작은 키값을 가지며 CFS 스케줄러 입장에서는 가장 높은 우선순위를 가진 태스크를 의미한다.
적백 트리는 균형 트리이기 때문에 가장 왼쪽의 노드를 찾기 위해 탐색하는데 O(lgN) 연산이 필요하다. (N은 트리 노드의 개수를 나타낸다). 그러나 효율을 향상시키기 위해 Linux 스케줄러는 이 값을 rb_leftmost 변수에 캐싱하므로 다음에 실행할 태스크를 결정하기 위해서는 이 캐시 값을 보면 된다.

사례: Windows 스케줄링

Windows는 우선순위에 기반을 둔 선점 스케줄링 알고리즘을 사용한다. Windows 스케줄러는 가장 높은 우선순위의 스레드가 항상 실행되도록 보장한다. Windows 커널 중 스케줄링을 담당하는 부분을 디스패처(dispatcher)라고 부른다.
디스패처에 의해 선택된 스레드는 높은 우선순위 스레드에 의해 선점되든지, 연산이 다 끝나든지, 시간 할당량이 만료되든지, 입출력을 위한 것과 같은 봉쇄를 야기하는 시스템 호출을 호출할 떄까지 실행된다.
우선순위가 낮은 스레드가 실행 중에 우선순위가 높은 실시간 스레드가 준비 상태가 되면 우선순위가 낮은 스레드는 선점된다. 이와 같은 선점은 필요한 경우에 실시간 스레드가 CPU를 액세스할 수 있는 우선권을 준다.
디스패처는 스레드의 실행 순서를 정하기 위하여 32단계의 우선순위를 두고 있다. 우선순위는 두 클래스로 구분된다. 가변 클래스(variable class)에 있는 스레드들은 우선순위가 1부터 15까지이다. 실시간 클래스는 우선순위 16부터 31까지의 스레드를 포함한다. 또한 우선순위가 0인 스레드도 존재하는데 이 스레드는 메모리 관리를 위해 사용된다.
디스패처는 각 우선순위를 위하여 큐를 사용하고 이들 큐를 높은 우선순위부터 낮은 우선순위까지 조사하면서 준비 상태의 스레드가 있는지를 본다. 준비 상태에 있는 스레드가 없으면 디스패처는 idle 스레드라고 불리는 특수한 스레드를 실행시킨다.
Windows API와 Windows 커널이 제공하는 숫자로 나타내지는 우선순위 사이에는 연관 관계가 있다. Windows API는 프로세스들이 속할 수 있는 몇 가지 우선순위 클래스를 제공하며 그들은 아래와 같다.
IDLE_PRIORITY_CLASS
BELOW_NORMAL_PRIORITY_CLASS
NORMAL_PRIORITY_CLASS
ABOVE_NORMAL_PRIORITY_CLASS
HIGH_PRIORITY_CLASS
REALTIME_PRIORITY_CLASS
프로세스는 통산 NORMAL_PRIORITY_CLASS에 속한다. 부모 프로세스가 IDLE_PRIORITY_CLASS에 속하지 않고 프로세스가 생성될 때 다른 클래스가 명시되지 않는 한 프로세스는 이 클래스에 속하게 된다.
추가적으로 프로세스의 우선순위 클래스는 Windows API 중 SetPriorityClass() 함수를 사용하여 변경될 수 있다.
REALTIME_PRIORITY_CLASS를 제외한 모든 우선순위 클래스는 가변적이고 이는 이 클래스에 속한 스레드의 우선순위가 변할 수 있다는 것을 뜻한다.
우선순위 클래스의 스레드들 역시 상대적인 우선순위를 가진다. 이 상대적인 우선순위를 위한 값은 아래와 같다.
IDLE
LOWEST
BELOW_NORMAL
NORMAL
ABOVE_NORMAL
HIGHEST
TIME_CRITICAL
각 스레드의 우선순위는 그 스레드가 속한 우선순위 클래스와 그 클래스 안에서의 상대적인 우선순위(relative priority)에 기반을 둔다. 그림 5.22에 이 상관관계가 나와 있다. 각 우선순위 클래스에 대응하는 값들은 맨 위의 행에 나타나 있다. 왼쪽 열은 상대적인 우선순위(relative priority)들을 나타낸다.
예컨대 ABOVE_NORMAL_PRIORITY_CLASS에 속한 스레드의 상대 우선순위가 NORMAL이라면 그 스레드의 우선순위는 숫자로 10이 된다.
게다가 각 스레드는 스레드가 속한 클래스의 우선순위 범위 안의 값을 기본 우선순위로 배정 받는다. 각 클래스의 디폴트 우선순위는 그 클래스의 NORMAL에 해당하는 상대적인 우선순위를 따른다.
스레드의 초기 우선순위는 보통 스레드가 속한 프로세스의 기본 우선순위가 배정된다. 하지만 Windows API의 SetThreadPriority() 함수를 이용하여 스레드의 기본 우선순위를 변경할 수 있다.
스레드의 시간 할당량이 만료되면 그 스레드는 인터럽트 된다. 그 스레드가 가변 우선순위 클래스에 속한다면 우선순위가 낮아진다. 그러나 우선순위는 기본 우선순위 보다 낮아지지는 않는다. 스레드의 우선순위를 이렇게 낮추게 되면 계산 중심 스레드들이 CPU를 독점하는 것을 제한하게 된다.
가변 우선순위 스레드가 대기 연산에서 풀려나면 디스패처는 그 우선순위를 높여준다. 얼마를 높여주느냐는 그 스레드가 무엇 때문에 기다려왔느냐에 따라 달려 있다. 예컨대 키보드 입출력을 기다렸다면 많이 높여주고 디스크를 기다렸다면 보통 정도로 높여준다.
이러한 전략은 마우스와 윈도우를 쓰는 대화형 스레드들에게 빠른 응답 시간을 허용한다. 계산 중심 스레드들에게는 후위로 실행되면서 남는 CPU 사이클을 활용하도록 하면서 입출력 중심 스레드들에게는 입출력 장치를 바쁘게 만들도록 한다. 이 전략은 UNIX와 같은 많은 시분할 시스템에서 사용된다.
이외에도 현재 사용자가 상호작용을 하고 있는 윈도우는 우선순위를 높게 받아서 응답 시간이 향상된다.
사용자가 대화형 프로그램을 실행 중일 때는 시스템은 그 프로세스가 특별히 좋은 성능을 얻도록 해야 한다. 이러한 이유 때문에 Windows는 NORMAL_PRIORITY_CLASS에 있는 프로세스들에게 특별한 스케줄링 법칙을 적용한다.
Windows는 스크린 상에서 활성화 중인 전위 프로세스들과 그렇지 않은 후위들을 구분한다. Windows는 프로세스가 전위 프로세스가 되면 시간 할당량을 보통 3배 정도 증가시킨다. 이렇게 높여주면 전위 프로세스는 시분할 선점을 당하기까지 3배나 더 오래 수행을 계속할 수 있게 된다.
Windows 7은 사용자 모드 스케줄(user-mode scheduling, UMS)를 도입하였는데, 응용프로그램이 커널과는 독립적으로 스레드를 생성하고 관리할 수 있게 한다. 따라서 응용은 Windows 커널 스케줄러의 도움 없이 여러 스레드를 생성하고 스케줄 할 수 있다.
매우 많은 스레드를 생성하는 응용의 경우 사용자 모드에서 스레드를 스케줄하면 커널의 개입이 필요하지 않기 때문에 커널 모드 스레드 스케줄링을 이용할 때보다 훨씬 효율적이다.
Windows 초기 버전들은 fiber라고 불렸던 이와 유사한 기능을 제공하였다. 이 fiber는 많은 사용자 스레드(fiber)가 하나의 커널 스레드에게 사상되는 것이 가능하게 한다.
그러나 fiber는 실제 사용시에 제약이 있었다. 모든 fiber들은 자신들이 실행되는 스레드의 스레드 환경 블록(thread environment block, TEB)을 공유해야만 했기 때문에 Windows API를 호출할 수 없었다.
Windows API 함수가 한 fiber의 상태 정보를 TEB에 저장하고 이 정보를 다른 fiber가 변경하는 경우 문제를 일으킨다. UMS는 모든 사용자 모드 스레드가 각자의 문맥을 저장할 수 있게 함으로써 이를 극복하였다.
게다가 fiber와 다르게 UMS는 프로그래머가 직접 사용하는 것을 염두에 두지 않고 설계되었다. 사용자 모드 스케줄러를 작성하는 것은 매우 힘든 작업이고 UMS는 그러한 스케줄러를 가지고 있지 않다. 오히려 UMS 위에 구축된 프로그래밍 언어 라이브러리들을 이용하여 스케줄러를 만들 수 있다.
예컨대 MS는 태스크 기반 병렬성을 제공하기 위해 설계된 C++를 위한 병행 프로그래밍 프레임워크인 Concurrency Runtime(ConRT)를 제공한다. ConRT는 프로그램을 분해하여 처리기 코어에서 스케줄 될 수 있는 태스크를 분해하는 설비와 함께 스케줄러를 제공한다.

사례: Solaris 스케줄링

Solaris는 우선순위 기반 스레드 스케줄링을 사용한다. Solaris는 우선순위에 따라 다음과 같은 6개의 스케줄링 클래스를 정의한다.
1.
시분할(time-shareing, TS)
2.
대화형(Interactive, IA)
3.
실시간(Real Time, RT)
4.
시스템(System, SYS)
5.
공평 공유(Fair Share, FSS)
6.
고정 우선순위(Fixed Priority, FP)
각 클래스에는 서로 다른 우선순위와 서로 다른 스케줄링 알고리즘이 존재한다.
프로세스의 디폴트 스케줄링 클래스는 시분할이다. 시분할 스케줄링 정책은 다단계 피드백 큐를 사용하여 동적으로 우선순위를 바꾸고, 서로 다른 길이의 시간 조각을 할당한다.
디폴트로, 우선순위와 시간 조각 사이에는 반비례 관계가 존재한다. 우선순위가 더 높을수록 시간 조각은 더 작고, 우선순위가 더 낮을수록 시간 조각은 더 크다. 통상 대화형 프로세스는 높은 우선순위를 가지고 CPU 위주의 프로세스는 낮은 우선순위를 가진다.
이러한 스케줄링 정책은 대화형 프로세스에는 더 나은 응답 시간을 제공하고, CPU 위주의 프로세스에는 더 나은 처리량을 제공한다. 대화형 클래스는 시분할 클래스와 같은 스케줄링 정채긍ㄹ 사용하지만 더 나은 성능을 위해 KDE 또는 GNOME 윈도우 관리자에 의해 생성된 윈도우의 응용에 더 높은 우선순위를 준다.
그림 5.23은 대화형과 시분할 스레드를 스케줄하기 위한 디스패치 테이블을 보이고 있다. 이 두 클래스는 60개의 우선순위 수준을 포함한다. 그러나 간단히 보이기 위하여 우리는 적은 수의 수준만 보인다. 그림 5.23의 디스패치 테이블은 다음과 같은 필드를 포함한다.
우선순위
시분할과 대화형 클래스를 위한 클래스 종속적인 우선순위. 큰 숫자가 높은 우선순위를 표시한다.
시간 할당량
연관된 우선순위를 위한 시간 할당량. 이 필드는 우선순위와 시간 할당량 간의 반비례 관계를 설명한다. 가장 낮은 우선순위(우선순위 0)가 가장 큰 시간 할당량(200ms)을 갖는다. 가장 높은 우선순위(우선순위 59)가 가장 작은 시간 할당량(20ms)을 갖는다.
시간 할당량 만료
봉쇄없이 시간 할당량 전부를 사용한 스레드의 새로운 우선순위. 이러한 스레드들은 CPU 중심 스레드로 간주된다. 테이블에 보인 것처럼 이 스레드들은 우선순위가 낮아진다.
수면 상태로부터 복귀
입출력 대기와 같은 수면 상태로부터 복귀한 스레드의 우선순위. 테이블이 설명하는 것처럼 대기 중인 스레드가 원하는 입출력 데이터가 가용한 경우 스레드의 우선순위는 50에서 59 사이의 값으로 상승한다. 따라서 대화형 프로세스가 좋은 응답시간을 가지도록 제공하는 정책을 지원한다.
실시간 클래스의 스레드에게는 가장 높은 우선순위가 주어진다. 실시간 프로세스는 다른 어떤 클래스의 프로세스보다 먼저 수행될 것이다. 이러한 배정은 실시간 프로세스가 제한된 주기 내에 시스템으로부터 응답을 보장받도록 한다. 그러나 일반적으로 실시간 클래스에 속하는 프로세스는 소수이다.
Solaris는 스케줄러와 페이지 디먼과 같은 커널 스레드를 실행하기 위해 시스템 클래스를 사용한다. 일단 시스템 스레드의 우선순위는 한 번 설정되면 바뀌지 않는다. 시스템 클래스는 커널용으로 예약되어 있다. (커널 모드에서 실행되는 사용자 프로세스는 시스템 클래스에 속하지 않는다)
Solaris 9는 고정 우선순위(fixed priority)와 공평 공유(fair share)의 새로운 스케줄링 클래스를 도입하였다.
고정 우선순위 클래스에 속한 스레드는 시분할 클래스의 스레드와 같은 우선순위를 갖는다. 그러나 이 우선순위는 동적으로 조정되지 않는다. 공평 공유 스케줄링 클래스는 스케줄링 결정을 위하여 우선순위 대신에 CPU 공유량(share)을 사용한다.
CPU 공유량은 가용한 CPU 자원에 대한 권리(entitlement)를 가리키고 프로젝트(project)라고 불리는 프로세스의 집합에 할당된다.
각 스케줄링 클래스 내에는 우선순위의 집합이 있다. 그러나 스케줄러는 클래스 고유의 우선순위를 전역 우선순위로 바꾸며, 가장 높은 전역 우선순위를 가진 스레드를 실행하도록 선택한다.
선택된 스레드는 (1) 봉쇄 되거나 (2) 시간 조각을 전부 사용하거나 (3) 높은 우선순위의 스레드에 의해 선점될 때까지 CPU 상에서 실행된다.
그림 5.24는 여섯 개의 스케줄링 클래스가 서로 어떻게 연관되어 있으며 어떻게 전역적인 우선순위로 사상되는 지를 보이고 있다.
커널이 인터럽트를 서비스하기 위하여 10개의 스레드를 유지한다는 사실에 주목해야 한다. 이 스레드들은 어느 스케줄링 클래스에도 속하지 않으며 가장 높은 우선순위로 실행된다.(160-169) 앞서 언급한 것처럼 Solaris는 전통적으로 다대다 모델을 사용하였으나 Solaris 9부터는 일대일 모델로 전환하였다.

알고리즘의 평가

알고리즘을 선택하기 위해 먼저 이 값들의 상대적인 중요성을 반드시 정의해야 한다. 우리의 기준은 다음과 같은 다수의 대책을 포함할 수 있다.
최대 응답 시간이 1초라는 제약 조건 하에서 CPU 이용률을 극대화한다.
총 처리 시간이 전체 실행 시간에 평균적으로 선형 비례가 되도록 처리량을 극대화 한다.

결정론적 모델링(Deterministic Modeling)

평가 방법의 한 중요한 부류로 분석적 평가(analytic evaluation)가 있다. 분석적 평가에서는 주어진 작업 부하에 대한 알고리즘의 성능을 평가하는 공식이나 값을 생성하기 위해 주어진 알고리즘과 시스템 작업 부하를 이용한다.
분석적 평가의 한 가지 유형은 결정론적 모델링(deterministic modeling)이다. 이 방식은 사전에 정의된 특정한 작업 부하를 받아들여 그 작업 부하에 대한 각 알고리즘의 성능을 정의한다.
예컨대 아래와 같은 작업 부하가 있다고 가정한다. 다섯 개의 프로세스들이 시간 0에 아래와 같은 순서로 도착하며 CPU 버스트의 길이는 밀리초 단위이다.
프로세스
버스트 시간
P1
10
P2
29
P3
3
P4
7
P5
12
이 프로세스들의 집합에 대해 선입 선처리(first-come first-served), SJF(shortest-job-first) 그리고 라운드 로빈(시간 할당량 = 10밀리초) 스케줄링 알고리즘을 고려하자. 어떤 알고리즘의 평균 대기 시간이 가장 짧은가?
선입 선처리 알고리즘으로는 다음과 같이 프로세스들을 실행할 것이다.
평균 대기시간은 (0 + 10 + 39 + 42 + 49) / 5 = 28 밀리초이다.
비선점 SJF 스케줄링으로는 다음과 같이 프로세스들을 실행할 것이다.
평균 대기 시간은 (10 + 32 + 0 + 3 + 20) / 6 = 13밀리초이다.
라운드 로빈 알고리즘에서는 프로세스들을 아래와 같이 수행할 것이다.
평균 대기시간은 (0 + 32 + 20 + 23 + 40) / 5 = 23 밀리초이다.
이 경우 SJF 정책의 평균 대기 시간은 선입 선처리 스케줄링으로 얻은 평균 대기시간의 1/2보다 작다. 라운드 로빈 알고리즘은 중간 정도이다.
결정론적 모델링은 단순하고 빠르다. 이것은 알고리즘들을 비교할 수 있도록 정확한 값을 제공한다. 그러나 이것은 입력으로 정확한 숫자를 요구하며, 그 응답도 단지 이들의 경우에만 적용된다.
결정론적 모델링은 주로 스케줄링 알고리즘을 섦여하고 예를 제공하는데 사용한다. 동일한 프로그램을 반복해 여러 번 실행하고, 프로그램의 처리 요구사항들을 정확하게 측정할 수 있는 경우, 우리는 스케줄링 알고리즘을 선택하기 위해 결정론적 모델링을 사용할 수 있다.
게다가 결정론적 모델링은 예들의 집합에 대해 별도로 분석하고 증명할 수 있는 경향들을 나타낼 수 있다. 예컨대 기술된 환경에 대해(모든 프로세스들과 이들의 시간들이 시간 0에 알 수 있을 때) SFJ 정책은 항상 대기 시간을 최소화한다.

큐잉 모델(Queueing Models)

많은 시스템에서 실행되는 프로세스들은 날마다 변화하기 때문에 결정론적 모델링을 사용할 수 있는 프로세스들(그리고 시간들)의 정적인 집합이 없다. 그러나 결정할 수 있는 것은 CPU와 입출력 버스트의 분포이다.
이들의 분포는 측정할 수 있으며 그런 후에 근사 값을 계산하거나 단순하게 추정할 수 있다. 결과로 특정 CPU 버스트의 확률을 기술하는 수학적인 공식을 얻을 수 있다. 일반적으로 이런 분포는 보통 지수적(exponential)이며 평균에 의해 기술된다.
마찬가지로 프로세스들이 시스템에 도착하는 시간의 분포(도착 시간 분포)도 기술할 수 있다. 이들 두 분포로부터 대부분의 알고리즘들에 대한 평균 처리량, 이용류르, 대기 시간 등을 계산하는 것이 가능하다.
컴퓨터 시스템은 서버들의 네트워크로 기술된다. 각 서버는 대기 프로세스들의 큐를 가지고 있다. CPU는 준비 완료 큐를 갖고 있는 서버이고, 장치 큐를 갖고 있는 입출력 시스템도 마찬가지이다.
도착률과 서비스율을 알면 우리는 이용률, 평균 큐 길이, 평균 대기 시간 등을 계산할 수 있다. 이러한 영역에 대한 연구를 큐잉 네트워크 분석(queueing-network analysis)이라고 한다.
예로써 nn을 평균 큐 길이(서비스를 받고 있는 프로세스는 제외)라 하고, WW를 큐에서의 평균 대기 시간이라 하고, λ\lambda를 새로운 프로세스들이 큐에 도착하는 평균 도착률(예컨대 1초에 세 개의 프로세스)이라고 하자.
그러면 프로세스가 대기하는 시간 WW 동안에 λ×W\lambda \times W 개의 새로운 프로세스들이 큐에 도착할 것이다. 만일 시스템이 안정 상태라면 큐를 떠나는 프로세스의 수는 도착하는 프로세스의 수와 같아야 한다. 그러므로 다음 식이 성립한다.
n=λ×Wn = \lambda \times W
이 식을 Little’s formula라고 하고 이 공식은 어떠한 스케줄링 알고리즘이나 어떠한 도착 분포에서도 성립하기 때문에 특히 유용하다.
세 개의 변수 중 두 개의 변수를 알고 있다면 나머지 하나를 계산하기 위해 Little’s formula를 사용할 수 있다. 예컨대 초당 7개의 프로세스가 평균적으로 도착하고, 큐에는 통상 14개의 프로세스가 있음을 우리가 안다면, 프로세스당 평균 대기 시간을 2초로 계산할 수 있다.
큐잉 분석은 스케줄링 알고리즘을 비교하는데 유용하게 사용할 수 있으나 역시 한계가 있다. 현재 분석할 수 있는 알고리즘과 분포의 부류가 상당히 제한되어 있다. 복잡한 알고리즘이나 분포와 관련된 수학적 분석이 어렵다.
따라서 도착과 서비스 분포들이 대개 비현실적이지만 수학적으로 분석하기 쉬운 방법으로 정의된다. 또한 정확하지 않을 수 있는 다수의 독립된 가정을 하는 것이 일반적으로 필요하다.
이러한 어려움 때문에 큐잉 모델들은 종종 단지 실제 시스템의 근사치이며 연산된 결과의 정확성에는 의심의 여지가 있다.

모의실험(Simulation)

스케줄링 알고리즘을 더욱 정확하게 평가하기 위해서 우리는 모의실험(simulation)을 사용할 수 있다. 모의실험을 하는 것은 컴퓨터 시스템의 모델을 프로그래밍 하는 것을 포함한다. 소프트웨어 자료구조가 시스템의 주요 구성 요소를 표현한다.
모의실험기(simulator)는 시간을 나타내는 변수를 갖는다. 이 변수의 값을 증가시키면서 시스템의 상태를 수정해 장치들 프로세스 및 스케줄러 등의 활동을 반영한다. 모의실험을 실행하면서 알고리즘의 성능을 나타내는 통계들을 수집하고 인쇄한다.
모의실험을 구동하기 위한 자료들은 여러 가지 방법으로 생성할 수 있다. 가장 보편적인 방법은 난수 발생기(random number generator)로서 이것은 확률 분포에 따라서 프로세스, CPU 버스트 시간, 도착, 출발 등을 생성하기 위해 프로그램 된다.
분포는 수학적으로(균등(uniform), 지수(exponential), 포아송(Poisson)) 또는 경험적으로 정의될 수 있다.
경험적으로 분포를 정의하려면 연구의 대상이 되는 실제 시스템에 대한 측정이 행해진다. 그 결과는 실제 시스템에서 사건(event)들의 실제 분포를 정의한다. 이 분포는 이어 모의실험을 구동하는데 사용될 수 있다.
그러나 분포에 의해 주도되는 모의실험은 실제 시스템에서 연속적인 사건들 사이의 관계 때문에 부정확할 수 있다. 빈도 수 분포는 단지 각 사건들이 얼마나 많이 발생하는가를 의미한다. 그러나 이들의 생성 순서에 대해서는 아무 정보도 제공하지 못한다.
이 문제를 해결하기 위해 우리는 추적 테이프(trace tape)를 사용할 수 있다 실제 시스템을 관찰해 실제 사건들의 순서를 기록하여 추적 테이프를 생성한다(그림 5.25).
우리는 이어 이 순서를 모의 실험을 실행하는데 사용할 수 있다. 추적 테이프는 실제 입력들과 정확히 동일한 입력으로 두 개의 알고리즘들을 비교하는 좋은 방법이다. 이 방법은 입력에 대하여 정확한 결과를 생성할 수 있다.
모의 실험은 컴퓨터를 몇 시간씩 사용하기 때문에 매우 많은 비용이 소요될 수 있다. 모의 실험을 상세하게 할수록 더 정확한 결과를 얻을 수 있으나 컴퓨터 사용 시간을 더 필요하게 된다. 더구나 추적 테이프는 대량의 저장 공간을 요구할 수 있다. 마지막으로 모의실험기의 설계, 코딩, 오류 수정은 매우 중요한 작업이 될 수 있다.

구현(Implementation)

모의시렇ㅁ도 정확성에 한계가 있다. 스케줄링 알고리즘을 완벽히 정확하게 평가하는 유일한 방법은 실제 코드로 작성해 운영체제에 넣고 실행해 보는 것이다. 이 접근 방식은 실제 운영 환경 하에서의 평가를 위해 실제 시스템에 실제 알고리즘을 삽입하는 것이다.
이 방식의 주요 어려움은 높은 비용에 있다. 비용은 알고리즘 코드를 작성하고 그것을 지원하기 위해 운영체제 코드와 그에 따른 자료구조를 변경하는 것 뿐만 아니라 끊임없이 변경되는 운영체제에 대한 사용자의 반응에 의해서 유발된다.
대부분의 사용자들은 더 좋은 운영체제를 구축하는데는 관심이 없고, 단지 자신의 프로세스를 실행하여 결과를 이용하기만을 원한다. 계속적으로 변경되는 운영체제는 사용자들이 작업을 수행하는데 도움을 주지 못한다.
이 방식의 다른 어려움은 알고리즘이 사용되는 환경이 변화할 것이라는 것이다. 환경은 새로운 프로그램이 작성되고 해결해야 할 문제의 유형이 변화하는데 따른 일상적인 방식을 따르기도 하지만, 스케줄러가 보이는 성능의 결과에 따라서도 변화할 것이다.
짧은 프로세스들에게 우선순위를 주면 사용자들은 큰 프로세스들을 작은 프로세스들의 집합으로 나눌 것이다. 비대화형 프로세스보다 대화형 프로세스들에게 우선순위를 주면, 사용자들은 컴퓨터를 대화형으로 사용할 것이다.
예컨대 연구자들이 단말기 입출력의 양을 보고 프로세스들을 자동적으로 대화형과 비대화형으로 분류하는 시스템을 설계했다고 하자. 프로세스가 1초 내에 단말기로 입력하거나 출력하지 않는다면 그 프로세스를 비대화형으로 분류하고 낮은 우선순위 큐로 이동시킨다.
이러한 정책은 한 프로그래머가 1초 내에 규칙적인 간격으로 임의의 문자를 단말기에 출력하도록 자신의 프로그램을 변경하는 결과를 낳았다. 단말기 출력이 전혀 의미가 없을지라도 시스템은 이 프로그램에게 높은 우선순위를 부여하였다.
가장 융통성이 있는 스케줄링 알고리즘은 시스템 관리자 또는 사용자에 의해 알고리즘이 특정 응용이나 응용 집합에 맞도록 조정될 수 있게 한다.
예컨대 고성능의 그래피컬 응용을 수행하는 워크스테이션은 웹 서버나 파일 서버와는 다른 스케줄링 요구를 가질 수 있다. 일부 운영체제(특히 UNIX의 다수의 버전)는 시스템 관리자가 특정 시스템 구성을 위해 스케줄링 변수들을 미세 조정할 수 있게 허용한다.
예컨대 Solaris는 시스템 관리자가 5.7.3절에서 설명된 스케줄링 클래스의 매개변수를 수정할 수 있게 하는 dispadmin 명령을 제공한다.
다른 접근 방법은 프로세스나 스레드의 우선순위를 변경하는 API를 사용하는 것이다. Java, POSIX 및 WinAPI가 이런 함수를 제공한다. 이 방법의 단점은 종종 시스템이나 응용의 성능 조정이 보다 일반적인 상황에서는 개선된 성능을 낳지 않는다는 것이다.