Resource Partition for Real-Time Systems

haejoo·2021년 3월 17일
0

원래 읽으려고 했던 논문 (Periodic Resource Model for Compositional Real-Time Guarantees)을 읽다가 resource model 부분이 너무 이해가 안 가서 레퍼런스 중에서 기본 notation을 가장 자세히 설명한 논문을 따로 가져왔다. 그리고 이 논문에서 제안하는 method (bounded-delay resource partition model)은 훑기만 하고 가져오지는 않았다.

원래 읽어야할 논문은 아니다보니 나오는 definition들이나 theorem 정도만 쭉 적으면서 이해했는데 거의 저작권에 걸리지 않을까 싶을정도로 그냥 베껴 쓴 정리가 되었다... 증명도 걍 그런가보다 하고 넘겨서 정리가 아니라 베껴쓰기가 되어버림 ㅜ


Introduction

  • 보통 schedulability analysis에서는 resource가 항상 사용/접근 가능하다고 간주하고 분석한다.
  • infinite time-slicing을 하는 것도 현실적으로 불가능

Definition 1. A task TT is defined as (c,p)(c, p), where cc is the (worst case) execution time requirement, pp is the period of the task.

Definition 2. A task group τ\tau is a collection of n tasks that are to be scheduled on a real-time virtual processor (a partition), τ={Ti=(ci,pi)}i=1n\tau = \{T_i=(c_i, p_i)\}_{i=1}^{n}

! notation이 이전까지 했던거랑 약간 다름 !

The Static Resource Partition Model

  • resource가 항상 가능한게 아니라 중간중간 partition으로 그어진 interval만큼만 가능하다면?

1. The Resource Partition

Definition 3. A resource partition Π\Pi is a tuple (Γ,P)(\Gamma, P), where Γ\Gamma is an array of NN time pairs {(S1,E1),(S2,E2),,(SN,EN)}\{(S_1, E_1), (S_2, E_2), \ldots, (S_N, E_N)\} that satisfies (0S1<E1<S2<E2<<SN<ENP)(0 \le S_1 < E_1 < S_2 < E_2 < \ldots < S_N < E_N \le P) for some N1N \ge 1, and P is the partition period. The physical resource is available to a task group executing on this partition only during time intervals (Si+j×P,Ei+j×P),1iN,j0(S_i+j\times P, E_i+j\times P), 1 \le i \le N, j \ge 0.

  • 우리가 보통 생각하는 언제나 사용 가능한 resource model (always dedicated to a task group)
    • Π=({0, P}, P)\Pi = (\{0,\ P\},\ P)

Definition 4. We call a resource partition where N=1N=1 a Single Time Slot Partition (STSPP). A partition is otherwise a Multi Time Slot Periodic Partition (MTSPP).

Definition 5. The availability factor of a resource partition Π\Pi is α(Π)=(i=1n(EiSi))/P\alpha(\Pi) = (\sum_{i=1}^{n}(E_i-S_i))/P

  • 그냥 단순하게 한 period내에서 실제로 사용가능한 interval들의 비율

Definition 6. The Supply Function S(t)S(t) of a partition Π\Pi is the total amount of time that is available in Π\Pi from time 00 to time tt.

  • S(t)가 가지는 몇가지 특성이 있음 - 주기를 가지는 demand function이라는거 고려하면 될듯
    1. S(0)=0S(0) = 0
    2. S(t)S(t) is monotonically non-decreasing function for t (t0)t\ (t\ge 0).
    3. S(u)S(v)uvS(u) - S(v) \le u - v for u>v0u > v \ge 0.
    4. S(t+P)S(t)=S(P) (t0)S(t+P) - S(t) = S(P)\ (t \ge 0)
    5. S(t)=tP×S(P)+S(tPtP)S(t) = \lfloor \frac {t}{P} \rfloor \times S(P) + S(t - P\lfloor \frac tP \rfloor ) for t>0t > 0.

1.1 Fixed Priority Scheduling

  • STSPP나 MTSPP 모두 기존의 classical utilization bound가 더이상 성립하지 않는다.
  • 그럼 이러한 경우에서의 critical instant는 ?
    • 원래(resource가 dedicate할 때)는 나보다 우선순위 높은 애들이 전부 동시에 요청됐을 때
  • STSPP에서는 가장 긴 longest blocking time slot과 함께 요청 됐을 때? - 그나마도 MTSPP에는 해당 X

Definition 7. We call E1,E2,,ENE_1, E_2, \ldots, E_N of a partition Π ({(S1,E1),(S2,E2),,(SN,EN)},P)\Pi\ (\{(S_1, E_1), (S_2, E_2), \ldots, (S_N, E_N)\}, P) interval-based critical points(IBCPs). If a task is requested simultaneously with all higher priority tasks at IBCP, it is called an interval-based critical instances(IBCI).

  • (Si,Ei)(S_i, E_i) 동안에는 resource를 사용할 수 있는 거니까 blocking 되기 시작하는 시점-EiE_i-들을 IBCP라고 정의

Theorem 1. For fixed priority assignment and a task group whose relative deadlines are no more than the periods, a task is scheduable in a partition Π\Pi iff its first request is schedulable in all IBCIs

  • critical instant는 IBCP에서만 발생할 수 있으니까 IBCI들만 확인해도 됨

Corollary 1. For the preemptive fixed priority scheduling discipline, a task group whose relative deadlines are no bigger than the periods is schedulable on a partition with the rate/deadline-monotonic priority assignments(RMA/DMA) if it is schedulable on the partition by some priority assignment.

1.2 Dynamic Priority Scheduling

Theorem 2. If a task group τ\tau is schedulable in partition Π\Pi by a scheduling policy, it is also schedulable by EDF(Earliest Deadline First) or LSF(Least Slack First).

  • 원래 EDF의 utilization bound는 1.0이었지만 이제 이것도 성립하지 않음

Definition 8. Let TT be a task, and tt a positive real number. The demand bound function dbf(T,t)dbf(T, t) denotes the maximum cumulative execution requirement of the jobs of TT that have both arrival times and deadlines within any time interval of duration tt.

Theorem 3. A task group GG is infeasible on a partition Π\Pi iff TGdbf(T,t)>S(t0+t)S(t0)\sum_{T\in G} dbf(T,t) > S(t_0+t) - S(t_0) for some positive real numbers t0t_0 and tt.

  • 일정한 기간 t 동안에 들어온 demand끼리의 비교니까 안되는게 당연하지 않을까..?
  • 그림그려서 확인해보기

2. Critical partition

2.1 Least Supply Function

Definition 9. The Least Supply Function(LSF) S(t)S^*(t) of a resource partition Π\Pi is the minimum of (S(t+d)S(d))(S(t+d)-S(d)) where t,d0t, d \ge 0.

  • 기존 supply function S(t)S(t)와 다른 점이 뭘까...

Definition 10. A Least Supply Time Interval(u, v)(u,\ v) is an interval that satisfies (S(u)S(v))=S(uv)(S(u)-S(v)) = S^*(u-v).

  • 시간이 0부터 시작할 때, S(t)S(t)NN steps with every PP time unit인 step function인데 S(t)S^*(t)는 최대 N×NN \times N steps with every PP time unit인 step function..

Lemma 1. Any time interval where a partition Π\Pi receives the least resource time has an equal amount of available time in an interval that starts with an IBCP point of Π\Pi.

  • LSF를 계산하기 위해서 모든 IBCP point에 대해서 이 point들을 시작점으로 잡았을 때 time 00에서 time tt까지의 S(t)S(t)중 min을 구한다.

2.2 Critical Partition

Definition 11. A critical partition of a resource partition Π=(Γ,P)\Pi = (\Gamma, P) is Π=(Γ,P)\Pi^* = (\Gamma^*, P) where Γ\Gamma^* has time pairs corresponding to the steps in S(t)S^*(t) such that Π\Pi^*'s supply function equals S(t)S^*(t) in (0,P)(0, P).

Corollary 2. Π\Pi^*'s supply function equals S(t)S^*(t) for t0t \ge 0.

Theorem 4. A task group τ\tau is feasible in a partition Π\Pi iff it is feasible in its critical partition Π\Pi^*.

2.3 Fixed Priority Scheduling

Definition 12. The critical instance of a task on partition Π\Pi is when it is requested simultaneously with all higher priority tasks at time 00 on the critical partition Π\Pi^*.

Theorem 5. Suppose the preemptive fixed priority scheduling policy is used to schedule a task group on a partition by some priority assignment where all deadlines are no bigger than the corresponding periods. If a task's first request is schedulable in a partition's critical instance, then the task is schedulable in the partition.

2.4 Dynamic Priority Scheduling

Corollary 3. A task group GG is infeasible on a partition Π\Pi iff TGdbf(T,t)>S(t)\sum_{T\in G} dbf(T,t) > S^*(t) for some positive real number tt.

profile
대학원생 전해주의 우당탕탕 공부일상

0개의 댓글