第05講-進(jìn)程調(diào)度

1、12021/8/141第第 五五 講講清華大學(xué)軟件學(xué)院清華大學(xué)軟件學(xué)院22021/8/1422.6 進(jìn)程調(diào)度進(jìn)程調(diào)度在多道系統(tǒng)當(dāng)中，往往有多個(gè)進(jìn)程同時(shí)在內(nèi)存中在多道系統(tǒng)當(dāng)中，往往有多個(gè)進(jìn)程同時(shí)在內(nèi)存中運(yùn)行。在任何時(shí)刻，一個(gè)進(jìn)程只可能是以下三種運(yùn)行。在任何時(shí)刻，一個(gè)進(jìn)程只可能是以下三種狀態(tài)之一：狀態(tài)之一：v 運(yùn)行狀態(tài)：該進(jìn)程正在運(yùn)行狀態(tài)：該進(jìn)程正在CPU上運(yùn)行，每個(gè)上運(yùn)行，每個(gè)CPU 上最多只能有一個(gè)進(jìn)程在運(yùn)行；上最多只能有一個(gè)進(jìn)程在運(yùn)行；v 就緒狀態(tài)：進(jìn)程已經(jīng)就緒，隨時(shí)可以運(yùn)行；就緒狀態(tài)：進(jìn)程已經(jīng)就緒，隨時(shí)可以運(yùn)行；v 阻塞狀態(tài)：如在某個(gè)信號(hào)量上被阻塞，等待阻塞狀態(tài)：如在某個(gè)信號(hào)量上被阻塞，等

2、待I/O與此相對(duì)應(yīng)，操作系統(tǒng)會(huì)維護(hù)相應(yīng)的狀態(tài)隊(duì)列。與此相對(duì)應(yīng)，操作系統(tǒng)會(huì)維護(hù)相應(yīng)的狀態(tài)隊(duì)列。32021/8/143就緒隊(duì)列和各種就緒隊(duì)列和各種I/O設(shè)備隊(duì)列設(shè)備隊(duì)列（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）選擇誰(shuí)去運(yùn)行？選擇誰(shuí)去運(yùn)行？42021/8/144 在操作系統(tǒng)中，負(fù)責(zé)去做這個(gè)選擇的那在操作系統(tǒng)中，負(fù)責(zé)去做這個(gè)選擇的那 部分程序，稱為部分程序，稱為調(diào)度程序調(diào)度程序(scheduler)； 調(diào)度程序在決策過(guò)程中所采用的算法，調(diào)度程序在決策過(guò)程中所采用的算法， 稱為是稱為是調(diào)度算法調(diào)度算法； 調(diào)

3、度程序是調(diào)度程序是CPU資源的管理者；資源的管理者； 調(diào)度的對(duì)象是進(jìn)程，也可以是線程，大調(diào)度的對(duì)象是進(jìn)程，也可以是線程，大 多數(shù)的調(diào)度問(wèn)題對(duì)兩者都是適用的。多數(shù)的調(diào)度問(wèn)題對(duì)兩者都是適用的。52021/8/1452.6.1 關(guān)于調(diào)度的若干問(wèn)題關(guān)于調(diào)度的若干問(wèn)題1. 歷史背景q 在早期的簡(jiǎn)單批處理系統(tǒng)當(dāng)中，調(diào)度算法很簡(jiǎn)在早期的簡(jiǎn)單批處理系統(tǒng)當(dāng)中，調(diào)度算法很簡(jiǎn) 單：選擇磁帶上的下一個(gè)作業(yè)運(yùn)行；單：選擇磁帶上的下一個(gè)作業(yè)運(yùn)行；q 隨著分時(shí)系統(tǒng)的出現(xiàn)，同時(shí)有多個(gè)用戶在等待隨著分時(shí)系統(tǒng)的出現(xiàn)，同時(shí)有多個(gè)用戶在等待 服務(wù)，使得調(diào)度算法變得越來(lái)越復(fù)雜。有些大服務(wù)，使得調(diào)度算法變得越來(lái)越復(fù)雜。有些大 型機(jī)系統(tǒng)還

4、把批處理與分時(shí)結(jié)合在一起，更增型機(jī)系統(tǒng)還把批處理與分時(shí)結(jié)合在一起，更增 大了難度。由于當(dāng)時(shí)的大了難度。由于當(dāng)時(shí)的CPU時(shí)間是一種稀缺資時(shí)間是一種稀缺資 源，因此調(diào)度算法的好壞將直接影響到系統(tǒng)的源，因此調(diào)度算法的好壞將直接影響到系統(tǒng)的 性能和用戶的滿意度，算法的設(shè)計(jì)很受重視。性能和用戶的滿意度，算法的設(shè)計(jì)很受重視。62021/8/146q 隨著個(gè)人計(jì)算機(jī)時(shí)代的到來(lái)，形勢(shì)發(fā)生了變化。隨著個(gè)人計(jì)算機(jī)時(shí)代的到來(lái)，形勢(shì)發(fā)生了變化。 首先，在首先，在PC上通常只有一個(gè)進(jìn)程在活動(dòng)，這樣，上通常只有一個(gè)進(jìn)程在活動(dòng)，這樣， 調(diào)度程序無(wú)事可做。其次，計(jì)算機(jī)變得越來(lái)越快調(diào)度程序無(wú)事可做。其次，計(jì)算機(jī)變得越來(lái)越快,

5、CPU已不是稀缺資源了，哪個(gè)程序先運(yùn)行或運(yùn)行已不是稀缺資源了，哪個(gè)程序先運(yùn)行或運(yùn)行, 已經(jīng)不重要了。因此，調(diào)度算法的作用已經(jīng)顯得已經(jīng)不重要了。因此，調(diào)度算法的作用已經(jīng)顯得 微不足道了。微不足道了。q 不過(guò)，對(duì)于那些高端聯(lián)網(wǎng)工作站和服務(wù)器而言，不過(guò)，對(duì)于那些高端聯(lián)網(wǎng)工作站和服務(wù)器而言， 多個(gè)進(jìn)程需要同時(shí)競(jìng)爭(zhēng)多個(gè)進(jìn)程需要同時(shí)競(jìng)爭(zhēng)CPU的使用權(quán)，因此調(diào)度的使用權(quán)，因此調(diào)度 問(wèn)題又出現(xiàn)了。首先，調(diào)度程序要選擇合適的進(jìn)問(wèn)題又出現(xiàn)了。首先，調(diào)度程序要選擇合適的進(jìn) 程去運(yùn)行，因?yàn)閷?duì)于不同的進(jìn)程，用戶期望的響程去運(yùn)行，因?yàn)閷?duì)于不同的進(jìn)程，用戶期望的響 應(yīng)時(shí)間和要求是不同的；其次，調(diào)度程序要注意應(yīng)時(shí)間和要求是不

6、同的；其次，調(diào)度程序要注意 CPU的使用效率，因?yàn)檫M(jìn)程切換的開(kāi)銷很大。的使用效率，因?yàn)檫M(jìn)程切換的開(kāi)銷很大。72021/8/1472. 進(jìn)程的行為 CPU繁忙（繁忙（CPU-bound）的進(jìn)程：大部分時(shí)間的進(jìn)程：大部分時(shí)間 處于運(yùn)行和就緒狀態(tài)；處于運(yùn)行和就緒狀態(tài)； I/O繁忙（繁忙（I/O-bound）的進(jìn)程：大部分時(shí)間處的進(jìn)程：大部分時(shí)間處 于阻塞狀態(tài)。于阻塞狀態(tài)。82021/8/148（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）CPU繁忙與繁忙與I/O繁忙繁忙CPU繁忙繁忙I/O繁忙繁忙92021/8/149 內(nèi)部因素

7、：進(jìn)程自身的功能決定了它的各種工內(nèi)部因素：進(jìn)程自身的功能決定了它的各種工作量。例如，矩陣相乘進(jìn)程的計(jì)算量大，文件作量。例如，矩陣相乘進(jìn)程的計(jì)算量大，文件管理進(jìn)程的管理進(jìn)程的I/O需求很大；需求很大； 外部因素：計(jì)算機(jī)系統(tǒng)的運(yùn)行速度決定了完成外部因素：計(jì)算機(jī)系統(tǒng)的運(yùn)行速度決定了完成這些工作量所需要的時(shí)間長(zhǎng)短。工作量和工作這些工作量所需要的時(shí)間長(zhǎng)短。工作量和工作時(shí)間是兩回事，判斷一個(gè)進(jìn)程是屬于時(shí)間是兩回事，判斷一個(gè)進(jìn)程是屬于CPU繁忙繁忙還是屬于輸入輸出繁忙，主要看它的計(jì)算時(shí)間還是屬于輸入輸出繁忙，主要看它的計(jì)算時(shí)間和輸入輸出時(shí)間；和輸入輸出時(shí)間； I/O設(shè)備的運(yùn)行速度較慢，設(shè)備的運(yùn)行速度較慢，C

8、PU的運(yùn)行速度較的運(yùn)行速度較快，而且更新?lián)Q代的速度快，將來(lái)進(jìn)程都趨向快，而且更新?lián)Q代的速度快，將來(lái)進(jìn)程都趨向于于I/O繁忙。繁忙。CPU繁忙還是繁忙還是I/O繁忙？繁忙？102021/8/1410 VCD播放軟件；播放軟件； WORD文字編輯器；文字編輯器； 磁盤(pán)碎片整理工具磁盤(pán)碎片整理工具defrag。CPU繁忙還是繁忙還是I/O繁忙？（續(xù)）繁忙？（續(xù)）112021/8/14113. 何時(shí)調(diào)度？當(dāng)一個(gè)新的進(jìn)程被創(chuàng)建時(shí)，是執(zhí)行新進(jìn)程還當(dāng)一個(gè)新的進(jìn)程被創(chuàng)建時(shí)，是執(zhí)行新進(jìn)程還是繼續(xù)執(zhí)行父進(jìn)程？是繼續(xù)執(zhí)行父進(jìn)程？當(dāng)一個(gè)進(jìn)程運(yùn)行完畢時(shí)；當(dāng)一個(gè)進(jìn)程運(yùn)行完畢時(shí)；當(dāng)一個(gè)進(jìn)程由于當(dāng)一個(gè)進(jìn)程由于I/O、信號(hào)量或

9、其他的某個(gè)原、信號(hào)量或其他的某個(gè)原因被阻塞時(shí)；因被阻塞時(shí)；當(dāng)一個(gè)當(dāng)一個(gè)I/O中斷發(fā)生時(shí)，表明某個(gè)中斷發(fā)生時(shí)，表明某個(gè)I/O操作已經(jīng)操作已經(jīng)完成，而等待該完成，而等待該I/O操作的進(jìn)程轉(zhuǎn)入就緒狀態(tài)；操作的進(jìn)程轉(zhuǎn)入就緒狀態(tài)；在分時(shí)系統(tǒng)中，當(dāng)一個(gè)時(shí)鐘中斷發(fā)生時(shí)。在分時(shí)系統(tǒng)中，當(dāng)一個(gè)時(shí)鐘中斷發(fā)生時(shí)。122021/8/1412不可搶占調(diào)度方式不可搶占調(diào)度方式：一個(gè)進(jìn)程若被選中，就：一個(gè)進(jìn)程若被選中，就一直運(yùn)行下去，直到它被阻塞（一直運(yùn)行下去，直到它被阻塞（I/O，或正在，或正在等待其他的進(jìn)程），或主動(dòng)地交出等待其他的進(jìn)程），或主動(dòng)地交出CPU。以。以上的情形上的情形13均可發(fā)生調(diào)度；均可發(fā)生調(diào)度；可搶占

10、調(diào)度方式可搶占調(diào)度方式：當(dāng)一個(gè)進(jìn)程在運(yùn)行時(shí)，調(diào)：當(dāng)一個(gè)進(jìn)程在運(yùn)行時(shí)，調(diào)度程序可以打斷它。以上的情形度程序可以打斷它。以上的情形15均可發(fā)均可發(fā)生調(diào)度，另外，在其他的一些情形下，如就生調(diào)度，另外，在其他的一些情形下，如就緒隊(duì)列中有進(jìn)程的優(yōu)先級(jí)高于當(dāng)前運(yùn)行進(jìn)程緒隊(duì)列中有進(jìn)程的優(yōu)先級(jí)高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)，也可能立即進(jìn)行調(diào)度。的優(yōu)先級(jí)，也可能立即進(jìn)行調(diào)度。兩種調(diào)度方式兩種調(diào)度方式132021/8/14134. 調(diào)度算法的類別不同的不同的OS有不同的目標(biāo)，對(duì)調(diào)度程序有不同的有不同的目標(biāo)，對(duì)調(diào)度程序有不同的要求，因此需要不同類型的調(diào)度算法。要求，因此需要不同類型的調(diào)度算法。批處理系統(tǒng)：無(wú)須及時(shí)的用戶響

11、應(yīng)，采用不批處理系統(tǒng)：無(wú)須及時(shí)的用戶響應(yīng)，采用不可搶占的調(diào)度方式，或時(shí)間間隔很長(zhǎng)的可搶可搶占的調(diào)度方式，或時(shí)間間隔很長(zhǎng)的可搶占調(diào)度方式，從而允許進(jìn)程能長(zhǎng)時(shí)間運(yùn)行，占調(diào)度方式，從而允許進(jìn)程能長(zhǎng)時(shí)間運(yùn)行，減少進(jìn)程的切換次數(shù)，提高系統(tǒng)的性能；減少進(jìn)程的切換次數(shù)，提高系統(tǒng)的性能；交互式系統(tǒng)：及時(shí)的用戶響應(yīng)非常重要，必交互式系統(tǒng)：及時(shí)的用戶響應(yīng)非常重要，必須采用可搶占的調(diào)度方式。以防單個(gè)進(jìn)程占須采用可搶占的調(diào)度方式。以防單個(gè)進(jìn)程占用太多用太多CPU時(shí)間，影響到其他進(jìn)程的運(yùn)行。時(shí)間，影響到其他進(jìn)程的運(yùn)行。實(shí)時(shí)系統(tǒng)：對(duì)響應(yīng)時(shí)間要求苛刻，每個(gè)進(jìn)程實(shí)時(shí)系統(tǒng)：對(duì)響應(yīng)時(shí)間要求苛刻，每個(gè)進(jìn)程運(yùn)行時(shí)間很短，可采用可搶占

12、的調(diào)度方式。運(yùn)行時(shí)間很短，可采用可搶占的調(diào)度方式。142021/8/14145. 調(diào)度算法的目標(biāo)算法調(diào)度的目標(biāo)是多元的，有些是可以共存的，算法調(diào)度的目標(biāo)是多元的，有些是可以共存的，也有些是相互牽制的，對(duì)于一個(gè)實(shí)際的調(diào)度算法也有些是相互牽制的，對(duì)于一個(gè)實(shí)際的調(diào)度算法來(lái)說(shuō)，有一個(gè)綜合權(quán)衡的過(guò)程。來(lái)說(shuō)，有一個(gè)綜合權(quán)衡的過(guò)程。所有系統(tǒng)普遍適用的目標(biāo)：所有系統(tǒng)普遍適用的目標(biāo)： 公平：大致相當(dāng)?shù)膬蓚€(gè)進(jìn)程所得到的公平：大致相當(dāng)?shù)膬蓚€(gè)進(jìn)程所得到的CPU時(shí)間時(shí)間 也應(yīng)是大致相同的；也應(yīng)是大致相同的； 對(duì)已制訂的調(diào)度策略必須能貫徹執(zhí)行；對(duì)已制訂的調(diào)度策略必須能貫徹執(zhí)行； 均衡：盡可能使整個(gè)系統(tǒng)的各部分都忙起來(lái)，均

13、衡：盡可能使整個(gè)系統(tǒng)的各部分都忙起來(lái)， 提高系統(tǒng)資源的使用效率。提高系統(tǒng)資源的使用效率。152021/8/1415批處理系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)：批處理系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)： 吞吐量吞吐量（Throughput）：?jiǎn)挝粫r(shí)間內(nèi)所完成的）：?jiǎn)挝粫r(shí)間內(nèi)所完成的 作業(yè)數(shù)，與作業(yè)本身特性和調(diào)度算法有關(guān)；作業(yè)數(shù)，與作業(yè)本身特性和調(diào)度算法有關(guān)； 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間（Turnaround time）：一個(gè)批處理作）：一個(gè)批處理作 業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。 包括：在收容隊(duì)列中等待，包括：在收容隊(duì)列中等待，CPU上執(zhí)行，就緒上執(zhí)行，就緒 隊(duì)列和阻塞隊(duì)列中等

14、待，結(jié)果輸出等待；隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待；C 平均周轉(zhuǎn)時(shí)間：一批作業(yè)的周轉(zhuǎn)時(shí)間的平均值；平均周轉(zhuǎn)時(shí)間：一批作業(yè)的周轉(zhuǎn)時(shí)間的平均值；C 平均帶權(quán)周轉(zhuǎn)時(shí)間：權(quán)值是實(shí)際執(zhí)行時(shí)間的倒數(shù)平均帶權(quán)周轉(zhuǎn)時(shí)間：權(quán)值是實(shí)際執(zhí)行時(shí)間的倒數(shù); CPU的利用率的利用率：大中型主機(jī)的：大中型主機(jī)的CPU較貴，所以較貴，所以 讓它時(shí)刻不停地轉(zhuǎn)著。讓它時(shí)刻不停地轉(zhuǎn)著。162021/8/1416周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間：iiiSET（Ei表示作業(yè)表示作業(yè)i完成時(shí)間，完成時(shí)間， Si表示作業(yè)表示作業(yè)i提交時(shí)間）提交時(shí)間）平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：NiiTNT11(N表示作業(yè)的個(gè)數(shù)表示作業(yè)的個(gè)數(shù))平均帶權(quán)周轉(zhuǎn)時(shí)間：平均帶

15、權(quán)周轉(zhuǎn)時(shí)間：NiiirTNW11(ri表示作業(yè)表示作業(yè)i的實(shí)際執(zhí)行時(shí)間的實(shí)際執(zhí)行時(shí)間)172021/8/1417交換式系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)：交換式系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)： 響應(yīng)時(shí)間：用戶輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)響應(yīng)時(shí)間：用戶輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng) 給出首次響應(yīng)（如屏幕顯示）的時(shí)間。響應(yīng)時(shí)間給出首次響應(yīng)（如屏幕顯示）的時(shí)間。響應(yīng)時(shí)間 越短越好，優(yōu)先考慮交互式進(jìn)程；越短越好，優(yōu)先考慮交互式進(jìn)程； 相稱性：滿足用戶對(duì)程序運(yùn)行時(shí)間的期望值。相稱性：滿足用戶對(duì)程序運(yùn)行時(shí)間的期望值。實(shí)時(shí)系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)：實(shí)時(shí)系統(tǒng)中調(diào)度算法的評(píng)價(jià)指標(biāo)： 實(shí)時(shí)響應(yīng)：必須嚴(yán)格地遵守時(shí)間期限；實(shí)時(shí)響應(yīng)：必

16、須嚴(yán)格地遵守時(shí)間期限； 可預(yù)測(cè)性：在實(shí)時(shí)多媒體系統(tǒng)中，信號(hào)的播放必可預(yù)測(cè)性：在實(shí)時(shí)多媒體系統(tǒng)中，信號(hào)的播放必 須連貫，不能時(shí)斷時(shí)續(xù)。須連貫，不能時(shí)斷時(shí)續(xù)。182021/8/14182.6.2 批處理系統(tǒng)中的調(diào)度算法批處理系統(tǒng)中的調(diào)度算法1. 先來(lái)先服務(wù) 先來(lái)先服務(wù)先來(lái)先服務(wù)（First Come First Served，F(xiàn)CFS； First In First Out，F(xiàn)IFO）：按照作業(yè)到達(dá)的）：按照作業(yè)到達(dá)的 先后次序進(jìn)行調(diào)度；先后次序進(jìn)行調(diào)度； 不可搶占方式：當(dāng)前進(jìn)程占用不可搶占方式：當(dāng)前進(jìn)程占用CPU，直到執(zhí)行，直到執(zhí)行 完或被阻塞，才讓出完或被阻塞，才讓出CPU給另外一個(gè)進(jìn)程；給另

17、外一個(gè)進(jìn)程； 在進(jìn)程被喚醒后（如在進(jìn)程被喚醒后（如I/O完成），并不立即恢復(fù)完成），并不立即恢復(fù) 執(zhí)行，而是放在就緒隊(duì)列的末尾；執(zhí)行，而是放在就緒隊(duì)列的末尾； 優(yōu)點(diǎn)：簡(jiǎn)單、公平，易于理解也易于實(shí)現(xiàn)。優(yōu)點(diǎn)：簡(jiǎn)單、公平，易于理解也易于實(shí)現(xiàn)。 現(xiàn)實(shí)生活中應(yīng)用廣泛：排隊(duì)。現(xiàn)實(shí)生活中應(yīng)用廣泛：排隊(duì)。192021/8/1419問(wèn)題問(wèn)題1. 平均周轉(zhuǎn)時(shí)間取決于各作業(yè)到達(dá)的順序，若平均周轉(zhuǎn)時(shí)間取決于各作業(yè)到達(dá)的順序，若短作業(yè)位于長(zhǎng)作業(yè)之后，將增大平均周轉(zhuǎn)時(shí)間。短作業(yè)位于長(zhǎng)作業(yè)之后，將增大平均周轉(zhuǎn)時(shí)間。例如，三個(gè)作業(yè)例如，三個(gè)作業(yè)A、B、C的運(yùn)行時(shí)間為的運(yùn)行時(shí)間為24、3、3時(shí)間時(shí)間 24 27 30ABC平均

18、周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間(24+27+30)/327平均等待時(shí)間平均等待時(shí)間(0+24+27)/317時(shí)間時(shí)間 3 6 30ABC平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間(3+6+30)/313平均等待時(shí)間平均等待時(shí)間(0+3+6)/33202021/8/1420問(wèn)題問(wèn)題2. 無(wú)法充分利用無(wú)法充分利用CPU繁忙的作業(yè)與繁忙的作業(yè)與I/O繁忙的繁忙的作業(yè)之間的互補(bǔ)關(guān)系。如果作業(yè)之間的互補(bǔ)關(guān)系。如果CPU繁忙的作業(yè)獨(dú)占很繁忙的作業(yè)獨(dú)占很長(zhǎng)時(shí)間的長(zhǎng)時(shí)間的CPU，使得，使得I/O設(shè)備空閑，也使得設(shè)備空閑，也使得I/O繁忙繁忙的作業(yè)無(wú)法運(yùn)行。的作業(yè)無(wú)法運(yùn)行。作業(yè)作業(yè)A作業(yè)作業(yè)BCPUI/O作業(yè)作業(yè)A作業(yè)作業(yè)B時(shí)間時(shí)間t0t

19、1 t2t3t4212021/8/14212. 短作業(yè)優(yōu)先 短作業(yè)優(yōu)先短作業(yè)優(yōu)先（Shortest Job First，SJF），設(shè)計(jì)），設(shè)計(jì) 目標(biāo)是改進(jìn)目標(biāo)是改進(jìn)FCFS算法，減少平均周轉(zhuǎn)時(shí)間；算法，減少平均周轉(zhuǎn)時(shí)間； SJF算法要求作業(yè)在開(kāi)始執(zhí)行時(shí)預(yù)計(jì)執(zhí)行時(shí)間，算法要求作業(yè)在開(kāi)始執(zhí)行時(shí)預(yù)計(jì)執(zhí)行時(shí)間， 對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)優(yōu)先分派處理器；對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)優(yōu)先分派處理器； 兩種實(shí)現(xiàn)方案：兩種實(shí)現(xiàn)方案：Q 不可搶占方式：當(dāng)前作業(yè)在運(yùn)行時(shí)不會(huì)被打不可搶占方式：當(dāng)前作業(yè)在運(yùn)行時(shí)不會(huì)被打 斷，只有運(yùn)行完畢或阻塞時(shí)，才讓出斷，只有運(yùn)行完畢或阻塞時(shí)，才讓出CPU；Q 可搶占方式：如果一個(gè)新的短作業(yè)

20、到來(lái)，其可搶占方式：如果一個(gè)新的短作業(yè)到來(lái)，其 運(yùn)行時(shí)間小于當(dāng)前正在運(yùn)行作業(yè)的剩余時(shí)間，運(yùn)行時(shí)間小于當(dāng)前正在運(yùn)行作業(yè)的剩余時(shí)間， 則搶占則搶占CPU運(yùn)行，稱為運(yùn)行，稱為SRTF（Shortest Remaining Time First）。）。222021/8/1422 可以證明：對(duì)于一組同時(shí)到達(dá)的作業(yè)，采用可以證明：對(duì)于一組同時(shí)到達(dá)的作業(yè)，采用SJF 算法將得到一個(gè)算法將得到一個(gè)最小最小的平均周轉(zhuǎn)時(shí)間。的平均周轉(zhuǎn)時(shí)間。D時(shí)間時(shí)間ACa a+b a+b+c a+b+c+d 例如，考察例如，考察4個(gè)作業(yè)個(gè)作業(yè)A、B、C、D，其運(yùn)行時(shí)間分，其運(yùn)行時(shí)間分別為別為a、b、c、dBA、B、C、D的周轉(zhuǎn)時(shí)

21、間分別為的周轉(zhuǎn)時(shí)間分別為a、a+b、a+b+c和和a+b+c+d，因此平均周轉(zhuǎn)時(shí)間為：，因此平均周轉(zhuǎn)時(shí)間為：(4a+3b+2c+d)/4顯然，當(dāng)顯然，當(dāng)a b c d時(shí)，平均周轉(zhuǎn)時(shí)間最小。時(shí)，平均周轉(zhuǎn)時(shí)間最小。232021/8/1423取得最優(yōu)解的前提之一：這組作業(yè)必須同時(shí)到達(dá)；取得最優(yōu)解的前提之一：這組作業(yè)必須同時(shí)到達(dá)；例如：例如：進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（不可搶占）：（不可搶占）：P1P3P2P403781216平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：(7 + 10 + 4 + 11) / 4 = 8平均等待時(shí)間：平

22、均等待時(shí)間：(0 + 6 + 3 + 7) / 4 = 4若按若按P2,P3,P4,P1順序順序, 平均周轉(zhuǎn)和等待時(shí)間平均周轉(zhuǎn)和等待時(shí)間7.75, 3.75242021/8/1424進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（可搶占）：（可搶占）：P1P3P2P4P2P1027411165平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：(16 + 5 + 1 + 6) / 4 = 7平均等待時(shí)間：平均等待時(shí)間：(9 + 1 + 0 + 2) / 4 = 3252021/8/1425前提條件之二：需要事先估計(jì)作業(yè)的運(yùn)行時(shí)間前提條件之二：需要事先估計(jì)

23、作業(yè)的運(yùn)行時(shí)間如何知道作業(yè)的運(yùn)行時(shí)間？如何知道作業(yè)的運(yùn)行時(shí)間？% 該時(shí)間只可能是一個(gè)估計(jì)值；該時(shí)間只可能是一個(gè)估計(jì)值；% 讓提交該作業(yè)的用戶來(lái)提供。不太實(shí)用；讓提交該作業(yè)的用戶來(lái)提供。不太實(shí)用；% 使用前面的使用前面的CPU運(yùn)行時(shí)間來(lái)預(yù)測(cè)后面的運(yùn)行時(shí)間來(lái)預(yù)測(cè)后面的CPU運(yùn)運(yùn) 行時(shí)間，通過(guò)過(guò)去的行為來(lái)預(yù)測(cè)將來(lái)的行為。行時(shí)間，通過(guò)過(guò)去的行為來(lái)預(yù)測(cè)將來(lái)的行為。C 如果一個(gè)作業(yè)已經(jīng)運(yùn)行很長(zhǎng)時(shí)間了，那它可能如果一個(gè)作業(yè)已經(jīng)運(yùn)行很長(zhǎng)時(shí)間了，那它可能 還會(huì)運(yùn)行更長(zhǎng)的時(shí)間；還會(huì)運(yùn)行更長(zhǎng)的時(shí)間；C 使用指數(shù)平均值函數(shù)來(lái)預(yù)測(cè)下一段使用指數(shù)平均值函數(shù)來(lái)預(yù)測(cè)下一段CPU時(shí)間時(shí)間;262021/8/1426指數(shù)平均值函

24、數(shù)方法指數(shù)平均值函數(shù)方法.1 1nnnt1. tn 第第n個(gè)個(gè)CPU運(yùn)行時(shí)間的實(shí)際長(zhǎng)度；運(yùn)行時(shí)間的實(shí)際長(zhǎng)度；2. n+1 下一個(gè)下一個(gè)CPU運(yùn)行時(shí)間的預(yù)測(cè)長(zhǎng)度；運(yùn)行時(shí)間的預(yù)測(cè)長(zhǎng)度；3. 定義系數(shù)定義系數(shù) ，0 14. 定義：定義：272021/8/14273. 三層調(diào)度模型（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）282021/8/1428 準(zhǔn)入調(diào)度：決定哪一些作業(yè)能夠進(jìn)入系統(tǒng)運(yùn)行。準(zhǔn)入調(diào)度：決定哪一些作業(yè)能夠進(jìn)入系統(tǒng)運(yùn)行。 在這個(gè)層次上的調(diào)度算法主要有短作業(yè)優(yōu)先進(jìn)入在這個(gè)層次上的調(diào)度算法主要有短作業(yè)優(yōu)先進(jìn)入, 以及把

25、以及把CPU繁忙的作業(yè)和繁忙的作業(yè)和I/O繁忙的作業(yè)混合在繁忙的作業(yè)混合在 一起提交給系統(tǒng)；一起提交給系統(tǒng)； 存儲(chǔ)調(diào)度：決定哪一些進(jìn)程應(yīng)該留在內(nèi)存中，哪存儲(chǔ)調(diào)度：決定哪一些進(jìn)程應(yīng)該留在內(nèi)存中，哪 一些進(jìn)程應(yīng)該保存在磁盤(pán)上。需要考慮的因素包一些進(jìn)程應(yīng)該保存在磁盤(pán)上。需要考慮的因素包 括該進(jìn)程呆在內(nèi)存或磁盤(pán)上的時(shí)間長(zhǎng)短，它所用括該進(jìn)程呆在內(nèi)存或磁盤(pán)上的時(shí)間長(zhǎng)短，它所用 的的CPU時(shí)間以及它的優(yōu)先級(jí)等；時(shí)間以及它的優(yōu)先級(jí)等； CPU調(diào)度：從內(nèi)存當(dāng)中，選擇一個(gè)已經(jīng)就緒的進(jìn)調(diào)度：從內(nèi)存當(dāng)中，選擇一個(gè)已經(jīng)就緒的進(jìn) 程去運(yùn)行。程去運(yùn)行。批處理系統(tǒng)中的三層調(diào)度模型批處理系統(tǒng)中的三層調(diào)度模型292021/8/1

26、4292.6.3 交互式系統(tǒng)中的調(diào)度算法交互式系統(tǒng)中的調(diào)度算法1. 時(shí)間片輪轉(zhuǎn)法 在在時(shí)間片輪轉(zhuǎn)算法時(shí)間片輪轉(zhuǎn)算法（Round-Robin，RR）中，將）中，將 所有的就緒進(jìn)程按照所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列；原則，排成一個(gè)隊(duì)列； 每次調(diào)度時(shí)將處理器分派給隊(duì)首進(jìn)程，讓其執(zhí)行每次調(diào)度時(shí)將處理器分派給隊(duì)首進(jìn)程，讓其執(zhí)行 一小段一小段CPU時(shí)間（時(shí)間片）；時(shí)間（時(shí)間片）； 在一個(gè)時(shí)間片結(jié)束時(shí)，如果進(jìn)程還沒(méi)有執(zhí)行完的在一個(gè)時(shí)間片結(jié)束時(shí)，如果進(jìn)程還沒(méi)有執(zhí)行完的 話，將發(fā)生時(shí)鐘中斷，在時(shí)鐘中斷中，進(jìn)程調(diào)度話，將發(fā)生時(shí)鐘中斷，在時(shí)鐘中斷中，進(jìn)程調(diào)度 程序?qū)和．?dāng)前進(jìn)程的執(zhí)行，并將其送到就緒隊(duì)

27、程序?qū)和．?dāng)前進(jìn)程的執(zhí)行，并將其送到就緒隊(duì) 列的末尾，然后執(zhí)行當(dāng)前的隊(duì)首進(jìn)程；列的末尾，然后執(zhí)行當(dāng)前的隊(duì)首進(jìn)程； 如果一個(gè)進(jìn)程在它的時(shí)間片用完之前就已結(jié)束或如果一個(gè)進(jìn)程在它的時(shí)間片用完之前就已結(jié)束或 被阻塞，那么立即讓出被阻塞，那么立即讓出CPU。302021/8/1430開(kāi)始時(shí)，進(jìn)程開(kāi)始時(shí)，進(jìn)程B位于隊(duì)列之首，因此被調(diào)度執(zhí)行。當(dāng)位于隊(duì)列之首，因此被調(diào)度執(zhí)行。當(dāng)它的時(shí)間片用完后，就把它送到就緒隊(duì)列的末尾。它的時(shí)間片用完后，就把它送到就緒隊(duì)列的末尾。同時(shí)，進(jìn)程同時(shí)，進(jìn)程F成為隊(duì)首進(jìn)程，被調(diào)度運(yùn)行。成為隊(duì)首進(jìn)程，被調(diào)度運(yùn)行。（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Moder

28、n Operating Systems” ）312021/8/1431Round robin, too.322021/8/1432 優(yōu)點(diǎn)：優(yōu)點(diǎn)：e 公平性公平性：各個(gè)就緒進(jìn)程平均地分配：各個(gè)就緒進(jìn)程平均地分配CPU的使用的使用 時(shí)間。假設(shè)有時(shí)間。假設(shè)有n個(gè)就緒進(jìn)程，時(shí)間片大小為個(gè)就緒進(jìn)程，時(shí)間片大小為q， 那么每個(gè)進(jìn)程將得到那么每個(gè)進(jìn)程將得到1/n的的CPU時(shí)間；時(shí)間；e 活動(dòng)性活動(dòng)性：每個(gè)進(jìn)程最多等待：每個(gè)進(jìn)程最多等待(n-1)q時(shí)間就能夠時(shí)間就能夠 再次得到再次得到CPU去運(yùn)行；去運(yùn)行；e 一般來(lái)說(shuō)，平均周轉(zhuǎn)時(shí)間較一般來(lái)說(shuō)，平均周轉(zhuǎn)時(shí)間較SJF算法為長(zhǎng)，但算法為長(zhǎng)，但 能夠得到能夠得到較短

29、的平均響應(yīng)時(shí)間較短的平均響應(yīng)時(shí)間； 缺點(diǎn)：缺點(diǎn)：q的大小難以確定的大小難以確定（一般在（一般在2050ms）。）。e q太大：退化為太大：退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片算法，進(jìn)程在一個(gè)時(shí)間片 內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。如內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。如q=100ms；e q太?。好總€(gè)進(jìn)程都需要更多的時(shí)間片才能處理太?。好總€(gè)進(jìn)程都需要更多的時(shí)間片才能處理 完，進(jìn)程切換次數(shù)增加，增大系統(tǒng)開(kāi)銷。如完，進(jìn)程切換次數(shù)增加，增大系統(tǒng)開(kāi)銷。如q=4ms時(shí)間片輪轉(zhuǎn)法的特點(diǎn)時(shí)間片輪轉(zhuǎn)法的特點(diǎn)332021/8/1433進(jìn)程進(jìn)程CPU時(shí)間時(shí)間P153 P2 17 P368 P4 24一個(gè)例子：時(shí)間片長(zhǎng)度一個(gè)例子：時(shí)間

30、片長(zhǎng)度q20P1P2P3P4P1P3P4P1P3P30 20 37 57 77 97 117 121 134 154 162平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：(134 + 37 + 162 + 121) / 4113.5SJF的平均周轉(zhuǎn)時(shí)間：的平均周轉(zhuǎn)時(shí)間： (94 + 17 + 162 + 41) / 478.5342021/8/14342. 優(yōu)先級(jí)算法1 輪轉(zhuǎn)法有一個(gè)缺省的前提，即各進(jìn)程同等重要；輪轉(zhuǎn)法有一個(gè)缺省的前提，即各進(jìn)程同等重要；1 “人人生而平等人人生而平等”？ 恐怕不太現(xiàn)實(shí)！同樣，并恐怕不太現(xiàn)實(shí)！同樣，并 不是每個(gè)進(jìn)程都同等重要，不是每個(gè)進(jìn)程都同等重要， 怎么辦？分等級(jí)！怎么辦？分等

31、級(jí)！1 優(yōu)先級(jí)算法優(yōu)先級(jí)算法（Priority Scheduling）：給每個(gè)進(jìn)）：給每個(gè)進(jìn) 程設(shè)置一個(gè)優(yōu)先級(jí)，然后在所有就緒進(jìn)程中選擇程設(shè)置一個(gè)優(yōu)先級(jí)，然后在所有就緒進(jìn)程中選擇 優(yōu)先級(jí)最高的那個(gè)進(jìn)程去運(yùn)行；優(yōu)先級(jí)最高的那個(gè)進(jìn)程去運(yùn)行；1 SJF就是一個(gè)優(yōu)先級(jí)算法，每個(gè)進(jìn)程的優(yōu)先級(jí)是就是一個(gè)優(yōu)先級(jí)算法，每個(gè)進(jìn)程的優(yōu)先級(jí)是 它的它的CPU運(yùn)行時(shí)間（時(shí)間越短，優(yōu)先級(jí)越高）；運(yùn)行時(shí)間（時(shí)間越短，優(yōu)先級(jí)越高）；1 分為分為可搶占可搶占和和不可搶占不可搶占兩種方式；各進(jìn)程優(yōu)先級(jí)兩種方式；各進(jìn)程優(yōu)先級(jí) 的確定方式可分為的確定方式可分為靜態(tài)靜態(tài)和和動(dòng)態(tài)動(dòng)態(tài)兩種。兩種。352021/8/1435靜態(tài)優(yōu)先級(jí)方式

32、靜態(tài)優(yōu)先級(jí)方式 確定優(yōu)先級(jí)的依據(jù)：確定優(yōu)先級(jí)的依據(jù)： 進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)高于用戶進(jìn)程，進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)高于用戶進(jìn)程，交互式進(jìn)程高于批處理進(jìn)程）；交互式進(jìn)程高于批處理進(jìn)程）； 對(duì)系統(tǒng)資源的需求（對(duì)對(duì)系統(tǒng)資源的需求（對(duì)CPU和內(nèi)存需求較少和內(nèi)存需求較少的進(jìn)程，優(yōu)先級(jí)較高）；的進(jìn)程，優(yōu)先級(jí)較高）； 用戶要求（用戶級(jí)別和付費(fèi)情況，如軍用電用戶要求（用戶級(jí)別和付費(fèi)情況，如軍用電腦、商用電腦）。腦、商用電腦）。 靜態(tài)方式的缺點(diǎn)：高優(yōu)先級(jí)的進(jìn)程一直占用靜態(tài)方式的缺點(diǎn)：高優(yōu)先級(jí)的進(jìn)程一直占用CPU，低優(yōu)先級(jí)的進(jìn)程，低優(yōu)先級(jí)的進(jìn)程“饑餓饑餓”。 靜態(tài)優(yōu)先級(jí)方式靜態(tài)優(yōu)先級(jí)方式是指在創(chuàng)建進(jìn)程時(shí)確定進(jìn)程

33、優(yōu)先級(jí)，是指在創(chuàng)建進(jìn)程時(shí)確定進(jìn)程優(yōu)先級(jí)，并保持不變到進(jìn)程結(jié)束。并保持不變到進(jìn)程結(jié)束。362021/8/1436動(dòng)態(tài)優(yōu)先級(jí)方式動(dòng)態(tài)優(yōu)先級(jí)方式 為防為防“饑餓饑餓”, 根據(jù)運(yùn)行時(shí)間和等待時(shí)間調(diào)整優(yōu)先根據(jù)運(yùn)行時(shí)間和等待時(shí)間調(diào)整優(yōu)先級(jí)級(jí) 進(jìn)程每執(zhí)行一個(gè)時(shí)間片就降低其優(yōu)先級(jí)。當(dāng)一進(jìn)程每執(zhí)行一個(gè)時(shí)間片就降低其優(yōu)先級(jí)。當(dāng)一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到讓出個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到讓出CPU； 在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行。其優(yōu)先級(jí)提高到可

34、被調(diào)度執(zhí)行。 為了讓為了讓I/O忙起來(lái)，可提高忙起來(lái)，可提高I/O繁忙進(jìn)程的優(yōu)先級(jí)。繁忙進(jìn)程的優(yōu)先級(jí)。但如何判定一個(gè)進(jìn)程是但如何判定一個(gè)進(jìn)程是I/O繁忙的？可把進(jìn)程優(yōu)先繁忙的？可把進(jìn)程優(yōu)先級(jí)設(shè)為級(jí)設(shè)為1/f，f是在上一個(gè)時(shí)間片中所用的時(shí)間比例是在上一個(gè)時(shí)間片中所用的時(shí)間比例動(dòng)態(tài)優(yōu)先級(jí)方式動(dòng)態(tài)優(yōu)先級(jí)方式是指在創(chuàng)建進(jìn)程時(shí)賦予給進(jìn)程的優(yōu)是指在創(chuàng)建進(jìn)程時(shí)賦予給進(jìn)程的優(yōu)先級(jí)，在進(jìn)程運(yùn)行過(guò)程中可以動(dòng)態(tài)改變，以便獲得先級(jí)，在進(jìn)程運(yùn)行過(guò)程中可以動(dòng)態(tài)改變，以便獲得更好的調(diào)度性能。更好的調(diào)度性能。372021/8/1437優(yōu)先級(jí)類別優(yōu)先級(jí)類別（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Mode

35、rn Operating Systems” ）可以把進(jìn)程按照不同的優(yōu)先級(jí)別分組，然后在不同可以把進(jìn)程按照不同的優(yōu)先級(jí)別分組，然后在不同級(jí)別之間使用優(yōu)先級(jí)算法，而在同一級(jí)別的各個(gè)進(jìn)級(jí)別之間使用優(yōu)先級(jí)算法，而在同一級(jí)別的各個(gè)進(jìn)程之間使用時(shí)間片輪轉(zhuǎn)法。程之間使用時(shí)間片輪轉(zhuǎn)法。382021/8/14383. 多級(jí)隊(duì)列算法多級(jí)隊(duì)列算法多級(jí)隊(duì)列算法（Multilevel Queue）引入多個(gè)就緒）引入多個(gè)就緒隊(duì)列，通過(guò)各個(gè)隊(duì)列的區(qū)別對(duì)待，達(dá)到一個(gè)綜合的隊(duì)列，通過(guò)各個(gè)隊(duì)列的區(qū)別對(duì)待，達(dá)到一個(gè)綜合的調(diào)度目標(biāo)。調(diào)度目標(biāo)。K 根據(jù)進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分根據(jù)進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分 為

36、為若干個(gè)子隊(duì)列若干個(gè)子隊(duì)列，如系統(tǒng)進(jìn)程、用戶交互進(jìn)程、，如系統(tǒng)進(jìn)程、用戶交互進(jìn)程、 批處理進(jìn)程等；批處理進(jìn)程等；K 不同的隊(duì)列可以有不同的隊(duì)列可以有不同的優(yōu)先級(jí)不同的優(yōu)先級(jí)；K 不同的隊(duì)列可以采用各自不同的隊(duì)列可以采用各自不同的調(diào)度算法不同的調(diào)度算法，如前，如前 臺(tái)的交互式進(jìn)程可采用臺(tái)的交互式進(jìn)程可采用RR算法，后臺(tái)的批處理進(jìn)算法，后臺(tái)的批處理進(jìn) 程可采用程可采用FCFS算法。算法。392021/8/1439K 在各個(gè)隊(duì)列之間也必須進(jìn)行調(diào)度：在各個(gè)隊(duì)列之間也必須進(jìn)行調(diào)度： 固定優(yōu)先級(jí)調(diào)度固定優(yōu)先級(jí)調(diào)度：按照各種類型的進(jìn)程的優(yōu)先：按照各種類型的進(jìn)程的優(yōu)先 級(jí)別從高到低地進(jìn)行，先運(yùn)行最高優(yōu)先級(jí)的所

37、級(jí)別從高到低地進(jìn)行，先運(yùn)行最高優(yōu)先級(jí)的所 有進(jìn)程，再運(yùn)行次一級(jí)所有進(jìn)程，依此類推。有進(jìn)程，再運(yùn)行次一級(jí)所有進(jìn)程，依此類推。 問(wèn)題：可能導(dǎo)致問(wèn)題：可能導(dǎo)致“饑餓饑餓”； 時(shí)間片方法時(shí)間片方法：把：把CPU時(shí)間按比例分配給不同的時(shí)間按比例分配給不同的 隊(duì)列，然后再由各個(gè)隊(duì)列的調(diào)度算法去調(diào)度，隊(duì)列，然后再由各個(gè)隊(duì)列的調(diào)度算法去調(diào)度， 如如80給前臺(tái)的交互式進(jìn)程隊(duì)列（給前臺(tái)的交互式進(jìn)程隊(duì)列（RR算法），算法）， 20給后臺(tái)的批處理進(jìn)程隊(duì)列（給后臺(tái)的批處理進(jìn)程隊(duì)列（FCFS）。）。402021/8/1440（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operat

38、ing System Concepts”）多級(jí)隊(duì)列算法的一個(gè)例子多級(jí)隊(duì)列算法的一個(gè)例子412021/8/14414. 多級(jí)反饋隊(duì)列算法J 多級(jí)隊(duì)列算法把每個(gè)進(jìn)程按照它的類型多級(jí)隊(duì)列算法把每個(gè)進(jìn)程按照它的類型固定固定在一在一 個(gè)隊(duì)列中，但問(wèn)題是如何來(lái)確定進(jìn)程的類型？個(gè)隊(duì)列中，但問(wèn)題是如何來(lái)確定進(jìn)程的類型？ 而且有的進(jìn)程其類型可能動(dòng)態(tài)變化，怎么辦？而且有的進(jìn)程其類型可能動(dòng)態(tài)變化，怎么辦？ “路遙知馬力，日久見(jiàn)人心路遙知馬力，日久見(jiàn)人心”！J 多級(jí)反饋隊(duì)列算法多級(jí)反饋隊(duì)列算法 (Multilevel Feedback Queue) 即根據(jù)一個(gè)進(jìn)程的運(yùn)行反饋信息，即根據(jù)一個(gè)進(jìn)程的運(yùn)行反饋信息，動(dòng)態(tài)地動(dòng)

39、態(tài)地調(diào)整它調(diào)整它 所在的隊(duì)列。所在的隊(duì)列。F 反饋反饋（Feedback）：即進(jìn)程在運(yùn)行當(dāng)中的表）：即進(jìn)程在運(yùn)行當(dāng)中的表 現(xiàn)，例如，它是否需要整個(gè)的時(shí)間片用于計(jì)現(xiàn)，例如，它是否需要整個(gè)的時(shí)間片用于計(jì) 算，或者它是否經(jīng)常地執(zhí)行算，或者它是否經(jīng)常地執(zhí)行I/O操作？操作？422021/8/1442J 如何實(shí)現(xiàn)多級(jí)反饋隊(duì)列算法？需要確定以下的一如何實(shí)現(xiàn)多級(jí)反饋隊(duì)列算法？需要確定以下的一 些參數(shù)：些參數(shù)：F 隊(duì)列的個(gè)數(shù)；隊(duì)列的個(gè)數(shù)；F 每個(gè)隊(duì)列所用的調(diào)度算法；每個(gè)隊(duì)列所用的調(diào)度算法；F 用來(lái)確定何時(shí)給一個(gè)進(jìn)程用來(lái)確定何時(shí)給一個(gè)進(jìn)程“升級(jí)升級(jí)”的方法；的方法；F 用來(lái)確定何時(shí)給一個(gè)進(jìn)程用來(lái)確定何時(shí)給一個(gè)進(jìn)

40、程“降級(jí)降級(jí)”的方法；的方法；F 用來(lái)確定一個(gè)進(jìn)程的初始隊(duì)列的方法；用來(lái)確定一個(gè)進(jìn)程的初始隊(duì)列的方法；432021/8/1443多級(jí)反饋隊(duì)列算法的一個(gè)例子多級(jí)反饋隊(duì)列算法的一個(gè)例子 三種優(yōu)先級(jí)別，三種優(yōu)先級(jí)別，3最高、最高、1最低，三個(gè)就緒隊(duì)列。時(shí)間片長(zhǎng)度最低，三個(gè)就緒隊(duì)列。時(shí)間片長(zhǎng)度 分別為分別為N、2N和和4N； 新進(jìn)程進(jìn)入內(nèi)存后，優(yōu)先級(jí)為新進(jìn)程進(jìn)入內(nèi)存后，優(yōu)先級(jí)為3，加入隊(duì)列，加入隊(duì)列3的末尾，按的末尾，按FCFS 算法調(diào)度；若一個(gè)時(shí)間片內(nèi)未能執(zhí)行完，則優(yōu)先級(jí)降為算法調(diào)度；若一個(gè)時(shí)間片內(nèi)未能執(zhí)行完，則優(yōu)先級(jí)降為2，加，加 入到隊(duì)列入到隊(duì)列2的末尾，同樣按的末尾，同樣按FCFS算法調(diào)度；依

41、此類推。算法調(diào)度；依此類推。 如果進(jìn)程在時(shí)間片用完之前即被阻塞，則增加它的優(yōu)先級(jí)；如果進(jìn)程在時(shí)間片用完之前即被阻塞，則增加它的優(yōu)先級(jí)； 僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn) 程執(zhí)行。若進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶程執(zhí)行。若進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶 先執(zhí)行新進(jìn)程。先執(zhí)行新進(jìn)程。優(yōu)先級(jí)優(yōu)先級(jí)321442021/8/1444多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法法的綜合和發(fā)展。其特點(diǎn)是：的綜合和發(fā)展。其特點(diǎn)是： 為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間

42、而照顧短為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程：新進(jìn)程一進(jìn)來(lái)即賦予最高優(yōu)先級(jí)。進(jìn)程：新進(jìn)程一進(jìn)來(lái)即賦予最高優(yōu)先級(jí)。 為獲得較好的為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧了照顧了I/O繁忙的進(jìn)程：繁忙的進(jìn)程： I/O繁忙進(jìn)程：讓其進(jìn)入最高優(yōu)先級(jí)隊(duì)列，以及時(shí)啟繁忙進(jìn)程：讓其進(jìn)入最高優(yōu)先級(jí)隊(duì)列，以及時(shí)啟動(dòng)動(dòng)I/O操作。通常只需一個(gè)小時(shí)間片，即可處理完一操作。通常只需一個(gè)小時(shí)間片，即可處理完一次次I/O請(qǐng)求，然后轉(zhuǎn)入到阻塞隊(duì)列。請(qǐng)求，然后轉(zhuǎn)入到阻塞隊(duì)列。 CPU繁忙進(jìn)程：每次都執(zhí)行完時(shí)間片，進(jìn)入更低級(jí)隊(duì)繁忙進(jìn)程：每次都執(zhí)行完時(shí)間片，進(jìn)入更低級(jí)隊(duì)列。最終采用最大

43、時(shí)間片來(lái)執(zhí)行，減少調(diào)度次數(shù)。列。最終采用最大時(shí)間片來(lái)執(zhí)行，減少調(diào)度次數(shù)。 不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)，能夠適應(yīng)不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)，能夠適應(yīng)一個(gè)進(jìn)程在不同時(shí)間段的不同運(yùn)行特點(diǎn)。一個(gè)進(jìn)程在不同時(shí)間段的不同運(yùn)行特點(diǎn)。452021/8/14452.6.4 實(shí)時(shí)系統(tǒng)中的調(diào)度算法實(shí)時(shí)系統(tǒng)中的調(diào)度算法 在實(shí)時(shí)系統(tǒng)中，對(duì)時(shí)間的要求是非常嚴(yán)格的。典在實(shí)時(shí)系統(tǒng)中，對(duì)時(shí)間的要求是非常嚴(yán)格的。典 型的例子是：一個(gè)或多個(gè)外部的物理設(shè)備定期或型的例子是：一個(gè)或多個(gè)外部的物理設(shè)備定期或 不定期地生成激勵(lì)信號(hào)，而計(jì)算機(jī)必須在一定的不定期地生成激勵(lì)信號(hào)，而計(jì)算機(jī)必須在一定的 時(shí)間期限內(nèi)做出恰當(dāng)?shù)姆磻?yīng)。時(shí)間期

44、限內(nèi)做出恰當(dāng)?shù)姆磻?yīng)。 硬實(shí)時(shí)硬實(shí)時(shí)：有一個(gè)絕對(duì)的時(shí)間期限，計(jì)算機(jī)的反應(yīng)：有一個(gè)絕對(duì)的時(shí)間期限，計(jì)算機(jī)的反應(yīng) 動(dòng)作必須在此期限之前完成，如核電站的控制系動(dòng)作必須在此期限之前完成，如核電站的控制系 統(tǒng)；統(tǒng)；軟實(shí)時(shí)軟實(shí)時(shí)：偶爾錯(cuò)過(guò)一次期限雖然是令人不快：偶爾錯(cuò)過(guò)一次期限雖然是令人不快 的，但也是可以容忍的，如的，但也是可以容忍的，如VCD的播放系統(tǒng)；的播放系統(tǒng)； 實(shí)時(shí)調(diào)度算法可以是實(shí)時(shí)調(diào)度算法可以是靜態(tài)的靜態(tài)的或或動(dòng)態(tài)的動(dòng)態(tài)的，前者在系，前者在系 統(tǒng)開(kāi)始運(yùn)行之前即已做好調(diào)度決策；而后者是在統(tǒng)開(kāi)始運(yùn)行之前即已做好調(diào)度決策；而后者是在 運(yùn)行中做出調(diào)度決策。運(yùn)行中做出調(diào)度決策。462021/8/14462.6.5 線程調(diào)度線程調(diào)度在進(jìn)程調(diào)度中，如果每個(gè)進(jìn)程都帶有多個(gè)的在進(jìn)程調(diào)度中，如果每個(gè)進(jìn)程都帶有多個(gè)的線程，那么我們就有了兩個(gè)層面上的并行關(guān)線程，那么我們就有了兩個(gè)層面上的并行關(guān)系：進(jìn)程和線程。若在這樣的系統(tǒng)中實(shí)現(xiàn)調(diào)系：進(jìn)程和線程。若在這樣的系統(tǒng)中實(shí)現(xiàn)