10.3 Task prioritization and deadline management

Priority Management

Real-time systems live or die by their ability to run the right task at the right time. Task prioritization determines which task gets the processor when multiple tasks compete, and deadline management ensures every task finishes before its timing constraint expires. Getting either one wrong can cause missed deadlines, which in hard real-time systems means system failure.

This section covers priority inversion problems and their solutions, deadline-based priority assignment, task characteristics, and schedulability analysis techniques.

Priority Inversion and Solutions

Priority inversion occurs when a high-priority task is blocked by a low-priority task that holds a shared resource. The high-priority task can't proceed until the low-priority task releases the resource. This gets worse if a medium-priority task preempts the low-priority task while it's in its critical section, further delaying the high-priority task indefinitely. This is called unbounded priority inversion, and it's the scenario that famously caused the Mars Pathfinder reset bug in 1997.

Three main protocols address this problem:

• Priority Inheritance Protocol (PIP): When a low-priority task blocks a higher-priority task through a shared resource, the low-priority task temporarily inherits the priority of the blocked task. This lets it finish its critical section faster without being preempted by medium-priority tasks. Once the resource is released, the task's priority drops back to its original level. PIP prevents unbounded inversion but does not prevent deadlocks.
• Priority Ceiling Protocol (PCP): Each shared resource is assigned a priority ceiling equal to the highest priority of any task that may lock it. A task can only lock a resource if its priority is strictly higher than the ceilings of all resources currently locked by other tasks. This prevents the chain of blocking that causes unbounded inversion and also prevents deadlocks.
• Immediate Priority Ceiling Protocol (IPCP): A variant of PCP where a task immediately inherits the priority ceiling of a resource the moment it locks it, rather than waiting until a higher-priority task actually becomes blocked. This is simpler to implement and is the approach used by many RTOSes. It also bounds blocking to at most one critical section.

Deadline Monotonic Priority Assignment

Deadline Monotonic (DM) priority assignment assigns static priorities based on relative deadlines: the shorter a task's deadline, the higher its priority. This is distinct from Rate Monotonic (RM) scheduling, which assigns priority based on period length.

When a task's deadline equals its period, DM and RM produce the same priority ordering. DM becomes important when deadlines are shorter than or different from periods.

Key properties of DM:

• It is optimal among fixed-priority algorithms for scheduling independent, periodic tasks with constrained deadlines (deadline ≤ period). If any fixed-priority assignment can schedule a task set, DM can too.
• It assumes tasks are independent (no shared resources or precedence constraints), have known worst-case execution times, and are released at the start of each period.
• For task sets where deadlines differ from periods, DM should be used instead of RM.

Task Scheduling

Task Characteristics

Understanding task parameters is essential before you can analyze schedulability.

• Period ($T_i$): The time interval between consecutive releases of a periodic task. A task with $T_i = 20\text{ms}$ is released every 20 ms.
• Worst-case execution time ($C_i$): The maximum processor time a task needs to complete in any single invocation.
• Relative deadline ($D_i$): The time by which the task must complete after its release. Often $D_i = T_i$, but not always.
• Utilization ($U_i$): The fraction of processor time consumed by a task, calculated as $U_i = \frac{C_i}{T_i}$. Total utilization for $n$ tasks is $U = \sum_{i=1}^{n} \frac{C_i}{T_i}$.

Not all tasks are periodic. Aperiodic tasks arrive at irregular times and often need fast response but lack hard deadlines. Sporadic tasks also arrive irregularly but have a guaranteed minimum inter-arrival time and typically carry hard deadlines.

Schedulability Analysis

Schedulability analysis answers a critical question: can this set of tasks meet all deadlines under a given scheduling algorithm? Two main approaches exist.

Utilization-based tests are quick but conservative. For Rate Monotonic scheduling, the Liu and Layland bound states that a set of $n$ periodic tasks is guaranteed schedulable if:

$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1)$

For large $n$, this bound converges to approximately $\ln(2) \approx 0.693$, meaning roughly 69.3% utilization. A task set that passes this test is definitely schedulable, but a task set that fails it might still be schedulable. That's why this is a sufficient but not necessary condition.

Response time analysis (RTA) is an exact test. It computes the worst-case response time $R_i$ for each task by accounting for interference from all higher-priority tasks and blocking from shared resources. The task is schedulable if $R_i \leq D_i$. The computation uses a fixed-point iteration:

1. Start with $R_i^{(0)} = C_i$
2. Compute $R_i^{(k+1)} = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$, where $hp(i)$ is the set of tasks with higher priority than task $i$
3. Repeat until $R_i$ converges ($R_i^{(k+1)} = R_i^{(k)}$) or exceeds $D_i$

RTA provides necessary and sufficient conditions for fixed-priority schedulability, but it's more computationally expensive than the utilization test. In practice, you often run the utilization test first as a quick check, then use RTA for task sets that fall between the utilization bound and 100%.