Earliest Deadline First Scheduling (EDF)

Given Task Set

You have 3 periodic tasks:

Task Execution Time (C) Deadline (D) Period (T)

T1 3 7 20

T2 2 4 5

T3 2 8 10

• Each task generates jobs periodically.

• Each job must complete before its deadline.

Step 1: Hyperperiod (LCM)

The schedule repeats every:

𝐿𝐶𝑀(20,5,10) = 20

So we analyze from time 0 → 20.

Step 2: Key EDF Rule

At any instant:
Pick the job with the earliest absolute deadline

Deadlines are updated every time a new job arrives.

Step 3: Job Arrivals & Deadlines

Task Releases:

• T1: releases at 0 → deadline = 7

• T2: releases at 0, 5, 10, 15 → deadlines = 4, 9, 14, 19

• T3: releases at 0, 10 → deadlines = 8, 18

Step 4: Scheduling Timeline (0–20)

Time 0–2

• Available: T1 (d=7), T2 (d=4), T3 (d=8)

• Earliest deadline → T2

• Run T2 (0–2)
Time 2–5

• Remaining: T1 (d=7), T3 (d=8)

• Earliest → T1

• Run T1 (2–5) (partial)

Time 5–7

• New T2 arrives (d=9)

• Compare: T1 (d=7), T2 (d=9), T3 (d=8)

• Earliest → T1

• Finish T1 (5–7)

Time 7–9

• Compare: T2 (d=9), T3 (d=8)

• Earliest → T3

• Run T3 (7–9)

Time 9–10

• Remaining: T2 (d=9)

• Run T2 (9–10) (partial)

Time 10–12

• New arrivals: T2 (d=14), T3 (d=18)

• Continue earliest → T2

• Finish T2 (10–12)

Time 12–14

• Remaining: T3 (d=18)

• Run T3 (12–14) (partial)

Time 14–15

• New T2 arrives (d=19)

• Compare: T3 (d=18), T2 (d=19)

• Run T3 (14–15) (finish)

Time 15–17
 • Run T2 (15–17)

Time 17–20

• Idle or next cycle begins

Final Schedule (as shown in diagram)

0–2 : T2
2–7 : T1
7–9 : T3
9–12 : T2
12–15 : T3
15–17 : T2

Key Observations

All tasks meet deadlines → Schedulable under EDF

EDF is optimal for uniprocessor scheduling
It is dynamic priority scheduling (priorities change over time)

Important Concept

• EDF always checks absolute deadlines, not fixed priorities.

• Whenever a new job arrives, scheduling decision may change.

Final Gantt Chart

Time → 0 2 5 7 9 10 12 14 15 17 20
|---|---|---|---|----|---|---|----|---|
Task → T2 T1 T3 T2 idle T2 T3 idle T2 idle

7. Deadline Verification

Task Instance Deadline Finish Time

T2 (0) 4 2

T1 (0) 7 5

T3 (0) 8 7

T2 (5) 9 9

T2 (10) 14 12

T3 (10) 18 14
Task Instance Deadline Finish Time

T2 (15) 19 17

EDF is Dynamic

• Priorities change continuously

• Based on closest deadline

Preemption Happens

• Example: If a new task had earlier deadline, current task would be interrupted

CPU Idle Time Exists

• EDF doesn’t force execution

• If no jobs → CPU idle

Schedulability Check (Optional)

3 2 2
𝑈= + + = 0.15 + 0.4 + 0.2 = 0.75
20 5 10

Since U ≤ 1, EDF guarantees feasibility

Final Conclusion

✔ EDF successfully schedules all tasks

✔ No deadline misses
✔ Efficient CPU utilization (75%)
✔ Matches the diagram you provided

Rate Monotonic Scheduling (RMS)

Core Idea

Feature EDF RMS

Priority Type Dynamic Fixed

Rule Earliest deadline gets highest priority Shortest period gets highest priority

Priority Assignment

EDF

• Priority changes at runtime

 • Based on absolute deadline

• Example:

o If T3 suddenly has earlier deadline → it preempts others

RMS

• Priority is fixed before execution

• Based on period (T):

Task Period Priority

T2 5 Highest

T3 10 Medium

T1 20 Lowest

Applying RMS to Your Example

Given:

Task C T

T1 3 20

T2 25

T3 2 10

Step-by-Step RMS Schedule

Priority order:

T2 > T3 > T1

Time 0–2

• All arrive → run T2 (highest priority)

Time 2–4

• Remaining: T1, T3

• Higher priority → T3

Time 4–5

• Run T1 (only one left)

Time 5 (new T2 arrives)

 • Preempts T1

Time 5–7

• Run T2

Time 7–9

• Run T3

Continue similarly…

Important Observation

Under RMS:

• Lower priority task (T1) may get delayed

• Risk of deadline miss if system is heavily loaded

Schedulability Comparison

EDF Condition:

𝑈≤1

RMS Condition:

𝑈 ≤ 𝑛(21/𝑛 − 1)

For n = 3:

𝑈 ≤ 3(21/3 − 1) ≈ 0.779

For Your Example:

𝑈 = 0.75

Result:

• EDF: Schedulable

• RMS: Also schedulable (since 0.75 < 0.779)

Key Differences (Very Important for Exams)

Aspect EDF RMS

Optimality Optimal Not optimal

Aspect EDF RMS

CPU Utilization Up to 100% ~69% (worst case)

Complexity Higher Lower

Implementation Harder Easier

Starvation Possible in edge cases Less likely

Preemption Frequent Less frequent

Intuitive Difference

EDF (Smart but Complex)

“Do the most urgent task first”

RMS (Simple but Rigid)

“Do the fastest repeating task first”

7. When EDF is Better

✔ High CPU utilization systems

✔ Dynamic environments
✔ Soft real-time systems

When RMS is Better

✔ Embedded systems (predictable)

✔ Low overhead requirement
✔ Fixed hardware scheduling

Final Conclusion

• EDF is theoretically superior (optimal scheduling)

• RMS is practically simpler and widely used

Alright—let’s fully solve your same problem step-by-step under both EDF and RMS, so you
can clearly see every decision point.

We’ll use the same task set:

Task C D T

T1 3 7 20
Task C D T

T2 24 5

T3 2 8 10

Hyperperiod = 20

Least Slack Time Scheduling (LST)—also called Least Laxity First (LLF)

Core Idea of LST

At any instant, pick the task with the least slack (laxity)

Slack (Laxity) Formula

Slack tells how much delay a task can tolerate:

Slack = (Deadline − Current Time) − Remaining Execution Time

Interpretation:

• Small slack → urgent task

• Zero slack → must run immediately

• Negative slack → deadline already missed

Given Task Set (Same as Before)

Task C D T

T1 3 7 20

T2 24 5

T3 2 8 10

Step-by-Step LST Scheduling

Time = 0

All tasks arrive:

Task Deadline Remaining Slack Calculation Slack

T1 7 3 (7−0)−3 4
Task Deadline Remaining Slack Calculation Slack

T2 4 2 (4−0)−2 2

T3 8 2 (8−0)−2 6

Minimum slack = T2

Run T2 (0–2)

Time = 2

Recalculate slack:

Task Deadline Remaining Slack

T1 7 3 (7−2)−3 = 2

T3 8 2 (8−2)−2 = 4

Minimum slack = T1

Run T1 (2–5)

Time = 5 (New T2 arrives)

Recalculate:

Task Deadline Remaining Slack

T2 9 2 (9−5)−2 = 2

T3 8 2 (8−5)−2 = 1

Minimum slack = T3

Run T3 (5–7)

Time = 7

Recalculate:

Task Deadline Remaining Slack

T2 9 2 (9−7)−2 = 0

Slack = 0 → must execute immediately

Run T2 (7–9)

Time = 9–10
Idle

Time = 10 (New arrivals)

Task Deadline Remaining Slack

T2 14 2 (14−10)−2 = 2

T3 18 2 (18−10)−2 = 6

Minimum slack = T2

Run T2 (10–12)

Time = 12

Task Deadline Remaining Slack

T3 18 2 (18−12)−2 = 4

Run T3 (12–14)

Time = 14–15

Idle

Time = 15

Task Deadline Remaining Slack

T2 19 2 (19−15)−2 = 2

Run T2 (15–17)

Time = 17–20

Idle

Final LST Schedule

0–2 T2
2–5 T1
5–7 T3
7–9 T2
9–10 Idle
10–12 T2
12–14 T3
14–15 Idle
15–17 T2
17–20 Idle
Key Observations

Same as EDF in this case

• LST schedule = EDF schedule

• All deadlines met

Feature LST

Priority basis Slack (dynamic)

Preemption Very frequent

Complexity High

Stability Less stable than EDF

Why LST Causes More Preemption

Slack changes every time unit, so:

Scheduler must recompute continuously
Tasks may switch frequently

Comparison (EDF vs RMS vs LST)

Feature EDF RMS LST

Type Dynamic Fixed Dynamic

Priority basis Deadline Period Slack

Optimal Yes N0 Yes

Preemption Medium Low High

Complexity Medium Low High

Final Insight

• EDF → best practical choice

• RMS → simplest

• LST → most “accurate urgency” but costly