📦 Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor

Contributions

• Sporadic Task Set의 Schedulability에 대한 필요충분조건 도출
• 대부분의 정수 단위 Sporadic Task Set에서 동작하는 Pseudo-polynomial 알고리즘 제안.
• $feasibility$ 테스트가 co-NP임을 증명
• 정수 제약이 없는 Continuous 모델로의 확장
• Sporadic + Polynomial task set에 대한 논의

Feasibility with respect to sporadic task systems

• 이미 Periodic task system에 대한 실행가능성 검사는 co-NP 완전임이 증명되었음.

Symbols

• $\tau$ 는 $\{T_1, \dots, T_n\}$ 들의 집합.
• $T_i = (e_i, d_i, p_i)$ : $e_i$: 실행 시간, $d_i$: 상대 데드라인, $p$: 최소 실행 주기
• $P = \rm{lcm}\{p_1, \dots, p_n\}$
• $(i, t_0)$: $t_0$ 시간에 발생한 $T_i$의 요청 ($\tau$-request)
• $\tau$-request의 집합 $R$이 $schedulable$ 함 : 프로세서가 $R$의 모든 요청을 처리할 수 있음.
• $legal$ : $R$이 $(i, t_1)$과 $(i, t_2)$를 포함할 때, $|t_1-t_2| \ge p_i$를 만족함.
• $feasible$: 모든 $\tau$-requests 의 $legal$한 집합이 $schedulable$함.
• $\sigma$ 라는 online scheduling iterative 알고리즘을 정의함.
• $(i, t_0)$가 $t$에 $active$ : $t_0 \le t < t_o + d_i$이고, $\sigma$가 $(i, t_0)$를 프로세서에 할당하지 않았음.
• $t$에 $failure$: $t_0+d_i = t$지만 $\sigma$가 $(i,t+0)$를 $[t_0, t)$에 프로세서에 할당하지 않았음.
• $\sigma$는 $\tau$-requests의 $legal$ set에 대해 절대 $failure$를 띄우지 않을 때 $schedulable$함.

• EDF가 최적임이 증명되어있으므로, $\sigma$도 EDF 알고리즘이라고 하자. + 일반성을 잃지 않고, 같은 우선순위일 경우 더 작은 인덱스의 작업을 실행한다고 하자.

  Lemma 1
  $\sigma$는 sporadic task system에 대해 최적이다. 따라서
  $\tau$가 $feasible$함 $\iff$ 모든 $legal$한 $\tau$-requests 집합 $R$에 대해 $(\sigma.R)$이 스케쥴링할 수 있음.

• $h_R(t) = \sum_{(i,t_0) \in R \land t_0 + d_i \le t}e_i$라고 할 때 다음이 성립한다.

  Lemma 2
  $h_R(t)>t$라면

  • $(\sigma.R)$이 $t$나 그 이전에 $failure$를 띄울 것이고,
  • $R$이 $legal$이라면 $\tau$는 $feasible$하지 않다. (Lemma 1.)

$R_1$은 단 한번만 $failure$를 보고함.

• $\tau$ 가 $feasible$ 하지 않다고 가정하자.
• 그리고 $\sigma$ 가 처음 실패를 보고하는 순간을 $t_f$라고 정의하자.
• $R_0$ 에 대해, 우리는 유한한 $legal$ 집합 $R_{1} = R_{0} - \{ (i, t_{0}| t_{0} + d_{i} > t_{f}) \}$를 생각할 수 있다.
• EDF 정책에 의해 $[0, t_f)$ 사이에는 $R_1$의 요청이 $active$ 한 이상 $R_0-R_1$의 요청을 프로세서에 할당하지 않을 것이다.
• 따라서, $[0, t_f)$ 사이에는 $R_0$과 $R_1$이 정확히 똑같이 동작할 것이며, $(\sigma.R_1)$은 $t_f$에 실패를 보고할 것이다.

$R_1$은 프로세서를 유휴상태로 두지 않음

• 다른 논문에서 많이 증명했으므로 넘어감.

$R_1$의 성질들을 다시 정리해보면 다음과 같다.

• 모든 $(i, t_0) \in R_1$ 은 $t_0 + d_i \le t_f$이다.
• $(\sigma.R_1)$은 $[0, t_f)$에 프로세서를 idle 상태로 두지 않는다.
• $(\sigma.R_1)$은 $t_f$에 단 한번 실패를 보고한다.

이는 $\sum_{(i,t_0) \in R \land t_0 + d_i \le t}e_i > t_f$으로 이어지므로, Lemma 2에 의해 $\tau$가 $not\;feasible$이라는 것이 증명된다.

 

이제 몇몇 $(i, t_0) \in R_1$에 대해 다음을 가정해보자.

• $t_0 \equiv r \mod p_i,\;r \neq 0$
• $\text{each}\;(i, t' <t_0)\in R_1\;\text{is}\;t'\equiv0 \mod p_i$

그러면 우리는 쉽게 다음을 통해, $R_4 = R_1 - \{(i, t_0)\} \bigcup \{(i, q \cdot p_i)\}$ 가 $schedulable$하지 않다는 것을 알 수 있다.

 

이는 우리가 $R_1$을 통해 반복적으로 $R'$을 만들 수 있다는 것을 의미 한다. $\rm{s.t.}$

그리고 이는 $\tau$가 $not\;feasible$이라는 것도 말해준다.

앞으로 $\mathcal{R}=\bigcup^n_{i=1} \bigcup _{k \ge 0}\{(i, k \cdot p_i)\}$이라 정의한다.

Lemma 3
$\tau$ 는 $not\;feasible$하다. $\iff$ $\exists\;t\ge0\;\text{and}\;t \in \mathbb Z$ $\rm s.t.$ $h_{\mathcal{R}}(t) > t$
더 나아가, $h_{\mathcal{R}}(t) > t$를 만족하는 가장 작은 $t$는 $t_f$와 같다.

$h_{\mathcal{R}}$은 $\sum^n_{i=1}e_i \cdot c(i,t)$로 나타낼 수 있고, 여기서 $c(i, t)$는 $t_0 + d_i \le t$를 만족하는 요청 $(i, t_0)$의 개수이다.

• $c(i,t)$는 $k\cdot p_i + d_i \le t$를 만족하는 가장 큰 정수 $k$에 대해 $k+1$로 나타낼 수 있고,
• 이런 정수가 존재하지 않는다면 $0$이 될 것이다.
• 따라서 우리는 $c(i, t) = \max\{0, \left\lfloor\frac{t-d_i}{p_i}\right\rfloor+1\}$임을 알 수 있고,
• $h_{\mathcal{R}} = \sum^n_{i=1}e_i \cdot \max\{0, \left\lfloor\frac{t-d_i}{p_i}\right\rfloor+1\}$로 나타낼 수 있다.

이를 통해 우리는 $\tau$ 가 $feasible$하기 위한 필요충분조건을 도출하였다.
하지만 우리는 $h_{\mathcal{R}} > t$를 만족하는 $t$를 선제적으로 알 수 없고, 다음 세개의 보조정리가 이를 더 유용하게 만들어 줄 것이다.

Lemma 4
$\sum^n_{i=1}e_i/p_i > 1$ 이라면 $\tau$는 $not\;feasible$하다.

Proof

$\sum^n_{i=1}e_i/p_i > 1$라 가정하자. 우리는 $h_{\mathcal{R}} > t$를 만족하는 $t$가 존재함을 보여야 한다.

다음을 만족하는 $t > \max_{1\le i \le n}\{d_i\}$를 설정하자.

$P|t\quad\text{\&}\quad t > -\frac{\sum^n_{i=1}e_i\cdot \left\lfloor\frac{p_i-d_i}{p_i}\right\rfloor}{\sum^n_{i=1}\frac{e_i}{p_i}-1}$

이때 다음이 성립한다.

$\begin{aligned} h_{\mathcal{R}}(t) = &\sum_{i=1}^{n} e_i \cdot \max\{0, \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1\} \\ = &\sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1 \right)\\ = &\sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t + p_i - d_i}{p_i} \right\rfloor \right)\\ = &t \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} + \sum_{i=1}^{n} e_i \cdot \left[ \frac{p_i - d_i}{p_i} \right]\\ = &t \cdot \left(1 + \sum_{i=1}^{n} \frac{e_i}{p_i} - 1 \right) + \sum_{i=1}^{n} e_i \cdot \left[\frac{p_i - d_i}{p_i}\right]\\ =&t + t \cdot \left( \sum_{i=1}^{n} \frac{e_i}{p_i} - 1 \right) + \sum_{i=1}^{n} e_i \cdot \left\lfloor \frac{p_i - d_i}{p_i} \right\rfloor\\ > &t + \frac{-\sum_{i=1}^{n} e_i \left\lfloor\frac{p_i - d_i}{p_i}\right\rfloor}{\sum_{i=1}^{n} \frac{e_i}{p_i} - 1} \cdot \left( \sum_{i=1}^{n} \frac{e_i}{p_i} - 1 \right) + \sum_{i=1}^{n} e_i \cdot \left\lfloor \frac{p_i - d_i}{p_i} \right\rfloor\\ = &t \end{aligned}$

따라서 $h_{\mathcal{R}}(t) > t$ 이다. $\blacksquare$

Lemma 5

$\sum^n_{i=1}e_i/p_i \le 1$이고 $t > \max_{1\le i \le n}\{d_i\}$라면 $h_{\mathcal{R}}(t) > t$ 이다.

Proof
$\sum^n_{i=1}e_i/p_i \le 1$와 $t > \max_{1\le i \le n}\{d_i\}$를 가정하자. 그러면:

$\begin{aligned} h_{\mathcal{R}}(t) + P &= \sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1 \right) + P \\ &\ge \sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1 \right) + P \sum_{i=1}^{n} \frac{e_i}{p_i} \\ &= \sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1 \right) + \sum_{i=1}^{n} e_i \cdot \frac{P}{p_i}\\ &= \sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t +P- d_i}{p_i} \right\rfloor + 1 \right)\\ &=h_{\mathcal{R}}(t+P)\\ &> t+P \end{aligned}$

따라서 $h_{\mathcal{R}}(t+P) > t+P$가 성립하고, $h_{\mathcal{R}}(t) > t$이다. $\blacksquare$

Corollary 1

$\tau$가 $feasible$하지 않고, $\sum^n_{i=1}\frac{e_i}{p_i}\le 1$ 이라면,

$h_{\mathcal{R}}(t) > t$를 만족하는 $t < P + \max_{1\le i \le n}\{d_i\}$가 존재한다.

Lemma 6

$\tau$가 $feasible$ 하지 않고, $\sum^n_{i=1}\frac{e_i} {p_i} < 1$, $h_{\mathcal{R}}(t)>t$라면:

• $t < \max_{1\le i \le n}\{d_i\}$ 또는
• $t < \max_{1\le i \le n}\{p_i-d_i\}\cdot\sum^n_{i=1} \frac{e_i}{p_i}\big/\left(1-\sum^n_{i=1}\frac{e_i}{p_i}\right)$이다.

Proof

$\tau$가 $feasible$ 하지 않고, $\sum^n_{i=1}\frac{e_i} {p_i} < 1$, $h_{\mathcal{R}}(t)>t$이며 $t \ge \max_{1\le i \le n}\{d_i\}$라고 가정하자.
이때, $t < \max_{1\le i \le n}\{p_i-d_i\}\cdot\sum^n_{i=1} \frac{e_i}{p_i}\big/\left(1-\sum^n_{i=1}\frac{e_i}{p_i}\right)$을 증명하면 된다.

$\begin{aligned} h_{\mathcal{R}}(t) &= \sum_{i=1}^{n} e_i \cdot \left( \left\lfloor \frac{t - d_i}{p_i} \right\rfloor + 1 \right)\\ &\le\sum_{i=1}^{n} e_i \cdot \left( \frac{t + p_i - d_i}{p_i} \right) \\ &= t \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} + \sum_{i=1}^{n} \frac{e_i}{p_i} (p_i - d_i)\\ &\le t \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} + \max_{1 \leq i \leq n} \{ p_i - d_i \} \sum_{i=1}^{n} \frac{e_i}{p_i} \end{aligned}$

여기에서 $h_{\mathcal{R}}(t)>t$ 이므로, 위 식은 다음과 같이 정리할 수 있다.

$\begin{aligned} t &< t \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} + \max_{1 \leq i \leq n} \{p_i - d_i\} \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} &\equiv\\ t\left(1-\sum^n_{i=1}\frac{e_i}{p_i}\right) &< \max_{1 \leq i \leq n} \{p_i - d_i\} \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} &\equiv\\ t &< \max \{ p_i - d_i \}_{1 \leq i \leq n} \cdot \frac{\sum_{i=1}^{n} e_i}{p_i}{\bigg/ \left( 1 - \sum_{i=1}^{n} \frac{e_i}{p_i} \right)}. &\blacksquare \end{aligned}$

Lemma 3,4,5,6과 Corollary 1에 의해서 다음이 성립한다.

Theorem
$\sum^n_{i=1}\frac{e_i}{p_i}=c$이고, $\tau$ 가 $feasible$하지 않다는 것은 다음과 동치이다.

1. $c>1$ 또는
2. $h_{\mathcal{R}}(t)>t$를 만족하는 정수 $t < min\left\{P+\max_{1\le i \le n}\{d_i\}, \frac{c}{1-c}\max_{1\le i \le n}\{p_i-d_i\}\right\}$가 존재한다.

Corollary 2
Sporadic task system의 $feasibility$ 검사는 $co$-$\rm NP$이다.

Proof

• 정수 $t < P+\max_{1\le i \le n}\{d_i\}$는 비결정론적 다항시간에 추측될 수 있으며,
• 반례로 사용되는 $t$는 시스템 파라미터에 대해 다항한 범위 내에 있고,
• $h_{\mathcal{R}}(t)>t$ 또는 $\sum^n_{i=1}\frac{e_i}{p_i}>1$을 검증하는 것은 결정론적 다항시간에 달성할 수 있다. $\blacksquare$

An algorithm for feasibility testing

본 논문에서 제시하는 알고리즘은 반복적으로 $h_{\mathcal{R}}(t)>t$ 를 만족하는 양수 $t$를 찾는다.

시뮬레이션은 $h_{\mathcal{R}}(t)$ 을 계산하는 것으로 대체된다.

알고리즘을 소개하기 전, 알고리즘을 좀 더 향상시킬 수 있는 결과를 제시한다.

Lemma 7

$\sum^n_{i=1}\frac{e_i}{p_i}\le 1$ 이고, 모든 $1 \le i \le p_i$에 대해 $d_i\ge p_i$라면 $\tau$는 $feasible$하다.

Proof

$\sum^n_{i=1}\frac{e_i}{p_i}\le 1$이고, 모든 $1 \le i \le p_i$에 대해 $d_i\ge p_i$라고 가정하자.

우리는 모든 정수 $t \ge 0$에 대해 $h_{\mathcal{R}}(t)\le t$를 보이면 된다.

$\begin{aligned} h_{\mathcal{R}}(t) &= \sum^n_{i=1} e_i \cdot \max \left\{0, \left\lfloor\frac{t-d_i}{p_i}\right\rfloor+1\right\}\\ &\le \sum_{i=1}^{n} e_{i} \cdot \left\lfloor \frac{t}{p_{i}} \right\rfloor \\ &\le t \cdot \sum_{i=1}^{n} \frac{e_i}{p_i} \\ &\le t &\blacksquare \end{aligned}$

bool isFeasible(Taskset tau) {
  c = sum(e[i] / p[i])
  if (c > 1) 
    return false; // Lemma 4
  if (d[i] > p[i] for i in 1..n) 
    return true; // Lemma 7

  P = lcm{p[1]..p[n]};
  D = max{d[1]..d[n]};
  M = P + D;

  T = (c==1) ? M : min{M, c/1-c * max{p[i] - d[i]}};
  H = 0; // h_R(t)

  for(t in 1..T) {
    for(i in 1..n )
      if(t >= d[i] && t % p[i] = d[i])
        H += e[i];
    // H is now h_R(t)
    if (H > t)
      return false;
  }
  return true;
}

Theorem 2

1. 만약 $\sum^n_{i=1}\frac{e_i}{p_i}>1$ 이라면 위 알고리즘은 선형 시간에 동작한다.
2. 만약 $\bigwedge^n_{i=1}d_i \ge p_i$라면 위 알고리즘은 선형 시간에 동작한다.
3. $c<1$라면 위 알고리즘은 $O(n\cdot \max_{1\le i \le n}\{p_i-d_i\})$ 에 동작한다.
4. 위 상황들에 모두 해당하지 않는다면 알고리즘은 지수 시간 $O(n\cdot \left(P+\max_{1\le i \le n}\{p_i-d_i\}\right))$ 에 동작한다. $\blacksquare$