Exact Schedulability Test : RTA, TDA

Intro

RTA는 Real-Time 분야 공부를 하며 자주 봤던 내용들이지만, 수렴성 증명 등은 꽤나 흥미로워서 글로 남기게 되었다. 가장 쉬운 schedulability analysis는 utilization를 계산하여 utilization bound보다 작은지 검사하는 것이지만, 최대한 보수적인 bound를 잡기 때문에 실제로는 schedulable하나 utilization 자체는 bound를 넘는 경우가 많다. 물론 time complexity 면에서는 utilization bound만 검사하는 것이 좋을 수 있으나, 정확한 schedulability anlaysis를 아는 것도 중요하다. 본 글에서 소개하는 두 방법은 주어진 task가 정확히 schedulable한지를 판단하는 방법들이다.

System Model

task set $\{ \tau_1, \dots, \tau_n \}$에 대해 각 task는 $\tau_i = (e_i, p_i, d_i)$와 같이 나타낼 수 있다.

• $e_i$ : WCET (Worst Case Execution Time)
• $p_i$ : period.
• $d_i$ : deadline

• processor demand $W_i(t) = \sum_{j=1}^{i}e_j \lceil t/p_j \rceil$
• Fixed-Priority scheduling을 사용한다. 즉, 한 task 내의 job들은 모두 같은 priority를 가진다. 편의를 위해 task set이 priority가 높은 순으로 배열되어있다고 가정한다. ($\tau_1$의 job들의 priority가 가장 높고 $\tau_n$의 job들의 priority가 가장 낮다.)
• preemption을 허용한다.

RTA (Response Time Analysis)

정확한 response time을 구할 수 있는 방법이다.

$r^{(0)}_i$부터 시작하여 $r^{(t+1)}_i = r^{(t)}_i$일 때까지 위 재귀식을 반복한다. 수렴했을 때의 $r^{(t)}_i$ 값이 최종적인 $\tau_i$의 response time $r_i$이며 $r_i \le d_i$ 인 경우 해당 task는 schedulable하다.

직관적으로 생각하자면, response time은 자신의 실행 시간과 preemption을 당한 시간이다. 따라서 +의 오른쪽 항이 preemption을 당한 시간이다.
response time이 가장 길어지는 경우는 $\tau_i$보다 priority가 높은 모든 task에 대해 최대한 많은 preemption을 당한 경우이다. 이는 모든 task가 같은 시점에 release되는 critical instant 조건이며, 이 경우 적어도 response time은 자신과 자신보다 priority가 높은 모든 task의 실행 시간의 합보다는 크다. 따라서 $r^{(0)}_i$이 위와 같다. ($e_i$로 시작해도 되지만 재귀 횟수가 더 길어질 뿐이다.) 재귀를 반복하여 길어진 response time에 대해 높은 priority task들이 새로 release될 수 있고 이 경우 해당 task의 실행 시간만큼 다시 preemption이 되므로 그만큼을 다시 더해준다.

Example

$e_1 = 4, p_1 = d_1 = 10$
$e_2 = 6.1, p_2 = d_2 = 14$
$e_3 = 1, p_3 = d_3 = 70$
에 대해

$r^0_2 = 4 + 6.1 = 10.1$
$r^1_2 = 6.1 + \lceil \frac{10.1}{10} \rceil \cdot 4 = 14.1 > 14$

response time이 deadline보다 길어졌으므로 $\tau_2$는 schedulable하지 않다.
그러나,

$r^0_3 = 4 + 6.1 + 1 = 11.1$
$r^1_3 = 1 + \lceil \frac{11.1}{10} \rceil \cdot 4 + \lceil \frac{11.1}{14} \rceil \cdot 6.1 = 15.1$
$r^2_3 = 1 + \lceil \frac{15.1}{10} \rceil \cdot 4 + \lceil \frac{15.1}{14} \rceil \cdot 6.1 = 21.2$
$r^3_3 = 1 + \lceil \frac{21.2}{10} \rceil \cdot 4 + \lceil \frac{21.2}{14} \rceil \cdot 6.1 = 25.2$
$r^4_3 = 1 + \lceil \frac{25.2}{10} \rceil \cdot 4 + \lceil \frac{25.2}{14} \rceil \cdot 6.1 = 25.2 < 70$

이므로 $\tau_3$는 schedulable하다.
이처럼 유의할 점은 task set 전체가 schedulable한지 판단하기 위해서는 priority가 가장 낮은 task 하나만 보면 안 되고 모든 task에 대해 검사해봐야 한다는 것이다.

RTA의 수렴성 증명

직관적으로는 response time을 구하는 재귀식이 수렴할 것처럼 보이지만, 정말 그럴까? task가 schedulable하지 않다고 하면 수렴하지 않을 것도 같다.

Thm) RTA의 재귀식은 task set의 utilization이 1 이하이면 수렴한다.
$r^{(t+1)}_i = e_i + \sum_{1 \le j < i} \lceil \frac{r^{(t)}_i}{p_j} \rceil \cdot e_j$

pf)
단조 증가하고 상한이 존재하는 수열은 수렴한다는 것을 이용하여, 수렴성을 증명한다.

(i) 상한 존재
utilization이 1보다 작으므로

를 만족한다. $p_1\cdots p_{n}$의 시간을 생각했을 때 $\tau_1$은 최대 $p_2\cdots p_n$번 release될 수 있고 $\tau_{n-1}$은 최대 $p_1\cdots p_{n-2}p_n$만큼 release될 수 있다. processor가 work-conserving (pending job이 있는 경우 idle하지 않음)이라고 가정하면, 남은 $p_1\cdots p_{n-1}e_n$ 시간 동안 $\tau_n$은 적어도 한 번 실행된다. 따라서 $\tau_n$의 response time이 $p_1\cdots p_{n}$ 이하라고 보장할 수 있다.

(ii) 단조 증가
증명의 편의를 위해 $r^{(0)}_i = e_i$라 하면
$r^{(1)}_i = e_i + \sum_{1 \le j < i} \lceil \frac{r^{(0)}_i}{p_j} \rceil \cdot e_j \ge r^{(0)}_i + \sum_{1 \le j < i} \lceil \frac{r^{(0)}_i}{p_j} \rceil \cdot e_j \ge r^{(0)}_i$

이제 $r^{(k)}_i \ge r^{(k-1)}_i$ 이라 가정하면
$r^{(k+1)}_i = e_i + \sum_{1 \le j < i} \lceil \frac{r^{(k)}_i}{p_j} \rceil \cdot e_j \ge e_i + \sum_{1 \le j < i} \lceil \frac{r^{(k-1)}_i}{p_j} \rceil \cdot e_j = r^{(k)}_i$

이므로 수학적 귀납법에 의해 임의의 k = 0, 1, 2, ...에 대해 $r^{(k)}_i$는 단조 증가한다.

(i), (ii)에 의해 재귀식은 수렴한다.

$\square$

유의할 점은 수렴성을 증명한 것이지, 수렴한다고 schedulable하다는 것은 아니라는 것이다.

TDA (Time Demand Analysis)

방법론 자체는 이전의 글에서 소개한 내용이다. 근데 이름을 Time Demand Analysis라고 하지는 않았는데 그렇게 부른다고 한다.

TDA (Time Demand Analysis)
periodic task $\tau_1, \dots, \tau_n$에 대해
$S_i = \{ k \cdot p_j | j = 1, \dots, i \ ; \ k = 1, \dots , \lfloor \frac{p_i}{p_j} \rfloor \}$
1. RM 하에서 $\tau_i$가 스케줄 가능할 필요충분조건은
$L_i = min_{\{ t \in S_i \}}W_i(t)/t \le 1$
2. RM 하에서 task set 전체가 스케줄 가능할 필요충분조건은
$L = max_{\{ 1 \le i \le n \}}L_i(t)\le 1$

더 간단하게는 각 scheduling point에 대해 $W_i(t) \le t$인 t가 있으면 해당 task는 schedulable하다. 직관적으로는 demand보다 supply가 같거나 많아지는 시점이 있으면 schedulable하다는 의미다.
증명은 이전의 글에 있으니 참고하길 바란다.

Example

$\tau_1 : e_1 = 40,p_1=100$
$\tau_2 : e_2 = 40,p_2=150$
$\tau_3 : e_3 = 100,p_3=350$

scheduling point $S_i = \{ 100, 150, 200, 300, 350 \}$ 이고
$t = 100 : e_1 + e_2 + e_3 = 40 + 40 + 100 > 100$
$t = 150 : 2e_1 + e_2 + e_3 = 2 \cdot 40 + 40 + 100 > 150$
$t = 200 : 2e_1 + 2e_2 + e_3 = 2 \cdot 40 + 2 \cdot 40 + 100 > 200$
$t = 300 : 3e_1 + 2e_2 + e_3 = 3 \cdot 40 + 2 \cdot 40 + 100 \le 300$
$t = 350 : 4e_1 + 3e_2 + e_3 = 4 \cdot 40 + 3 \cdot 40 + 100 > 350$

t = 300일 때 supply가 demand 이상이므로 $\tau_3$은 schedulable하다.

RTA와 TDA는 동치인가?

RTA의 재귀식에서 왼쪽이 supply, 오른쪽이 demand (본인의 demand와 higher priority task의 demand)라고 생각하면 그 의미는 같아보인다. 따라서 schedulability 면에서는 동치라고 생각할 수 있다.
차이점이 있다면 RTA는 response time을 정확하게 구할 수 있다는 장점이 있으나, time complexity가 TDA보다는 크다. (근데 scheduling point가 많아지면 TDA도 꽤나 클 것 같긴 하다.)