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

時間片輪轉(RR)調度算法(詳解版)

時間片輪轉(RR)調度算法是專門為分時系統設計的。它類似于 FCFS調度,但是增加了搶占以切換進程。

該算法中,將一個較小時間單元定義為時間量時間片。時間片的大小通常為 10~100ms。就緒隊列作為循環隊列。CPU 調度程序循環整個就緒隊列,為每個進程分配不超過一個時間片的 CPU。

為了實現 RR 調度,我們再次將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程序從就緒隊列中選擇第一個進程,將定時器設置在一個時間片后中斷,最后分派這個進程。

接下來,有兩種情況可能發生。進程可能只需少于時間片的 CPU 執行。對于這種情況,進程本身會自動釋放 CPU。調度程序接著處理就緒隊列的下一個進程。否則,如果當前運行進程的 CPU 執行大于一個時間片,那么定時器會中斷,進而中斷操作系統。然后,進行上下文切換,再將進程加到就緒隊列的尾部,接著 CPU 調度程序會選擇就緒隊列內的下一個進程。

不過,采用 RR 策略的平均等待時間通常較長。假設有如下一組進程,它們在時間 0 到達,其 CPU 執行以 ms 計:

進程 執行時間
P1 24
P2 3
P3 3

如果使用 4ms 的時間片,那么 P1 會執行最初的 4ms。由于它還需要 20ms,所以在第一個時間片之后它會被搶占,而 CPU 就交給隊列中的下一個進程。由于 P2 不需要 4ms,所以在其時間片用完之前就會退出。CPU 接著交給下一個進程,即進程 P3。在每個進程都得到了一個時間片之后,CPU 又交給了進程 P1 以便繼續執行。因此,RR 調度結果如下:

時間片輪轉調度結果

現在,我們計算這個調度的平均等待時間。P1 等待 10-4 = 6ms,P2 等待 4ms,而 P3 等待 7ms。因此,平均等待時間為 17/3 = 5.66ms

在 RR 調度算法中,沒有進程被連續分配超過一個時間片的 CPU(除非它是唯一可運行的進程)。如果進程的 CPU 執行超過一個時間片,那么該進程會被搶占,并被放回到就緒隊列。因此,RR調度算法是搶占的。

如果就緒隊列有 n 個進程,并且時間片為 q,那么每個進程會得到 1/n 的 CPU 時間,而且每次分得的時間不超過 q 個時間單元。每個進程等待獲得下一個 CPU 時間片的時間不會超過 (n-1)q 個時間單元。例如,如果有 5 個進程,并且時間片為 20ms,那么每個進程每 100ms 會得到不超過 20ms 的時間。

RR 算法的性能很大程度取決于時間片的大小。在一種極端情況下,如果時間片很大,那么 RR 算法與 FCFS 算法一樣。相反,如果時間片很小(如 1ms),那么 RR 算法可以導致大量的上下文切換。

例如,假設我們只有一個需要 10 個時間單元的進程。如果時間片為 12 個時間單元,那么進程在一個時間片不到就能完成,而且沒有額外開銷。如果時間片為 6 個時間單元,那么進程需要 2 個時間片,并且還有一個上下文切換。如果時間片為 1 個時間單元,那么就會有 9 個上下文切換,相應地使進程執行更慢(圖 1)。

更小時間片如何增加上下文切換
圖 1 更小時間片如何增加上下文切換

因此,我們希望時間片遠大于上下文切換時間。如果上下文切換時間約為時間片的 10%,那么約 10% 的 CPU 時間會浪費在上下文切換上。在實踐中,大多數現代操作系統的時間片為 10~100ms,上下文切換的時間一般少于 10ms;因此,上下文切換的時間僅占時間片的一小部分。

周轉時間也依賴于時間片大小。正如從圖 2 中所看到的,隨著時間片大小的增加,一組進程的平均周轉時間不一定會改善。一般情況下,如果大多數進程能在一個時間片內完成,那么平均周轉時間會改善。

周轉時間如何隨著時間片大小而改變
圖 2 周轉時間如何隨著時間片大小而改變

例如,假設有三個進程,都需要 10 個時間單元。如果時間片為 1 個時間單元,那么平均周轉時間為 29;如果時間片為 10,那么平均周轉時間會降為 20;如果再考慮上下文切換時間,那么平均周轉時間對于較小時間片會增加,這是因為需要更多的上下文切換。

盡管時間片應該比上下文切換時間要大,但也不能太大。如果時間片太大,那么 RR 調度就演變成了 FCFS 調度。根據經驗,80% 的 CPU 執行應該小于時間片。

所有教程

優秀文章

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

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

底部Logo