最早截止時間優先調度

最早截止時間 (EDF) 是一個實時作業系統中使用的，動態優先級的將進程放入優先隊列的算法。每當一個引起調度的事件發生(任務完成等) ，將搜索出隊列中最後期限最接近的進程，接下來要被執行的就是這個進程。

EDF在搶佔式、單CPU的場景下是一個最優的調度算法：如果有一組互相無關的任務，每個任務都有一個到達時間、一個執行需求和一個截止時間，如果存在一個調度算法能夠確保在截止時間前完成這些任務，使用EDF算法來調度這些任務將會達到這個效果。

對於調度最後期限等於其周期的周期性進程， EDF 的利用率為100％。EDF 的可調度性檢驗是：

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,$

然而，當該系統超載、會錯過最後期限的進程集合很大程度上是不可預知的。在實時作業系統上，這是一個相當大的缺點。 算法也難以使用硬件實現，表達不同範圍內的截止時間也是一個棘手的問題(截止時間不能比用於調度的時間粒度更為精確)。 因此， EDF 並不常用於工業實時計算機系統中。

相反，大多數實時計算機系統使用 固定優先級調度 (通常使用 速率的單調調度)。由於優先級是固定的，顯然，超載時會造成的低優先級的任務會錯過最後期限，而最高的優先級進程將仍然滿足其最後期限。

例

考慮在一個單處理器搶佔式調度系統上的3個定期到來的進程。執行時間和到來周期如下表所示:

進程實現數據

進程	執行時間	到來周期
P1	1	8
P2	2	5
P3	4	10

在這個例子中，該單元的時間可以被認為是可調度 的時間片。截止時間是每個周期的進程必須在這一個周期內完成。

時序圖

時序圖 表示一個可能的時間安排的一部分。

在時序圖中，列代表的時間片隨時間增加，所有進程都在時間片0開始運行。 計時圖的藍色和白色陰影表示的每個進程的周期，顏色的變化表示最後期限到來。

由EDF調度的第一個進程是P2，因為它的周期短，因此具有最早的截止時間。 同樣地，當P2完成，P1被調度，隨後是P3。

在時間片5，P2和P3具有相同的截止時間：需要在時間片10前完成，所以EDF可能調度其中任何一個。

利用率

利用率為：

$\left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\right)=\left({\frac {37}{40}}\right)=0.925={\mathbf {92.5\%} }$

由於周期的 最小公倍數 是40、調度模式可在每40時間片後重複。 但是，只有這40個時間片中的37個用於P1、P2或P3的執行。 由於利用率，92.5%，是不大於100%，該系統可以用EDF調度。

截止時間交換

EDF調度中可能出現截止時間交換問題。 一個進程可能在一個臨界區內使用了一個共用內部資源，防止其被有一個較早的最後期限的進程搶佔。 如果是這樣，調度程序應該為正在運行過程中的進程分配比等待該資源的其他進程更早的截止時間。 否則有更早的最後期限的進程與可能會錯過其期限。

與固定優先級的調度器相比較

公認一個固定優先級的搶佔式調度器比一個動態優先級調度器，如EDF，要容易實現。 但是，當比較固定優先級（每個線程的優先級由Rate-monotonic調度算法給出）下最佳調度的最大使用率時，EDF可以達到100％，而Rate-monotonic調度的理論最大值約為69％ 。

請注意，EDF沒有對任務的周期性做出任何具體假設；因此，它可用於安排周期性和非周期性任務 。

參見

• 動態優先級調度