The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior

• 제시한 문제 → 일반적으로 Rate-Monotonic algorithm의 경우 utilization bond가 $n(2^{(1/n)}-1)$ 라고 알려져 있으나, 실제로 실험을 해보면 average case의 utilization은 90% 정도를 상회한다.
• 문제를 해결하고자 접근한 방향 → 임의의 randomly generated large task set을 정의하고, 그로부터 utilization bound를 구해냄

---

Definitions

• a.s. → almost surely
• breakdown utilization → 어느 task라도 deadline을 놓치게 되는 순간의 utilization

Introduction

• Fixed priority algorithm 을 사용하는 경우 RM (Rate-Monotonic) 알고리즘이 최적이라고 알려져 있음

• 그러나 worst-case 의 경우 RM의 utilization bound → $n(2^{(1/n)}-1)$

  • $n=2$일 때 $.83$
  • $n \rightarrow \infin$ 일 때 $.693$

• Dynamic priority algorithm 을 사용하는 경우에는 nearest deadline algorithm(EDF)이 최적이라고 알려져 있음

  • worst-case utilization bound → 1.0

• 단순 성능만 보면 굳이 RM을 사용할 이유가 없지만, RM은 practical한 측면에서 장점이 많음

  1. 일시적으로 오버로드가 왔을 때에도 대부분의 중요한 job들이 수행될 수 있음을 보장함

  2. periodic한 task의 deadline을 맞추면서도 비주기적인 task에 대해 빠른 response time을 요구할 수 있다.

     • aperiodic task는 RM 알고리즘에서 어떻게 priority가 계산되지?

  3. task synchronization requirements을 다룰 수 있게끔 알고리즘을 수정할 수도 있음

  4. 부정확한 computation이 있을 때도 task를 scheduling할 수 있음

  5. 구현하기 쉬움

     ⇒ provides approach to system-wide timing integration

• 그리고 실제로 실험해보다 large task set에 RM을 적용해도 $.90$ 정도의 utilization을 얻을 수 있음

• 대체로 average case가 worst case보다 훨씬 낫다는 것을 확인할 수 있음

Problem Formulation

• a set of periodic task $\tau_1, \ldots , \tau_n$ 개가 있으며, $\tau_i$는 period $T_i$, computation requirements $C_i$, phasing relative to 0 $I_i$ ($0\le I_i < T_i$) 를 가진다.

• the job initiated at time $I_i+kT_i$는 $I_i+(k+1)T_i$ 이전까지 수행완료 되어야하며, $T_1\le T_2 \le \dots \le T_n$이다.

• 가장 worst case는 $I_i=0$ for $1\le i\le n$ (critical instant)

  • 이 상황에서 모든 task들의 첫번째 job이 모두 deadline 내에 실행될 수 있다면 task set은 schedulable함

• the cumulative demands over $[0,t]$ → $W_i(t)=\sum_{j=1}^{i}C_j\cdot \lceil t/T_j \rceil$

• $L_i(t) = W_i(t)/t$ → $W_i(t)$를 단위시간으로 나눈 것 (당연히 1 넘으면 non-schedulable)

• $L_i=\min_{\{0<t\le T_i\}}L_i(t)$

• $L=\max_{\{1\le i \le n\}}L_i$

Theorem 1. Given periodic tasks $\tau_1, \ldots , \tau_n$
(1) $\tau_i$ can be scheduled for all task phasings using the rate monotonic algorithm iff $L_i \le 1$
(2) The entire task set can be scheduled for all task phasings using the rate monotonic algorithm iff $L \le 1$

[Proof 1] worst case phasing에서 scheduling한다고 가정 → 모든 task $\tau$는 동시에 0에서 첫번째 job 시작

1. task $\tau_i$는 자기보다 낮은 task들을 preemption하고 더 높은 task들에게 preempt당함 → 제일 priority 낮은 애만 확인해주면 됨
2. 프로세서는 task $\tau_i$의 첫번째 job을 수행하던지 deadline miss가 나기 전까지 IDLE하지 않음

⇒ 주어진 time t에 task들이 완료되려면 $W_i(t)=t$이고, $W_i(s)>s$ for $0\le s<t$

The entire task set is schedulable iff each of the tasks is scheduable

• continuous variable $t \in [0, T_i]$ 에 대해 $L$을 최소화 해야함

• function $L_i(t)$의 특성상 piecewise monotocially decresing하지만 중간중간에 값이 갑자기 커지는 부분이 있음 (task release되는 순간)

• 이 local minimum point들만 확인해주면 $L_i$ 을 찾을 때 연속적인 공간을 다 보지 않아도 됨

  ⇒ $L_i=\min_{\{t\in S_i\}}L_i(t)$ where $S_i = \{k\cdot T_j|j=1,\ldots, i;k=1,\ldots,\lfloor\frac{T_i}{T_j} \rfloor \}$

• 여기에서 가장 작은 값 하나만 확인해도 되는 이유?

  • 특정 $S_i$에 대해서 조건을 만족한다면 그 시간 전에 내 task가 수행완료됨
  • 내 task가 수행 완료면 나보다 높은 priority는 모두 수행 완료됨

Theorem 2. Given periodic tasks $\tau_1, \ldots , \tau_n$
(1) $\tau_i$ can be scheduled for all task phasings using the rate monotonic algorithm iff $L_i = \min_{\{t \in S_i\}}W_i(t)/t \le 1$
(2) The entire task set is schedulable for all task phasings using the rate monotonic algorithm iff $L = \max_{\{1\le i\le n\}}L_i \le 1$

Stochastic Characterization

• randomly하게 task를 만들어보고 이 average case들이 processor를 fully utilize하는 레벨 확인하기
• Cumulative Distribution Function (c.d.f.) $F_T(t)$ for the task periods and c.d.f. $F_C(c)$ for the task computation requirements
• 두 c.d.f.에서 n개씩의 sample을 추출한 후 $T_1\le T_2 \le \dots \le T_n$ 으로 이름을 붙이면 n개의 pair 정의할 수 있음.
• $C_is$ 와 $T_is$를 relative한 값이라고 생각하고, $C_is$에 small factor $\Delta$를 곱해서 utilization을 높일 수 있다고 하자.
  • $\Delta$는 threshold value $\Delta^*$까지 높일 수 있고, 그 이상 올리면 알고리즘은 job의 deadline을 놓치게 된다.
  • 이때의 breakdown utilization → $U_n^*$

$L=max_{\{1\le i \le n\}}\min_{\{t\in S_i\}}\sum_{j=1}^{i}\Delta\cdot\lfloor t/T_j \rfloor / t \le 1\ \ \ \rightarrow \ \ \ \Delta\le [max_{\{1\le i \le n\}}\min_{\{t\in S_i\}}\sum_{j=1}^{i}\Delta\cdot\lfloor t/T_j \rfloor / t]^{-1}$

⇒ $\Delta^* = [max_{\{1\le i \le n\}}\min_{\{t\in S_i\}}\sum_{j=1}^{i}\Delta\cdot\lfloor t/T_j \rfloor / t]^{-1}$

이 경우의 break utilization은 $U_n^* = [\sum_{i=1}^{n}U_i]/max_{\{1\le i \le n\}}\min_{\{t\in S_i\}}W_i(t)/t$ where $U_i = C_i/T_i$

numerator $\sum_{i=1}^{n}\frac{C_i}{T_i}$ 부분은 전체 task set의 total utilization 부분이고, i가 클수록 나중에 scaling factor가 커질때 deadline miss가 나기 쉬운 task

→ 왜???

Theorem 3. Suppose $1\le\tau_1\le \ldots \le \tau_n\le 2$ .
Then $U_n^* = [\sum_{i=1}^{n}\frac{C_i}{T_i}] / \min_{\{t\in S_n\}}\sum_{j=1}^{n}C_j\cdot\lceil \frac{t}{T_j} \rceil / t$

[Proof 3] $\delta_i = \min_{\{t\in S_n\}}\sum_{j=1}^{n}C_j\cdot\lceil \frac{t}{T_j} \rceil / t$ 이라고 했을 때, $\delta_i$의 최솟값은 반드시 $T_j, 1\le j\le i$에서 발생하게 된다.

• $S_i$의 정의-$k\cdot T_j$-나 주어진 조건에 의해 $\lfloor \frac{T_n}{T_1} \rfloor = 1$이니까

모든 i에 대해서 $\delta_i\le \delta_{i+1}$ → $\delta_i\le \delta_n$ 임

Asymptotic Approximation

• 지금까지 구한 breakdown utilization $U_n^*$은 $C_is$와 $T_is$로 만들어진 일종의 random variable

• random variable들이 bound를 가지기 때문에 $U_n^*$도 bound를 구할 수 있지 않을까?

• 수식을 끌어내는 내용을 완전히 이해하지는 못했지만, task set size $n$이 증가하면 $U_n^*$은 특정 상수로 수렴하게 된다.

• 이 특정상수는 $F_T$에만 영향을 받으며, $F_C$는 영향을 주지 못한다. (n이 커지면 점근적으로 버려짐)

• 사실 break down utilization을 만드는 것 자체가 computation time $C_i$ 들에 일정한 $\Delta$를 schedulable하지 않을때까지 곱하는 것이었기 때문에, 정말 큰 task set이 있다고 할 때 중요한 것은 period들이지 computation time이 아닐 것 같기는 하다.

• 그냥 computation time은 breakdown 되기 직전까지 계속 곱해주면 되니까

Questions

• generate된 임의의 task를 가지고 계산한 결과 → 실제로 worst case 까지 커버할 수 있나 ?
  • realtime scheduling이면 무조건 deadline안으로 맞추는게 중요하니까 worst-case를 상정하는게 아니었나?
• 실제 task들이 randomly / uniformly distributed 되어있나? 다른 확률분포를 따르지는 않나 ? - asymptotically하게 보내서 상관없나?
  • 큰수의 법칙
• 주어진 task들을 generate한건 어떤 cdf 기반인거지? - monotonic하다는 말밖에 없는거 같은데
• 실제로 scheduling algorithm이 고려하는 task의 개수는 몇 개 정도 되지?