時間片輪轉（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 的時間片，那麼 P₁ 會執行最初的 4ms。由於它還需要 20ms，所以在第一個時間片之後它會被搶占，而 CPU 就交給佇列中的下一個進程。由於 P₂ 不需要 4ms，所以在其時間片用完之前就會退出。CPU 接著交給下一個進程，即進程 P₃。在每個進程都得到了一個時間片之後，CPU 又交給了進程 P₁ 以便繼續執行。因此，RR 排程結果如下：

---