Scheduling Periodic Time Critical Tasks

Periodic Task가 뭡니까?
주기적으로 activate되는 task가 periodic task입니다.

보통 표시할 때,
$\tau_i(T_i,C_i,D_i)$로 표현하죠.

$T_i$는 i번째 task가 release되는 주기이며,
$D_i$는 Relative Deadline입니다.
$C_i$는 WCET이죠.

그리고 해당 $\tau_i$의 job들은 $\tau_{i,1}$ , $\tau_{i,2}$ , ...처럼 표시합니다.

그 First Job에 대해 다음 notation들도 성립합니다.

$a_{i,1} = \phi_i$
$a_{i,k} = \phi_i + (k-1)T_i$

1번째 task의 arrival time에다가 (k-1)번의 activation이 곱해진 절대시간이죠.

$d_{i,k} = a_{i,k} + D_i$

k번째 job의 Absolute deadline도 이렇게 표현할 수 있구요.

우리가 가지는 Problem은 다음 Problem입니다.

$\tau = \{\tau_1, \tau_2, \tau_3, ...\}$일 때,
Task의 arrival time까지 포함해서

$\tau_i(\phi_i,T_i,C_i,D_i)$로 표현을 해주면,

각 $\tau_{i,j}$는 $a_{ij} = \phi_i + (j-1)T_i$에 activate되겠죠?

$\phi_i$는 1번째 job의 activation time이니까요.
그리고 $d_{ij} = a_{ij} + D_i$에 끝날겁니다.

우리는 모든 task $\tau_i$에 대해 $C_i$가 $a_{ij}$와 $d_{ij}$ 사이에 있게 하고 싶습니다.

다르게 말하면 deadline miss가 없게 하고 싶다는거죠.

Proportional Share Algorithm

Timeline을 잘게 쪼개고, 각 Task의 Utilization ($C_i/T_i$)만큼에 해당하는
time slot을 할당해줍니다.

다음과 같은 두개의 periodic task가 있다면,

utilization이 $\tau_1 = 1/4$, $\tau_2 = 1/2$이니 각 time slot에서 각각 $1/4, 1/2$의 비율을 갖게 할당해주면 됩니다.

그러면 그 time slot은 어떻게 설정합니까?

$\Delta = \text{GCD}(T_1, T_2) = 8$라고 하면,
time slot의 크기는 8이 되게 하면 되고,
각 task를 $\delta_i = U_i\Delta$로 설정해줘서 배당해주면 됩니다.

Feasible한가요?

$\sum \delta_i \leq \Delta$가 되면 Feasible합니다. 즉, $\sum U_i \leq 1$과 같은 조건이죠.
그냥 Utilization 합이 1 이하라면,
Proportional Share Algorithm으로는 task set이 feasible해집니다.

만약 $\sum U_i \gt 1$이라면요?

time slot을 8로 잡았는데, 그 8칸 안에 10칸을 할당하라는 것과 같은 말뜻입니다.
말이 안되죠.

이런 Proportional Share Algorithm은 fluid system을 approximate합니다.

가장 큰 문제점은, $\Delta = \text{GCD}(T_1, T_2, ...)$가 harmonic하지 않아서,
최대공약수가 1이 나와버리면,

$\Delta = 1$이 되며, 각 task가 너무 많이 fragmentate 되게 됩니다.
이러면 Overhead가 너무 커집니다. Context Switch는 조상님이 해주시는 건 아니잖아요.

Work And Sleep

Task가 $C_i$ 만큼 실행하고, 나머지 시간동안 잠을 잡니다.

이 방식은 기본적인 Priority 정도는 할당이 되어 있다는 가정하에 이뤄집니다.

실행이 끝나면 자면 되고,
실행이 끝나기 전에 Higher Priority Task가 깬다면, 그놈한테 할만큼 주고
사라지면 됩니다.

Task 3 입장에선 T=20에 바로 activate되지 못하긴 했지만,
deadline miss는 일어나지 않았으니 한 잔 해도 됩니다.

하지만 문제점도 있습니다.
당연히 Priority based이기 때문에, 어쩔 수 없이 $\tau_3$는 priority가 낮아서
long delay를 겪게 됩니다.

$\tau_1, \tau_2$가 전부 실행이 끝나야 $\tau_3$의 차례가 오니까요.

아주 간단한 while loop 하나만으로 쉽게 구현이 되죠.

문제가 좀 보이긴 합니다.

$T1, T2, T3, ...$의 곱이나 $LCM$을 계산해서 count를 초기화 하고자 해도,
사실 구현이 안됩니다. 너무 커요.

또, 각 function들의 시행 시간도 고려가 되지 않았습니다.

조금 더 괜찮은 스케줄링 구현체입니다.

이런 간단한 Computation time을 가진 예시를 구현하고자 하면,
잘 되는데,
코드를 잘 분석해 보면 Non-preemptive하다는 걸 알 수 있습니다.

상위 priority의 task가 충분히 delay될 수 있는 여지가 존재합니다.

또, 현실적으로 생각해 보면,
scheduler만이 only thread이진 않습니다.

그래서 thread가 loop 1회가 끝나면 어느정도 sleep이 필수불가결한데,
그러면 그 sleep time동안 해당 task들이 deadline miss를 만날수도 있죠.

그래서 지금까지 했던 이 work and sleep, proportional share 가
상당히 precise하지 못한 알고리즘들이라고 간주됩니다.

Good Example

Cyclic scheduling (Timeline Scheduling)

30년 넘게 쓰인 좋은 scheduling algorithm입니다.

1. 시간축을 equal 크기의 time slot으로 나눕니다.
2. 각 task가 statistically allocate됩니다.

무슨말일까요?

GCD로 쪼개는 proportional share의 기본 기조는 구현이 되긴 했습니다.
이 때, 각 task의 LCM을 계산하고,
LCM을 기준으로 쪼갠 T가 계속 무한히 repeat되는 구조입니다.

이 경우,
순서대로 줄을 세워놨을 때,

$C_1 + C_2 \leq \Delta$
$C_1 + C_3 \leq \Delta$
이게 성립하면 timing guarantee가 보장됩니다.

되게 단순하게 바뀌었죠?
timer를 minor cycle마다 돌리고,
timer가 돌 때마다 sync()가 실행되게 하였습니다.
물론, [1,2], [1,3], [1,2], [1]이라는 scheduling 계산은 미리 해줘야 하긴 해요.

이 Timeline Scheduling은
구현이 간단하며, (RTOS 필요없음)
overhead도 적고, jitter도 적습니다.

하지만, overload에 취약하며,
schedule의 확장이 힘들고,
aperiodic activity에 대한 반응이 거의 불가합니다.

Problems during overload

task는 2 time unit밖에 못 쓰는데,
자기는 3 time unit을 쓰고 싶다고 합니다.

어떻게 할까요?

그냥 'ㅇㅇ 써' 해버리면 도미노 효과로 timeline이 망할 수 있구요.
'ㄲㅈ' 하고 없애버려도 되는데, 그러면.. 좀 곤란하죠

가령,

$\tau_2$가 $C_2 = 20$이 되게 업데이트가 되었습니다.
그랬더니 $\tau_1 + \tau_2$에서 $\Delta$를 넘어버렸네요.

이러면, $C_2$를 쪼개는 방법을 생각해 볼 수 있습니다.

그러고 minor interval에 잘 쑤셔넣어주면 됩니다.

고려해야 할 덩어리가 바뀌었네요.
이제 $C_1 + C_{2A} \leq \Delta$와 $C_1 + C_{2B} + C_3 \leq \Delta$를 확인해야 합니다.

Period가 바뀌면요?

이렇게 했더니, GCD가 25 -> 5로 줄었습니다. LCM은 100->200이 되었구요.

더 작은 time unit에 task를 집어넣어야 합니다.
하나의 major cycle 안에 40개의 minor cycle이생겼네요.

task를 잘게 쪼개서 넣는다고 해도,
그걸 전부 다 넣어서 모두의 조합이 $\Delta$보다 작은지 확인하는걸거쳐야 합니다.

최악의 경우에는 40번요.

그리고, 그걸 또 어떤 조합으로 어떻게 넣을지는 누가 정합니까..?

이런 면에서 Scalability (expandability)가 낮다고 하는거고,

확장성이 좋은 Priority Scheduling을 따져보겠습니다.