Real-Time Scheduling

What is a periodic task example?

• Reading a rotary encoder at fixed rate

• Miss a tick and you lose position information

• Time-driven, not event-driven

What is an aperiodic task example?

• Button press

• Temperature threshold being exceeded

• Event-driven, not time-driven

What is the deadline of a task?

• Latest time by which task must be completed

• For behaviour to be correct, it must be on time

• Useful for guarantees that predictable behaviour can give

What is the hierarchy of constraints a system may need to satisfy?

• Correct (required by any system)

• Within deadline (required by real-time systems)

• Within power budget (emerging research concern, not examined)

What is the difference between hard and soft real-time?

• Hard: deadlines absolute, missing one catastrophic (flight control)

• Soft: occasionally missing tolerable (video streaming degrades gracefully)

• Only algorithms with provable guarantees suitable for hard real-time

What is CPU utilisation U?

• Fraction of total CPU time spent doing useful work

• Idle time and sleeping do not count

• U = (ctotal - cidle) / ctotal ≤ 1

How is U computed from a set of periodic tasks?

• Given n tasks: ci = worst-case CPU time, pi = period

• Task Ti contributes ci/pi fraction of CPU

• Total U = Σ(ci/pi) ≤ 1

Why use worst-case ci throughout analysis?

• Need guarantees for real-time systems

• Must plan for worst case, not average

• Context switching assumed free (leave margin or fold into ci)

What happens if Σ(ci/pi) exceeds 1?

• Impossible to fix with scheduling alone

• Example: 2ms task every 4ms + 3ms task every 4ms = 1.25 > 1

• Scheduling cannot magically create more CPU time

What are the two ways to fix capacity problems?

• Increase pi (run tasks less often if requirements allow)

• Decrease ci (optimisation or offloading to faster hardware)

• Cannot increase pi beyond specification

What are the five requirements for Rate Monotonic Scheduling (RMS)?

1. Tasks independent (no task blocks waiting on another)

2. Fixed CPU requirement (ci worst-case constant)

3. Free context switching (zero cost)

4. Deadline equals period (must finish before next release)

5. Priority rule: shortest period gets highest priority

Why is RMS optimal among fixed-priority schedulers?

• If requirements are met, RMS is optimal

• No other static priority assignment can outperform it

• Priority rule: most frequent task (shortest period) gets highest priority

What is the RMS schedulability condition?

• Σ(ci/pi) ≤ n(2^(1/n) - 1)

• LHS: your task set's total utilisation

• RHS: worst-case bound for n tasks (most adversarial period ratios)

What is the "69% rule" in RMS?

• As n → ∞, bound converges to ln 2 ≈ 0.693

• If U ≤ 0.693, RMS guaranteed regardless of n

• 69% is worst-case guarantee, not hard ceiling

What are the three cases of RMS schedulability test?

• If U ≤ n(2^(1/n)-1): RMS guaranteed to work

• If n(2^(1/n)-1) < U ≤ 1: RMS may still work (inconclusive, needs deeper analysis)

• If U > 1: unschedulable by any algorithm

What can run in the remaining 30% CPU capacity under RMS?

• Lowest priority tasks run in remaining time

• Examples: logging, UI updates, general background work

• Not wasted - used for non-critical work

Why does the RMS bound exist?

• High-priority (fast) task can fire while low-priority task mid-execution

• Fast task preempts, eating into time slow task needed

• Non-integer period ratios cause irregular collisions that accumulate

What is a harmonic task set?

• Every task's period is exact integer multiple of every shorter-period task's period

• Example: 2, 4, 8 ms (harmonic)

• Non-example: 2, 3, 6 ms (not harmonic, 3/2=1.5 not whole number)

What is the benefit of harmonic task sets under RMS?

• Can use up to 100%CPU (immune to Liu-and-Layland bound)

• Fast tasks always complete in neat whole cycles

• Preemption mid-execution never happens

How can you make tasks harmonic?

• Decrease pi (make it run more often - cannot increase pi beyond specification)

• Round every other period DOWN to nearest integer multiple of base

• Change ci through optimisation (usually not feasible unless was silly)

What is Earliest Deadline First (EDF)?

• Dynamic priority scheduling system

• Task priority changes at runtime based on urgency

• Task with closest deadline always runs next

What is the EDF schedulability condition?

• U = Σ(ci/pi) ≤ 1

• Not capped like RMS (always 100% utilisation)

• No need for task set to be harmonic

What are the benefits of EDF over RMS?

• 100% utilisation (RMS limited to 69% for guarantees)

• Can handle new tasks added at runtime (RMS priorities compiled in)

• Can handle varying execution times (RMS always assumes worst case)

• Deadlines can adapt mid-process

What is the overload weakness of EDF?

• Any task can miss deadline (not just low-priority)

• No idea what task will drop when overload occurs

• Unsuitable for safety-critical systems

What is the overload behaviour of RMS?

• Only low-priority tasks miss deadlines

• System can gracefully recover

• Can design around potential of low-priority tasks being dropped

What are the three types of real-time systems?

• Hard: missing deadline = catastrophic failure (airbag, pacemaker, flight control)

• Firm: result useless but system survives (financial trade timing)

• Soft: quality degraded (video, audio streaming)

How do you draw a Gantt diagram for RMS?

• List tasks in priority order

• Compute hyperperiod = LCM of all periods (simulate only one hyperperiod)

• At each tick, highest-priority ready task runs

• Mark preemptions clearly, state whether all deadlines met

What is the RMS bound for n=1, 2, 3, 4?

• n=1: 1.000 (100%)

• n=2: 0.828

• n=3: 0.780

• n=4: 0.757

)

• n=2: 0.828

• n=3: 0.780

• n=4: 0.757