왜 우선순위를 “누가, 어떻게” 정하는지가 핵심 출제 지점인가

13편에서 태스크를 실행 시간 $C_i$, 주기 $T_i$, 데드라인 $D_i$ 세 값으로 나타내는 법을 배웠습니다. 이제 여러 태스크가 동시에 준비 상태에 있을 때 RTOS 스케줄러가 누구에게 먼저 CPU를 줄지를 결정해야 합니다. 08편에서 배운 범용 운영체제(GPOS)의 CPU 스케줄링(FCFS, SJF, RR 등)은 “평균 대기 시간을 줄이는 것”이 목표였지만, RTOS의 스케줄링은 목표 자체가 다릅니다 — 모든 태스크가 각자의 데드라인을 지키는가를 수학적으로 보장할 수 있어야 합니다. 이 편에서 다루는 RM과 EDF는 그 보장을 미리 계산으로 확인할 수 있게 해 주는 대표적인 두 방식입니다.

쉽게 말하면: GPOS 스케줄링은 “평균적으로 빠르게”를 목표로 하고, RTOS 스케줄링은 “이 태스크 집합이 절대 늦지 않는다”를 미리 증명하는 것을 목표로 합니다.

1. 선점형과 비선점형 — RTOS 관점에서 다시 보기

08편에서 배운 선점(preemption) 개념을 RTOS 관점에서 다시 짚습니다.

• 선점형(preemptive) 스케줄링: 더 급한(우선순위가 높은) 태스크가 도착하면, 지금 실행 중인 태스크를 즉시 중단시키고 CPU를 넘긴다.
• 비선점형(non-preemptive) 스케줄링: 한 번 실행을 시작한 태스크는 스스로 끝내거나 자원 대기 상태에 들어갈 때까지 CPU를 놓지 않는다.

hard real-time을 지원하는 RTOS는 대부분 선점형을 기본으로 씁니다. 비선점형에서는 긴 태스크 하나가 실행 중일 때 아무리 급한 태스크가 도착해도 그 긴 태스크가 끝날 때까지 기다려야 하므로, 데드라인이 촘촘한 hard real-time 요구를 만족시키기 어렵기 때문입니다. 이 편의 RM과 EDF는 모두 선점형을 전제로 계산합니다.

자주 틀리는 점: “선점형이 항상 더 좋다”고 단정하면 안 됩니다. 선점이 자주 일어나면 06편에서 배운 컨텍스트 스위치(문맥 교환)가 잦아져 오버헤드가 커집니다. 다만 hard real-time에서는 이 오버헤드를 감수하고서라도 데드라인 보장을 우선시하기 때문에 선점형을 씁니다.

2. RM (Rate Monotonic Scheduling) — 짧은 주기가 곧 높은 우선순위

RM(Rate Monotonic, 비율 단조)은 태스크의 우선순위를 주기의 역수(rate)에 비례해, 즉 주기가 짧을수록 높은 우선순위로 고정 배정하는 정적 우선순위(static priority) 스케줄링입니다. 한 번 정해진 우선순위는 시스템이 도는 동안 바뀌지 않습니다.

쉽게 말하면: RM은 “자주 반복되는 일일수록 급한 일”이라고 보고, 반복 주기가 짧은 태스크에 항상 높은 우선순위를 고정으로 줍니다.

스케줄 가능성 — 리우-레이랜드(Liu & Layland) 공식

태스크 집합이 RM으로 데드라인을 항상 지킬 수 있는지 확인하려면 먼저 CPU 이용률(utilization) $U$를 구합니다.

• $C_i$: 태스크 $i$의 실행 시간
• $T_i$: 태스크 $i$의 주기
• $n$: 태스크 개수

이 값이 다음 리우-레이랜드 상한(Liu & Layland bound, $U_{lub}$) 이하이면, RM으로 반드시 모든 데드라인을 지킬 수 있음이 수학적으로 보장됩니다(충분조건).

• $n$: 태스크 개수
• $2^{1/n}$: 2의 $1/n$ 제곱

이 공식은 태스크 개수 $n$이 늘어날수록 상한이 점점 줄어들어, $n \to \infty$일 때 $U_{lub} \to \ln 2 \approx 0.693$에 수렴합니다. 즉 RM은 태스크가 많아질수록 “CPU를 69.3퍼센트(약 0.693) 넘게 못 쓰게 하더라도 안전을 보장하기 어려워지는” 보수적인 조건이 됩니다.

자주 틀리는 점: $U \leq U_{lub}$은 충분조건이지 필요조건이 아닙니다. 즉 이 조건을 만족하면 반드시 스케줄 가능하지만, 이 조건을 만족하지 못한다고(즉 $U > U_{lub}$이라고) 해서 반드시 스케줄 불가능한 것은 아닙니다 — 실제로 스케줄 가능한지는 정확한 검사(exact test)나 시뮬레이션으로 다시 확인해야 합니다.

예제 1 — 세탁기 제어 태스크 집합에 RM 적용하기

13편 2절에서 쓴 세 태스크로 다시 계산해 보겠습니다.

먼저 이용률을 계산합니다.

$n = 3$이므로 리우-레이랜드 상한을 계산합니다.

$U = 0.75 \leq U_{lub} \approx 0.7798$이므로, 이 태스크 집합은 RM으로 반드시 스케줄 가능합니다.

간트 표로 검산하기

세 주기의 최소공배수(LCM)인 하이퍼피리어드(hyperperiod) 20ms 동안 실제로 실행되는 순서를 추적해 검산합니다. 우선순위는 $\tau_1 > \tau_2 > \tau_3$(숫자가 클수록 주기가 길어 우선순위가 낮음)입니다.

이 표가 만들어지는 과정을 단계별로 짚어 보겠습니다.

1. [0,1): 시각 0에 세 태스크가 모두 요청됩니다. 최고 우선순위 $\tau_1$이 1ms 실행 후 완료(데드라인 4ms 이내로 성공).
2. [1,3): 다음 순위 $\tau_2$가 2ms 실행 후 완료(데드라인 5ms 이내로 성공).
3. [3,4): 남은 것은 $\tau_3$뿐이라 1ms만큼 실행하다가, 시각 4에 $\tau_1$의 두 번째 요청이 도착해 선점됩니다($\tau_3$은 1ms 남음).
4. [4,5): $\tau_1$의 두 번째 실행. 완료(데드라인 4+4=8ms 이내).
5. [5,7): 시각 5에 $\tau_2$의 두 번째 요청 도착, 2ms 실행 후 완료(데드라인 5+5=10ms 이내).
6. [7,8): $\tau_3$이 남은 1ms를 마저 실행해 시각 8에 완료(데드라인 20ms 이내로 여유 있게 성공).
7. [8,9): 시각 8에 $\tau_1$의 세 번째 요청 도착, 1ms 실행 후 완료.
8. [9,10): 준비 상태인 태스크가 없어 CPU는 유휴(idle) 상태.
9. [10,12): 시각 10에 $\tau_2$의 세 번째 요청 도착, 2ms 실행 후 완료.
10. [12,13): 시각 12에 $\tau_1$의 네 번째 요청 도착, 1ms 실행 후 완료.
11. [13,15): 준비 상태인 태스크가 없어 유휴.
12. [15,16): 시각 15에 $\tau_2$의 네 번째 요청 도착, 실행을 시작하지만 1ms만 진행했을 때 시각 16에 $\tau_1$의 다섯 번째 요청이 도착해 선점됩니다($\tau_2$는 1ms 남음).
13. [16,17): $\tau_1$의 다섯 번째 실행, 완료(데드라인 20ms 이내).
14. [17,18): $\tau_2$가 남은 1ms를 마저 실행해 완료(데드라인 15+5=20ms 이내로 성공).
15. [18,20): 준비 상태인 태스크가 없어 유휴. 시각 20에 하이퍼피리어드가 끝나고 세 태스크가 모두 다시 요청되며 같은 패턴이 반복됩니다.

검산: 유휴 시간은 [9,10), [13,15), [18,20)을 더해 $1+2+2=5$ms이고, 실제 실행에 쓰인 시간은 $20-5=15$ms입니다. 이용률로 환산하면 $15/20 = 0.75$로, 앞서 공식으로 구한 $U=0.75$와 정확히 일치합니다. 또한 모든 태스크의 매 실행이 각자의 데드라인 안에 끝났으므로, 공식으로 예측한 “스케줄 가능”이라는 결론이 시뮬레이션으로도 확인되었습니다.

3. EDF (Earliest Deadline First) — 가장 급한 데드라인이 곧 최고 우선순위

EDF(Earliest Deadline First, 최단 데드라인 우선)는 우선순위를 고정하지 않고, 매 순간 절대 데드라인이 가장 임박한 태스크에게 CPU를 주는 동적 우선순위(dynamic priority) 스케줄링입니다. 어떤 태스크의 우선순위가 절대적으로 높은 것이 아니라, 상황에 따라(데드라인이 얼마나 남았는지에 따라) 계속 바뀝니다.

쉽게 말하면: EDF는 “지금 이 순간 가장 급하게 마감이 다가온 일부터 처리한다”는 원칙입니다.

스케줄 가능성 — RM보다 관대한 조건

암시적 데드라인(주기 태스크의 $D_i = T_i$)을 가진 주기 태스크 집합에서 EDF는 다음 조건이 필요충분조건입니다(RM의 리우-레이랜드 공식은 충분조건이었던 것과 다릅니다).

즉 CPU 이용률이 100퍼센트($U \le 1$)를 넘지 않기만 하면, EDF는 항상 모든 데드라인을 지킬 수 있습니다. 이는 RM의 상한($n=3$일 때 약 0.7798)보다 훨씬 관대한 조건으로, 이론적으로 EDF는 단일 프로세서에서 가장 CPU 활용률이 높은 최적(optimal) 스케줄링 알고리즘임이 증명되어 있습니다.

예제 2 — RM은 실패하지만 EDF는 성공하는 태스크 집합

RM과 EDF의 차이를 극명하게 보여주는 대표적인 예제로, 두 태스크로 이루어진 집합을 계산해 보겠습니다.

$n=2$이므로 RM의 리우-레이랜드 상한을 계산합니다.

$U \approx 0.9714 > U_{lub} \approx 0.8284$이므로, RM의 충분조건은 만족되지 않습니다(이 조건만으로는 스케줄 가능 여부를 단정할 수 없으므로, 실제로 간트 표를 그려 확인해야 합니다).

RM 간트 표 — 실제로 데드라인을 놓친다

RM 우선순위는 주기가 짧은 $\tau_1$이 높습니다. 시각 0부터 추적합니다.

1. [0,2): $\tau_1$, $\tau_2$ 모두 시각 0에 요청. 우선순위가 높은 $\tau_1$이 2ms 실행 후 완료(데드라인 5ms 이내로 성공).
2. [2,5): $\tau_2$가 실행을 시작해 3ms를 진행했을 때(남은 실행 시간 1ms), 시각 5에 $\tau_1$의 두 번째 요청이 도착해 선점됩니다.
3. [5,7): $\tau_1$의 두 번째 실행이 2ms 진행되어 완료(데드라인 5+5=10ms 이내로 성공).
4. [7,8): 그제야 $\tau_2$가 남은 1ms를 마저 실행해 시각 8에 완료됩니다. 그런데 $\tau_2$의 첫 번째 요청은 시각 0에 이루어졌고 데드라인은 $0+7=7$ms였습니다. 실제 완료 시각 8ms는 데드라인 7ms를 1ms 넘긴 것으로, 데드라인 위반(deadline miss)이 발생했습니다.

결과 해석: 앞서 리우-레이랜드 상한 검사에서 “충분조건을 만족하지 못한다”고 나온 결과가, 실제 시뮬레이션에서 데드라인 위반으로 확인되었습니다. RM의 정적 우선순위 규칙 때문에, $\tau_1$의 두 번째 요청이 $\tau_2$의 데드라인보다 먼저 들어와도 무조건 $\tau_1$이 선점해 버려 $\tau_2$가 늦어진 것입니다.

EDF 간트 표 — 같은 태스크 집합이 성공하는 이유

같은 태스크 집합에 EDF를 적용하면, 우선순위가 “누가 더 절대 데드라인이 임박했는가”로 매 순간 다시 계산됩니다.

1. [0,2): 시각 0에 $\tau_1$(데드라인 5), $\tau_2$(데드라인 7)가 모두 요청됩니다. 데드라인이 더 임박한 $\tau_1$이 먼저 실행되어 2ms 만에 완료(데드라인 5 이내로 성공).
2. [2,6): $\tau_2$가 실행을 시작합니다. 시각 5에 $\tau_1$의 두 번째 요청이 도착하지만, 그 데드라인은 $5+5=10$ms입니다. 반면 지금 실행 중인 $\tau_2$의 데드라인은 7ms로 여전히 더 임박하므로, EDF는 $\tau_1$을 선점시키지 않고 $\tau_2$를 계속 실행합니다. $\tau_2$는 4ms를 전부 실행해 시각 6에 완료됩니다(데드라인 7ms 이내로 성공).
3. [6,8): 이제 대기하던 $\tau_1$의 두 번째 요청을 실행합니다. 2ms 실행 후 시각 8에 완료되며, 데드라인 10ms 이내로 성공합니다.

결과 해석: RM에서는 실패했던 같은 태스크 집합이 EDF에서는 모든 데드라인을 지켰습니다. 핵심 차이는 시각 5에서 $\tau_1$이 도착했을 때, RM은 “주기가 짧은 태스크는 무조건 우선”이라는 고정 규칙 때문에 즉시 선점했지만, EDF는 “지금 이 순간 실제로 어느 쪽 데드라인이 더 급한가”를 다시 계산해 $\tau_2$를 계속 실행시켰다는 데 있습니다. 또한 이 태스크 집합의 이용률 $U \approx 0.9714 \leq 1$이므로, EDF의 필요충분조건에 따라 앞으로도 하이퍼피리어드 전체에서 데드라인 위반이 발생하지 않음이 보장됩니다.

자주 틀리는 점: “EDF가 항상 RM보다 우월하다”는 명제 자체는 학술적으로 맞지만(이론적 최적), 실무에서 RM을 여전히 널리 쓰는 이유가 있습니다. RM은 우선순위가 정적이라 구현이 단순하고 우선순위 역전(16편) 같은 문제를 다루는 기존 이론(우선순위 상속 프로토콜 등)이 잘 갖춰져 있는 반면, EDF는 우선순위가 계속 바뀌는 동적 방식이라 스케줄러 구현 오버헤드가 더 크고, 과부하(overload) 상황에서 어떤 태스크가 데드라인을 놓칠지 예측하기 어렵다는 단점이 있습니다.

4. RM vs EDF 한눈에 비교

핵심 정리

• RTOS 스케줄링의 목표는 평균 성능이 아니라 모든 태스크의 데드라인 준수를 수학적으로 보장하는 것이며, hard real-time에서는 선점형을 기본으로 쓴다.
• RM은 주기가 짧을수록 높은 우선순위를 고정으로 주는 정적 우선순위 방식이며, 스케줄 가능성은 리우-레이랜드 공식 $U \leq n(2^{1/n}-1)$으로 판정하는 충분조건이다.
• EDF는 절대 데드라인이 가장 임박한 태스크에게 매 순간 CPU를 주는 동적 우선순위 방식이며, 암시적 데드라인 조건에서 $U \leq 1$이 스케줄 가능성의 필요충분조건이다.
• 같은 태스크 집합이라도 RM에서는 데드라인을 놓치고 EDF에서는 지키는 경우가 있으며, 이는 EDF가 이론적으로 더 높은 CPU 활용률까지 최적으로 스케줄링할 수 있음을 보여준다.
• 실무에서는 EDF의 이론적 우수성에도 불구하고, 구현 단순성과 우선순위 역전 대응 이론이 성숙한 RM이 여전히 널리 쓰인다.

마무리 복습

참고 자료

• FreeRTOS documentation 
• FreeRTOS Reference Manual 
• 국가평생교육진흥원 독학학위제 - 과목별 평가영역