is the least common multiple (lcm) of the periods.

maximum num of arriving jobs

$$N = \sum_{i=1}^{n} \frac{H}{p_i}$$

Frames: each task must fit within a single frame with size $f$ ⇒ number of frames $F = \frac{H}{f}$

C1: A job must fit in a frame, or $f \geq \text{max} \space e_i \forall \space 1\leq i \leq n$ for all tasks

C2: hyperperiod has an integer number of frames, or $\frac{H}{f} = \text{integer}$

C3: $2f - \text{gcd}(P_i, f) \leq D_i$ per task.

idea: if framesize constraint doesn’t met, then “slice” into smaller sub-tasks

$T_3=(20, 5)$ becomes $T_{3_{1}}=(20,1)$ and $T_{3_{2}}=(20,3)$ and $T_{3_{3}}=(20, 1)$

• Denote all jobs in hyperperiod of $F$ frames as $J_{1} \cdots J_{F}$
• Vertices:
  • $k$ job vertices $J_{1},J_{2},\cdots,J_{k}$
  • $F$ frame vertices $x,y,\cdots,z$
• Edges:
  • $(\text{source}, J_i)$ with capacity $C_i=e_i$
    • Encode jobs’ compute requirements
  • $(J_i, x)$ with capacity $f$ iff $J_i$ can be scheduled in frame $x$
    • encode periods and deadlines
    • edge connected job node and frame node if the following are met:
      1. job arrives before or at the starting time of the frame
      2. job’s absolute deadline larger or equal to ending time of frame
  • $(f, \text{sink})$ with capacity $f$
    • encodes limited computational capacity in each frame

• running on uniprocessor, tasks are preemptive, no OS overhead for preemption

task $T_i$ has higher priority than task $T_j$ if $p_i < p_j$

schedulability test for RM (Test 1)

Given $n$ periodic processes, independent and preemptable, $D_i \geq p_i$ for all processes, periods of all tasks are integer multiples of each other

a sufficient condition for tasks to be scheduled on uniprocessor: $U = \sum_{i=1}^{n}\frac{e_i}{p_i} \leq 1$

schedulability test for RM (Test 2)

A sufficient but not necessary condition is $U \leq n \cdot (2^{\frac{1}{n}} - 1)$ for $n$ periodic tasks

for $n \to \infty$, we have $U < \ln(2) \approx 0.693$

schedulability test for RM (Test 3)

Consider a set of task $(T_{1},T_{2},\cdots,T_i)$ with $p_{1}<p_{2}<\cdots<p_i$. Assume all tasks are in phase. to ensure that $T_1$ can be feasibly scheduled, that $e_1 \leq p_1$ ($T_1$ has highest priority given lowest period)

Supposed $T_2$ finishes at $t$. Total number of isntances of task $T_1$ released over time interval $[0; t)$ is $\lceil \frac{t}{p_{1}} \rceil$

Thus the following condition must be met for every instance of task $T_1$ released during tim interval $(0;t)$:

$$t = \lceil \frac{t}{p_{1}} \rceil \space e_1 + e_2$$

idea: find $k$ such that time $t = k \times p_1 \geq k * e_1 + e_2$ and $k\times p_1 \leq p_2$ for task 2

general solution for RM-schedulability

The time demand function for task $i; 1 \leq i \leq n$:

$$\begin{aligned} \omega_i(t) &= \sum_{k=1}^{i} \lceil \frac{t}{p_k} \rceil \space e_k \leq t \\ \\ &\because 0 \leq t \leq p_i \end{aligned}$$

holds a time instant $t$ chosen as $t=k_j p_j, (j=1,\cdots,i)$ and $k_j = 1, \cdots, \lfloor \frac{p_i}{p_j} \rfloor$

• if every task has period equal to relative deadline, same as RM
• arbitrary deadlines then DM performs better than RM
• RM always fails if DM fails

depends on closeness of absolute deadlines

EDF schedulability test 1

set of $n$ periodic tasks, each whose relative deadline is equal to or greater than its period iff $\sum_{i=1}^{n}(\frac{e_i}{p_i}) \leq 1$

EDF schedulability test 2

relative deadlines are not equal to or greater than their periods

$$\sum_{i=1}^{n}(\frac{e_i}{\text{min}(D_i, p_i)}) \leq 1$$

serially reusable: a resource cannot be interrupted

If a job wants to use $k_i$ units of resources $R_i$, it executes a lock $L(R_i; k_i)$, and unlocks $U(R_i; k_i)$ once it finished

idea: schedule all critical sections non-preemptively

While a task holds a resource it executes at a priority higher than the priorities of all tasks

a higher priority task is blocked only when some lower priority job is in critical section

pros:

• zk about resource requirements of tasks cons:
• task can be blocked by a lower priority task for a long time even without resource conflict

• url: thoughts/.../PIP-and-PCP
• description: PIP and PCP

PIP and PCP

Priority Inheritance Protocol (PIP)

idea: increase the priorities only upon resource contention

avoid NPCS drawback

would still run into deadlock (think of RR task resource access)

rules:

• When a task T1 is blocked due to non availability of a resource that it needs, the task T2 that holds the resource and consequently blocks T1, and T2 inherits the current priority of task T1.
• T2 executes at the inherited priority until it releases R.
• Upon the release of R, the priority of T2 returns to the priority that it held when it acquired the resource R

Priority Ceiling Protocol (PCP)

idea: extends PIP to prevent deadlocks

• If lower priority task TL blocks a higher priority task TH, priority(TL) ← priority(TH)
• When TL releases a resource, it returns to its normal priority if it doesn’t block any task. Or it returns to the highest priority of the tasks waiting for a resource held by TL
• Transitive
  • T1 blocked by T2: priority(T2) ← priority(T1)
  • T2 blocked by T3: priority(T3) ← priority(T1)

ceiling(R): highest priority. Each resource has fixed priority ceiling

Lien vers l'original