Resource Partition for Real-Time Systems

원래 읽으려고 했던 논문 (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 $T$ is defined as $(c, p)$, where $c$ is the (worst case) execution time requirement, $p$ 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), $\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 $(\Gamma, P)$, where $\Gamma$ is an array of $N$ time pairs $\{(S_1, E_1), (S_2, E_2), \ldots, (S_N, E_N)\}$ that satisfies $(0 \le S_1 < E_1 < S_2 < E_2 < \ldots < S_N < E_N \le P)$ for some $N \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 $(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)
  • $\Pi = (\{0,\ P\},\ P)$

Definition 4. We call a resource partition where $N=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 $\alpha(\Pi) = (\sum_{i=1}^{n}(E_i-S_i))/P$

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

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

• S(t)가 가지는 몇가지 특성이 있음 - 주기를 가지는 demand function이라는거 고려하면 될듯
  1. $S(0) = 0$
  2. $S(t)$ is monotonically non-decreasing function for $t\ (t\ge 0)$.
  3. $S(u) - S(v) \le u - v$ for $u > v \ge 0$.
  4. $S(t+P) - S(t) = S(P)\ (t \ge 0)$
  5. $S(t) = \lfloor \frac {t}{P} \rfloor \times S(P) + S(t - P\lfloor \frac tP \rfloor )$ for $t > 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 $E_1, E_2, \ldots, E_N$ of a partition $\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).

• $(S_i, E_i)$ 동안에는 resource를 사용할 수 있는 거니까 blocking 되기 시작하는 시점-$E_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 $T$ be a task, and $t$ a positive real number. The demand bound function $dbf(T, t)$ denotes the maximum cumulative execution requirement of the jobs of $T$ that have both arrival times and deadlines within any time interval of duration $t$.

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

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

2. Critical partition

2.1 Least Supply Function

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

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

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

• 시간이 0부터 시작할 때, $S(t)$는 $N$ steps with every $P$ time unit인 step function인데 $S^*(t)$는 최대 $N \times N$ steps with every $P$ 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 $0$에서 time $t$까지의 $S(t)$중 min을 구한다.

2.2 Critical Partition

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

Corollary 2. $\Pi^*$'s supply function equals $S^*(t)$ for $t \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 $0$ 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 $G$ is infeasible on a partition $\Pi$ iff $\sum_{T\in G} dbf(T,t) > S^*(t)$ for some positive real number $t$.