迴圈輪詢 (RR) 排程演算法

在 CPU 排程策略中，迴圈輪詢排程是最有效和最廣泛使用的排程演算法之一，它不僅適用於作業系統的程序排程，也適用於網路排程。

迴圈輪詢 (RR) 排程

這種排程策略的名字來源於古老的迴圈輪詢原則，該原則主張所有參與者都應該輪流平等地共享資產或機會。在 RR 排程中，每個程序獲得相等的時間片（或時間量子），依次在 CPU 上執行。當一個程序輪到它時，它會執行分配的時間片，然後釋放 CPU 供佇列中的下一個程序使用。如果程序還有剩餘的突發時間，則將其傳送到佇列的末尾。程序按照先到先服務（FCFS）的原則進入佇列。

迴圈輪詢排程是搶佔式的，這意味著正在執行的程序可能會被另一個程序中斷併發送到就緒佇列，即使它尚未在 CPU 中完成整個執行。它是先到先服務 (FCFS) 排程演算法的搶佔式版本。

迴圈輪詢排程的特點

• RR 是一種公平的排程策略，所有程序都獲得平等的份額以輪流執行。
• 它是一種搶佔式排程方法，正在執行的程序必須在時間量子到期後放棄對 CPU 的控制。
• 透過 RR 排程策略，任何程序都不會發生飢餓現象。
• 它因其簡單的執行原理而被廣泛使用。
• RR 排程的效能很大程度上取決於所選擇的時間量子。

迴圈輪詢排程的執行原理

• 任何到達系統的新的程序都以 FCFS 的方式插入到就緒佇列的末尾。
• 佇列中的第一個程序被移除並分配到 CPU。
• 如果所需的突發時間小於或等於時間量子，則該程序執行到完成。當程序完成執行時，排程程式被呼叫以讓就緒佇列中的下一個程序進入 CPU。
• 如果所需的突發時間大於時間量子，則程序執行到分配的時間量子。然後更新其 PCB（程序控制塊）狀態，並將其新增到佇列的末尾。發生上下文切換，就緒佇列中的下一個程序被分配到 CPU。
• 重複上述步驟，直到就緒佇列中沒有更多程序。

我們可以透過以下示例來了解 RR 排程演算法的工作原理。

迴圈輪詢排程的示例

讓我們考慮一個系統，該系統有四個程序，它們以 P1、P2、P3 和 P4 的順序同時到達。每個程序的突發時間（以毫秒為單位）由下表給出：

讓我們考慮時間量子為 2 毫秒，並對它執行 RR 排程。我們將繪製甘特圖並找到平均週轉時間和平均等待時間。

時間量子為 2 毫秒的甘特圖

平均週轉時間

平均 TAT = 每個程序的週轉時間之和 / 程序數

$\mathrm{= \: (TAT_{P1} \: + \: TAT_{P2} \: + \: TAT_{P3} \: + \: TAT_{P4})/4}$

= ( 24 + 28 + 22+ 16) / 4 = 22.5 毫秒

為了計算每個程序的等待時間，我們將時間量子乘以程序在就緒佇列中等待的時間片數。

平均等待時間

平均 WT = 每個程序的等待時間之和 / 程序數

$\mathrm{= \: (WT_{P1} \: + \: WT_{P2} \: + \: WT_{P3} \: + \: WT_{P4})/4}$

= ( 8*2 + 9*2+ 8*2+ 6*2) / 4 = 15.5 毫秒

迴圈輪詢排程的優點

• 迴圈輪詢排程是最公平的排程演算法，所有程序都獲得相等的時間量子進行執行。
• 在 RR 排程中，完全消除了任何程序由於在就緒佇列中無限期等待而導致的飢餓現象。
• 它不需要任何複雜的方法來計算每個程序的 CPU 突發時間，然後才能進行排程。
• 它非常易於實現，因此在各種情況下都有應用。
• 在 RR 排程中不會發生像先到先服務 CPU (FCFS) 排程中那樣的車隊效應。

迴圈輪詢排程的缺點

• 迴圈輪詢排程的效能高度依賴於所選擇的時間量子。這需要在實施之前進行謹慎的分析，否則無法獲得所需的結果。
• 如果選擇的時間量子過大，大多數程序將在突發時間內完成。實際上，RR 排程將充當 FCFS 排程。因此，FCFS 的所有限制都將進入系統。
• 如果選擇的時間量子過小，CPU 將非常忙於上下文切換，即在 CPU 和記憶體之間交換進和交換出程序。這將降低系統的吞吐量，因為更多的時間將花費在上下文切換上，而不是程序的實際執行上。
• RR 排程沒有提供為程序分配優先順序的範圍。因此，需要高優先順序的系統程序與後臺程序獲得相同的優先順序。這通常會影響系統的整體效能。

結論

如果正確實現，迴圈輪詢排程可以為排程問題提供最簡單和最佳的解決方案。為了避免該演算法的缺點，正在研究和實施許多 RR 排程的變體。有助於提供接近完美時間量子的一個變體是動態時間量子排程。在這裡，時間量子根據系統中程序的行為動態變化。另一個變體，自私迴圈輪詢排程，為程序分配優先順序，併為高優先順序程序提供更多 CPU 時間片。