Real-Time CPU Scheduling

Real-time system은 task 처리에 걸리는 시간을 일관되게 유지할 수 있냐가 중요한 성능의 척도이다. Real-time system의 목표는 실시간 성능 보장에 있다.

* Soft real-time systems: task 처리 시간이 달라지면 성능이 감소하는 경우 (streaming video 등)

* Hard real-time systems: task 처리 시간이 달라지면 실패하는 경우 (자동차의 air-bag 등)

1. Minimizing Latency

Real-time system은 사건-중심의 특성을 가지고 있어서, 일이 발생하면 빠르게 처리되어야 한다. 따라서 Latency를 최소화 해야한다.

Event Latency는 event가 발생하고 system이 응답하기까지의 시간이다. 아래 그림 1과 같다.

[그림 1] Event Latency

event를 실제로 처리하는 시간 외에도, event handler(Interrupt Service Routine, ISR)가 시작하기 전에 추가적으로 처리해야할 두가지 단계가 더 있다.

* determine interrupt type: Interrupt processing는 어떤 interrupt가 발생할 지, 어떤 interrupt handler routine이 실행될 지 결정한다. 동시에 interrupt가 발생하는 경우, 어떤 ISR이 가장 높은 우선 순위를 가지며 다음에 시작할 지 결정하기 위해 우선 순위 정책이 필요하다.

* context switch: context switching은 CPU로부터 실행중인 process를 제거하고, 그 process의 상태를 저장하고, ISR이 실행될 수 있도록 적재한다.

Interrupt Latency는 이 두 단계로 소모 되는(CPU에 interrupt가 도착해서 service 될 때까지의) 시간이며, 아래 그림 2와 같다.

[그림 2] Interrupt Latency

Dispatch Latency는 실행중인 process를 제거하고, ISR에 필요한 리소스를 확보하고, ISR을 CPU에 적재할 때까지의 시간이다. (context switch) 이 과정은 아래 그림 3과 같다.

[그림 3] Dispatch Latency

2. Priority-Based Scheduling

Real-time 시스템은 선점형이고 우선순위 기반의 scheduling이 필요하다.

Soft real-time 시스템은 위에서 설명했듯이 최선을 다하지만 보장하지는 않는다. Hard real-time 시스템은 task들이 scheduling이 충분히 되도록 반드시 보장해야 한다. 이를 위해 admission-control algorithm을 사용하며, 주기 안에 돌아갈 수 있는 process만 받는다. 또한, 일정 시간 내에 무조건 실행돼야 하는 것들을 위해 process 개수를 제한한다.

Hard real-time 시스템의 task는 반드시 규칙적인 주기에 따라 실행돼야 한다. 아래 그림 4처럼 주기 p, CPU burst t, deadline d가 있을 때, t <= d <= p 이다.

[그림 4] Periodic Task

3. Rate-Monotonic Scheduling

Rate-Monotonic scheduling algorithm은 정적 우선순위의 선점형 알고리즘이다. 우선순위는 주기에 반비례하여 할당되며, 짧은 주기의 작업이 높은 우선순위를 받게 된다.

예를 들어, 두 개의 process P1, P2가 있는데 주기가 각각 50, 100, CPU burst가 각각 20, 35, deadline은 주기와 같다고 하자. 만약 우선순위가 제대로 지켜지지 않아서 P2가 먼저 실행된다면, P1은 deadline 내에 작업을 끝내지 못할 것이다. (그림 5)

[그림 5] Scheduling of tasks when P2 has a higher priority than P1

반대로, P1이 높은 우선순위를 받으면, P1이 먼저 시작되고 P1이 작업을 마치면 P2가 시작된다. P2는 35 중 30만 작업을 완료하지만 P1의 주기가 돌아와 선점된다. P1이 작업을 마치면 P2가 다시 시작되고, 나머지 작업 5를 마친다. (그림 6)

[그림 6] Rate-Monotonic Scheduling

두 process는 75에 완료되고 다시 반복되기 전 25가 유휴상태가 된다.

이 알고리즘으로 scheduling 할 수 없는 process 집합은 다른 priority scheduler로도 scheduling 할 수 없다. 따라서 정적 우선순위를 사용하는 알고리즘 중에서 Rate-Monotonic Scheduling이 가장 적합한 것으로 여겨진다.

정적 우선순위로 schedule 할 수 없는 process 집합을 살펴보자. 예를 들어, 두 개의 process P1, P2는 주기가 각각 50, 80, CPU burst가 각각 25, 35, deadline은 주기와 같다고 하자. 아래 그림 7처럼 P1이 먼저 실행되어 25에 작업을 완료하고 P2가 시작되어 25만큼 하고 P1에 선점된다. 다시 P1이 75에 작업을 마치고 P2가 시작되어 나머지 작업 10을 하려하지만, P2의 주기인 80을 넘어 deadline을 놓쳤다.

[그림 7] Missing deadlines with rate-monotonic scheduling

4. Earliest-Deadline-First Scheduling

Earliest-Deadline-First(EDF) scheduling은 우선 순위를 동적으로 변경하여 deadline이 가장 빠른 process에게 가장 높은 우선순위를 부여한다. 아래 그림 8은 두 개의 process P1(50 / 25 / 50), P2(80 / 35 / 80)이 있을 때 EDF scheduling을 도시한 것이다.

[그림 8] Earliest-Deadline-First Scheduling

50에서 P1이 들어왔음에도 P2의 deadline이 P1보다 빨라 선점되지 않는 것을 볼 수 있다. Rate-Monotonic scheduling과는 차이가 난다.

Rate-Monotonic scheduling보다 유휴시간이 적지만, ready queue에 process가 들어올 때마다 deadline을 확인해야 해서 overhead가 크다.

5. Proportional Share Scheduling

Proportional Share scheduling은 동일한 share수로 총 시간을 나눈 것을 사용한다. 각 process는 시작할 때 특정 share를 반드시 요청해야 한다. Proportional Share scheduling은 admission-control 정책으로 동작하며, task에 필요한 share를 보장하지 못할 경우, 작업을 시작하지 않는다.

* 참고

CPU scheduling

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html

Real-Time CPU scheduling

http://twinw.tistory.com/87