Real Time System (8)

햄스터·2024년 12월 18일

실시간시스템개론

RealTimeSystem

목록 보기

9/11

EDF

Processor가 absolute deadline이 제일 작은 task에게 priority 우선권을 부여하는 알고리즘입니다.

$U_{sum} \leq 1.0$ 만 보장된다면 schedulable함 역시 보장됩니다!

EDF는 모든 알고리즘에 대해 optimal한데요.
조건이 좀 붙습니다.

Preemptive
No context switch overhead
Uniprocessor

이것만 만족하면 됩니다.

Why is EDF optimal?

지금의 경우에는 $\tau_E$ 가 earliest deadline task를 갖고 있죠.

이때, $C_E$ 가 다른 job보다 늦게 execute되었다고 칩시다.

지금같은 edf violation이 일어났다면,
간단히 저 빨간 덩어리 두개의 위치를 swap해주기만 하면 되겠죠.

계속 swap하고 swap해서 edf가 될때까지 가면 돼요.

EDF Feasibility Condition when T = D

이것도Liu랑 Layland인데요.

이 두 분께서 $U_{lub} = 1.0$ 임을 밝혔습니다.

U > 1.0이 경우엔 아무도 feasible task set을 만들 수 없기에,
T=D condition에서는 EDF가 optimal함을 밝혔죠.

EDF Feasibility condition proof

$U \leq 1.0$ 이라면 $\tau$ 는 schedulable하다.

EDF의 Feasibility condition이죠?
이거 증명해봅시다.

증명을 위해서는,
$U \leq 1.0$ 인데 $\tau$ 가 unschedulable한 상황을 가정합니다.

그렇게 가정햇더니, $U$ 가 1.0보다 크더라.

이런 느낌의 귀류법으로 증명을 하면 됩니다.

처음으로 deadline miss가 감지된 시간대를 $t_2$ 라고 합시다.

그리고, $t_2$ 보다 deadline이 작은 애들만 실행이 되어 온
가장 긴 continuous utilization interval을 $[t_1, t_2]$ 로 잡습니다.

즉, $[t_1, t_2]$ 범위에서는 모든 job이 $t_2$ 보다 deadline이 작습니다.

그 $[t_1, t_2]$ 에서의 총 demand를 $C_p(t_1, t_2)$ 라고 합시다.

멍청하게는 그냥 보이는 파란색 다 더하면 되고,
수학적으로는

C_p(t_1,t_2) = \sum_{r_k \geq t_1}^{d_k\leq t_2} C_k

가 되구요.

이 값은

\sum_{i=1}^n \frac{t_2-t_1}{T_i}C_i = (t_2-t_1)U

보다는 작거나 같겠죠?

여기서, deadline miss가 일어났다는 가정을 했으니,
$C_p(t_2,t_1) > (t_2 - t_1)$ 이 성립합니다.
즉, 저 시간 interval보다 요구되는 demand량이 컸다는 거죠.

근데 방금 구한 식을 집어 넣으면,
$C_p(t_1,t_2) \leq (t_2-t_1)U$ 가 성립하구요.

정리하면 $1 < U$ 가 나옵니다.
모순이네요.

귀류법에 의해서, EDF는 U가 1.0 이하면 모든 task set을 schedulable하게 한다.
이게 증명되었습니다.

Is EDF Only Optimal?

No!
Proportional Share Algorithm도 optimal합니다.

short interval $\Delta$ 를 LCM of periods로 잡고,
$\delta$ 를 Utilization에 비례하게 제공하는 알고리즘이었죠.

문제점은, $\Delta$ 가 매우 작아지면 split이 안된다는 점이었습니다.
하지만, 그래도 '쪼갤 수 있는 단위'까지 $\Delta$ 가 커버해준다면, Optimal하죠.

그래서, 만약 이론적으로 infinitely small $\delta$ 가 가능하다면,
이 알고리즘은 optimal합니다.

즉, 'quantum이 무한히 작아질 수만 있다면'
$U \leq 1.0$ 인 condition에서 optimal하다는 거죠.

EDF with D <= T

$D_i \leq T_i$ 인 경우에도 optimal하긴 한데,
조금 증명 방법이 다릅니다.

'Processor Demand Criterion'이라는게 있는데,
어떻게 길이 L을 잡아도,
computational demand g(0,L)은 L 이하여야 합니다.

앞서 EDF의 $D_i = T_i$ 인 경우 optimality를 증명할 때 computational demand라는 개념을 썼죠.

다시 등장합니다.

0 ~ L 사이의 computational demand에 대한 공식은 다음과 같습니다.

$g(0,L) = \lfloor\frac{L-D_i+T_i}{T_i}\rfloor C_i$

이 조건을 모든 L에 대해 살펴봐야 한다는건데,
사실 그게 말이 안되거든요

비록 $g(0,L)$ 이 step function이라서 $D_i, T_i + D_i, 2T_i + D_i ...$ 같은 deadline point에서만 살펴봐도 되지만,
그래도 많아요. 애초에 L이 엄청 길면 어떻게 해요.

그래서, task가 동시에 시작하며, U < 1.0이라면, (등호 없어야 함)
feasibility check는 $LCM(T_1, T_2, ... , T_n)$ 까지만 살펴봐도 됩니다.

그 값을 Hyperperiod H라고 합니다.

Summary

이렇게 Analysis technique를 총 3개 살펴봤습니다.
Utilization bound, (RM이나 T=D EDF에서 쓰였습니다)
Response Time Analysis, (Fixed Priority인 경우, RM과 DM에서 쓰였습니다)
Processor Demand Criterion (D <= T EDF에서 쓰였습니다)

이 3가지 technique를 이용해 계산만 해주면,
실제로 무한히 돌려보지 않고도
'아, task set이 schedulable하구나.'를 체크할 수 있게 돼요.

Complexity Issues

Utilization based analysis는 $O(n)$ 의 complexity를 가집니다.
n개의 task에 대해 utilization의 합을 구해야 하니까요.

Response-time Analysis의 경우,
Pseudo-Polynomial complexity를 가집니다.

$T_i, C_i, R_i$ 가 매개변수로 쓰였죠.

Processor Demand Criterion도 같습니다. pseudo-polynomial complexity를 가집니다.

RM vs EDF

Context Switches

RM에서 task 1은 죽을때까지 high-priority입니다.
EDF에선 priority가 변하죠.
그래서 그런지, RM이 Preemption (Context switch)가 더 많네요.
EDF 승!

Schedulability Analysis

RM은 Utilization based analysis와 response time analysis를 썼고,
EDF는 Utilization based analysis와 demand based analysis를 썼습니다.

+ RM의 강점 하나.

RM은 Harmonic task set의 경우 RM에 의해 schedule이 가능한데요,
$U \leq 1.0$ 이어야 합니다.

지금의 경우는 Non-harmonic한데요.
upper bound입니다. C가 조금만 커져도 unschedulable해져요.

조화롭죠. RM으로 schedulable하면 U <= 1.0 이기에 무조건 schedulable하고 upper bound가 1.0이 됩니다