How do you check whether a task set is schedulable? Give a worked example.
Short answer: First compute utilisation and compare with the RMS bound; if it is above the bound, use response-time analysis (RTA): for each task, iterate Rᵢ = Cᵢ + Bᵢ + Σⱼ∈hp(i) ⌈Rᵢ / Tⱼ⌉ · Cⱼ (its own execution, blocking by lower-priority tasks, plus interference from every higher-priority task) until it converges. The set is schedulable if every Rᵢ ≤ Dᵢ.
Example (times in ms, RMS priorities: shortest period highest)
| Task | Period T = deadline D | WCET C | Utilisation |
|---|---|---|---|
| T1 | 10 | 3 | 0.300 |
| T2 | 15 | 4 | 0.267 |
| T3 | 40 | 10 | 0.250 |
| Total | 0.817 |
The RMS bound for 3 tasks is 0.780, and 0.817 is above it, so the simple test is inconclusive. Run RTA (no blocking):
- T1: R = 3 (no higher-priority tasks) ≤ 10 ✓
- T2: R₀ = 4 → R = 4 + ⌈4/10⌉·3 = 7 → R = 4 + ⌈7/10⌉·3 = 7 (converged) ≤ 15 ✓
- T3: R₀ = 10
- R = 10 + ⌈10/10⌉·3 + ⌈10/15⌉·4 = 10 + 3 + 4 = 17
- R = 10 + ⌈17/10⌉·3 + ⌈17/15⌉·4 = 10 + 6 + 8 = 24
- R = 10 + ⌈24/10⌉·3 + ⌈24/15⌉·4 = 10 + 9 + 8 = 27
- R = 10 + ⌈27/10⌉·3 + ⌈27/15⌉·4 = 10 + 9 + 8 = 27 (converged) ≤ 40 ✓
All tasks meet their deadlines even though utilisation is above the bound.
Adding reality
- Blocking time
Bᵢ: the longest time a lower-priority task can hold a resource that task i needs (with priority inheritance/ceiling, typically one critical section). - ISR load: treat interrupts as the highest-priority "tasks" with their own C and minimum inter-arrival time.
- Kernel overhead: add context switch time to each C (twice per job: switch in and out).
- Jitter: release jitter adds to the interference terms.
Interview tip: even if you do not remember the formula exactly, explain the idea: "a task's worst-case response is its own work plus the work of every higher-priority job released during that window plus blocking; iterate until stable and compare with the deadline."