明確先來先服務(wù)FCFS、時間片輪轉(zhuǎn)RR、優(yōu)先級三種常用的調(diào)度算法的實現(xiàn)思想，并在此基礎(chǔ)上計算周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

（一）先來先服務(wù)

先來先服務(wù)（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）方法是最簡單的一種調(diào)度算法。它的實現(xiàn)思想就是“排隊買票”的辦法。對于作業(yè)調(diào)度來說，按照先來先服務(wù)法，是每次調(diào)度從后備作業(yè)隊列（按進(jìn)入時間先后為序）中選擇隊頭的一個或幾個作業(yè)，把它們調(diào)入內(nèi)存，分配相應(yīng)的資源，創(chuàng)建進(jìn)程，然后把進(jìn)程放入就緒隊列。

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

設(shè)有3個作業(yè)，編號為1，2，3，各作業(yè)分別對應(yīng)一個進(jìn)程。各作業(yè)依次到達(dá)，相差一個時間單位。圖示出采用FCFS方式調(diào)度時這3個作業(yè)的執(zhí)行順序。

FCFS調(diào)度算法示意圖

根據(jù)圖，可算出各作業(yè)的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間等，如表所示。

表 FCFS調(diào)度算法性能

由表可以看出，F(xiàn)CFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。因為短作業(yè)運行時間很短，如果讓它等待較長時間才得到服務(wù)，它的帶權(quán)周轉(zhuǎn)時間就會很長。

另外，F(xiàn)CFS調(diào)度算法對CPU繁忙型作業(yè)（指需要大量CPU時間進(jìn)行計算的作業(yè)）較有利，而不利于I/O繁忙型作業(yè)（指需要頻繁請求I/O的作業(yè)）。因為在執(zhí)行I/O操作時，往往該作業(yè)（進(jìn)程）要放棄對CPU的占有。當(dāng)I/O完成后要進(jìn)入就緒隊列排隊，可能要等待相當(dāng)長一段時間，才得到較短時間的CPU服務(wù)，從而使這種作業(yè)的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間都很大。

FCFS調(diào)度算法容易實現(xiàn)，但它的效率較低。

（二）時間片輪轉(zhuǎn)法

時間片輪轉(zhuǎn)法（Round-Robin，RR）主要用于分時系統(tǒng)中的進(jìn)程調(diào)度。為實現(xiàn)輪轉(zhuǎn)調(diào)度，系統(tǒng)把所有就緒進(jìn)程按先入先出的原則排成一個隊列。新來的進(jìn)程加到就緒隊列末尾。每當(dāng)執(zhí)行進(jìn)程調(diào)度時，進(jìn)程調(diào)度程序總是選出就緒隊列的隊首進(jìn)程，讓它在CPU上運行一個時間片的時間。

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

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

RR法（q=1和q=4時進(jìn)程運行情況）

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

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

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

（1）系統(tǒng)的響應(yīng)時間。在進(jìn)程數(shù)目一定時，時間片的長短直接正比于系統(tǒng)對響應(yīng)時間的要求。

（2）就緒隊列進(jìn)程的數(shù)目。當(dāng)系統(tǒng)要求的響應(yīng)時間一定時，時間片的大小反比于就緒隊列中的進(jìn)程數(shù)。

（3）進(jìn)程的轉(zhuǎn)換時間。若執(zhí)行進(jìn)程調(diào)度時的轉(zhuǎn)換時間為t，時間片為q，為保證系統(tǒng)開銷不大于某個標(biāo)準(zhǔn)，應(yīng)使比值t/q不大于某一數(shù)值，如1/10。

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

（三）優(yōu)先級法

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

在進(jìn)程調(diào)度時，當(dāng)前就緒隊列中有最高優(yōu)先級的那個進(jìn)程獲得CPU的使用權(quán)。以后在該進(jìn)程的運行過程中，如果在就緒隊列中出現(xiàn)優(yōu)先級更高的進(jìn)程時，怎么辦？有兩種不同的處理方式。

（1）非搶占式優(yōu)先級法。這種辦法就是：當(dāng)前占用CPU的進(jìn)程一直運行下去，直到完成任務(wù)或者因等待某事件而主動讓出CPU時，系統(tǒng)才讓另一個優(yōu)先級高的進(jìn)程占用CPU。

（2）搶占式優(yōu)先級法。這種辦法就是：當(dāng)前進(jìn)程在運行過程中，一旦有另一個優(yōu)先級更高的進(jìn)程出現(xiàn)在就緒隊列中，進(jìn)程調(diào)度程序就停止當(dāng)前進(jìn)程的運行，強行將CPU分給那個進(jìn)程。

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

進(jìn)程的優(yōu)先級是“一定終身”、還是“隨機應(yīng)變”？這涉及兩種確定進(jìn)程優(yōu)先級的方式：靜態(tài)方式和動態(tài)方式。

（1）靜態(tài)優(yōu)先級是在創(chuàng)建進(jìn)程時就確定下來的，而且在進(jìn)程的整個運行期間保持不變。往往利用上述的內(nèi)部定義或外部指定的辦法規(guī)定進(jìn)程的靜態(tài)優(yōu)先級。

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

靜態(tài)優(yōu)先級調(diào)度算法易于實現(xiàn)，系統(tǒng)開銷小。但其主要問題是會出現(xiàn)“饑餓”現(xiàn)象。即某些低優(yōu)先級的進(jìn)程無限期地等待CPU。在負(fù)載很重的計算機系統(tǒng)中，如果高優(yōu)先級的進(jìn)程很多，形成一個穩(wěn)定的進(jìn)程流，就使得低優(yōu)先級進(jìn)程任何時候也得不到CPU。

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

對于作業(yè)調(diào)度同樣可采用優(yōu)先級法，即系統(tǒng)從后備作業(yè)隊列中選擇一批優(yōu)先級相對高的作業(yè)調(diào)入內(nèi)存。

設(shè)有如下一組進(jìn)程，它們都在時刻0到達(dá)，依次為P1，P2，…，P5，各自的運行時間和優(yōu)先數(shù)如表所示。采用優(yōu)先級調(diào)度算法，這5個進(jìn)程的執(zhí)行順序如圖所示。可以算出，這5個進(jìn)程的平均周轉(zhuǎn)時間是12個時間單位。