임베디드 스터디 - 실시간 스케줄링 RM, EDF, 이용률 상한

실시간 스케줄링이 필요한 이유

• 일반 스케줄러(Round Robin, Priority 등)는 데드라인 개념이 없음
• Hard RT 시스템에서는 “이 태스크는 반드시 Xms 안에 끝내야 한다”는 보장이 필요
• 실시간 스케줄링은 데드라인을 기준으로 우선순위를 결정

RM (Rate Monotonic)

• 태스크의 주기(Period)를 기반으로 우선순위를 정적으로 할당
• 핵심 규칙 : 주기가 짧을수록 우선순위가 높음

태스크 A: 주기 10ms → 10ms마다 데드라인 → 높은 우선순위
태스크 B: 주기 50ms → 50ms마다 데드라인 → 낮은 우선순위

• 정적(Static) 우선순위 — 실행 중 우선순위 변경 없음
• 구현 단순, 예측 가능 → 임베디드 시스템에 적합

EDF (Earliest Deadline First)

• 데드라인이 가장 빠른 태스크를 먼저 실행
• 동적(Dynamic) 우선순위 — 매 순간 데드라인을 비교하여 재결정

RM vs EDF 비교

구분	RM	EDF
우선순위	정적 (주기 기반, 고정)	동적 (데드라인 기반, 매 순간 재결정)
CPU 이용률	낮음	높음
구현 복잡도	단순	복잡
오버헤드	작음	큼

이용률 상한 (Utilization Bound)

• RM 스케줄링에서 모든 태스크의 데드라인 보장 가능 여부를 사전에 검증하는 공식

\[U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1)\]

• $C_i$ : 태스크 i의 실행시간
• $T_i$ : 태스크 i의 주기
• $n$ : 태스크 수
• $n \to \infty$ 일 때 우변은 $\ln 2 \approx$ 0.693에 수렴
• EDF의 경우 우변은 1
  • 단, 실제로 컨텍스트 스위치 오버헤드 때문에 데드라인 미스가 발생하므로, 일정 여유를 확보할 필요가 있음

계산 예제

태스크	실행시간 $C_i$	주기 $T_i$
A	1ms	4ms
B	2ms	8ms

\[U = \frac{1}{4} + \frac{2}{8} = \frac{1}{2} = 0.5\]

n=2일 때 상한 = $2(2^{1/2}-1) \approx 0.828$

$0.5 \leq 0.828$ → 데드라인 보장 가능

• U가 상한 초과 시 → 태스크 실행시간 단축 또는 주기 연장 필요