리눅스 스케줄러(Linux Scheduler)

O(1) scheduler

리눅스 2.6에서 사용된 스케줄러이며 현재 리눅스 CFS(Completely Fair Scheduler) 이전까지의 스케줄러 방식이다.

리눅스에서 버전 2.4까지는 Single Queue(이하 SQ) 방식이었는데 이는 처리기가 유휴 상태일 때 순차적으로 처리하는 방식이다. SQ 방식은 구현이 간단하고 로드가 분산되는 장점이 있다(?). 그러나 Affinity가 좋지 않아 Cache 성능 저하 및 Race Condition 문제 등이 발생할 수 있다.

따라서 O(1) 스케줄러에서는 Multi Queue(이하 MQ)로 진화하였으며 각각의 큐는 우선순위 레벨에 따른 연결 리스트를 지닌다.

O(1) 스케줄러는 각 우선순위에 해당하는 큐의 유무를 binary로 식별하기 위해 Bitmap을 이용한다. 가령 Max Priority가 140일 때 unsinged long 타입의 bitmap은 5개가 필요하다 (5 * 32)

O(1) scheduler Algorithm

O(1) 스케줄러가 동작하는 알고리즘을 살펴보자.

O(1) 스케줄러의 큐는 두개의 타입이 존재하는데 Active Queue와 Expired Queue가 존재한다. Active에는 실행 가능한 Task가 Expired에는 time slice를 모두 소진한 Task가 포함되며 Active Queue가 빈 상태가 되었을 때 Active Queue와 Expired Queue를 스왑하여 진행한다. 우선순위가 낮은 Task들의 Starvation을 막기 위해서이다.

O(1) 스케줄러의 O(1)은 무슨 의미일까? 익히 알듯이 O(1)은 Worst Time Complexity를 의미하며 최악의 수행 시간에 대하여 상수 시간 내에 수행이 가능하다는 의미이다. 즉 O(1) 스케줄러는 우선 순위 큐에서 다음 Task를 스케줄링할 때 O(1) 내로 수행이 가능하다 (삽입, 삭제 연산이 O(1) 내로 수행 가능함)

Proportional Share Scheduling을 살펴보기에 앞서 Linux 스케줄링의 역사적인 배경을 간략히 살펴보자. Linux 초창기에는 UNIX의 전통적인 스케줄링 기법을 활용하여 스케줄링 알고리즘을 사용하고 있었는데 2000년대 초반에 다양한 멀티 프로세서의 등장과 단일 시스템 내에 어플리케이션이 증가하는 등의 확장성 문제가 발생하였고 이를 해결하기 위해 O(1) 스케줄러가 사용되었다.

2000년대 중반에 들어서면서 안드로이드 모바일 기기, SNS 등이 도입되면서 멀티 미디어에 대한 요구 사항에 대한 문제가 대두되기 시작하였고 이는 곧 사용자가 서비스 품질에 관심을 가지기 시작했다는 것을 의미한다. (ex. 미디어에서 초당 30 Frame 이상의 Frame Rate 보장 등) 이러한 CPU 대역폭(CPU bandwidth)를 보장하기 위해 나온 스케줄링 기법이 Proportional Share Scheduling이다.

Proportinal Share Scheduling의 경우 최근에는 Virtual Machine Monitor(이하 VMM) 등에 활용되고 있다. VMM은 크게 두 가지의 타입이 존재하는데 Type2는 우리가 널리 알고 있는 Virtual Box가 이에 해당하는데 하드웨어 위에 Host OS가 존재하며 그 위에 VMM이 존재하는 형태이고 Type1은 하드웨어 위에 바로 VMM이 존재하는 형태이다. 이러한 물리적인 하드웨어 자원을 가상적으로 CPU에 적절히 분배하는 것이 Proportional Share Scheduling의 핵심 의의이다. 이를 통해 Amazon과 같은 가상 CPU 자원에 대하여 weight 구해 적절히 유저에게 과금하는 등에 사용될 수 있다.

Optimization Criteria

Proportional Share Scheduling 알고리즘의 최적화 기준은 얼마나 Fairness를 정확하게 보장하느냐 이다. 이를 정량적으로 측정하기 위해 Service Time Error에 대한 지표를 활용 가능하다. 다음은 Service Time Error에 대한 몇 가지 측정 지표이다.

$W_{i}(t_{1},t_{2})$ : $t_{1}$ 과 $t_{2}$ 사이에 실제로 할당된 시간의 양
$S_{i}(t_{1},t_{2})$ : $t_{1}$ 과 $t_{2}$ 사이에 할당되어야 하는 시간의 양
$E_{i}(t_{1},t_{2})$ : $t_{i}$ 에 대하여 시간 오차

따라서 $t_{1}$ 과 $t_{2}$ 사이에 $t_{i}$ 의 오차는 다음과 같다. $E_{i}(t_{1},t_{2}) = W_{i}(t_{1},t_{2}) - S_{i}(t_{1},t_{2})$ 또한 스케줄링 알고리즘을 수행하는데에 걸리는 시간, 즉 스케줄링의 오버헤드도 최적화 기준 중 하나다.

WFQ(Weighted Fair Queueing) Example

WFQ는 이름에서 볼 수 있듯이 가중치(Weight)와 공정성(Fair)이 주요 개념이다. 가령 WFQ는 네트워크의 트래픽 관리에서 주로 사용되는데 각 트래픽의 흐름이 특정한 가중치를 받고 가중치에 따라 자원을 분배받으며 모든 트래픽의 흐름이 공정하게 처리될 수 있도록 보장하는 것이다.

WFQ에는 가상의 시간 개념인 virtual time(이하 VT)을 사용하는데, VT는 수행시간의 누적 값과 가중치를 정규화한 값에 기반하여 계산된다. $VT_{i}(t) = \frac{w_{i}(t)}{\phi_{i}}$ 이해가 어려우니 예제로 살펴보자. 각각 A부터 D까지의 큐가 존재할 때 가중치가 다음과 같이 비례한다고 가정한다.

A : B : C : D = 4 : 3 : 2 : 1 이때 실행전 즉 수행 시간이 0일 때 $W_{i}(0)$ 는 A,B,C,D 수행시간이 없기 때문에 모두 0으로 동일하다. 따라서 $VT_{i}(0)$ 또한 모두 0이 된다. 여기서 Virtual Finish Time(이하 VFT)라는 개념이 등장하는데 이는 가상 완료 시간으로 처리를 완료할 것으로 예상되는 시간이다. VFT는 VT에 weight를 정규화한 값의 역수를 더해준 값과 같다. $VFT_{i}(t) = \frac{w_{i}(t) + 1}{\phi_{i}}$ 따라서 비례 관계에 따라 A,B,C,D의 VFT는 각각 1/4, 1/3, 1/2, 1이 된다. 따라서 가상 완료시간이 가장 짧은 A부터 D순으로 수행된다.

최종적으로 스케줄링의 순서를 결정할 때 VFT가 짧은 순으로 실행되며 VFT만큼 실행되었을 때 값이 누적되어 VFT가 증가하게 된다. (ex. A의 경우 1/4만큼 실행되어 VFT가 이후 1/2로 증가) 이처럼 VFT만큼 실행되어 값을 누적하고 누적되어 증가된 VFT를 비교해 가장 VFT가 적은 순으로 스케줄링 할 수 있다.

Completely Fair Sheduler(CFS)

CFS는 앞서 살펴본 WFQ와 유사한 Proportional Share Scheduling 기법이다. WFQ와 유사하게 virtual runtime이라는 필드를 사용하며 virtual runtime이 가장 짧은 Task를 선택한다.

일반적으로 Time Complexity는 완전 탐색을 가정할 때 O(n) 만큼 수행되며 이를 개선하기 위해 Binary Search Tree, Heap 등의 자료구조 등을 활용할 수 있다. 그러나 이러한 경우 노드들의 workload에 따라 편향될 수 있으며 이러한 편향을 줄이기 위해 Balanced Binary Tree를 이용할 수 있다. 대표적인 예로 Red-Black Tree 가 있으며 리눅스에서도 실제로 Red-Black Tree를 사용한다.

Heterogeneous Multiprocessing (HMP)

HMP의 경우 Heterogenous(이질적인) 라는 어원에 맞게 다중 처리기이긴 하나 각 처리기 간의 이질성을 가진다. 가령 처리리 간 클럭 속도나 전력 소모 등이 차이를 보인다.

HMP는 AMP(Asymmetric MultiProcessing)과는 차이를 보이는데 AMP의 경우, 커널이 master process에서만 작동하고 유저의 경우 slave process에서만 작동하게 되어있는 역할 분담 구조이다.

HMP는 주로 모바일 컴퓨팅에서 많이 사용되곤 하는데 모바일 컴퓨팅은 전력 소모를 가장 주된 목표로 삼으며 대표적으로 ARM사의 big.LITTLE 솔루션이 있다. 성능 요구가 높은 big cores와 에너지 효율적인 little cores가 존재하며 이 두 타입의 코어를 적절히 결합하여 에너지를 효율적으로 관리하는 것이다.

big cores : power가 많이 필요하고 비교적 짧은 시간에 수행되는 작업
little cores : 높은 성능을 요구하지 않으며 비교적 긴 시간동안 수행되는 작업

Real-Time Scheduling

실시간 시스템(Real-Time System)은 실시간으로 발생하는 작업을 기다리고 이를 주어진 시간 내에 실시간으로 처리하도록 작동한다. (ex.주기적인 타이머에 의한 작업, 비주기적으로 발생하는 차량 장애)

따라서 실시간 시스템은 가능한 빨리 응답하는 것이 중요한데 이때 event latency라는 개념이 쓰인다. $Event\ latency = Interrupt\ latency + Dispatch\ latency$

위와 같이 event latency는 인터럽트에 의한 지연 시간과 작업이 대기 하다가 실행되기 까지의 지연시간을 합친 값을 의미한다. 이를 낮추기 위해서 preemtive kernel을 제공하는 것이 가장 효율적인 방법이다. 그래야 실시간 작업에 대해서 우선적인 처리가 가능하기 때문이다.

그렇다면 Real-Time Scheduling에서 가장 중요한 평가 기준은 뭘까? 아쉽게도 latency를 최소화하는 것이 핵심적인 목표는 아니다. 작업이 적절한 시간에 실행되고 완료되도록 보장하는 것(적재적소) 이 가장 핵심적인 평가 요소이다. 이러한 시간적인 기준이 얼마나 잘 보장되는지에 따라 두 가지 시스템으로 나뉜다. ^73d1c0

Soft real-time systems : deadline을 때때로 지키지 못할 수 있으며 이때 시스템에 치명적이지는 않음. 그러나 어느정도 성능 저하가 발생함 (ex. 비디오 스트리밍)
Hard-real-time systems : 반드시 deadline까지 서비스(시작 혹은 완료)되어야 하고 이러한 것이 시스템에 치명적인 문제를 야기할 수 있음 (ex. 항공 교통 제어)

Real-Time Task Terminologies

실시간 작업에서 쓰이는 몇 가지 용어를 살펴보자. 먼저 주기적 관점에서 두 가지 작업이 존재한다.

Periodic task (주기 작업) : 주기적으로 고정된 시간에 의해 수행되는 작업
Aperiodic task (비주기 작업) : 도착 시간이 정해지지 않은 작업

마감시간에서도 다음과 같이 두 가지 마감시간이 존재한다.

Starting deadline : 작업이 시작되어야 하는 시간
Completion deadline : 작업이 종료되어야 하는 시간

Priority-Based Scheduling

앞서 Real-Time 시스템에서는 응답 시간이 중요하여 선점 방식을 채택해야 한다고 얘기했다. 따라서 반드시 우선순위에 기반한 선점 방식 스케줄링, Priority-Based Scheduling을 사용해야 한다.

가장 기본적인 형태를 보았을 때 (OS마다 조금씩 차이가 있음) ready queue를 여러 개 두어 가장 우선 순위가 높은 큐에서 스케줄러가 작업을 시작한다. 이 경우 선점 방식을 통해 우선 실행은 보장해주지만 마감 시간은 보장해주지는 않기 때문에 Soft real-time에 해당한다.

Earliest-Deadline-First (EDF)

EDF는 real-time scheduling의 가장 대표적인 기법으로써 이름처럼 마감 시간이 가장 빠른 프로세스를 우선하여 스케줄링하는 방식이다. 먼저 아래와 같이 주기적인 Task에 대하여 프로세스 A,B가 존재하며 각 프로세스 내에 Task별로 도착 시간, 실행 시간, 마감 시간이 지정되어 있다고 가정하자.

먼저 고정된 우선순위 기반의 스케줄링을 살펴보자. A 프로세스에 우선순위가 있다고 가정할 때 A 프로세스가 우선적으로 실행되고 완료된 뒤 B프로세스를 실행하다가 이후에 또다른 A 프로세스의 작업이 들어왔을 때 B 프로세스가 blcok되는 것을 알 수 있다. 이 경우 B1의 마감시간이 50ms 인데 우선순위에 의해 밀리다가 50ms 시점에서 작업을 완료하지 못한 체 missed되는 것을 확인할 수 있다.

B프로세스가 우선권을 가질 때에도 마찬가지이다. 비교적 실행 시간이 긴 B 프로세스의 작업이 끝날 때 까지 대기하다가 A1과 A4는 실행되지 못하고 missed되었다.

마지막으로 EDF의 경우를 살펴보자. 각각의 Task들은 위에 표에 나온 것처럼 Ending Deadline을 가지며 이 Deadline을 기점으로 우선순위가 부여된다. B1이 실행되는 동안 A3이 도착했을 때 A프로세스 우선 스케줄링의 경우 B1이 밀리고 missed되었지만 여기서는 B1의 deadline이 50ms로 60ms보다 빠르기 때문에 계속 실행되는 것을 볼 수 있다. 따라서 위 고정 우선순위 스케줄링 방식에 비해 missed되는 task가 훨씬 적다.

이번에는 비주기적인 Task에 대하여 프로세스 A,B가 존재하며, 종료 마감시간이 아닌 시작 마감시간이 주어진다고 가정해보자. 아래 표를 보면 각 프로세스 별로 도착 시간, 실행 시간, 시작 마감시간이 지정되어 있다.

starting deadline의 경우 종종 비선점 방식으로 스케줄링할 수 있다. 따라서 비선점 방식으로 EDF 스케줄링에 대한 예제를 살펴보자. A 프로세스를 수행하는 동안 B가 arrive했음에도 비선점 방식이기 때문에 B는 starting deadline을 맞추지 못해 missed 되었다.

다음은 스케줄러가 Arrival Time에 대한 정보를 사전에 알고 있는 스케줄링 방식이다. 따라서 A는 가장 먼저 도착함에도 시작 마감시간이 110ms이고 다음에 도착하는 B의 시작 마감시간은 20ms(도착시간과 동일)이므로 강제로 유휴시간을 가진 뒤 B를 수행하는 모습을 보인다.

마지막으로 시작 마감시간을 고려하지 않고 FIFO 스케줄링을 했을 때의 예시이다. 상당 수의 프로세스가 missed됨을 알 수 있다.

Rate Monotonic Scheduling (RMS)

EDF와 더불어 실시간 시스템에 대한 스케줄링에 많이 활용되는 기법이다. RMS의 우선순위는 실행주기에 역으로 결정된다.

$Period(A_{p}) : 20ms$ 일 때, $Rate(A_{p}) : 50Hz(\frac{1}{0.02})$
$Period(B_{p}) : 50ms$ 일 때, $Rate(B_{p}) : 20Hz(\frac{1}{0.05})$

즉, RMS의 경우 실행주기가 짧을 수록 높은 우선순위, 길수록 낮은 우선순위를 가진다. 하단 그래프에서 볼 수 있듯이 작업의 Rate와 비례하여 우선순위가 Monotonically하게 증가하기 때문에 Rate Monotonic Scheduling이라고 불린다.

EDF는 마감시간을 기준으로 Dynamical하게 우선순위가 정해진 반면, RMS의 경우 주기가 변하지 않는 이상 static하게 우선순위를 결정하게 된다. 즉, 주기성이 있는 Periodic Task를 처리할 때 RMS를 사용하게 된다.

RMS Notation

RMS의 주요 용어에 대해 살펴보자.

$C$ : 실행 시간 ( $C<=T$ )
$T$ : 실행 주기
$U$ : 프로세스 이용률 ( $C/T$ ) 예를 들어, 주기가 40ms이고 실행 시간이 10ms인 process가 존재할 때 이 프로세스의 $U$ (Process Utilization)값은 25%( $10ms/40ms$ )인 것이다.

또한 n개의 Task가 존재할 때 n개의 Task에 대한 이용률의 총합은 1을 넘어서는 안된다. $\frac{C_{1}}{T_{1}} + \frac{C_{2}}{T_{2}} + \frac{C_{3}}{T_{3}} + ... +\frac{C_{n}}{T_{n}} \leq 1$ 그러나 몇몇 알고리즘에 따라 범위의 상한선이 낮아질 수 있는데 RMS의 경우 아래와 같은 조건을 만족해야 하며 이때 마감시간을 기준으로 한 스케줄링이 성공적임을 알 수 있다. (n이 무한히 커졌을 때 약 0.693에 수렴한다.) $\frac{C_{1}}{T_{1}} + \frac{C_{2}}{T_{2}} + \frac{C_{3}}{T_{3}} + ... +\frac{C_{n}}{T_{n}} \leq n(2^{\frac{1}{n}}-1)$

RMS Example

예시로 세 가지의 주기 Task가 존재한다고 가정하자. 각 Task의 실행 시간, 실행 주기, 이용률은 다음과 같다.

	C	T	U
P1	20	100	0.2
P2	40	150	0.267
P3	100	350	0.286

모든 Task의 utilization의 합은 0.2 + 0.267 + 0.286 = 0.753으로 스케줄링이 가능한 것을 확인할 수 있다. RMS의 bound를 기준으로 했을 때 0.779보다 작음으로 스케줄링이 가능한 기준에 만족하는 것을 확인할 수 있다.
$\frac{C_{1}}{T_{1}} + \frac{C_{2}}{T_{2}} + \frac{C_{3}}{T_{3}} + ... +\frac{C_{n}}{T_{n}} \leq n(2^{\frac{1}{3}}-1) = 0.779$

EDF vs RMS

그렇다면 실시간 시스템에서 활용되는 스케줄링 기법인 EDF와 RMS는 어떤 차이점을 보일까? 각 스케줄링 기법의 특징을 살펴보자.

먼저 EDF의 경우 실행 가능할 때 (Runnable) 마감시간이 주어지며, 마감시간이 가장 가까운(earliest) 작업을 우선순위로 수행하는 스케줄링 기법이다. EDF의 가장 큰 장점은 이론적으로 Optimal 하다는 것이다. (실제 상황에서는 context switching, interrupt handling 등으로 인해 가장 최적의 utilization을 달성하는데에는 한계가 있음으로 이론적인 Optimal이다.)

그러므로 다른 스케줄링에 비해 전반적인 process utilization을 향상 시킬 수 있고 이는 곧, 실시간으로 수행할 수 있는 작업의 수를 더 늘릴 수 있음을 의미한다.

그럼에도 불구하고 RMS가 실시간 OS 및 현실적인 상황에서 더 많이 사용되고 있다. 그 이유가 몇 가지 존재하는데 다음과 같다.

앞서 살펴보았듯이 RMS의 수행 조건에 대한 상한선이 보편적인 상한선(1)보다 더 보수적으로 계산된다.
대부분의 hard real-time system은 soft real-time component들과 결합되어 사용되는데 hard real-time system이 유휴상태일 때 soft real-time component를 활용할 수 있다.
우선순위를 변경하기 위해 RMS는 실행 주기만을 변경하면 되는데, EDF는 매 주기마다 마감시간을 변경해야 함으로 우선순위를 변경하는 것이 복잡하다.