5 Earliest-Deadline-First Scheduling

admin

EDF always executes a job whose deadline is the earliest.
在實時系統中，"Earliest-Deadline-First Scheduling" (EDF) 是一種調度策略，這種策略根據任務的截止時間來給予優先級。具有最早截止時間的任務將獲得最高的優先級。

Theorem: A set of tasks is schedulable by EDF if and only if its total CPU utilization is no more than 1.
The critical instance of a task with EDF is the same as that with RM.
Lemma: With EDF, there is no idle time before an overflow.
這個引理的意思是，在使用 Earliest-Deadline-First（EDF，最早截止時間優先）調度策略時，不會在超載（overflow）發生前有空閒時間。

EDF 調度策略的工作原理是：當有多個任務可以運行時，它會選擇截止時間最早的任務來執行。這種策略的一個關鍵特性是，如果系統有足夠的資源（例如處理器時間）來完成所有的任務，那麼它就不會有空閒時間。

這個引理的含義是，在超載發生之前，調度器會儘可能地利用所有的處理器時間來執行任務，以防止任務的截止時間被違反。換句話說，如果系統在超載之前有空閒時間，那麼它就有可能在不增加資源的情況下避免超載，例如通過更有效地調度任務。

因此，這個引理表明，如果系統在使用EDF調度策略時發生了超載，那麼這個超載是不可避免的，除非我們增加更多的資源（例如增加處理器速度或者增加處理器數量）。


定義和觀察：

可行性（Feasible）：如果存在一種方式可以調度任務，而不會違反任何截止時間，那麼這組任務就是可行的。

可調度性（Schedulable）：給定一種調度算法A，如果算法A可以成功地調度任務，而不會違反任何截止時間，那麼這組任務就是可調度的。

關於這兩種概念，我們可以有以下的觀察：

一組可行的任務可能不是可調度的（例如使用速率單調調度策略（Rate-Monotonic Scheduling，RM））。這是因為雖然存在一種不違反任何截止時間的調度方式，但RM可能無法找到這種方式。

如果一組任務可以由某種算法A調度，那麼它就是可行的。這是因為如果算法A可以成功地調度任務，那麼就存在一種不違反任何截止時間的調度方式。

因此，我們可以說，可調度性是一種更強的概念，它不僅要求存在一種不違反截止時間的調度方式，而且還要求我們能夠找到這種方式。而可行性則只需要存在一種不違反截止時間的調度方式，無論我們能否找到這種方式。