時間片輪轉

時間片輪轉調度是一種最古老,最簡單,最公平且使用最廣的算法,又稱RR調度。每個進程被分配一個時間段,稱作它的時間片,即該進程允許運行的時間。

基本介紹

  • 中文名:時間片輪轉
  • 外文名:Round robin
  • 注意:時間片設得太短會導致頻繁切換
  • 套用:分時作業系統
基本原理,時間片長度的影響,時間片大小的確定,

基本原理

在早期的時間片輪轉法中,系統將所有的就緒進程按先來先服務的原則,排成一個佇列,每次調度時,把CPU分配給隊首進程,並令其執行一個時間片。時間片的大小從幾ms到幾百ms。當執行的時間片用完時,由一個計時器發出時鐘中斷請求,調度程式便據此信號來停止該進程的執行,並將它送往就緒佇列的末尾;然後,再把處理機分配給就緒佇列中新的隊首進程,同時也讓它執行一個時間片。這樣就可以保證就緒佇列中的所有進程,在一給定的時間內,均能獲得一時間片的處理機執行時間。
如果在時間片結束時進程還在運行,則CPU將被剝奪並分配給另一個進程。如果進程在時間片結束前阻塞或結束,則CPU當即進行切換。調度程式所要做的就是維護一張就緒進程列表,當進程用完它的時間片後,它被移到佇列的末尾。

時間片長度的影響

時間片輪轉調度中特別需要關注的是時間片的長度。從一個進程切換到另一個進程是需要一定時間的--保存和裝入暫存器值及記憶體映像,更新各種表格和佇列等。假如進程切換(process switch) - 有時稱為上下文切換(context switch),需要5毫秒,再假設時間片設為20毫秒,則在做完20毫秒有用的工作之後,CPU將花費5毫秒來進行進程切換。CPU時間的20%被浪費在了管理開銷上。
為了提高CPU效率,我們可以將時間片設為500毫秒。這時浪費的時間只有1%。但考慮在一個分時系統中,如果有十個互動用戶幾乎同時按下回車鍵,將發生什麼情況?假設所有其他進程都用足它們的時間片的話,最後一個不幸的進程不得不等待5秒鐘才獲得運行機會。多數用戶無法忍受一條簡短命令要5秒鐘才能做出回響。同樣的問題在一台支持多道程式個人計算機上也會發生。
結論可以歸結如下:時間片設得太短會導致過多的進程切換,降低了CPU效率;而設得太長又可能引起對短的互動請求的回響變差。

時間片大小的確定

1.系統對回響時間的要求
2.就緒佇列中進程的數目
3.系統的處理能力

相關詞條

熱門詞條

聯絡我們