CPU scheduling은 multiprogramming의 기본이다.
OS는 효율적인 CPU scheduling을 통해 컴퓨터를 보다 생산적으로 만들 수 있다.

5.1 Basic Concepts

CPU가 노는 시간을 줄이기, 즉 CPU 이용률을 최대화하는 것이 multi-programming의 목적이다.
다수의 프로세스를 메모리 내에 유지하고, 어떤 프로세스가 대기해야 할 경우, OS는 CPU를 그 프로세스로부터 회수해서 다른 프로세스에 할당하는 패턴을 계속 유지하면서 그 목적에 도달하고자 한다.

5.1.1 CPU-I/O Burst Cycle

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
프로세스 실행은 CPU burst로 시작된다. 뒤이어 I/O burst가 발생하고, 그 뒤를 이어 또다른 CPU burst가 발생하는 식으로 프로세스들은 이 두 상태를 왔다갔다 한다.

이들 CPU burst들의 지속시간을 광범위하게 측정해보면, 일반적으로 빈도수 곡선은 지수형(exponential)으로 특성화되는데 짧은 CPU burst가 많이 있다는 특징이 있다.
(I/O 중심의 프로그램은 전형적으로 짧은 CPU burst를 가진다고 한다.)

5.1.2 CPU Scheduler

CPU가 idle한 상태가 될 때마다, OS는 ready queue에 있는 프로세스 중에서 하나를 선택해서 실행해야 한다. 이때 선택 절차는 CPU scheduler에 의해 수행된다.
ready queue는 반드시 FIFO 방식의 queue가 아니어도 되는 것에 유의해야 한다.
(이후에 스케줄링 알고리즘 소개)

5.1.3 Preemptive and Nonpreemptive Scheduling

CPU scheduling 결정은 다음의 네 가지 상황에 발생할 수 있다.
1. 한 프로세스가 running state에서 waiting state로 전환될 때
(예를 들어, I/O 요쳥이나 자식 프로세스가 종료되기를 기다리기 위해 wait()를 호출할 때)
2. 프로세스가 running state에서 ready state로 전환될 때
(예를 들어, 인터럽트가 발생할 때)
3. 프로세스가 waiting state에서 ready state로 전환할 때
(예를 들어, I/O의 종료시)
4. 프로세스가 종료할 때

1번과 4번 상황의 경우, 실행을 위해 세로운 프로세스가 반드시 선택되어야 한다.
1번과 4번 상황에서만 스케줄링이 발생할 경우, nonpreemptive 라고 한다.
그렇지 않으면, preemptive 라고 한다.

nonpreemptive scheduling 하에서는 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 waiting state로 전환해 CPU를 방출할 때까지 점유한다.
(쉽게 말해 preemptive에서는 강제 종료 가능)

5.1.4 Dispatcher

dispatcher는 CPU 코어의 제어를 CPU scheduler가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.

• 한 프로세스에서 다른 프로세스로 context를 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 jump 하는 일

dispatcher는 모든 프로세스의 context 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 한다.

dispatcher가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 dispatch latency라고 한다.

5.2 Scheduling Criteria

서로 다른 CPU scheduling 알고리즘들은 다른 특성이 있으며 이를 비교하기 위한 여러 기준이 제시되었다.

• CPU utilization
• throughput
• turnaround time (총처리 시간 = 대기 + 실행 + I/O)
• waiting time
• response time (응답 시간)

5.3 Scheduling Algorithms

처리 코어가 하나뿐이라고 가정하고 설명한다. 즉, 한 개의 처리 코어를 가진 CPU가 한 개인 시스템이므로 한 번에 하나의 프로세스만 실행할 수 있다.

5.3.1 FIFO Scheduling

가장 간단하고 이해하기 쉬운 CPU scheduling algorithm이다.
이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.

P1, P2, P3 순으로 도착하고, FIFO로 처리된다면, 첫 번째 그림과 같은 결과를 얻을 수 있다.
(*Gantt chart는 참여한 각 프로세스의 시작 시각과 종료 시각을 포함하여 특정 스케줄 기법을 그래프로 나타낸 막대형 차트이다)

일반적으로 FIFO scheduling에서 평균 대기 시간은 최소가 아니며, 프로세서 CPU burst 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있다.

또한 FIFO scheduling은 nonpreemptive임을 주의해야 한다.

5.3.2 Shortest-Job-First Scheduling (SJF)

이 알고리즘은 각 프로세스에 다음 CPU burst 길이를 연관시킨다.
가장 작은 CPU burst를 가진 프로세스에 CPU를 할당하고, 두 프로세스가 동일한 길이의 CPU burst를 가질 경우 순위를 정하기 위해 FIFO scheduling을 적용한다.

SJF 알고리즘은 최소의 평균 대기 시간을 가진다는 점에서 최적이긴 하지만, 다음 CPU burst 길이를 알 방법이 없기 때문에 CPU scheduling 수준에서는 구현할 수 없다.

한 가지 접근 방식은 SJF scheduling 방식과 근사한 방법을 사용하는 것이다.
다음 CPU burst 길이의 근삿값을 계산해, 가장 짧은 예상 CPU burst를 가진 프로세스를 선택한다.

지수 평균 계산식은 다음과 같다.
tn(최근의 정보)은 n번째 CPU burst 길이이고, τ(n+1)은 다음 CPU burst에 대한 예측값이라고 하고, 0 <= α <= τ_n(과거의 정보) 이다.

지수 평균(exponential average)의 동작 특성을 이해하기 위해, 우리는 τn을 대치해 τ(n+1)에 대한 공식을 다음과 같이 확장할 수 있다.

일반적으로 α와 (1-α)가 모두 1보다 작거나 같기 때문에, 각 후속 항은 그 전 항보다 가중치가 작게 든다.

5.3.3 Round-Robin Scheduling (RR)

RR scheduling은 FIFO scheduling과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있다는 점이 추가된다. time quantum(시간 할당량) 또는 time slice라고 하는 작은 단위의 시간을 정의하여, CPU scheduler는 ready queue를 돌면서 한 번에 한 프로세스에 한 번의 time quantum 동안 CPU를 할당한다.

RR scheduling 알고리즘에서는, 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당받는 프로세스는 없다. 만약 프로세스의 CPU burst가 한 번의 time quantum을 초과하면, 프로세스는 선점되고 ready queue로 되돌아 간다. 따라서 RR scheduling 알고리즘은 preemptive이다.

5.3.4 Priority Scheduling

우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. SJF 알고리즘은 일반적인 priority scheduling의 특별한 경우로, 우선순위가 (예상되는) 다음 CPU burst의 역이다. 따라서 CPU burst가 클수록 우선순위가 낮다.

priority scheduling의 주요 문제점은 indefinite blocking 또는 starvation이다.
실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 blocking된 것으로 간주할 수 있다. priority scheduling 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.
이에 대한 해결책은 aging이다. aging은 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.

5.3.5 Multilevel Queue Scheduling

실무에서는 특정 우선순위에 해당하는 큐를 따로 갖기도 하는데, 일반적으로 보면 우선순위란 정적으로 각 프로세스에 할당되고 프로세스는 실행 중엔 같은 큐에 존재한다.

프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 multilevel queue scheduling 알고리즘을 사용할 수 있다.
각 큐에는 자체 스케줄링 알고리즘이 있을 수 있고, 큐와 큐 사이에도 스케줄링이 반드시 있어야 하며 일반적으로 고정 우선순위의 preemptive scheduling으로 구현된다. (예를 들어, real-time queue는 interactive queue보다 절대적으로 높은 우선순위를 가진다.)

각 큐는 낮은 우선순위의 큐보다 잘대적인 우선순위를 가진다. 예를 들어, real-time processes, system processes, interactive processes를 위한 큐들이 모두 비어 있지 않으면 batch processes를 위한 큐는 실행될 수 없다.
또한 batch processes가 실행되고 있는데 interactive process가 ready queue 상태에 들어가면 batch processes는 preempted 된다.

5.3.6 Multilevel Feedback Queue Scheduling (MFQS)

multilevel queue scheduling에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 이러한 방식은 scheduling overhead에 대한 장점이 있으나 융통성이 적다.

대조적으로 MFQS 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다. CPU burst에 따라 프로세스를 구분하여, 프로세스가 CPU를 너무 많이 사용하면 우선순위가 낮은 큐로 옮긴다. 또한 낮은 우선순위의 큐에서는 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동하여 starvation 상태를 예방한다.

위의 그림에서처럼 프로세스가 첫번째 큐에 들어갔을 때, time quantum 8 내에 못 끝내면 두번째 큐의 끝에 넣어주고, 거기서도 time quantum 16 내에 못 끝내면 마지막 FCFS 큐에 넣어준다. starvation 상태 방지를 위해 너무 오랫동안 FCFS 큐에서 기다리면 위로 올려준다.

MFQS 알고리즘은 가장 일반적인 CPU scheduling 알고리즘이다. 설계에 따라 특정 목적을 만족하게 해줄 수도 있다. 하지만 모든 매개변수의 값을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘이기도 하다.

5.4 Thread Scheduling

thread는 user-level thread와 kernel-level thread로 나뉜다. 대부분 최신 OS에서는 스케줄 되는 대상은 프로세스가 아니라 kernel-level thread이다. user-level thread는 thread library에 의해 관리되고, 커널은 그들의 존재를 모른다. CPU 상에서 실행되기 위해서 user-level thread는 연관된 kernel-level thread에 mapping 되어야 한다.

5.4.1 Contention Scope

user-level thread와 kernel-level thread의 차이점은 스케줄링 방식이다. 다대일이나 다대다의 경우 thread library가 user-level thread를 LWP(light-weight process, 매개체 역할)에 대해 스케줄링하고, 동일한 프로세스에 속한 thread들 사이에서 CPU를 경쟁하기 때문에 process-contention scope(PCS)로 알려져 있다.

같은 프로세스의 thread 간에 CPU 점유를 위해 경쟁하니까 thread library가 user-level thread를 LWP에 스케줄링한다는 것은 thread가 실제 CPU에서 실행 중이라는 것과는 다르다. 실제로 CPU 상에서 실행되기 위해서는 OS가 LWP의 kernel-level thread를 물리적인 CPU 코어로 스케줄링해야 한다. CPU 상에서 어느 kernel-level thread를 스케줄링할 것인지 결정하기 위해 커널은 system-contention scope(SCS)를 사용한다.

보통 PCS는 우선순위에 따라 처리되고, thread간 고르게 시간 분배를 한다는 보장은 없다.

5.4.2 Pthread Scheduling

Pthread는 다음과 같이 contention scope 값을 구분한다.

• PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하여 thread를 스케줄링
• PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용하여 thread를 스케줄링

Pthread IPC는 contention scope의 정보를 얻어내고 지정하기 위해서 다음의 두 함수를 제공한다.

• pthread_attr_setscope(pthread_attr_t *attr, int scope)
• pthread_attr_getscope(pthread_attr_t attr, int scope);

위의 코드는 Pthread 스케줄링 API를 설명한다. 이 프로그램은 기존의 contention scope를 결정하고, 그 값을 PTHREAD_SCOPE_PROCESS 값으로 지정한다. 그런 후에 SCS 스케줄링 정책을 이용하여 실행될 5개의 thread를 생성한다.

5.5 Multiple-Processor Scheduling

여러 개의 CPU가 사용 가능하다면, 여러 thread가 병렬로 실행될 수 있으므로 load sharing이 가능해진다.

5.5.1 Approaches to Multiple-Processor Scheduling

asymmetric scheduling이란 스케줄링 결정, 입출력 처리 등 모든 체제 활동을 하나의 프로세서, 즉 마스터 서버가 처리하게 하고, 다른 프로세서는 사용자 코드만 실행하는 것이다. 이 경우 한 코어만 시스템 자료 구조에 접근하니까 자료 공유의 필요성도 줄어들어 단순해진다. 단점이라면 마스터 서버가 병목점이 되어 전체 성능이 낮아질 수도 있다.

일반적으로 Multiple-processor를 처리하는 법은 symmetric multiprocessing(SMP) 이다. 각 프로세서는 자기 스스로 스케줄링하고, 각 scheduler가 ready queue를 확인하고 실행할 스레드를 선택한다. 이 경우 스레드 스케줄링을 하기 위해 구조화할 때 두 가지 전략이 나온다.

• 모든 thread가 common ready queue에 있을 수 있다.
• 각 프로세서는 자신만의 thread queue를 가질 수 있다.

첫 번째 전략의 경우 common ready queue에 대한 contention 조건이 설정되므로 두 프로세서가 동일한 스레드를 스케줄링하지 않도록, 그리고 thread가 큐에서 사라지지 않도록 확인해야 한다.

두 번째 전략이 SMP에선 가장 일반적이다. 프로세서 당 개인 실행 큐를 갖는게 캐시 메모리 활용에 있어 더 효율적이라고 한다.

5.5.2 Multicore Processors

보통 SMP 체제는 여러 개의 물리적인 프로세서를 바탕으로 프로세스를 병렬 처리했었다. 하지만 최근 현대적인 컴퓨터 하드웨어는 다중 연산 코어를 하나의 칩에 넣고 multicore processor 구조가 된다. 각 코어는 구조를 갖는 상태를 가지므로 OS 입장에선 마치 분리된 논리 CPU로 인식된다. Multicore Processor를 사용하는 SMP 체제가 사실 CPU 마다 물리적인 칩을 갖는 경우보다 더 빠르고 적은 전력을 소모한다.

Multicore Processor는 스케줄링 문제를 복잡하게 만든다. 예를 들어 프로세서가 메모리에 접근을 할 때, 해당 메모리의 자료를 사용할 수 있을 때까지 많은 시간을 허비한다는 것을 발견했고, 이럴 때 memory stall이 발생한다. 이 상황은 최신 프로세서가 메모리보다 훨씬 빨라서 발생한다. 이뿐만 아니라 캐시 미스(캐시 메모리에 없는 자료에 접근) 때문에 발생하기도 한다. 위의 그림이 memory stall을 나타낸 것이고, 이 경우 프로세서는 자료 사용할 수 있을 때까지 대기하는데 자기 시간의 50%를 사용한다고 한다.

이 상황을 처리하기 위해 현대적인 하드웨어 설계는 두 개 이상의 hardware thread가 각 코어에 할당되는 multithreaded processing cores를 구현한다. 그래서 한 hardware thread가 메모리 대기하느라 지연되면 코어는 다른 thread로 교환할 수 있게 된다. 위의 그림이 dual-threaded processing core이다.

OS 입장에서는 각 hardware thread가 각자 구조적 상태(명령어 포인터, 레지스터 집합 등)를 유지하므로 마치 소프트웨어 스레드를 돌릴 수 있는 논리 CPU로 보인다. 이 기술을 chip multithreading(CMT)이라 부른다. 위의 그림의 경우 프로세서가 네 개의 연산 코어를 갖고, 각 코어마다 두 개의 하드웨어 스레드를 가지므로, OS 입장에서는 논리 CPU가 여덟 개인 것이다.

일반적으로 프로세싱 코어를 멀티스레딩하는 방법은 두 가지이다.

• coarse-grained multithreading
• fine-grained multithreading

coarse-grained multithreading의 경우 메모리 지연과 같이 지연 속도가 긴 이벤트 발생 전까지 스레드가 코어에서 실행된다. 이때 지연이 길기 때문에 코어는 반드시 다른 스레드로 교환해야 한다. 하지만 스레드 간 교환 시 기존 스레드가 사용하던 명령어 파이프라인을 깨끗이 비워야 새 스레드가 사용할 수 있으므로 교환 비용이 높다.
fine-grained multithreading은 더 미세한 수준으로 교환이 이루어지며, 보통 명령어의 경계에서 일어난다. fined-grained 체제에서의 구조적 설계에는 스레드 교환에 대한 로직도 포함하므로 스레드 간 교환 비용이 적다.

5.5.3 Load Balancing

SMP 체제에서는 load balancing을 통해 프로세스 간 작업을 고르게 분산해서 multi-processor의 이득을 최대한 활용해야 하며, 특히 프로세서가 각자 개인 ready queue가 있는 체제에서 필요하다.

일반적으로 두 가지 방법이 있다.

• push migration
• pull migration

push migration의 경우 특정 작업이 현재 각 프로세서의 load를 확인하고, 불균형하다 싶으면 스레드 간 load를 덜 바쁘거나 놀고 있는 프로세서로 옮겨준다(밀어줌). pull migration의 경우 놀고 있는 프로세서가 바쁜 프로세서에서 대기 중인 작업을 갖고 오는 것이다.

5.5.4 Processor Affinity

스레드가 프로세서에서 실행될 때 스레드에서 자주 접한 자료가 프로세서의 캐시에 들어가있을 것이다. 어차피 자주 계속 들락날락할 자료라서 계속해서 캐시 메모리에서 해당 자료 찾을 수 있다("따뜻한 캐시"라고 부름). 근데 스레드가 load balancing 등의 이유로 다른 프로세서로 간다면 새로운 프로세서의 캐시 메모리 내용이 당연히 달라서 다시 스레드가 사용할 내용으로 채워야할 것이다. 기존 캐시 무효화하고 새 캐시로 채우는 과정이 비싼 연산이라 SMP 지원하는 대부분의 운영체제들은 스레드를 프로세서 간 이동시키는 걸 좀 피하고, 최대한 따뜻한 캐시를 유지하려한다. 이것을 processor affinity 라고 한다.

5.6 Real-time CPU Scheduling

real-time OS에서 CPU를 스케줄링할 때는 sort real-time system과 hard real-time system으로 구분한다.
soft real-time system의 경우 중요한 실시간 프로세스가 언제 처리될지는 모른다. 오직 중요 프로세스가 그렇지 않은 프로세스에 비해 우선권을 가진다는 것만 보장한다.
hard real-time system은 더 엄격한 요구 조건을 만족시켜야 한다. 마감시간까지 서비스를 받아야하며, 마감시간이 지난 이후에는 서비스 유통기한이 지났다고 간주해서 서비스가 없는 걸로 간주한다.

5.6.1 Minimizing Latency

실시간 체제가 이벤트 기반임을 우선 알아야 한다. 보통 이벤트가 발생할 때까지 대기하는데, 이벤트란 타이머 종료와 같은 소프트웨어 이벤트랑 센서처럼 하드웨어 이벤트 등이 있다. 이벤트가 발생하면 최대한 빠르게 대응해야 하는데, 이때 이벤트 발생 시간부터 그에 맞는 서비스가 수행된 시간까지를 이벤트 지연 속도 event latency라 한다.

이벤트마다 latency도 다른데, 다음의 두 가지 유형의 latency가 시스템의 성능을 좌우한다.

• interrupt latency
• dispatch latency

interrupt latency란 interrupt가 CPU에 도착하는 시점부터 이에 대응하는 서비스가 시작할 때까지를 의미한다. interrupt가 발생하면 OS는 일단 자기가 실행 중이던 명령어를 끝내고 나서 무슨 interrupt인지 확인한다. 현재 프로세스의 상태 저장하고 특정 인터럽트 서비스 루틴(ISR)에 따라 서비스를 한다. 이때 걸린 총 시간이 interrupt latency가 된다.

dispatch latency란 스케줄링 dispatcher가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간을 말한다. CPU에 즉시 접근해야하는 작업이 있다면 이 지연 시간을 최소화 해야한다. 가장 효과적인 방법은 preemptive kernel을 제공하는 것이다.

5.6.2 Priority-Based Scheduling

실시간 OS에서 가장 중요한 긴ㅇ은 실시간 프로세스에 CPU가 필요할 때 바로 응답을 해주는 것이다. 따라서 실시간 운영체제의 스케줄러는 preemptive를 이용한 우선순위 기반의 알고리즘을 지원해야만 한다.
priority-based scheduling은 각각의 프로세스의 중요성에 따라 그 우선순위를 부여한다. 또한 스케줄러가 preeptive 기법을 제공한다면, 현재 CPU를 이용하고 있는 프로세스가 더 높은 우선순위를 갖는 프로세스에 preepmted 될 수 있다.

5.6.3 Rate-Monotonic Scheduling

rate-monotonic scheduling 알고리즘이란 정적 우선순위 정책을 통해 주기적 작업을 선점적으로 스케줄링하는 것이다. 주기적 작업은 시스템에 들어온 순간 자기 주기의 역수를 우선순위로 가진다. 즉, 주기가 짧을수록 우선순위가 높고 길수록 우선순위가 낮다. 이 정책은 CPU를 자주 쓰는 task에게 우선순위를 계속 주겠다는 논리를 포함한다. 게다가 주기적 프로세스의 처리 시간이 각 CPU 버스트마다 동일하다고 가정한다. 즉, 프로세스가 CPU를 차지한 시간은 각각의 CPU burst 시간과 동일하다는 것이다.

5.6.4 Earliest-Deadline-First Scheduling

earliest-deadline-first(EDF) scheduling은 마감 기한에 따라 동적으로 우선순위 부여한다. 마감 기한이 빠른 순으로 우선순위 부여하는 것이다. 프로세스가 실행 가능할 때 반드시 시스템에 자기 마감 기한 소요를 알려서 우선순위 갱신해야 한다. 비율 단조처럼 정적 우선순위가 아니다.

5.6.5 Proportionate Share Scheduling

proportional share scheduling 알고리즘은 모든 어플리케이션에 T만큼의 지분을 할당해준다. 어플리케이션은 N개의 시간 지분을 받을 수 있어 모든 어플리케이션이 총 프로세서 시간의 N/T를 가진다.
예를 들어 총 T = 100의 지분이 있고, 이걸 A, B, C에 각각 지분을 50, 15, 20으로 준다고 가정하자. proportional share scheduling는 승인 제어 정책과 같이 협력해서 어플리케이션이 자기 지분만큼의 시간을 받도록 보장해야 한다. 물론 충분한 지분이 남아있어야 클라이언트의 요청을 받아줄 수 있다. 이 예시의 경우 50 + 15 + 20 = 85 지분이니 여유가 있고, 만약 새 프로세스 D가 지분 30 요청하면 승인 제어가 D의 시스템 진입을 거부할 것이다.