Periodic Resource Model for Compositional Real-Time Guarantees

haejoo·2021년 3월 22일
1
post-thumbnail

지금까지 읽었던 real time system 관련 논문 중에서는 읽는 데 가장 오래 걸렸던 것 같다. scheduling model의 periodic capacity bound를 구하고 이를 기반으로 single periodic workload로 추상화하는 개념이 신기했다. 역시 똑똑한 사람은 정말 많다..


Introduction

  • scheduling model은 보통 3가지의 요소로 이루어져있음
    1. a resource model
    2. a scheduling algorithm
    3. a workload model
  • hierarchical scheduling interface model I(GS,GD)I(G_S, G_D)
    • GSG_S : real-time guarantee that parent node supplies to the child node
    • GDG_D : real-time guarantee that child node demands to the parent node
    • desirable to have following properties
      1. independence → 다른 스케쥴링 모델이랑 독립적으로 분석되어야함
      2. separation → parent scheduling model이랑 chlid scheduling model이 분리되고 interface model을 통해서만 interact할 수 있음
      3. universality → 아무 scheduling algorithm이나 scheduling model에서 사용할 수 있음
      4. compositionality → parent scheduling model의 timing guarantee가 만족 iff framework 내 child scheduling model의 timing guarantee도 만족

System model and Problem Statement

  • Scheduling algorithm MM(W,R,A)(W, R, A)
    • WW → workload model - L&L tasks (period, execution time)
    • RR → resource model - partitioned resource model
    • AA → scheduling algorithm - RM / EDF
    • scheduling algorithm MM is said to be scheduable if WW is schedulable under AA with RR
  • Periodic Resource Model Γ(Π,Θ)\Gamma(\Pi, \Theta)Π\Pi time unit마다 Θ\Theta time unit만큼 리소스 쓸 수 있다고 개런티
    1. Exact schedulability : necessary and sufficient 하게 schedulable하지 않은지 확인 가능해야함
    2. Periodic capacity bound : scheduling algorithm M에서 schedulable smallest possible periodic capacity bound를 (Θ/Π)(\Theta^* / \Pi) 라고 했을 때 ΘΘ\Theta \ge \Theta^* 여야함
    3. Utilization bound : the largest possible utilization bound UBUB(TiWeipi\ge \sum_{T_i\in W}\frac{e_i}{p_i})를 찾아야 함
    4. Algorithm set : a set of algorithms A\mathcal{A}( has schedulable algorithm AA) 찾기
    5. Compositional guarantee : parant scheduling이 schedulable하다면, iff 그를 구성하는 n개의 child model도 schedulable하다.

Periodic Resource Model

  • periodic resource model Γ(Π,Θ)\Gamma(\Pi, \Theta) → 매 Π\Pi 시간마다 Θ\Theta 시간 만큼의 resource allocation 보장
    • Γ(k,k)\Gamma(k, k)는 항상 이용가능한 dedicated resource라는 의미 (kk 시간마다 kk시간 만큼 가능하다는거니까)

✔ Resource supply
→ the amount of resource allocations that the resource provides

  • minimum resource supply bound function sbfΓ(t)=t(ΠΘ)ΠΘ+ϵs\mathbf{sbf}_\Gamma(t) = \lfloor \frac{t-(\Pi-\Theta)}{\Pi}\rfloor \cdot\Theta + \epsilon_s
    • where ϵs=max(t(ΠΘ)t(ΠΘ)Π(ΠΘ),0)\epsilon_s = \max(t-(\Pi-\Theta) - \lfloor \frac{t-(\Pi-\Theta)}{\Pi}\rfloor -(\Pi-\Theta), 0)
  • linear supply bound function (lower bound of sbfΓ(t)\mathbf{sbf}_\Gamma(t)) lsbfΓ(t)=ΘΠ(t2(ΠΘ))sbfΓ(t)\mathbf{lsbf}_\Gamma(t) = \frac\Theta\Pi (t-2\cdot(\Pi-\Theta)) \le \mathbf{sbf}_\Gamma(t)

✔ Service time
→ the duration that it takes for the resource to provide a resource supply

  • maximum service time bound function (for tt time unit supply) tbfΓ(t)=(ΠΘ)+ΠtΘ+ϵt\mathbf{tbf}_\Gamma(t) = (\Pi-\Theta) +\Pi \cdot \lfloor \frac{t}{\Theta}\rfloor + \epsilon_t
    • where ϵs={ΠΘ+tΠtΘif (tΘtΘ>0)0otherwise\epsilon_s = \begin{cases} \Pi-\Theta+ t -\Pi \lfloor \frac{t}{\Theta}\rfloor &\text{if ($t-\Theta \lfloor\frac t\Theta \rfloor > 0$)}\\ 0 &\text{otherwise} \end{cases}
  • linear service time bound function (upper bound of tbfΓ(t)\mathbf{tbf}_\Gamma(t)) ltbfΓ(t)=ΠΘt+2(ΠΘ)tbfΓ(t)\mathbf{ltbf}_\Gamma(t) = \frac\Pi\Theta \cdot t+2(\Pi-\Theta) \ge \mathbf{tbf}_\Gamma(t)

Schedulability Analysis

  • 이 장에서는 scheduling model M(W,Γ,A)M(W, \Gamma, A)이 주어졌을 때 이 scheduling model이 schedulable한지 확인한다.

Schedulability Analysis under EDF Scheduling

✔ Resource demand
→ the amount of resource allocation that the workload set requests

  • maximum resource demand bound function (of time interval length tt under EDF) dbfW(t)=TiWtpiei\mathbf{dbf}_W(t) = \displaystyle \sum_{T_i\in W} \lfloor \frac{t}{p_i} \rfloor \cdot e_i
  • linear demand bound function (upper bound of dbfW(t)\mathbf{dbf}_W(t)) ldbfW(t)=UWtdbfW(t)\mathbf{ldbf}_W(t) = U_W \cdot t \ge \mathbf{dbf}_W(t) where UWU_W is utilization of the workload set WW
  • dedicated resource라고 할 때, hyperperiod에서의 resource demand ≤ the length of the time interval이면 schedulable 하다.
    • 여기에서 t time에 대한 resource demand는 변하지 않지만 partitioned resource를 표현하기 위해서 우변이 바뀔 필요가 있음
    • 아까 구해뒀던 sbfΓ(t)\mathbf{sbf}_\Gamma(t) -minimum resource supply bound function-로 우변을 바꿀 수 있음

Theorem 1. For a given scheduling model M(W,Γ,EDF)M(W, \Gamma, \text{EDF}), MM is schedulable iff the resource demand of WW during a time interval is no greater than the resource supply of Γ\Gamma during the same time interval for all time interval during a hyperperiod, i.e., 0<t2LCMW:dbfW(t)sbfΓ(t)\forall 0 < t \le 2 \cdot \text{LCM}_W : \mathbf{dbf}_W(t) \le \mathbf{sbf}_\Gamma(t).

Schedulability Analysis under Fixed-Priority Scheduling

  • scheduling model M(W,Γ(1,1),FP)M'(W, \Gamma(1,1), \text{FP}) -dedicated resource- 에 대해서 MM'은 iff WCRT(Worst-Case Response Time) ≤ its relative deadline 일 때 schedulable하다.
  • rir_i의 WCRT는 나보다 더 높은 priority들이 전부 동시에 들어오는 critical instant에 발생한다. rir_i를 구하는 iterative algorithm ↓
    • ri(k)=ei+TkHP(W,T)rik1pkek   where Tk=(pk,ek)r_i^{(k)} = e_i + \displaystyle \sum_{T_k\in \text{HP}(W, T)} \lfloor \frac {r_i^{k-1}}{p_k} \rfloor \cdot e_k \text{\ \ \ where }T_k = (p_k, e_k)
    • (dedicated resource 상황-tt time의 resource supply를 얻기위한 service duration이 t time-에서) 나보다 높은 priority(HP\text{HP})에 의해 preemption되는 시간을 반복적으로 구하는 알고리즘이다.
  • periodic partitioned resource Γ(Π,Θ)\Gamma(\Pi, \Theta)을 고려한 WCRT를 구하는 식을 구하면
    • ri(k)(Γ)=tbfΓ(Ii(k))r_i^{(k)}(\Gamma)=\mathbf{tbf}_\Gamma(I_i^{(k)}) where Ii(k)=ei+TkHP(W,T)ri(k1)(Γ)pkekI_i^{(k)} = e_i + \displaystyle \sum_{T_k \in \text{HP}(W, T)} \lceil \frac{r_i^{(k-1)}(\Gamma)}{p_k} \rceil \cdot e_k

Theorem 2. For a given scheduling model M(W,Γ,FP)M(W, \Gamma, \text{FP}), where FP\text{FP} is a fixed-priority algorithm, MM is schedulable iff TiW:ri(Γ)pi, where Ti=(pi,ei)\forall T_i \in W : r_i(\Gamma) \le p_i, \ \text{where}\ T_i=(p_i, e_i).

Schedulability Bounds

Periodic Capacity Bounds

  • periodic resource Γ(Π,Θ)\Gamma(\Pi, \Theta)의 periodic capacity CΓC_\GammaΘ/Π\Theta / \Pi 로 정의할 수 있음
  • 그러면 periodic capacity bound PCBW(Π,A)ΘΠ\text{PCB}_W(\Pi, A) \le \frac \Theta \Pi 을 만족할 때 schedulable한 PCBW\text{PCB}_W를 정의할 수 있다.
  • single periodic workload T(p,e)T(p,e)p=Πp=\Pi, e=ΠPCBW(Π,A)e=\Pi\cdot\text{PCB}_W(\Pi, A)로 추상화할 수 있다..

✔ Periodic Capacity Bound for EDF scheduling

Theorem 3. For a given periodic workload set WW under EDF\text{EDF} scheduling algorithm, the optimal(minimum) periodic capacity bound PCBW(Π,EDF)\text{PCB}_W^*(\Pi, \text{EDF}) of a period is
PCBW(Π,EDF)=ΘΠPCB_W^*(\Pi, \text{EDF}) = \frac{\Theta^*}{\Pi} where Θ\Theta^* is smallest possible Θ\Theta satisfying 0<t2LCMW:dbfW(t)sbfΓ(t)\forall 0<t \le 2 \cdot \text{LCM}_W : \mathbf{dbf}_W(t) \le \mathbf{sbf}_\Gamma(t)
A scheduling model M(W,Γ(Π,Θ),EDF)M(W, \Gamma(\Pi, \Theta), \text{EDF}) is schedulable iff PCBW(Π,EDF)CΓPCB_W^*(\Pi, \text{EDF}) \le C_\Gamma.

Theorem 4. For a given periodic workload set WW under EDF\text{EDF} scheduling algorithm, a periodic capacity bound PCBW(Π,EDF)\text{PCB}_W(\Pi, \text{EDF}) of a resource period Π\Pi is
PCBW(Π,EDF)=Θ+ΠPCB_W(\Pi, \text{EDF}) = \frac{\Theta^+}{\Pi} where Θ+=max0<t2LCMw((t2Π)2+8ΠdbfW(t)(t2Π)4)\Theta^+ = \displaystyle \max_{0<t\le 2\text{LCM}_w} (\frac{\sqrt{(t-2\Pi)^2 + 8\Pi\mathbf{dbf}_W(t)}-(t-2\Pi)}{4})

  • dbfW(t)lsbfΓ(t)=ΘΠ(t2Π+2Θ)sbfΓ(t)\mathbf{dbf}_W(t) \le \mathbf{lsbf}_\Gamma(t) = \frac \Theta \Pi(t - 2\Pi + 2\Theta) \le \mathbf{sbf}_\Gamma(t) 이므로 근의 공식을 이용해 최소 Θ\Theta의 값을 찾을 수 있다.

✔ Periodic Capacity Bound for RM scheduling

Theorem 5. For a given periodic workload set WW under RM\text{RM} scheduling algorithm, the optimal(minimum) periodic capacity bound PCBW(Π,EDF)\text{PCB}_W^*(\Pi, \text{EDF}) of a resource period Π\Pi for a periodic partition resource Γ\Gamma isPCBW(Π,RM)=ΘΠPCB_W^*(\Pi, \text{RM}) = \frac{\Theta^*}{\Pi} where Θ\Theta^* is smallest possible Θ\Theta satisfying TiW:ri(Γ)pi, where Ti=(pi,ei)\forall T_i \in W : r_i(\Gamma) \le p_i, \ \text{where}\ T_i=(p_i, e_i).
A scheduling model M(W,Γ(Π,Θ),RM)M(W, \Gamma(\Pi, \Theta), \text{RM}) is schedulable iff PCBW(Π,RM)CΓPCB_W^*(\Pi, \text{RM}) \le C_\Gamma.

Theorem 6. For a given periodic workload set WW under RM\text{RM} scheduling algorithm, a periodic capacity bound PCBW(Π,RM)\text{PCB}_W(\Pi, \text{RM}) of a resource period Π\Pi for a periodic partition resource Γ\Gamma is
PCBW(Π,RM)=Θ+ΠPCB_W(\Pi, \text{RM}) = \frac{\Theta^+}{\Pi} where Θ+=maxTiW((pi2Π)+(pi2Π)2+8ΠIi4)\Theta^+ = \displaystyle \max_{\forall T_i \in W} (\frac{-(p_i - 2\Pi)+\sqrt{(p_i-2\Pi)^2 + 8\Pi I_i}}{4}), where Ii=ei+TkHP(W,T)pipkek\displaystyle I_i = e_i + \sum_{T_k \in \text{HP}(W, T)}\lfloor \frac{p_i}{p_k} \rfloor \cdot e_k

  • TiW:ltbfΓ(Ii)=ΠΘIi+2(ΠΘ)pi\forall T_i \in W : \mathbf{ltbf}_\Gamma(I_i) = \frac \Pi \Theta \cdot I_i + 2(\Pi-\Theta) \le p_i 이므로 마찬가지로 근의 공식을 이용해 최소 Θ\Theta의 값을 찾을 수 있다.

Utilization Bounds

  • 위에서 구했던 periodic capacity처럼, periodic resource Γ\Gamma에 대해 아래의 조건을 만족해야 schedulable한 utilization bound UBΓ(A)\text{UB}_\Gamma (A)를 정의할 수 있다.
    • TiWeipiUBΓ(A)\displaystyle \sum_{T_i \in W} \frac{e_i}{p_i} \le \text{UB}_\Gamma(A)

✔ Utilization Bound for EDF scheduling

  • partitioned resource에서 workload set의 utilization은 periodic capacity보다 커서는 안됨
    • i.e. UWCΓ=ΘΠU_W \le C_\Gamma = \frac \Theta \Pi
  • 아까 구해뒀던 linear resource demand bound function ldbfW(t)=UWt\mathbf{ldbf}_W(t)=U_W\cdot t와 linear resource supply bound function lsbfΓ(t)=ΘΠ(t2(ΠΘ))\mathbf{lsbf}_\Gamma(t)=\frac \Theta \Pi (t-2\cdot(\Pi-\Theta))
  • M(W,Γ(Π,Θ),EDF)M(W, \Gamma(\Pi, \Theta), \text{EDF})가 schedulable하려면 ldbfW(t)\mathbf{ldbf}_W(t)의 기울기 ≤ lsbfΓ(t)\mathbf{lsbf}_\Gamma(t)의 기울기여야함 (UWΘΠ\because U_W \le \frac \Theta \Pi)

  • interval length가 일정 값 이상으로 커지면, 그 값 이상에 대해서는 위의 대소관계가 항상 성립함을 알 수 있다.

Theorem 7. Given a periodic resource Γ(Π,Θ)\Gamma(\Pi, \Theta), a utilization bound UBΓ(EDF)\text{UB}_\Gamma(\text{EDF}) of the EDF\text{EDF} algorithm for a periodic workload set WW is UBΓ(EDF)=ΘΠ(12(ΠΘ)p)\text{UB}_\Gamma(\text{EDF})=\displaystyle \frac \Theta \Pi (1-\frac {2(\Pi-\Theta)} {p^*}) where pp^* is the smallest period in the workload set WW.

✔ Utilization Bound for RM scheduling

Theorem 8. Given a periodic resource Γ(Π,Θ)\Gamma(\Pi, \Theta), a utilization bound UBΓ(RM)\text{UB}_\Gamma(\text{RM}) of the RM\text{RM} algorithm for a set of m periodic workload is UBΓ(RM)=ΘΠ(m(2m1)2m(ΠΘ)p)\text{UB}_\Gamma(\text{RM})=\displaystyle \frac \Theta \Pi (m(\sqrt[m]2 -1)- \frac {\sqrt[m]2 (\Pi-\Theta)} {p^*}) where pp^* is the smallest period in the workload set WW.

Compositional Real-Time Guarantees & Conclusions

Definition. Given multiple scheduling models M1,,MnM_1, \ldots, M_n, we derive a scheduling model MP(WP,ΓP,AP)M_P(W_P, \Gamma_P, A_P) from M1,,MnM_1, \ldots, M_n as follows.
1. we assume that APA_P and ΠP\Pi_P are given
2. we derive WPW_P by simply mapping the resource model of a child scheduling model Γi(Πi,Θi)\Gamma_i(\Pi_i, \Theta_i) to its periodic task Ti(pi,ei)T_i(p_i, e_i) such that WP={T1(Π1,Θ1),,Tn(Πn,Θn)}W_P = \{T_1(\Pi_1, \Theta_1), \ldots, T_n(\Pi_n, \Theta_n)\}.
3. we first derive PCBWP(ΠP,AP)\text{PCB}^*_{W_P}(\Pi_P, A_P) according to Theorem 3 or Theorem 5 depending on APA_P. If PCBWP(ΠP,AP)\text{PCB}^*_{W_P}(\Pi_P, A_P) is derived, we then compute ΘP\Theta_P such that ΘP=ΠPPCBWP(ΠP,AP)\Theta_P = \Pi_P\cdot \text{PCB}^*_{W_P}(\Pi_P, A_P).

Theorem 9. Given multiple scheduling models M1,,MnM_1, \ldots, M_n that are individually schedulable, we derive a scheduling model MP(WP,ΓP,AP)M_P(W_P, \Gamma_P, A_P) from M1,,MnM_1, \ldots, M_n according to the composition method in above Definition. Then, we construct a hierarchical schduling framework HH such that MPM_P is a parent scheduling model of M1,,MnM_1, \ldots, M_n. HH supports the compositional real-time guarantees such that MPM_P is schedulable, iff M1,,MnM_1, \ldots, M_n are schedulable in the framework.

  • Π\Pi time마다 최소 Θ\Theta time만큼 사용할 수 있는 partitioned resource를 가진 scheduling model을 주기 Π\Pi마다 execution time이 Θ\Theta인 하나의 task로 추상화
profile
대학원생 전해주의 우당탕탕 공부일상

2개의 댓글

comment-user-thumbnail
2021년 3월 23일

잘 보고 갑니다 ㅎㅎ 흥미로운 내용이네요 앞으로도 많은 포스팅 부탁드려요

1개의 답글