Earliest Deadline First - ianchen0119/AwesomeCS GitHub Wiki

Earliest-Deadline First 又稱 Dynamic-Priority Scheduling，該排程演算法的特點是：

  • Task 的 deadline 越近，priority 越高
  • 因為上面的特性，所以每一個 Task 的 priority 都是動態的
  • 針對 preemptive 設計的
  • Critical Instance 與 RM 的別無二致
  • Urgency of tasks is dynamic, but static for jobs

與 RM 的比較

image

Advanced Topics

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 image

  • 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)