時間片輪轉調度
外觀
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/76/Round_Robin_Schedule_Example.jpg/350px-Round_Robin_Schedule_Example.jpg)
時間片輪轉調度(Round-Robin Scheduling) 是進程和網絡調度程序常用的算法之一。[1] 這一方法將相等長度的時間片按照不變的順序依次分配給每個進程[2],且在處理所有進程時不考慮任何優先級。這一算法簡單並易於實現,並且不會產生飢餓問題。時間片輪轉調度可以應用於其他調度問題,例如計算機網絡中的數據包調度。它是一個作業系統概念。[3]
該算法的名稱來自於其他領域通用的循環制原則,即每個參與者輪流獲得相同分量的物品。
進程調度
[編輯]為了公平地調度進程,循環調度程序通常採用分時機制,為每個作業分配一個時間片或時間量[4] (CPU 時間),如果用完這一分配的時間還沒有完成,則中斷該進程。下次為該進程分配時間時,該進程將恢復執行。如果進程在其時間片內終止或將其狀態更改為等待(或阻塞),則調度程序會選擇就緒隊列中的第一個進程來執行。
循環算法是一種搶占式算法,因為一旦時間片用盡,調度程序就會強制性的暫停進程的執行。
例如,如果時間片為100毫秒,而進程1完成的總時間為250毫秒,則循環調度程序將在100毫秒後暫停該進程,並讓其他進程在CPU上占用時間。一旦其他執行緒都使用過一次相同的時間片(100毫秒),進程1將獲得另一次CPU時間分配。這個過程一直將持續循環到進程結束並且不需要更多的CPU時間。
例子
[編輯]在時間片長度為100毫秒的系統中,考慮下表所列舉的進程:
進程名稱 | 開始時間(ms) | 執行時間(ms) |
---|---|---|
P0 | 0 | 250 |
P1 | 50 | 170 |
P2 | 130 | 75 |
P3 | 190 | 100 |
P4 | 210 | 130 |
P5 | 350 | 50 |
![時間片輪轉調度](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/RoundRobin.jpg/400px-RoundRobin.jpg)
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C., Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books, 2014 [2022-12-28], (原始內容存檔 (PDF)於2018-10-13)
- ^ Stallings, William. Operating Systems: Internals and Design Principles. Pearson. 2015: 409. ISBN 978-0-13-380591-8.
- ^ Nash, Stacey L. Best scheduling software of 2022. Popular Science. 2022-06-11 [2022-07-07]. (原始內容存檔於2022-12-28) (英語).
- ^ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg. Process Scheduling 8th. John Wiley & Sons (Asia). 2010: 194. ISBN 978-0-470-23399-3.
5.3.4 Round Robin Scheduling