Q20Real Time Systems

EDF is a highly aggressive, Dynamic, Preemptive scheduling architecture. Unlike RMS (which hardcodes priorities based on periods), EDF treats the OS as a live mathematical engine. Every time a new task enters the ready queue, EDF evaluates the absolute physical deadlines of all tasks and violently assigns the absolute highest CPU priority to the task whose deadline is closest to the current microsecond.

The absolute greatest architectural triumph of EDF is its utilization bound.

• The Math: For a set of $n$ independent, periodic tasks, EDF can mathematically schedule them if and only if: $U={\sum }_{i=1}^n\frac{C_i}{T_i}\le 1.0$
• Comparison to RMS: RMS is mathematically capped at a catastrophic 69.3% CPU utilization for large task sets. If you buy a $1,000CPU,RMSforcesyoutowaste$300 of its power to guarantee safety. EDF mathematically guarantees safety all the way up to exactly 100% (1.0). EDF extracts absolute maximum performance from the silicon hardware.

• RMS: Execution is instantaneous. The OS uses a static $O(1)$ priority bitmap. The CPU spends zero energy thinking.
• EDF: Execution is highly expensive. Because absolute deadlines change constantly (e.g., Task A's deadline was $t=50$, its next is $t=100$), priorities constantly shift. The OS must maintain a dynamic priority queue (like a Min-Heap) and execute an $O(\log n)$ mathematical sort every single time a task releases. This burns massive CPU cycles (Overhead).

What happens if a hardware error causes $U$ to spike to 1.05 (Overload)?

• RMS: It fails gracefully and mathematically. Only the absolute lowest priority tasks will miss their deadlines. The high-frequency control loops survive perfectly.
• EDF: It fails catastrophically. Because EDF constantly elevates the priority of whatever task is closest to failing, during an overload, it desperately tries to save everything. It violently context-switches between tasks as their deadlines approach, resulting in a scenario where NO tasks finish in time. This is the mathematical "Domino Effect" of cascading failures.