Rate Monotonic

Rate Monotonic (RM) — 주기가 짧을수록(= rate가 높을수록) 높은 우선순위를 부여하는 Task-level Fixed Priority(TFP) 정책. Implicit deadline 조건에서 고정 우선순위 영역의 최적 정책이며, 명시적 이용률 상한 $U_{RM}(n)$이 존재해 간이 스케줄 가능성 테스트가 가능하다.

규칙

Rate가 높을수록 (즉, 주기 $p_i$가 짧을수록) 높은 우선순위.

• 전제: 주기 태스크, implicit deadline($d_i=p_i$), 독립, 선점 가능 싱글코어 CPU
• Implicit 조건이 아니면 Deadline Monotonic (DM)을 대신 사용

Optimality

“최적”의 정의는 고정 우선순위 스케줄링 참고.

RM이 스케줄 불가능한 태스크 집합은 어떤 FP 알고리즘도 스케줄 불가능하다.

Optimality 증명 (두 태스크, pairwise swap)

RM이 아닌 우선순위로 스케줄 가능한 임의의 사례를 RM으로 변환해도 스케줄 가능성이 유지됨을 보이면, 일반화하여 RM이 최적임이 증명된다.

1. 두 태스크 $T_1,T_2$가 주어졌을 때, RM이 아니게 $T_2$가 더 높은 우선순위를 가진다고 가정 (즉 $p_1<p_2$인데 $T_2$ 우선).
2. $T_2$의 Job $J_{21}$과 $T_1$의 Job $J_{11}$의 실행 순서를 스왑한다.
3. $J_{11}$을 $t=0$으로 당겨도 릴리스 조건을 만족하며, $J_{11}$은 여전히 자기 데드라인 안에 완료.
4. $J_{21}+J_{11}=J_{11}+J_{21}$이고, $J_{11}$ 종료 시각 $t<D_1<D_2$이므로 $J_{21}$ 역시 $D_2$ 내 완료.
5. 따라서 두 Job 모두 데드라인을 만족하며, 이후 모든 Job에 대해서도 동일 논리가 반복 적용 (why: 주기성).

스왑으로 RM으로 변환해도 스케줄 가능성이 보존되므로, RM이 실패하면 다른 FP도 실패. ∎

최적성의 조건

• 데드라인 = 주기 (implicit deadline)일 때만 최적.
• Arbitrary deadline이면 DM이 최적.

Utilization Bound

임의의 태스크 집합에 대해 이용률(utilization)은 다음과 같이 정의된다.

$$U=\sum _{i=1}^N\frac{e_i}{p_i}$$

N개 독립 선점 가능 주기 태스크 (implicit deadline) 시스템에서 RM의 이용률 상한은:

$$U_{RM}(n)=n\left(2^{1/n}-1\right)$$

$n$	$U_{RM}(n)$
1	1.000
2	0.828
3	0.780
4	0.757
5	0.743
6	0.735
7	0.729
8	0.724
9	0.721
10	0.718
…	→ $\ln 2\approx 0.693$

이용률 테스트는 충분 조건

판정	결론
$U\le U_{RM}(n)$	스케줄 가능 (guaranteed schedulable)
$U>U_{RM}(n)$	알 수 없음 — 스케줄 가능할 수도, 불가할 수도

즉 Only a sufficient condition이다. 정확한 판정이 필요하면 WCRT 분석으로 넘어가야 한다.

왜 여전히 유용한가

• One-shot 계산 — 표에서 값을 읽어 $U$와 비교만 하면 끝
• Online admission test에 적합 — 새 태스크가 들어올 때 빠르게 가부를 판정
• 반면 WCRT는 태스크마다 재귀식을 수렴시켜야 함

스케줄 가능성 분석 표준 절차

1. Step 1 — Utilization Bound Test: $U\le U_{RM}(n)$이면 완료.
2. Step 2 — Exact WCRT 분석: 각 $T_i$의 $r_i$를 계산해 $r_i\le p_i=d_i$인지 확인. 자세한 절차는 응답 시간 분석.

같이 보기

• 스케줄링 알고리즘 분류
• EDF
• 주기 태스크 모델