📦 Response Time Analysis for Real-Time Global Gang Scheduling

Introduction

본 논문은 두 개의 문제를 해결하고자 합니다.

1. 어떻게 기존의 RTA framework를 gang task model에 일반화하고, 기존 RTA의 구성요소를 어떻게 활용하나요?
2. Gang Scheduling의 특성을 RTA framework에 통합하여 비관성을 최소화하는 방법은 무엇인가요?

Assumptions

• Gang task model
• Global Preemptive scheduling
• Work-conserving scheduling

Recent Work

• Gang EDF Scheduling of Parallel Task Systems 에서는 EDF scheduling에서만 스케쥴 가능성을 도출하였고, 나머지 알고리즘에 대해 적용하는 방법은 다루지 않았습니다.
• 또한 이 방법은 Comments on "gang EDF schedulibility analysis"에서 결함이 있음이 나타났습니다.

Generalizing RTA Framework to Gang Scheduling

Definition 1 ($m_i = 1$)
$X$를 $\tau_k$의 target interval $L$에 대해서 $\tau_k$가 active하지만 실행되지 못한 시간의 길이라고 정의하자.

• 만약 $X$가 $(L-C_k+1)$ 보다 크다면 임의로 $(L-C_k+1)$개의 time slot을 $X$에서 선택하자.
• $X$가 $(L-C_k+1)$보다 작다면 $X$의 전부를 선택하자.

여기에서 이 선택된 time slot들을 $k$-interference time slots of length $L$ for $\tau_k$라고 하자.

• 여기에서 우리는 $(L-C_k+1)$만큼의 $k$-interference time slots가 존재함이 $\tau_k$가 $L$ 안에 $C_k$만큼을 실행하지 못할
  필요조건임을 알 수 있습니다.

Definition 2
$I_{k\leftarrow i}(L)$는 $k$-interference time slots of length $L$ for $\tau_k$에서 $\tau_i$의 실행시간으로 정의되며, 이를 duration of interference of $\tau_i$ on $\tau_k$라고 하자.

• 앞에서 이야기했던 $(L-C_k+1)$만큼의 $k$-interference time slots가 존재함은 결국 $\sum_{\tau_i \in \tau,\tau_k \neq \tau_i}I_{k\leftarrow i}(L)=m\cdot (L-C_k+1)$로 정리할 수 있습니다.
• 따라서, 식 $(1)$(식 $(2)$와 동치)을 만족하는 $C_k \le L \le D_k$가 있다면 $\tau_k$는 $L$ 안에 $C_k$만큼을 실행할 수 있습니다.

• Offline test에서 사용하기 위해 각 target 알고리즘에 대해서 $I_{k\leftarrow i}(L)$의 upper bound $I_{k\leftarrow i}^+(L)$를 구해야 합니다.
• 이때 모든 $\tau_k \in \tau$에 대해서 $I_{k\leftarrow i}^+(L)$를 식 $(1)$에 대입하였을 때 성립한다면, Schedulable하다는 것을 알 수 있습니다.
• 이제 Gang Scheduling에 적용하기 위하여 $m_i = 1$ 가정을 해제하고, 다음과 같이 정의할 수 있습니다.

Definition 3
$k$-interference time slots 동안 $(m-m_k+1)$개의 프로세서가 $\tau_k$가 아닌 작업에 의해 점유되어야 한다.
만약 덜 점유되어있다면 $k$-interference time slots의 정의에 위배된다.
이때 우리는 임의로 $(m-m_k+1)$개의 프로세서를 선택할 수 있고,
이때 선택된 프로세서들을 $k$-interference processors of $k$-interference time slots라고 하자.

(진한 빨간색이 $k$-interference processors of $k$-interference time slots)

• 여기에서 duration of interference(1차원)도 amount of interference(2차원)로 일반화할 수 있습니다.

Definition 4
$A_{k\leftarrow i}(L)$은 $k$-interference processors of $k$-interference time slots에서 $\tau_i$의 실행양으로 정의되며, 이를 amount of interference of $\tau_i$ on $\tau_k$라고 하자.

그러면 다음 lemma를 통해 작업이 실행을 완료하지 못할 정확한 조건을 도출해낼 수 있습니다.

Lemma 1
식 $(3)$은 $\tau_k$가 $L$ 안에 $C_k$만큼을 실행하지 못할 필요충분조건이다.

$\sum_{\tau_i \in \tau, \tau_i \neq \tau_k} A_{k \leftarrow i}(L) = (m - m_k + 1) \cdot (L - C_k + 1) \tag{3}$

Proof
충분조건

• 만약 식(3)이 성립한다면 정의에 의해 각 $k$-interference time slots에 대해서 $(m-m_k+1)$개의 프로세서가 $\tau_k$가 아닌 작업에 의해 점유되어야 하므로, $\tau_k$는 $L$ 안에 $C_k$만큼을 실행하지 못합니다.

필요조건

• 만약 $\tau_k$가 $L$ 안에 $C_k$만큼을 실행하지 못한다면, 적어도 $(L-C_k+1)$의 time slot동안 실행되지 못해야 하며,
• 정의에 의해 $(m-m_k+1)$개의 프로세서가 $\tau_k$가 아닌 작업에 의해 점유되어야 하므로, 식(3)이 성립합니다.

• Lemma 1을 부정함으로써 Theorem 1을 도출할 수 있습니다.

Theorem 1
만약 식 $(4)$를 만족하는 $C_k \le L \le D_k$가 존재한다면 $\tau_k$는 $L$ 안에 $C_k$만큼을 실행할 수 있다.

$\sum_{\tau_i \in \tau, \tau_i \neq \tau_k} A_{k \leftarrow i}(L) < (m - m_k + 1) \cdot (L - C_k + 1) \tag{4}$

$\Leftrightarrow C_k + \left\lfloor \frac{\sum_{\tau_i \in \tau, \tau_i \neq \tau_k} A_{k \leftarrow i}(L)}{m - m_k + 1} \right\rfloor \leq L \tag{5}$

또한 $A_{k\leftarrow i}(L)$의 상한 $A_{k\leftarrow i}^+(L)$를 모든 $\tau_k$에 대해서 유도하였고, 모든 $\tau_k$에 대해서 $A_{k\leftarrow i}^+(L)$에 대해 식 $(4)$를 만족한다면 타겟 알고리즘에 대해 $\tau$는 schedulable하다.
이때 $\tau_k$에 대한 최소 $L$을 $\tau_k$의 response time $R_k$라고 정의한다.

Proof
식 $(4)$를 만족하지만 $L$안에 $\tau_k$가 완료되지 않음을 가정한다면 Lemma 1에 의해 모순이 발생합니다.
정리의 두번째 부분은 $A_{k\leftarrow i}(L) \le A_{k\leftarrow i}^+(L)$이므로 만족합니다.

• 이를 통해 우리는 다음과 같은 알고리즘을 도출할 수 있습니다.
• 이는 Slack $S_k$를 이용하며, $S_k$가 양수라면 모든 $\tau_k$의 작업들이 deadline보다 $S_k$만큼 먼저 완료될 수 있음을 의미합니다.

위 식에서 $A_{k\leftarrow i}^+(L)$를 구하기 위해서 $A_{k\leftarrow i}(L)$를 $I_{k\leftarrow i}(L)$와 processors of interest의 개수로 분해할 수 있습니다.

Lemma 2

$A_{k \leftarrow i}(L) \leq I_{k \leftarrow i}(L) \cdot \min(m_i, m - m_k + 1) \tag{6}$

Proof
$k$-interference time slots과 $k$-interference processors의 정의에 의해 $A_{k \leftarrow i}(L)$는 $I_{k \leftarrow i}(L)$와 $\min(m_i,m - m_k + 1)$의 곱으로 제한된다는 것을 알 수 있습니다.

Fixed Priority Scheduling

FP에서 $I_{k\leftarrow i}(L)$는 다음과 같이 구할 수 있습니다. (Schedulability analysis of global scheduling algorithms on multiprocessor platforms, 2008)

• $W_i(L)$는 workload의 upper bound로, $\tau_i$가 $L$ 안에 실행할 수 있는 최대 양을 의미합니다.

Earliest Deadline First Scheduling

EDF에서 $I_{k\leftarrow i}(L)$는 다음과 같이 구할 수 있습니다.

여기에서 $E_{k \leftarrow i}$는 deadline이 $\tau_k$보다 이르거나 같은 $\tau_i$가 $D_k$안에 실행되는 최대 시간을 의미합니다.

이렇게 FP와 EDF에 대해서 알고있는 $I^+_{k\leftarrow i}(L)$를 이용하면 Gang Scheduling에 대해서도 적용할 수 있습니다.

Theorem 2

• Algorithm 1에 $A^+_{k \leftarrow i}(L) = I^+_{k \leftarrow i}(L) \cdot \min(m_i, m - m_k + 1)$를 적용하고,
• RHS의 $I^+_{k \leftarrow i}(L)$를 식 $(7)$ 또는 $(8)$로 대체한다면, 각각 FP와 EDF에 대한 schedulability test를 수행할 수 있다

• 이렇게 processor의 수와 interference time slot을 분리하여 계산함으로써 계산은 매우 쉬워졌지만, parallel execution을 완전히 고려하기는 어렵습니다.
• 그렇기 때문에 다음 섹션에서 이 pessimism을 줄이기 위한 두가지 기법을 제안합니다.
  • 동시에 실행될 수 없는 작업에 대해 분석하여 이를 개선합니다.
  • 어떻게 각 task의 job들이 $k$-interference processor를 점유하는지 조사하고 과추정된 부분을 찾습니다.

Addressing Non-Parallel Execution Constraints

Example 1

$m=10$ 환경에서 다음과 같은 세 개의 작업을 가정합시다.

• $\tau_1(T_1=10,D_1=10,C_1=5,m_1=6)$
• $\tau_2(T_2=10,D_2=10,C_2=5,m_2=5)$
• $\tau_3(T_3=5,D_3=5,C_3=1,m_3=2)$

• 이 상황에서 Theorem 2는 $\tau_1$과 $\tau_2$가 동시에 실행될 수 없음을 활용하지 못하기에 $\tau_3$가 실행될 수 없다고 판단합니다.

Lemma 3
만약 $m_i + m_j > m$ 이라면 다음 부등식이 성립힌다.

$I_{k \leftarrow i}(L) + I_{k \leftarrow j}(L) \leq L - C_k + 1 \tag{9}$

Proof
식(9)를 부정하면 비둘기집의 원리에 의해 반드시 $\tau_i$와 $\tau_j$가 동시에 실행되는 적어도 한개의 time slot이 필요하고, 이는 모순임.

또한 이를 $A_{k\leftarrow i}(L)$에 대해서도 적용할 수 있습니다.

Lemma 4
만약 $m_i + m_j > m$, $m_i \ge m_j$ 이라면 다음 부등식이 성립힌다.

$\begin{aligned} A_{k \leftarrow i}(L) + A_{k \leftarrow j}(L) &\le I_{k \leftarrow i}(L) \cdot \min(m_i, m - m_k + 1) \\ &\quad+ I_{k \leftarrow j}(L) \cdot \min(m_j, m - m_k + 1) \\ &\le I^{+}_{k \leftarrow i}(L) \cdot \min(m_i, m - m_k + 1) \\ &\quad+ \widehat{I_{k \leftarrow j}(L)} \cdot \min(m_j, m - m_k + 1) \end{aligned} \tag{10}$

여기에서 $\widehat{I_{k \leftarrow j}(L)}$는 $I^{+}_{k \leftarrow j}(L)$와 $(L+C_k+1)-I^{+}_{k \leftarrow i}(L)$ 중 작은 값이다.

Proof
첫번째 부등식은 Lemma 2에 의해 성립합니다.

Case 1. $I^{+}_{k \leftarrow i}(L) + I^{+}_{k \leftarrow j}(L) \le L-C_k+1$

• 이 경우는 단순히 RHS에 upper bound를 대입한 것입니다.

Case 2. otherwise

• 새로운 upper bound $I'_{k \leftarrow i}(L) \le I^{+}_{k \leftarrow i}(L)$ 와 $I'_{k \leftarrow j}(L) \le I^{+}_{k \leftarrow j}(L)$를 도입합시다.
• 우리는 LHS의 안전한=가장 큰큰 upper bound를 구해야 합니다.
• $m_i \ge m_j$이므로 $I'_{k \leftarrow i}(L)$이 최대가 될 때 upper bound가 최대가 됩니다.
• 이때 $I'_{k \leftarrow j}(L)$는 최소가 되고, 이는 $(L+C_k+1)-I^{+}_{k \leftarrow i}(L)$로 제한됩니다.

Example 2

Example 1에서 $\tau_1$을 두 개로 쪼개봅시다.

• $\tau_{1a}(T_{1a}=10,D_{1a}=10,C_{1a}=5,m_{1a}=3)$
• $\tau_{1b}(T_{1b}=10,D_{1b}=10,C_{1b}=5,m_{1b}=3)$
• $\tau_2(T_2=10,D_2=10,C_2=5,m_2=5)$
• $\tau_3(T_3=5,D_3=5,C_3=1,m_3=2)$

이 경우는 Example 1과 똑같이 schedulable해야 하지만 $m_i + m_j > 10$인 경우가 없으므로 Lemma 4를 이용해서도 검출 할 수 없습니다.

따라서 동시에 실행할 수 없는 task set의 크기가 두 개보다 클 때에 대해서도 일반화해야 합니다.

Lemma 5
만약 크기 $g$의 $\tau' \subset \tau$, $\tau_k \notin \tau'$가 존재하여 어떤떤 $h\le g$에 대해 $\sum_{h\;\text{tasks}\;\tau_i \in \tau'}m_i > m$이라면 다음 부등식이 성립한다.

$\sum_{\tau_i \in \tau'} I_{k \leftarrow i}(L) \leq (h-1) \cdot (L - C_k + 1) \tag{11}$

Proof
증명은 비둘기집 원리를 이용한 Lemma 3의 증명과 유사함.

이를 통해 우리는 Lemma 4를 일반화할 수 있습니다.

Theorem 3
만약 $g$개의 $\tau' \subset \tau$, $\tau_k \notin \tau'$가 존재하여 어떤 $h\le g$에 대해 $\sum_{h\;\text{tasks}\;\tau_i \in \tau'}m_i > m$이라면 다음 부등식이 성립한다.

$\begin{aligned} \sum_{\tau_i \in \tau'} A_{k \leftarrow i}(L) &\le \sum_{\tau_i \in \tau'} I_{k \leftarrow i}(L) \cdot \min(m_i, m - m_k + 1) \\ &\le \sum_{\tau_i \in \tau'} \widehat{I_{k \leftarrow i}(L)} \cdot \min(m_i, m - m_k + 1), \end{aligned} \tag{12}$

여기에서 WLOG. $\tau_i \in \tau'$가 $m_i$에 대해 내림차순으로 정렬되어 있다고 할 때, $\widehat{I_{k \leftarrow i}(L)}$은 다음과 같이 정의된다.

$\widehat{I_{k \leftarrow i}(L)} =\begin{cases} I^+_{k \leftarrow i}(L), & \text{if } C1 \text{ holds}; \\ (h-1) \cdot (L - C_k + 1) - \sum_{z=1}^{i-1} I^+_{k \leftarrow z}(L), & \text{if } C2 \text{ holds}; \\ 0, & \text{otherwise}. \end{cases}$

$C1$: $\sum_{z=1}^i I^+_{k \leftarrow z}(L) \le (h-1) \cdot (L - C_k + 1)$,
$C2$: $\sum_{z=1}^i I^+_{k \leftarrow z}(L) > (h-1) \cdot (L - C_k + 1)\;\text{and}\;\sum_{z=1}^{i-1} I^+_{k \leftarrow z}(L) \le (h-1) \cdot (L - C_k + 1)$

Proof
증명은 Lemma 4의 증명과 유사함.

이제 $\tau'$를 찾는 방법만 알면 됩니다. Algorithm 2는 이 Theorem 3을 이용하여 $A_k^\text{total}(R_k)$를 구하는 방법을 서술합니다.

• 이 방법을 Example 2에 대입하면, $\tau_k$가 $\tau_3$일 때 $\tau_x$가 순서대로 $\tau_2, \tau_{1a}, \tau_{1b}$로 되고,
• $C_3 + \left\lfloor\frac{5L + 3L + 0L}{10-2+1}\right\rfloor = 1+(L-1) \le L$이므로 $\tau_3$가 실행 가능하다는 것을 도출합니다.

Over-Estimation of k-Interference Processor Occupation

실제로는 $m-m_k+1$ 개의 프로세서만 $k$-interference Processor에 영향을 주지만, Algorithm 1에서 $I^+_{k \leftarrow i}(L)$를 재사용함으로써, 더 많은 프로세서가 영향을 주는 것처럼 가정합니다.

Example 3

$m=10$ 환경에서 다음과 같은 네 개의 작업을 가정합시다.

• $\tau_1(T_1=10,D_1=10,C_1=9,m_1=4)$

• $\tau_2(T_2=10,D_2=10,C_2=9,m_2=3)$

• $\tau_3(T_3=10,D_3=10,C_3=9,m_3=2)$

• $\tau_4(T_4=10,D_4=10,C_4=1,m_4=3)$

• 여기에서 $L$을 $D_4$로 두었을 때, $W_1(D_4)=9$, $W_2(D_4)=9$, $W_3(D_4)=9$이므로 식 $(5)$의 분자는 81로 계산됩니다.

• 그리고, 이를 $\tau_4$에 대해 적용하면 $C_4 + \left\lfloor\frac{81}{8}\right\rfloor = 1+10 > 10$이므로 $\tau_4$의 schedulability를 보장할 수 없습니다.

그러나 실제로는 가능합니다.

이렇게 과추정한 부분을 제거하기 위해서 Lemma 6을 이용합니다.

Lemma 6
$\tau' \subset \tau$에 대해서 $\sum_{\tau_i \in \tau'} \min(m_i, m - m_k + 1) > m - m_k + 1$와 $I_k^\Delta >0$이라면 다음 부등식이 성립한다.

$\begin{aligned} \sum_{\tau_i \in \tau'} A_{k \leftarrow i}(L) &\leq \sum_{\tau_i \in \tau'} I_{k \leftarrow i}^+(L) \cdot \min(m_i, m - m_k + 1) \\ &- I_k^\Delta \cdot \left( \sum_{\tau_i \in \tau'} \min(m_i, m - m_k + 1) - (m - m_k + 1) \right), \end{aligned} \tag{13}$

$I_k^\Delta = (L - C_k + 1) - \sum_{\tau_i \in \tau'} ((L - C_k + 1) - I_{k \leftarrow i}^+(L)).$

이를 일반화해서 Theorem 5를 도출할 수 있습니다.

Theorem 5
$\tau' \subset \tau$에 대해서 다음 부등식이 성립한다.

$\sum_{\tau_i \in \tau'} A_{k \leftarrow i}(L) \leq \sum_{\tau_i \in \tau'} I_{k \leftarrow i}^+(L) \cdot \min(m_i, m - m_k + 1) - A_k^{\Delta} \tag{14}$

$A_k^{\Delta} = \sum^{|\tau'|}_{x=1}A_{k \leftarrow x}^\Delta$ 이고, $m^{sum}(i) = \sum_{x=1}^i \min(m_i, m - m_k + 1)$ 일 때, $A_{k \leftarrow x}^\Delta$는 $\tau_1$부터 $\tau_{|\tau'|}$까지 차례대로 계산된다.

$A_{k \leftarrow x}^\Delta = \begin{cases} I_k^{\Delta}(i) \cdot \min(m_i, m - m_k + 1) & \text{if } m^{\text{sum}}(i - 1) > m - m_k + 1 \\ &\;\;\text{ and } I_k^{\Delta}(i) > 0; \\ I_k^{\Delta}(i) \cdot (m^{\text{sum}}(i) - (m - m_k + 1)) & \text{else if } m^{\text{sum}}(i) > m - m_k + 1 \\ &\;\;\text{ and } I_k^{\Delta}(i) > 0; \\ 0 & \text{otherwise.} \end{cases}$

$\tag{15}$

Proof

• else if의 경우는 Lemma 6을 이용하여 증명할 수 있습니다.
• otherwise는 아무것도 빼지 않으므로 증명됩니다.
• if의 경우를 보면 이미 $i-1$ tasks만으로도 $\sum_{x=1}^{i-1} \min(m_i, m - m_k + 1) > m-m_k+ 1$이 성립하므로,
  $I_k^\Delta \cdot m_i$가 전부 $\sum_{\tau_i \in \tau'} A_{k \leftarrow i}(L)$에 기여하지 못함을 알수 있습니다.
• 따라서 이를 모두 제거해주면 if를 증명할 수 있습니다.

여기까지 계산하는 방법을 Algorithm 3에 정리하였습니다.

Algorithm 2와 3을 사용하기 위해서 우리는 두 알고리즘을 결합해야 합니다.

Algorithm 2에서는 그대로 $I^+_{k \leftarrow i}(L)$를 사용하고 그 동안 $I^*_{k \leftarrow i}(L)$를 $\widehat{I_{k \leftarrow i}(R_k)}$로로 업데이트합니다.

Algorithm 3에서는 $I_{k \leftarrow i}^+(L)$를 $I^*_{k \leftarrow i}(L)$로 대체합니다.

Theorem 7
Algorithm 1의 Line 6을 Algorithm 4로 대체하고, $I^+_{k \leftarrow i}(L)$를 식 $(7)$ 또는 $(8)$로 대체한다면, 각각 FP와 EDF에 대한 schedulability test를 수행할 수 있다.

Proof

• Algorithm 1, Lemma 2, 식 $(7)$ 또는 $(8)$에 의해 남은 증명은 Algorithm 4를 통해 계산한 $A^\text{total}_k(R_k)$가 $\sum_{\tau_i \in \tau} A_{k \leftarrow i}(R_k)$의 upper bound임을 보이는 것입니다.
• 먼저 Algorithm 2의 기초인 Theorem 3에서는 $\sum_{\tau_i \in \tau} A_{k \leftarrow i}(R_k)$의 안전한 upper bound를 구하기 위해 각 $I^+_{k \leftarrow i}(L)$에 대하여 duration constraint를 유지할 때까지 가장 큰 $m_i$를 선택합니다.
• 따라서 Algorithm3에서 Algorithm 2를 수행한 다음 Line 3에서 Algorithm 3을 수행하는 경우, 다른 선택이 더 큰 upper bound를 만들 수 없음을 증명하는 것으로 충분합니다.
• $\widehat{I'_{k \leftarrow i}(R_k)}$을 $\widehat{I_{k \leftarrow i}(R_k)}$와 다른 선택이라고 정의합시다.
• 일단 $h=g=2$, 즉 $m_h + m_j > m$인 경우만 가정합니다. 다른 경우에서의 증명도 비슷합니다.
• $\tau_h$와 $\tau_j$ 사이에 딱 1 time unit을 교환했다고 가정합시다.
• 즉 $\widehat{I'_{k \leftarrow h}(R_k)} = \widehat{I_{k \leftarrow h}(R_k)} - 1$, $\widehat{I'_{k \leftarrow j}(R_k)} = \widehat{I_{k \leftarrow j}(R_k)} + 1$이라 합시다. 나머지 $\widehat{I'_{k \leftarrow i}(R_k)}$는 $\widehat{I_{k \leftarrow i}(R_k)}$와 같습니다.
• 이때 원래 interference로부터 감소하는 양은 $\min(m_h, m-m_k + 1) = \min(m_j, m-m_k + 1) \le 0$입니다.
• 따라서, 남은 증명은 $\min(m_h, m-m_k + 1) = \min(m_j, m-m_k + 1) \le 0$이 Algotihm 3에서 감소하는 interference의 upper bound임을 보이는 것입니다.
• 만약 $\widehat{I'_{k \leftarrow i}(R_k)}$으로 $\widehat{I_{k \leftarrow i}(R_k)}$를 대체한다면, 단 하나의 차이점은 한개 time slot에 대해서 $\min(m_h, m-m_k + 1) = \min(m_j, m-m_k + 1)$만큼의 기여가 줄어드는 것 뿐입니다.
• 즉 $A_k^\Delta$는 많아야 $\min(m_h, m-m_k + 1) = \min(m_j, m-m_k + 1)$만큼 줄어들고, 즉 전체 upper bound가 1의 time unit을 바꾼다고 해서 더 커지지 않음을 증명합니다.
• 이 과정을 계속 반복하면 $\widehat{I_{k \leftarrow i}(R_k)}$의 어떤 다른 선택도 upper bound를 더 키우지 않음을 증명할 수 있고, Theorem 7이 증명됩니다.

Evaluation

• WaPe: global scheduling for FP
• DoLi: global scheduling for EDF
• UGB: non-global scheduling (i.e., a generalization of partitioned scheduling) for FP
• RTA-FP and RTA-EDF: Theorem 2 for FP and EDF
• RTA1-FP and RTA1-EDF: Theorem 4 for FP and EDF
• RTA2-FP and RTA2-EDF: Theorem 6 for FP and EDF
• RTA∗-FP and RTA∗-EDF: Theorem 7 for FP and EDF