RTOS Scheduling Algorithms
Scheduling decides which task runs when; in real-time systems the algorithm must be analyzable so deadlines can be guaranteed in advance.
The Scheduling Problem
A scheduler assigns the processor to ready tasks over time. In a real-time system the goal is not fairness or throughput but meeting every deadline. A good real-time scheduler comes with a schedulability test: a way to prove, before deployment, that a given task set will always meet its deadlines.
Preemptive Priority Scheduling
The dominant model is fixed-priority preemptive scheduling. Each task has a priority; the scheduler always runs the highest-priority ready task, preempting lower-priority work immediately. This gives low latency to important tasks. The two central questions are how to assign priorities and how to prove the resulting set is schedulable.
Static Versus Dynamic Priority
- Static (fixed) priority: assigned once, as in rate-monotonic scheduling; simple and predictable
- Dynamic priority: recomputed at runtime, as in earliest-deadline-first; higher utilization but more complex
- Time-triggered: a fixed table dictates exactly when each task runs; maximally deterministic, rigid to change
Schedulability Analysis
For fixed-priority systems, response-time analysis computes each task's worst-case completion time by accounting for its own execution plus interference from every higher-priority task that can preempt it. If every task's worst-case response is within its deadline, the set is schedulable. This analysis needs trustworthy worst-case execution times and knowledge of blocking from shared resources.
Utilization and Overload
No scheduler can meet all deadlines if the total demanded work exceeds capacity. Analysis bounds the safe utilization; beyond it, deadlines will be missed. A robust system plans for overload with defined policies, shedding or deferring lower-criticality work rather than failing unpredictably. The scheduler's value is that it makes the boundary between safe and unsafe operation calculable rather than a matter of testing luck.