明確先來先服務FCFS、時間片輪轉RR、優先級三種常用的調度算法的實現思想，并在此基礎上計算周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間。

（一）先來先服務

先來先服務（First-Come，First-Served，FCFS）方法是最簡單的一種調度算法。它的實現思想就是“排隊買票”的辦法。對于作業調度來說，按照先來先服務法，是每次調度從后備作業隊列（按進入時間先后為序）中選擇隊頭的一個或幾個作業，把它們調入內存，分配相應的資源，創建進程，然后把進程放入就緒隊列。

對于進程調度算法來說，采用先來先服務法，就是每次調度從就緒隊列中選擇一個最先進入該隊列的進程，把CPU分給它，令其投入運行。該進程一直運行下去，直至完成或者由于某些原因而阻塞，才放棄CPU。這樣，當一個進程進入就緒隊列時，它的PCB就鏈入就緒隊列的末尾。每次進程調度時就把隊頭進程從該隊列中摘下，分給它CPU，使它運行。

設有3個作業，編號為1，2，3，各作業分別對應一個進程。各作業依次到達，相差一個時間單位。圖示出采用FCFS方式調度時這3個作業的執行順序。

FCFS調度算法示意圖

根據圖，可算出各作業的周轉時間和帶權周轉時間等，如表所示。

表 FCFS調度算法性能

由表可以看出，FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。因為短作業運行時間很短，如果讓它等待較長時間才得到服務，它的帶權周轉時間就會很長。

另外，FCFS調度算法對CPU繁忙型作業（指需要大量CPU時間進行計算的作業）較有利，而不利于I/O繁忙型作業（指需要頻繁請求I/O的作業）。因為在執行I/O操作時，往往該作業（進程）要放棄對CPU的占有。當I/O完成后要進入就緒隊列排隊，可能要等待相當長一段時間，才得到較短時間的CPU服務，從而使這種作業的周轉時間和帶權周轉時間都很大。

FCFS調度算法容易實現，但它的效率較低。

（二）時間片輪轉法

時間片輪轉法（Round-Robin，RR）主要用于分時系統中的進程調度。為實現輪轉調度，系統把所有就緒進程按先入先出的原則排成一個隊列。新來的進程加到就緒隊列末尾。每當執行進程調度時，進程調度程序總是選出就緒隊列的隊首進程，讓它在CPU上運行一個時間片的時間。

時間片是一個小的時間單位，通常為10至100毫秒數量級。當進程用完分給它的時間片后，系統的計時器發出時鐘中斷，調度程序便停止該進程的運行，并把它放入就緒隊列的末尾；然后，把CPU分給就緒隊列的隊首進程，同樣也讓它運行一個時間片，如此往復。

例如，考慮如下4個進程A、B、C和D的執行情況。設它們依次進入就緒隊列，但彼此相差時間很少，可以近似認為“同時”到達。四個進程分別需要運行12，5，3和6個時間單位。圖3-6示出時間片q=1和q=4時它們運行的情況。

RR法（q=1和q=4時進程運行情況）

由圖可以看出，在輪轉法中，一次輪回時間內分給任何進程的CPU時間都不會大于一個時間片。如果一個進程在一個時間片內沒有做完自己的事情，那么在時間片用完后，該進程就失去對CPU的控制權，被放到就緒隊列的末尾。所以，一個運行較長時間的進程需要經過多次輪轉才能完成。

可見，時間片的大小對輪轉法的性能有很大影響。如果時間片太長，每個進程都在這段時間內運行完畢，那么時間片輪轉法就退化為先來先服務算法。很顯然，對用戶的響應時間必然加長。如果時間片太短，CPU在進程間的切換工作就非常頻繁，從而導致系統開銷增加。因為在每個時間片末尾，都產生時鐘中斷，操作系統要處理這個中斷，在把CPU分給另一個進程之前，要為“老”的進程保留全部寄存器的內容，還要為新選中的進程裝配所有寄存器的值。這一工作無疑加大了系統開銷。

時間片的長短通常由以下4個因素確定：

（1）系統的響應時間。在進程數目一定時，時間片的長短直接正比于系統對響應時間的要求。

（2）就緒隊列進程的數目。當系統要求的響應時間一定時，時間片的大小反比于就緒隊列中的進程數。

（3）進程的轉換時間。若執行進程調度時的轉換時間為t，時間片為q，為保證系統開銷不大于某個標準，應使比值t/q不大于某一數值，如1/10。

（4）CPU運行指令速度。CPU運行速度快，則時間片可以短些；反之，則應取長些。

（三）優先級法

“急事先辦”、“重要的事先辦”，這是大家都熟知的辦事原則。先辦就是優先處理，表明急事、重要的事有最高的優先級。在操作系統中也經常使用優先級法作為作業調度和進程調度的算法。利用優先級調度算法進行進程調度時，是從就緒隊列中選出優先級最高的進程，把CPU分給它使用。

在進程調度時，當前就緒隊列中有最高優先級的那個進程獲得CPU的使用權。以后在該進程的運行過程中，如果在就緒隊列中出現優先級更高的進程時，怎么辦？有兩種不同的處理方式。

（1）非搶占式優先級法。這種辦法就是：當前占用CPU的進程一直運行下去，直到完成任務或者因等待某事件而主動讓出CPU時，系統才讓另一個優先級高的進程占用CPU。

（2）搶占式優先級法。這種辦法就是：當前進程在運行過程中，一旦有另一個優先級更高的進程出現在就緒隊列中，進程調度程序就停止當前進程的運行，強行將CPU分給那個進程。

進程的優先級如何確定呢？一般說來，進程優先級可由系統內部定義或由外部指定。內部決定優先級是利用某些可度量的量來定義一個進程的優先級。例如，進程類型、進程對資源的需求（時間限度、需要內存大小、打開文件的數目、I/O平均工作時間與CPU平均工作時間的比值等），用它們來計算優先級。外部優先級是按操作系統以外的標準設置的，例如，使用計算機所付款的類型和總數，使用計算機的部門以及其他的外部因素。

進程的優先級是“一定終身”、還是“隨機應變”？這涉及兩種確定進程優先級的方式：靜態方式和動態方式。

（1）靜態優先級是在創建進程時就確定下來的，而且在進程的整個運行期間保持不變。往往利用上述的內部定義或外部指定的辦法規定進程的靜態優先級。

優先級一般用某個固定范圍內的整數表示，例如0～7或0～4095中的某一個數。這種整數稱作優先數。注意，優先級與優先數的對應關系因系統而異，在有些系統中優先數越大，優先級越高；而另外一些系統則恰恰相反，優先數越小，優先級越高，如UNIX/linux系統就是這樣。本書采用“優先數小、優先級高”的表示方式。

靜態優先級調度算法易于實現，系統開銷小。但其主要問題是會出現“饑餓”現象。即某些低優先級的進程無限期地等待CPU。在負載很重的計算機系統中，如果高優先級的進程很多，形成一個穩定的進程流，就使得低優先級進程任何時候也得不到CPU。

（2）動態優先級是隨著進程的推進而不斷改變的。解決低優先級進程“饑餓”問題的一種辦法是“論年頭”。這種辦法使系統中等待CPU很長時間的進程逐漸提升其優先級。例如在UNIX系統中，正在運行的用戶進程隨著占用CPU時間的加長，其優先數也逐漸增加（優先級降低）；而在就緒隊列中的用戶進程隨著等待CPU時間的加長，其優先數遞減（優先級漸升）。經過一段時間后，原來級別較低的進程的優先級就升上去，而正在運行進程的級別就降下來，從而實現“負反饋”作用—— 防止一個進程長期占用CPU，也避免發生“饑餓”現象。

對于作業調度同樣可采用優先級法，即系統從后備作業隊列中選擇一批優先級相對高的作業調入內存。

設有如下一組進程，它們都在時刻0到達，依次為P1，P2，…，P5，各自的運行時間和優先數如表所示。采用優先級調度算法，這5個進程的執行順序如圖所示?？梢运愠觯@5個進程的平均周轉時間是12個時間單位。

優先級調度算法執行順序