</>EmbeddedInterview

How do you check whether a task set is schedulable? Give a worked example.

HardRTOS & Real-Time Systems

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."