C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:1,081

最早截止時間優先(EDF)算法詳解

最早截止期限優先(EDF)調度根據截止期限動態分配優先級。截止期限越早,優先級越高;截止期限越晚,優先級越低。

根據 EDF 策略,當一個進程可運行時,它應向系統公布截止期限要求。優先級可能需要進行調整,以便反映新可運行進程的截止期限。注意單調速率調度與 EDF 調度的不同,前者的優先級是固定的。

錯過截止期限的單調速率調度
圖 1 錯過截止期限的單調速率調度

為了說明 EDF 調度,我們再次調度如圖 1 所示的進程,這些進程通過單調速率調 度不能滿足截止期限要求。記住:進程 P1 有 ρ1 = 50 和 t1 = 25,進程 P2 有 ρ2 = 80 和 t2 = 35,這些進程的 EDF 調度如圖 2 所示。

最早截止期限優先調度
圖 2 最早截止期限優先調度

進程 P1 的截止期限為最早,所以它的初始優先級比進程 P2 的要高。當 P1 的 CPU 執行結束時,進程 P2 開始運行。不過,雖然單調速率調度允許 P1 在時間 50(即下一周期開始之際)搶占 P2,但是 EDF 調度允許進程 P2 繼續運行。進程 P2 的優先級比 P1 的更高,因為它的下一個截止期限(時間 80)比 P1 的(時間 100)要早。因此,P1 和 P2 都能滿足它們的第一個截止期限。

進程 P1 在時間 60 再次開始運行,在時間 85 完成第二個 CPU 執行,也滿足第二個截止期限(在時間 100)。這時,進程 P2 開始運行,只是在時間 100 被 P1 搶占。P2 之所以被 P1 搶占是因為 P1 的截止期限(時間 150)要比 P2 的(160)更早。在時間 125,P1 完成 CPU 執行,P2 恢復執行;在時間 145,P2 完成,并滿足它的截止期限。然后,系統空閑直到時間 150;在時間 150 進程 P1 開始再次被調度。

與單調速率調度不一樣,EDF 調度不要求進程應是周期的,也不要求進程的 CPU 執行的長度是固定的。唯一的要求是,進程在變成可運行時,應宣布它的截止期限。

EDF 調度具有吸引力的地方是,它是理論上最佳的。從理論上說,它可以調度進程,使得每個進程都可以滿足截止期限的要求并且 CPU 利用率將會是 100%。然而,在實際中,由于進程的上下文切換和中斷處理的代價,這種級別的 CPU 利用率是不可能的。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo