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

單調速率調度(RMS)算法(詳解版)

單調速率(RMS)調度算法采用搶占的、靜態優先級的策略,調度周期性任務。

當較低優先級的進程正在運行并且較高優先級的進程可以運行時,較高優先級進程將會搶占低優先級。在進入系統時,每個周期性任務會分配一個優先級,它與其周期成反比,即周期越短,優先級越高;周期越長,優先級越低。

這種策略背后的理由是:更頻繁地需要 CPU 的任務應分配更高的優先級。此外,單調速率調度假定:對于每次 CPU 執行,周期性進程的處理時間是相同的。也就是說,在每次進程獲取 CPU 時,它的 CPU 執行長度是相同的。

舉一個例子,我們有兩個進程 P1 和 P2。P1 和 P2 的周期分別為 50 和 100,即 ρ1 = 50 和 ρ2= 100。P1 和 P2 的處理時間分別為 t1 = 20 和 t2 = 35。每個進程的截止期限要求,它在下一個周期開始之前完成 CPU 執行。

首先,我們應問自己是否可能調度這些任務以便每個進程都能滿足截止期限。如果我們按執行與周期的比率 tii 測量一個進程的 CPU 利用率,那么 P1 的 CPU 利用率 20/50 = 0.40,P2 的是 35/100 = 0.35,總的 CPU 利用率為 75%。因此,我們似乎可以調度這些任務以便滿足它們的截止期限,并且仍讓 CPU 有多余可用的時間。

假設為 P2 分配比 P1 更高的優先級。P1 和 P2 的執行情況如圖 1 所示。

當 P<sub>2</sub> 的優先級高于 P<sub>1</sub> 時的任務調度
圖 1 當 P2 的優先級高于 P1 時的任務調度

我們可以看到,P2 首先開始執行并在時間 35 完成。這時,P1 開始,它完成 CPU 執行時間 55。然而,P1 的第一個截止期限是在時間 50,所以調度程序讓 P1 錯過其截止期限。

現在假設使用單調速率調度,這里 P1 分配的優先級要高于 P2 的,因為 P1 的周期比 P2 的更短。在這種情況下,這些進程執行如圖 2 所示。

單調速率調度
圖 2 單調速率調度

首先,P1 開始,并在時間 20 完成 CPU 執行,從而滿足第一個截止期限。P2 在這點開始運行,并運行直到時間 50。此時,它被 P1 搶占,盡管它的 CPU 執行仍有 5ms 的時間。P1 在時間 70 完成 CPU 執行,在這點調度器恢復 P2。P1 在時間 75 完成 CPU 執行,也滿足第一個截止期限。然后,系統一直空閑直到時間 100,這時,P1 再次被調度。

單調速率調度可認為是最優的,因為如果一組進程不能由此算法調度,它不能由任何其他分配靜態優先級的算法來調度。我們接下來分析一組進程,它們不能使用單調速率算法來調度。

假設進程 P1 具有周期 ρ1=50 和 CPU 執行 t1 = 25。進程 P2 的對應值是 ρ2=80 和 t2 = 35。單調速率調度將為進程 P1 分配較高的優先級,因為它具有較短的周期。兩個進程的總 CPU 利用率為 (25/50)+(35/80)=0.94,因此似乎合乎邏輯的結論是:這兩個進程可以被調度,并且仍讓 CPU 有 6% 的可用時間。

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

圖 3 顯示了進程 P1 和 P2 的調度。最初,P1 運行,直到在時間 25 完成 CPU 執行。進程 P1 然后開始運行,并運行直到時間 0,這時它被 P1 搶占;這時,P2 在 CPU 執行中仍有 10ms 的剩余。進程 P1 運行直到時間 75,導致 P2 在時間 85 結束,因而超過了在時間 80 完成 CPU 執行的截止期限。

盡管是最優的,然而單調速率調度有一個限制,CPU 的利用率是有限的,并不總是可能完全最大化 CPU 資源。調度 N 個進程的最壞情況下的 CPU 利用率為

N(21/N - 1)

對于具有一個進程的系統,CPU 利用率是 100%;但是當進程數量接近無窮時,它大約接近 69%。對于具有兩個進程的系統,CPU 利用率是 83%。圖 1 和圖 2 調度的兩個進程的組合利用率為 75%,因此單調速率調度算法保證能夠調度它們。圖 3 所示的兩個進程的組合利用率為 94%,因此,單調速率調度不能保證它們可以調度以便滿足它們的截止期限。

所有教程

優秀文章

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

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

底部Logo