Earliest Deadline First
Earliest-Deadline First 又稱 Dynamic-Priority Scheduling，該排程演算法的特點是：
- Task 的 deadline 越近，priority 越高
- 因為上面的特性，所以每一個 Task 的 priority 都是動態的
- 針對 preemptive 設計的
- Critical Instance 與 RM 的別無二致
- Urgency of tasks is dynamic, but static for jobs
1. Context-switch overheads under RM
- 一個 Job 被另一個 Job preempt。
- Preemption 帶來了 context-switch overheads。
- 假設 context-switch operation 會花費時間 x。
- 那麼 computation time
c至少需要加上 2x 的時間。
2. Preemption overhead under EDF
- Paradox 因為 EDF 是 dynamic-priority scheduling，任意兩個 task 會不斷的做 preempt 取代對方，這樣會造成額外的 context-switch overheads。
- Fact 一個 Job 只會被比它還要低 period 的 Jobs 替換，EDF 的 Context-switch overheads 與 RM 其實差不多。
- 在 EDF 下，一個 Job 通常會被其他 longer period 的 jobs 推遲。
3. Optimality of RM
- Theorem 如果帶有任意 priority assignment 的 Task Set 可以被 fixed-priority sheduling 排程，那麼這個 task set 一定能被 RM 排程。
- Proof 交換它們的 priority 直到變成 RM。
4. Arbitrary task priority assignment 如果使用 Arbitrary task priority assignment，那麼 utilization test 將無法使用：
- 因為這種方式的可排程性又比 RM 更低，Utilization test 已經無法保證它是否可排。
- 但是，RMA 的估量方法仍然有效。
5. Optimality of EDF EDF 廣泛用於 periodic & preemptive tasks：
- Least-Slack-Time (LST) or Least-Laxity First (LLF) is also universal to periodic, preemptive tasks
- 但如果使用 LLF，它會有極高的 Context-switch 頻率（Let’s try {(8,16),(8,18)}）。
- The goods of EDF
- EDF is universal to periodic, preemptive tasks with arbitrary arrival times.
- EDF is optimal to non-periodic, non-preemptive jobs whose ready times are all 0
- EDF is optimal to preemptive and non-periodic jobs with arbitrary arrival times
- The bas(s) of EDF
- EDF is not optimal to periodic, non- preemptive tasks with arbitrary arrival times (NP- complete)
- EDF is not optimal to non- periodic, non-preemptive jobs with arbitrary arrival times (NP-complete)
- EDF is not optimal for multiprocessor scheduling (NP-complete, without task migration)