응답 시간 분석

응답 시간 분석 (Worst-Case Response Time Analysis, WCRT Analysis) — 고정 우선순위 스케줄링에서 각 태스크의 최악 응답 시간 $r_{i}$ 를 계산하여 $r_{i} \leq d_{i}$ 여부로 스케줄 가능성을 정확히 판정하는 방법. Rate Monotonic 포함 임의 FP 알고리즘과 arbitrary deadline에 적용 가능하다.

Response Time 정의

Job의 Response Time = Job의 Release time부터 Completion time까지의 시간.

태스크 $T_{i}$ 의 WCRT $r_{i}$ = 해당 태스크의 모든 Job이 가질 수 있는 가장 긴 response time.

언제 WCRT가 발생하는가? — Critical Instant에 발생.

Critical Instant Theorem

태스크 $T_{i}$ 의 최악 시나리오는, $T_{i}$ 의 릴리스 시각에 $T_{i}$ 보다 우선순위가 높은 모든 태스크 $h p (T_{i})$ 가 동시에 릴리스되는 경우에 발생한다.

함의

$T_{i}$ 의 첫 Job이 이 critical instant에서 릴리스된다고 가정하고 데드라인 만족 여부를 확인하면, 이후 모든 Job도 데드라인을 만족한다.
증명 없이 정리만 숙지해도 스케줄 가능성 테스트에 사용 가능.

hp(Ti) 집합

높은 우선순위 태스크 집합. 예: $T_{1} > T_{2} > T_{3}$ 우선순위일 때

태스크	$h p (T_{i})$
$T_{1}$	$\emptyset$
$T_{2}$	${T_{1}}$
$T_{3}$	${T_{1}, T_{2}}$

WCRT 관찰

최고 우선순위 태스크의 WCRT = 자기 WCET — 방해받지 않음.
$T_{i}$ 는 자신보다 높은 우선순위 태스크들에 의해서만 지연된다 (단, same-priority 없음 가정).

직관식

r_{i} = e_{i} + (WCRT 구간 내 h p (T_{i}) 태스크들이 선점한 총 시간)

$r_{1} = e_{1}$
$r_{2} = e_{2} + (r_{2} 구간 중 T_{1} 의 방해)$
$r_{3} = e_{3} + (r_{3} 구간 중 T_{1}, T_{2} 의 방해)$

“WCRT 구간 내 방해”가 $r_{i}$ 자신에 의존하므로 재귀식이 필요하다.

재귀식

초기값

r_{i}^{0} = e_{i} + T_{j} \in h p (T_{i}) \sum e_{j}

반복식

r_{i}^{k + 1} = e_{i} + T_{j} \in h p (T_{i}) \sum ⌈ \frac{r _{i}^{k}}{p _{j}} ⌉ e_{j}

의미: 각 상위 태스크 $T_{j}$ 가 구간 $r_{i}^{k}$ 내에 최대 $⌈ r_{i}^{k} / p_{j} ⌉$ 번 릴리스되어 매번 $e_{j}$ 만큼 CPU를 빼앗아 간다.

수렴 판정

$r_{i}^{k + 1} = r_{i}^{k}$ 가 될 때까지 $k = 0, 1, 2, \dots$ 반복. 수렴한 값이 $r_{i}$ .

만약 반복 중 $r_{i}^{k + 1} > d_{i}$ 가 되면 스케줄 불가능이 확정되어 조기 종료.

계산 예시

$T_{3}$ 에 대한 반복 수렴 ( $h p (T_{3}) = {T_{1}, T_{2}}$ ):

$r_{3}^{0} = 6$
$r_{3}^{1} = 9$
$r_{3}^{2} = 10$
$r_{3}^{3} = 10$ → 수렴

→ $r_{3} = 10$ . 이 값을 $d_{3}$ 과 비교하여 판정.

스케줄 가능성 판정

모든 태스크에 대해 WCRT 계산:

\forall i : r_{i} \leq d_{i} (implicit 이면 p_{i}) ⟹ 스케줄 가능

Exact test — 충분 그리고 필요 조건.
임의의 FP 스케줄링 알고리즘에 적용 가능 (arbitrary deadline 포함) — 단지 $h p (T_{i})$ 만 정의되면 된다.

Utilization Bound와의 역할 분담

Step	방법	성격	비용
Step 1	Utilization Bound Test	충분 조건	1회 계산 (간단)
Step 2	Exact WCRT 분석	충분+필요	태스크별 재귀 수렴 (무거움)

표준 절차

Step 1: $U \leq U_{b o u n d}$ 이면 스케줄 가능 확정 → 종료.
아니면 Step 2로 진행해 각 $r_{i}$ 를 계산.
모든 $r_{i} \leq d_{i}$ 이면 스케줄 가능, 하나라도 위반이면 시스템이 워크로드를 감당 불가.

Step 1은 [[Rate Monotonic#utilization-bound| $U_{RM}$ ]]을 사용. Step 1이 빠른 online admission test에 유용한 이유는 수렴 반복이 없기 때문.

AE Wiki

탐색기