1、先來先服務(wù)調(diào)度算法 先來先服務(wù)（FCFS）調(diào)度算法是一種最簡單的調(diào)度算法，該調(diào)度算法既可以用于作業(yè)調(diào)度也可以用于進(jìn)程調(diào)度。 在作業(yè)調(diào)度中，先來先服務(wù)調(diào)度算法每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入該隊(duì)列的一個(gè)或幾個(gè)作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。 在進(jìn)程調(diào)度中，先來先服務(wù)調(diào)度算法每次從就緒隊(duì)列中選擇最先進(jìn)入該隊(duì)列的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行，該進(jìn)程一直運(yùn)行下去，直到完成或某種原因而阻塞時(shí)才釋放處理機(jī)。 例1：假設(shè)系統(tǒng)中有3個(gè)進(jìn)程P1，P2和P3，它們的運(yùn)行時(shí)間依次是24，3，3（單位為ms）。如果進(jìn)程P1，P2，P3依次在0,1,2時(shí)刻到達(dá)，并且采用FCFS調(diào)度

2、算法計(jì)算其平均等待時(shí)間。2427300進(jìn)程時(shí)間（ms）P1P2P3(a)(b)3個(gè)進(jìn)程執(zhí)行的甘特圖FCFS調(diào)度算法性能表進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1024024241P2132427268.67P3232730289.33平均周轉(zhuǎn)時(shí)間=（24+26+28）/3=26平均帶權(quán)周轉(zhuǎn)時(shí)間=（1+8.67+9.33）/3=6.33進(jìn)程P1的等待時(shí)間是0ms，進(jìn)程P2的等待時(shí)間是23ms，P3的等待時(shí)間是25ms。這樣，平均等待時(shí)間是（0+23+25）/3=16ms如果進(jìn)程到達(dá)的順序是P2，P3，P1，那么得到的平均等待時(shí)間是（4+0+2）/3=2ms。平均等待時(shí)間很明顯

3、地減少了。因而，F(xiàn)CFS策略下的平均等待時(shí)間通常不是最小的，而且如果進(jìn)程的執(zhí)行時(shí)間有明顯的變化時(shí)平均時(shí)間也會(huì)有明顯的變化。FCFS調(diào)度算法是非搶占式的。一旦CPU被分配給一個(gè)進(jìn)程，該進(jìn)程將持有CPU直到它釋放CPU（通過終止或請(qǐng)求I/O）。對(duì)分時(shí)系統(tǒng)來說，F(xiàn)CFS算法尤其糟糕，因?yàn)檫@種系統(tǒng)中的每個(gè)用戶以有規(guī)則的時(shí)間間隔共享CPU。允許一個(gè)進(jìn)程長期地占有CPU會(huì)產(chǎn)生災(zāi)難性的后果。先來先服務(wù)調(diào)度算法的特點(diǎn)是算法簡單，但效率較低；有利于長作業(yè)，但對(duì)短作業(yè)不利；有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)最短作業(yè)優(yōu)先法短作業(yè)優(yōu)先（SJF）調(diào)度算法用于進(jìn)程調(diào)度時(shí)稱為短進(jìn)程優(yōu)先調(diào)度算法，該調(diào)度算法主要

4、用于作業(yè)調(diào)度。其實(shí)現(xiàn)思想是：從作業(yè)的后備隊(duì)列中挑選那些需要運(yùn)行的時(shí)間（估計(jì)值）最短的作業(yè)放入內(nèi)存。這是一種非搶占式的策略。系統(tǒng)一旦選中某個(gè)短作業(yè)后，就讓該作業(yè)投入執(zhí)行，直到該作業(yè)完成并退出系統(tǒng)。如果有四個(gè)作業(yè)A，B，C，D。它們的預(yù)計(jì)運(yùn)行時(shí)間分別為6，3，15，8個(gè)時(shí)間單位，利用最短作業(yè)優(yōu)先法調(diào)度，它們的執(zhí)行順序是：B-A-D-C。例2 假設(shè)系統(tǒng)中有4個(gè)作業(yè)A，B，C，D。下表給出了提交時(shí)間和運(yùn)行時(shí)間作業(yè)提交時(shí)間運(yùn)行時(shí)間/hA5:002B6:000.5C6:300.2D6:360.4 由于作業(yè)A的開始時(shí)間是5：00，而其余作業(yè)均未到達(dá)，故先運(yùn)行作業(yè)A，當(dāng)作業(yè)A運(yùn)行完畢，其余作業(yè)均按短作業(yè)優(yōu)先運(yùn)

5、行。所以作業(yè)運(yùn)行次序?yàn)椋篈，C，D，B。最短作業(yè)優(yōu)先調(diào)度算法的調(diào)度性能作業(yè)提交時(shí)間運(yùn)行時(shí)間/h開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間/h帶權(quán)周轉(zhuǎn)時(shí)間A5:0025:007:002.01B6:000.57:368:062.14.2C6:300.27:007:120.73.5D6:360.47:127:361.02.5 由此：此作業(yè)流的平均周轉(zhuǎn)時(shí)間為T=（2.0+2.1+0.7+1.0）/4=1.45h。此作業(yè)流的平均帶權(quán)周轉(zhuǎn)時(shí)間為W=（1.0+4.2+3.5+2.5）/4=2.8h。 通過以上分析，雖然這種算法易于實(shí)現(xiàn)，且效率也比較高，但未考慮長作業(yè)的利益輪轉(zhuǎn)法（Round-Robin,RR）時(shí)間片是一個(gè)很小

6、的時(shí)間單位，通常為10100ms數(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ù)。例3：考慮如下四個(gè)進(jìn)程A，B，C，D的執(zhí)行情況。設(shè)它們依次進(jìn)入就緒隊(duì)列，但彼此相差時(shí)間很短，可以近似認(rèn)為“同時(shí)”到達(dá)隊(duì)列。四個(gè)進(jìn)程分別需要運(yùn)行12，5，3和6個(gè)時(shí)間單位。下圖為時(shí)間片q等于1和等于4時(shí)它們運(yùn)行情況。510152025260ABCDABCD進(jìn)程tq=4q=1RR法（q=1和q=4時(shí)進(jìn)程的運(yùn)行情況）時(shí)間片進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間時(shí)

7、間片q=1A012026262.17B05117173.4C03211113.67D06320203.33平均周轉(zhuǎn)時(shí)間T=18.5 平均帶權(quán)周轉(zhuǎn)時(shí)間W=3.14時(shí)間片q=4A012026262.17B05420204C03811113.67D061122223.67平均周轉(zhuǎn)時(shí)間T=19.75 平均帶權(quán)周轉(zhuǎn)時(shí)間W=3.38RR調(diào)度算法的性能指標(biāo)可見，時(shí)間片的大小對(duì)輪轉(zhuǎn)法的性能有很大的影響。如果時(shí)間片太長，每個(gè)進(jìn)程都在這段時(shí)間運(yùn)行完畢，那么時(shí)間輪轉(zhuǎn)法就退化為先來先服務(wù)算法，這樣對(duì)用戶的響應(yīng)時(shí)間必然會(huì)加長。如果時(shí)間片太短，CPU在進(jìn)程間的切換工作就非常頻繁，從而導(dǎo)致系統(tǒng)開銷增加，因?yàn)樵诿總€(gè)時(shí)間片末尾

8、都產(chǎn)生時(shí)鐘中斷。操作系統(tǒng)要處理這個(gè)中斷，在把CPU分給另一個(gè)進(jìn)程之前，要為“老”的進(jìn)程保留全部寄存器的內(nèi)容，還要為新選中的進(jìn)程裝配所有寄存器的值，這一工作無疑加大了系統(tǒng)開銷。時(shí)間片的長短通常由以下四個(gè)因素確定： （1）系統(tǒng)的響應(yīng)時(shí)間。在進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長短直接正比于系統(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)開銷不大于某個(gè)標(biāo)準(zhǔn)，應(yīng)使比值t/q不大于某一數(shù)值，如1/10。 （4）CPU運(yùn)行指令速度。CPU運(yùn)行速度快，則時(shí)間片可以短些；反之，

9、則應(yīng)取長些。最高響應(yīng)優(yōu)先法以例2為例，由于作業(yè)A的開始時(shí)間是5:00，而其余作業(yè)均未到達(dá)，故先運(yùn)行作業(yè)A。當(dāng)作業(yè)A運(yùn)行完畢，計(jì)算后備隊(duì)列中作業(yè)B，C，D的響應(yīng)比。計(jì)算如下 作業(yè)B：R=（W+T）/T=（1+0.5）/0.5=3 作業(yè)C：R=（W+T）/T=（0.5+0.2）/0.2=3.5 作業(yè)D：R=（W+T）/T=（0.4+0.4）/0.4=2 可見作業(yè)C的響應(yīng)最高，選擇作業(yè)C運(yùn)行，故作業(yè)C的開始時(shí)間為作業(yè)A的完成時(shí)間，即7：00，當(dāng)作業(yè)C運(yùn)行完畢，計(jì)算后備隊(duì)列作業(yè)B，D的響應(yīng)比，計(jì)算如下 作業(yè)B：R=（W+T）/T=（1.2+0.5）/0.5=3.4 作業(yè)D：R=（W+T）/T=（0.6

10、+0.4）/0.4=2.5 顯然這次應(yīng)該選擇作業(yè)B，故作業(yè)B的開始時(shí)間是作業(yè)C的完成時(shí)間，即7：12，最后運(yùn)行作業(yè)D。故作業(yè)的次序是A，C，B，D作業(yè)號(hào)提交時(shí)間運(yùn)行時(shí)間/h開始時(shí)間完成時(shí)間/h周轉(zhuǎn)時(shí)間/h帶權(quán)周轉(zhuǎn)時(shí)間A5:0025:007:002.01B6:000.57:127:421.73.4C6:300.27:007:120.73.5D6:360.47:428:061.53.75最高響應(yīng)比優(yōu)先法的調(diào)度性能由此：此作業(yè)流的平均周轉(zhuǎn)時(shí)間T=（2.0+1.7+0.7+1.5）/4=1.475h 此作業(yè)流的平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+3.4+3.5+3.75)/4=2.9125h作業(yè)（10月24號(hào)）系統(tǒng)有5個(gè)進(jìn)程，其到達(dá)時(shí)間，運(yùn)行時(shí)間如下表所示，若采用先來先服務(wù)，最短作業(yè)，最高響應(yīng)比優(yōu)先，時(shí)間片輪轉(zhuǎn)調(diào)度算法（時(shí)間片q=1）,計(jì)算相關(guān)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間P103P226P344P4