text: 最早截止時間 (EDF) 是一個實時作業系統中使用的，動態優先順序的將程序放入優先佇列的演算法。每當一個引起排程的事件發生(任務完成等) ，將搜尋出佇列中最後期限最接近的程序，接下來要被執行的就是這個程序。EDF在搶佔式、單CPU的場景下是一個最優的排程演算法：如果有一組互相無關的任務，每個任務都有一個到達時間、一個執行需求和一個截止時間，如果存在一個排程演算法能夠確保在截止時間前完成這些任務，使用EDF演算法來排程這些任務將會達到這個效果。對於排程最後期限等於其週期的週期性程序， EDF 的利用率為100％。EDF 的可排程性檢驗是：formula_1然而，當該系統超載、會錯過最後期限的程序集合很大程度上是不可預知的。在實時作業系統上，這是一個相當大的缺點。 演算法也難以使用硬體實現，表達不同範圍內的截止時間也是一個棘手的問題(截止時間不能比用於排程的時間粒度更為精確)。 因此， EDF 並不常用於工業實時計算機系統中。相反，大多數實時計算機系統使用 固定優先順序排程 (通常使用 速率的單調排程)。由於優先順序是固定的，顯然，超載時會造成的低優先順序的任務會錯過最後期限，而最高的優先順序程序將仍然滿足其最後期限。例.考慮在一個單處理器搶佔式排程系統上的3個定期到來的程序。執行時間和到來週期如下表所示:在這個例子中，該單元的時間可以被認為是可排程 的時間片。截止時間是每個週期的程序必須在這一個週期內完成。時序圖.在時序圖中，列代表的時間片隨時間增加，所有程序都在時間片0開始執行。 計時圖的藍色和白色陰影表示的每個程序的週期，顏色的變化表示最後期限到來。由EDF排程的第一個程序是P2，因為它的週期短，因此具有最早的截止時間。 同樣地，當P2完成，P1被排程，隨後是P3。在時間片5，P2和P3具有相同的截止時間：需要在時間片10前完成，所以EDF可能排程其中任何一個。利用率.利用率為：formula_2由於週期的 最小公倍數 是40、排程模式可在每40時間片後重復。 但是，只有這40個時間片中的37個用於P1、P2或P3的執行。 由於利用率，92.5%，是不大於100%，該系統可以用EDF排程。截止時間交換.EDF排程中可能出現截止時間交換問題。 一個程序可能在一個臨界區內使用了一個共用內部資源，防止其被有一個較早的最後期限的程序搶佔。 如果是這樣，排程程式應該為正在執行過程中的程序分配比等待該資源的其他程序更早的截止時間。 否則有更早的最後期限的程序與可能會錯過其期限。與固定優先順序的排程器相比較.公認一個固定優先順序的搶佔式排程器比一個動態優先順序排程器，如EDF，要容易實現。 但是，當比較固定優先順序下最佳排程的最大使用率時，EDF可以達到100％，而Rate-monotonic排程的理論最大值約為69％ 。請注意，EDF沒有對任務的週期性做出任何具體假設；因此，它可用於安排週期性和非週期性任務 。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 最早截止時間優先排程
metadata: https://zh.wikipedia.org/wiki?curid=6779924