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

haejoo·2021년 3월 15일
0
  • 제시한 문제 → 일반적으로 Rate-Monotonic algorithm의 경우 utilization bond가 n(2(1/n)1)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^{(1/n)}-1)

    • n=2n=2일 때 .83.83
    • nn \rightarrow \infin 일 때 .693.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.90 정도의 utilization을 얻을 수 있음

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

Problem Formulation

  • a set of periodic task τ1,,τn\tau_1, \ldots , \tau_n 개가 있으며, τi\tau_i는 period TiT_i, computation requirements CiC_i, phasing relative to 0 IiI_i (0Ii<Ti0\le I_i < T_i) 를 가진다.

  • the job initiated at time Ii+kTiI_i+kT_iIi+(k+1)TiI_i+(k+1)T_i 이전까지 수행완료 되어야하며, T1T2TnT_1\le T_2 \le \dots \le T_n이다.

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

    • 이 상황에서 모든 task들의 첫번째 job이 모두 deadline 내에 실행될 수 있다면 task set은 schedulable함
  • the cumulative demands over [0,t][0,t]Wi(t)=j=1iCjt/TjW_i(t)=\sum_{j=1}^{i}C_j\cdot \lceil t/T_j \rceil

  • Li(t)=Wi(t)/tL_i(t) = W_i(t)/tWi(t)W_i(t)를 단위시간으로 나눈 것 (당연히 1 넘으면 non-schedulable)

  • Li=min{0<tTi}Li(t)L_i=\min_{\{0<t\le T_i\}}L_i(t)

  • L=max{1in}LiL=\max_{\{1\le i \le n\}}L_i

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

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

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

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

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

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

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

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

    Li=min{tSi}Li(t)L_i=\min_{\{t\in S_i\}}L_i(t) where Si={kTjj=1,,i;k=1,,TiTj}S_i = \{k\cdot T_j|j=1,\ldots, i;k=1,\ldots,\lfloor\frac{T_i}{T_j} \rfloor \}

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

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

Theorem 2. Given periodic tasks τ1,,τn\tau_1, \ldots , \tau_n
(1) τi\tau_i can be scheduled for all task phasings using the rate monotonic algorithm iff Li=min{tSi}Wi(t)/t1L_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{1in}Li1L = \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.) FT(t)F_T(t) for the task periods and c.d.f. FC(c)F_C(c) for the task computation requirements
  • 두 c.d.f.에서 n개씩의 sample을 추출한 후 T1T2TnT_1\le T_2 \le \dots \le T_n 으로 이름을 붙이면 n개의 pair 정의할 수 있음.
  • CisC_isTisT_isrelative한 값이라고 생각하고, CisC_is에 small factor Δ\Delta를 곱해서 utilization을 높일 수 있다고 하자.
    • Δ\Delta는 threshold value Δ\Delta^*까지 높일 수 있고, 그 이상 올리면 알고리즘은 job의 deadline을 놓치게 된다.
    • 이때의 breakdown utilization → UnU_n^*

L=max{1in}min{tSi}j=1iΔt/Tj/t1      Δ[max{1in}min{tSi}j=1iΔt/Tj/t]1L=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}

Δ=[max{1in}min{tSi}j=1iΔt/Tj/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은 Un=[i=1nUi]/max{1in}min{tSi}Wi(t)/tU_n^* = [\sum_{i=1}^{n}U_i]/max_{\{1\le i \le n\}}\min_{\{t\in S_i\}}W_i(t)/t where Ui=Ci/TiU_i = C_i/T_i

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

→ 왜???

Theorem 3. Suppose 1τ1τn21\le\tau_1\le \ldots \le \tau_n\le 2 .
Then Un=[i=1nCiTi]/min{tSn}j=1nCjtTj/tU_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] δi=min{tSn}j=1nCjtTj/t\delta_i = \min_{\{t\in S_n\}}\sum_{j=1}^{n}C_j\cdot\lceil \frac{t}{T_j} \rceil / t 이라고 했을 때, δi\delta_i의 최솟값은 반드시 Tj,1jiT_j, 1\le j\le i에서 발생하게 된다.

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

모든 i에 대해서 δiδi+1\delta_i\le \delta_{i+1}δiδn\delta_i\le \delta_n

Asymptotic Approximation

  • 지금까지 구한 breakdown utilization UnU_n^*CisC_isTisT_is로 만들어진 일종의 random variable

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

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

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

  • 사실 break down utilization을 만드는 것 자체가 computation time CiC_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의 개수는 몇 개 정도 되지?
profile
대학원생 전해주의 우당탕탕 공부일상

0개의 댓글