輪詢 (RR) 是一種先佔式 CPU 排程演算法，每個進程獲得固定時間片稱作量子。不同於到達時間為零的標準輪詢，此變體處理不同時刻到達的進程，使排程更複雜，因就緒佇列動態變化。
在先佔式排程中，執行中進程可被中斷並移回就緒佇列。輪詢透過給每個進程平等 CPU 時間確保公平性，防止飢餓並維持互動系統的良好回應時間。
不同到達時間下的輪詢運作方式
當進程有不同到達時間，演算法遵循以下步驟：
- 進程根據到達時間進入就緒佇列
- CPU 服務第一個可用進程持續量子時長
- 若進程在量子內完成則終止
- 未完成則移至就緒佇列末端
- 新到達進程加入就緒佇列等待輪到
- 上下文切換儲存被先佔進程狀態
關鍵特性
- 防止飢餓：每個進程最終都能獲得 CPU 時間
- 公平排程：所有進程獲得相等時間量子
- 良好回應時間：適合互動和即時系統
- 上下文切換開銷：較小量子增加切換成本
範例 1 量子時間 = 2
考慮三個具有不同到達和爆發時間的進程：
| 進程 | 到達時間 | 爆發時間 |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 7 |
甘特圖 — 輪詢 (量子 = 2) P1 P2 P3 P1 P2 P3 0 2 4 6 8 9 14
逐步執行
| 時間 | 進程 | 就緒佇列 | 動作 |
|---|---|---|---|
| 0-2 | P1 | P1 | P1 執行 2 單位，P2 在 t=1 到達 |
| 2-4 | P2 | P2, P1 | P2 執行 2 單位，P3 在 t=2 到達 |
| 4-6 | P3 | P3, P1 | P3 執行 2 單位 |
| 6-8 | P1 | P1, P2, P3 | P1 完成剩餘 2 單位 |
| 8-9 | P2 | P2, P3 | P2 完成剩餘 1 單位 |
| 9-14 | P3 | P3 | P3 完成剩餘 5 單位 |
計算平均時間
| 進程 | 到達 | 爆發 | 完成 | 周轉 | 等待 |
|---|---|---|---|---|---|
| P1 | 0 | 4 | 8 | 8 | 4 |
| P2 | 1 | 3 | 9 | 8 | 5 |
| P3 | 2 | 7 | 14 | 12 | 5 |
平均周轉時間 = (8 + 8 + 12) / 3 = 9.33 單位
平均等待時間 = (4 + 5 + 5) / 3 = 4.67 單位
範例 2 量子時間 = 4
較大量子大小下：
| 進程 | 到達時間 | 爆發時間 |
|---|---|---|
| P1 | 2 | 8 |
| P2 | 0 | 7 |
| P3 | 1 | 9 |
甘特圖 — 輪詢 (量子 = 4) P2 P3 P1 P2 P3 P1 0 4 8 12 15 20 24
| 進程 | 到達 | 爆發 | 完成 | 周轉 | 等待 |
|---|---|---|---|---|---|
| P1 | 2 | 8 | 24 | 22 | 14 |
| P2 | 0 | 7 | 15 | 15 | 8 |
| P3 | 1 | 9 | 20 | 19 | 10 |
平均周轉時間 = (22 + 15 + 19) / 3 = 18.67 單位
平均等待時間 = (14 + 8 + 10) / 3 = 10.67 單位
結論
具有不同到達時間的輪詢排程在處理動態進程到達時提供公平 CPU 分配。量子大小顯著影響效能 — 較小量子改善回應時間但增加上下文切換開銷，較大量子可能降低公平性但提高吞吐量。
