Earliest Deadline First

Topics: Embedded Systems

Definition

Earliest Deadline First (EDF) is a dynamic-priority, preemptive scheduling algorithm used in real-time operating systems. In EDF, the scheduler assigns the highest priority to the task with the closest absolute deadline. If a new task has an earlier deadline than the one currently running, the scheduler preempts it.

Advantages

• works with periodic/aperiodic tasks
• it is mathematically proven to be optimal on uniprocessor systems
• fewer context switches than Rate Monotonic Scheduling

Disadvantages

• more complex than RMS and requires RTOS; it would require building a custom task manager to run bare-metal, which is not typically practical
• high computational overhead for finding the earliest deadline and maintaining sorted list of tasks
• a cascading failure can occur in case of overload. The scheduler spends time on tasks that are already doomed to miss their deadlines, causing subsequent tasks to fail.

References

1. https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
2. https://www.geeksforgeeks.org/operating-systems/earliest-deadline-first-edf-cpu-scheduling-algorithm/