1. 先來先服務

在所有調度算法中，最簡單的是非搶占式的先來先服務（first-come first-severd）算法。使用該算法，進程按照它們請求CPU的順序使用CPU。基本上，有一個就緒進程的單一隊列。早上，當第一個作業從外部進入系統，就立即開始并允許運行它所期望的時間。不會中斷該作業，因為它需要很長的時間運行。當其他作業進入時，它們就被安排到隊列的尾部。當正在運行的進程被阻塞時，隊列中的第一個進程就接著運行。在被阻塞的進程變為就緒時，就像一個新來到的作業一樣，排到隊列的末尾。

這個算法的主要優點是易于理解并且便于在程序中運用。就難以得到的體育或音樂會票的分配問題而言，這對那些愿意在早上兩點就去排隊的人們也是公平的。在這個算法中，一個單鏈表記錄了所有就緒進程。要選取一個進程運行，只要從該隊列的頭部移走一個進程即可；要添加一個新的作業或阻塞一個進程，只要把該作業或進程附加在相應隊列的末尾即可。

缺點：假設有一個一次運行1秒鐘的計算密集型進程和很少使用CPU但是每個都要進行1000次磁盤讀操作才能完成的大量I/O密集型進程存在。計算密集進程運行1秒鐘，接著讀一個磁盤塊。所有的I/O進程開始運行并讀磁盤。當該計算密集進程獲得其磁盤塊時，它運行下一個1秒鐘，緊跟隨著的是所有I/O進程。這樣做的結果是，每個I/O進程在每秒鐘內讀到一個磁盤塊，要花費1000秒鐘才能完成操作。如果有一個調度算法每10ms搶占計算密集型進程，那么I/O進程將在10秒鐘內完成而不是1000秒鐘，而且還不會對計算密集型進程產生多少延遲。

2. 最短作業優先

適用于運行時間可以預知的另一個非搶占式的批處理調度算法。例如，一家保險公司，因為每天都做類似的工作，所以人們可以相當精確地預測處理1000個索賠的一批作業需要多少時間。當輸入隊列中有若干個同等重要的作業被啟動時，調度程序應使用最短作業優先（shortest job first）算法，請看圖2-40。這里有4個作業A、B、C、D，運行時間分別為8、4、4、4分鐘。若按圖中的次序運行，則A的周轉時間為8分鐘，B為12分鐘，C為16分鐘，D為20分鐘，平均為14分鐘。

?

圖2-40?? 最短作業優先調度的例子：a) 按原有次序運行4個作業；b) 按最短作業優先次序運行

現在考慮使用最短作業優先算法運行這4個作業，如圖2-40b所示。目前周轉時間分別為4、8、12和20分鐘，平均為11分鐘。可以證明最短作業優先是最優的。考慮有4個作業的情況，其運行時間分別為a、b、c、d。第一個作業在時間a結束，第二個在時間a + b結束，以此類推。平均周轉時間為（4a + 3b + 2c + d）/4。顯然a對平均值影響最大，所以它應是最短作業，其次是b，再次是c，最后的d只影響它自己的周轉時間。對任意數目作業的情況，道理完全一樣。

有必要指出，只有在所有的作業都可同時運行的情形下，最短作業優先算法才是最優化的。作為一個反例，考慮5個作業，從A到E，運行時間分別是2、4、1、1和1。它們的到達時間是0、0、3、3和3。開始，只能選擇A或B，因為其他三個作業還沒有到達。使用最短作業優先，將按照A、B、C、D、E的順序運行作業，其平均等待時間是4.6。但是，按照B、C、D、E、A的順序運行作業，其平均等待時間則是 4.4。

3. 最短剩余時間優先

最短作業優先的搶占式版本是最短剩余時間優先（shortest remaining time next）算法。使用這個算法，調度程序總是選擇剩余運行時間最短的那個進程運行。再次提醒，有關的運行時間必須提前掌握。當一個新的作業到達時，其整個時間同當前進程的剩余時間做比較。如果新的進程比當前運行進程需要更少的時間，當前進程就被掛起，而運行新的進程。這種方式可以使新的短作業獲得良好的服務。

總結

以上是生活随笔為你收集整理的批处理系统中的调度---先来先服务、最短作业优先、最短剩余时间优先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。