Real Time System(7)

Priority Scheduling

Scalable하고,
시스템적으로 scheduling을 할 수 있는 방식입니다.

1. 각 Task에 Timing Constraint를 바탕으로 Priority를 부여합니다.

2. Analytic Technique를 이용하여 feasibility를 검증합니다.

3. Priority-based하게 task를 수행하면 됩니다.

How to assign priority?

보통 '중요도' 에 따라서 priority를 부여하는게 자연스럽죠?
근데, priority assignment를 어떻게 주냐에 따라 processor utilization bound가 달라집니다.

Task가 3개 있으면, 가능한 조합이 6개인데,
어떻게 priority를 주냐에 따라서 utilization의 최대치가 달라져요.

$\tau_1$이 $\tau_2$보다 task period가 작습니다.
$C_1$보다 $C_2$가 압도적으로 크구요.

이 때, $\tau_1$의 priority를 더 높게 주면, 딱히 문제는 안 생겨 보입니다.

근데, $P_2$를 더 크게줬더니, 이런. $\tau_1$이 deadline miss가 2번이나 일어나네요.

그래서 priority를 부여하는 기준이 매우 중요합니다.

Utilization Bound란?

특정 scheduling algorithm의 utilization bound가 A라면,
task set의 Utilization 합이 A보다 작거나 같다면
task set은 schedulable함이 보장되어야 합니다.

이따구로 priority를 부여하는 scheduling algorithm이라면,
utilization bound가 0이 됩니다.

task set의 utilization sum이 '0'을 넘으면 schedulable하지 않다는 뜻입니다.
뭔 개소립니까.
망한 알고리즘이죠.

Optimal Priority Assignments

학자들이 열심히 연구해서,
'이렇게 priority를 부여하면 이런 조건 하에서 optimal해요'라는걸 찾아낸 알고리즘들입니다.

Rate Monotonic (RM)

$T_i$에 반비례하게 $P_i$를 부여합니다.
즉, 더 자주 activate될 수록 priority가 높습니다.
단순하죠?

이 경우, $D_i = T_i$인, Fixed-Priority 알고리즘 중에서 optimal합니다.

Deadline Monotonic (DM)

$D_i$에 반비례하게 $P_i$를 부여합니다.
deadline이 빨리 끝나는 놈을 더 중요히 여깁니다.

이 경우, $D_i \leq T_i$인 Fixed-Priority 알고리즘 중에선 optimal합니다.

Earliest Deadline First (EDF)

$d_{i,j}$에 반비례하게 $P_i$를 부여합니다.
job level priority assignment입니다.

앞선 RM, DM과는 다르게 Job 단위로 priority가 부여되며,
그 job들 중 Absolute deadline이 가장 짧은 놈이 priority가 제일 셉니다.

이 경우, $D_i \leq T_i$인 모든 알고리즘에서 optimal합니다.
심지어, $D_i > T_i$여도 EDF가 optimal합니다.

하나하나 살펴봅시다..

Rate Monotonic is Optimal

RM은 $D_i = T_i$인 FP 알고리즘에서 optimal합니다.

다르게 표현하면,

Task set이 RM으로 schedulable하게 만들 수 없다면,
Fixed-priority assignment 중 뭘 가져와도 schedulable하게 만들 수 없습니다.

Deadline Monotonic is Optimal

DM은 $D_i \leq T_i$인 모든 FP 알고리즘에서 optimal합니다.

EDF is optimal

EDF는 그냥 생판 optimal합니다.
얘는 신이에요.

특정 조건 하에서요.
(Uniprocessor, Preemptive scheduling)

task set에게 feasible한 schedule이 존재한다면,
EDF로도 무조건 schedule이 가능합니다.

만약 EDF로 schedule이 가능하지 않다면, 그 task set에 feasible한 schedule은 존재하지 않습니다.

약간, task set이 구멍이고, EDF를 탁구공으로 생각하면 됩니다.

특정 조건이 만족되면 탁구공은 모든 구멍에 들어갑니다.
만약, 어떤 공이 구멍에 들어갈 수 있다면, 탁구공도 무조건 들어갈 수 있습니다.

하지만, 만약 탁구공도 안 들어가는구멍이 있다면, 그 구멍에는 어떤 공도 못 들어가죠.

RM (Rate Monotonic)

Period가 짧은 놈에게 먼저 부여하는 겁니다.

Utilization Sum이 1.0보다는 작긴 한데,
RM으로 schedule하면 unschedulable합니다.

물론, EDF는 Job level이기 때문에 저걸 EDF으로 조지면 schedulable해지겠죠.

How do we verify Feasibility?

Optimality는 알겠는데, 결국 궁금한건
그래서 이 task set이 이 algorithm으로 feasible함?

이걸 알고싶거든요.

Feasibility를 체크하기 위해서는 Worst Case를 알아야 합니다.
최악의 경우에도 feasible하다면, 걔는 feasible할테니까요.

그리고 그걸 위한 개념 중 하나가 Critical Instant입니다.
Response time이 최대가 되는 situation이 Critical Instant입니다.

그리고 Task-level FP scheduling에 적용되는 critical instant가 있는데요.

Longest Response Time은 그 task가 더 높은 priority의 task와 같이 들어올 때 발생한다입니다.

즉, RM이나 DM이라면 아래의 case에서 'critical instant'가 발생한다는 뜻입니다.

Task Set이 schedulable하려면, 최소한 U $\leq 1.0$은 맞춰야 합니다.

물론, 그렇다고 무조건 schedulable한 것도 아니죠.

즉, Task Set에 따라서 알고리즘이 같아도 Upper Bound는 달라질 수 있습니다.

이렇게 Task가 (4,2)와 (8,4)로 고정된다면,
이 Task Set에 대한 RM의 upper bound는 1.0입니다.

즉, Utilization sum이 1.0보다 작다면, C를 어떻게 바꿔도 schedulable해진다는 뜻이죠.

그럼 upper bound는 의미가 없죠.
우리는 Least Upper Bound를 찾아야 합니다.

어떤 task set을 집어넣어도, U가 이거 이상만 되면 schedulable하더라
이걸 알고 싶은겁니다.

즉, $U \leq U_{lub}$가 성립하면 RM으로는 무조건 schedulable함.을 말하고 싶다는 거네요.

주의할 건, $U_{lub} \leq U \leq 1.0$이 성립할 때에는 그 어떤 것도 말할 수 없습니다.
Schedulable할지 아닐지 몰라요

LUB for RM

Liu와 Layland라는 2명의 연구자가 $U_{lub}\text{ for RM}$을 밝혔는데,
$n(2^{1/n}-1.0)$이라고 밝혔습니다.

n을 무한대로 증식시키면, ln2가 되는데,

다른 말로는 $U_{sum} \leq ln2$ 인 전세계의 모든 task set은,
$T_i = D_i$만 성립한다면, RM으로 schedulable해집니다.

특이 케이스

task set의 task 중 아무거나 2개를 잡았을 때,
서로의 period가 배수 관계라면,

그 경우를 harmonic period라고 부르고,
그런 harmonic period task set에 대해서는 특별히 $U_{lub} = 1.0$이 됩니다.

RM에서는,
WCET를 쭉 늘려서 processor의 utilization을 최대화하고,
그렇게 Upper bound of U를 계산한 후,

여러 변수를 고려해서 U를 최소화하면 됩니다.

Extension to Tasks with D <= T

DM과 EDF를 고려해볼 수 있습니다.

Deadline Monotonic

다음과 같이, Task가 두개 있다고 합시다.
$\tau_1(10,2,3)$과 $\tau_2(8,3,6)$입니다.

이 때, Utilization이 아닌 Utilization Density를 계산해봅시다.
왜냐면 Utilization은 $T = D$인 경우에 썼던 분석법이니까,
검증을 할 수치를 쓴다면 $D$도 계산에 들어가는 편이 좋을 것 같네요.

$C/T = U$고, $C/D = UD$입니다.

이 경우는 계산해보면 Utilization Density가 1.16이 나옵니다.
UD는 1.0이 넘어도 돼요.

Response Time Analysis

$U_{lub} < U \leq 1.0$이라면 schedulability를 읊을 수 있을까요?

모릅니다.

그러면, 영원히 모른 채로 살아야 할까요?

훨씬 더 sufficient하며, necessary한 guarantee test가 존재합니다.

Response time을 계산할 때에도 Critical Instant를 고려합니다.
즉, 모든 task가 동일한 시간에 release되었다고 봅시다.

$R_k$에 대해서, $\lceil\frac{R_k}{\tau_i}\rceil C_i$라는 식을 생각해봅시다.
이 식이 뭘 말하는 거냐면,

$R_k$ 이전에 얼마나 $\tau_i$가 많이 등장했나요?
$\lceil\frac{R_k}{\tau_i}\rceil$회 등장했네요.

그리고 그만큼 등장할 때마다 $C_i$씩 쳐먹었네요.

즉, Task i가 Task k의 원활한 시행을 '얼마나 방해했나' 정도가 됩니다.

그리고 그걸, $\tau_k$보다 priority가 높은 모든 task에 대해서
interference를 다 구해 더해줍니다.

정리하면,
$R_k$는 이렇게 표현됩니다.

그리고 이 $R_k$는 iterative하게 계산합니다.

Response time을 계산하고,
해당 Response time이 더이상 update가 되지 않을 때까지 iterate합니다.

다음 task에서 response time을 계산해보면,
RM이라고 쳤을 때,
Task1은 priority 1순위이니 계산 안해도 되고,

Task2는
$40 + ceil(40/100)*20 = 60$
$40 + ceil(60/100)*20 = 60$

변화가 없네요. Task 2의 response time은 60이며,
Deadline보다 작으니까,
자기보다 상위의 모든 task를 고려해도 schedule이 가능함이라는 결론이 나옵니다.

똑같이 해보면, Task 3은 Response time이 240이 나옵니다.