CoreSource checked

Earliest Deadline First

Runs the ready task with the nearest deadline first.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Intermediate
Family: Priority Scheduling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Earliest Deadline First prioritizes tasks by deadline so urgent work is selected before later work.

Core Concepts

task orderingdeadline constraintgreedy choicepriority schedulingready queuetask priorityresource allocation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Earliest Deadline First when you need to order tasks by deadline.
Use it for real-time systems with inputs like tasks with deadlines.
Use it when tasks, priorities, deadlines, or resource limits drive execution order.
Use it when the Priority Scheduling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when worst-case timing cannot be bounded well enough.
Avoid it when fairness, latency, and throughput requirements conflict but are not prioritized.
Avoid it when the required output is not deadline-prioritized schedule.

What It Does

Orders tasks by deadline
Chooses the most urgent ready task

Use Cases

Real-time systems
Deadline-driven scheduling
Embedded task planning

Inputs

Tasks with deadlines
Ready times or release times

Outputs

Deadline-prioritized schedule

Key Formulas (1)

Priority rule

priority(task) = earliest absolute deadline

priority(task) = earliest absolute deadline

Runs the ready task with the closest deadline first.

Pseudocode

1.Keep ready tasks ordered by deadline
2.Choose the task with the earliest deadline
3.Run it until completion or preemption
4.Insert newly ready tasks by deadline
5.Repeat until all tasks are scheduled

Canonical Example

Input: tasks = A(4ms), B(2ms), C(1ms)
Output: execution order and completion times
Explanation: Earliest Deadline First: The scheduler chooses which task should run next according to its rule.

Implementation Notes

Keep the input contract explicit: Tasks with deadlines; Ready times or release times.
Record arrival time, remaining work, and completion time so schedule metrics can be checked.
State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.

Common Pitfalls

EDF works best when task timing assumptions are known and monitored.
Ignoring starvation, preemption cost, or inaccurate duration estimates.
Handle empty, invalid, and boundary inputs before trusting deadline-prioritized schedule.
Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show tasks ordered against their upcoming deadlines.

Step 1 of 5: Keep ready tasks ordered by deadline

deadline-timeline

Notes

Earliest Deadline First operates in O(n log n) time and O(n) space within the Priority Scheduling family. Key governing relation: priority(task) = earliest absolute deadline. Often compared with Round Robin Scheduling and Shortest Job First.