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

（一）先來(lái)先服務(wù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時(shí)間片的長(zhǎng)短通常由以下4個(gè)因素確定：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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