第3章處理機(jī)調(diào)度與死鎖1

1、第三章處理機(jī)調(diào)度與死鎖 3.1處理機(jī)調(diào)度3.1.1處理機(jī)的三級(jí)調(diào)度3.1.2調(diào)度的基本原則3.1.3調(diào)度隊(duì)列模型3.1.4常見調(diào)度算法第三章處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 3.1處理器的三級(jí)調(diào)度1 1、高級(jí)調(diào)度（作業(yè)調(diào)度）、高級(jí)調(diào)度（作業(yè)調(diào)度）(1) 作業(yè)作業(yè)(Job)。作業(yè)是一個(gè)比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 第三章處理機(jī)調(diào)度與死鎖 （2 2）作業(yè)控制塊）作業(yè)控制塊JCB

2、(Job Control Block)JCB(Job Control Block)是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。 在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型作業(yè)類型(CPU 繁忙型、繁忙型、I/O 繁忙型繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級(jí)、作業(yè)已運(yùn)行時(shí)間)、資源需求(預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。 第三章處理機(jī)調(diào)度與死鎖 （3 3）作業(yè)調(diào)度）作業(yè)調(diào)度 根據(jù)作業(yè)控制塊中的

3、信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求， 按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存內(nèi)存， 為作業(yè)創(chuàng)建進(jìn)程、分配必要的資源。 然后再將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。 作業(yè)調(diào)度的運(yùn)行頻率較低，通常為幾分鐘一次。 作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能少，有利于提高CPU 的利用率和系統(tǒng)的吞吐量作業(yè)調(diào)度，需要解決兩個(gè)問題：作業(yè)調(diào)度，需要解決兩個(gè)問題：1) 決定接納多少個(gè)作業(yè)決定接納多少個(gè)作業(yè)作業(yè)調(diào)度每次要接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度。2) 2) 決定接納哪些作業(yè)決定接納哪些作業(yè)應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。 先來先服務(wù)調(diào)度

4、算法； 短作業(yè)優(yōu)先調(diào)度算法； 基于作業(yè)優(yōu)先級(jí)的調(diào)度算法第三章處理機(jī)調(diào)度與死鎖 2 2、 低級(jí)調(diào)度（進(jìn)程調(diào)度）低級(jí)調(diào)度（進(jìn)程調(diào)度）它所調(diào)度的對(duì)象是進(jìn)程進(jìn)程( (或內(nèi)核級(jí)線程或內(nèi)核級(jí)線程) )。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種類型的OS中，都必須配置這級(jí)調(diào)度。（1 1）低級(jí)調(diào)度的功能）低級(jí)調(diào)度的功能低級(jí)調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程就緒隊(duì)列中的哪個(gè)進(jìn)程(或內(nèi)核級(jí)線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機(jī)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。進(jìn)程調(diào)度的運(yùn)行頻率很高，一般隔幾十毫秒要運(yùn)行一次。第三章處理機(jī)調(diào)度與死鎖 （2 2）進(jìn)程調(diào)度方式）進(jìn)程調(diào)

5、度方式 非搶占方式非搶占方式(Nonpreemptive Mode)(Nonpreemptive Mode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，不管它要運(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。 第三章處理機(jī)調(diào)度與死鎖 在采用非搶占調(diào)度方式非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個(gè)：(1)

6、正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；(2) 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；(3) 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。 第三章處理機(jī)調(diào)度與死鎖 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正允許調(diào)度程序根據(jù)某

7、種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。一進(jìn)程。搶占方式的優(yōu)點(diǎn)是，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條： 第三章處理機(jī)調(diào)度與死鎖 (1) 優(yōu)先權(quán)原則優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)行

8、；或者說，允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。(2) 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先原則優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時(shí)，將暫停當(dāng)前長(zhǎng)作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行； 或者說，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長(zhǎng)作業(yè)(進(jìn)程)的處理機(jī)。(3) 時(shí)間片原則時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。 3 3、 中級(jí)調(diào)度中級(jí)調(diào)度中級(jí)調(diào)度又稱中程調(diào)度。 目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量目的是為了提高內(nèi)存利用率和系統(tǒng)

9、吞吐量。 將處于外存對(duì)換區(qū)中的具備運(yùn)行條件的進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存中的暫時(shí)不能運(yùn)行的進(jìn)程交換到外存對(duì)換區(qū)。 在存儲(chǔ)器管理中詳細(xì)介紹外存內(nèi)存掛起第三章處理機(jī)調(diào)度與死鎖 掛起和激活第三章處理機(jī)調(diào)度與死鎖 在上述三種調(diào)度中， 進(jìn)程調(diào)度進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10100 ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。 作業(yè)調(diào)度作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘一次，因此把它稱為長(zhǎng)程調(diào)度長(zhǎng)程調(diào)度。由于其運(yùn)行頻率較低，故允許作

10、業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。 中級(jí)調(diào)度中級(jí)調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。 第三章處理機(jī)調(diào)度與死鎖 作業(yè)調(diào)度與進(jìn)程調(diào)度區(qū)別：作業(yè)調(diào)度與進(jìn)程調(diào)度區(qū)別：（1）作業(yè)調(diào)度的結(jié)果：是為作業(yè)創(chuàng)建進(jìn)程進(jìn)程調(diào)度的結(jié)果：是進(jìn)程被執(zhí)行（2）作業(yè)調(diào)度次數(shù)少，進(jìn)程調(diào)度頻度高（3）作業(yè)調(diào)度一般只在批處理系統(tǒng)，但所有系統(tǒng)進(jìn)程調(diào)度必須有。第三章處理機(jī)調(diào)度與死鎖 3.1.2 調(diào)度的基本原則調(diào)度的基本原則 為了衡量調(diào)度算法的性能，人們提出了一些評(píng)價(jià)標(biāo)準(zhǔn)：1、CPU利用率2、系統(tǒng)吞吐量3、響應(yīng)時(shí)間4、周轉(zhuǎn)時(shí)間（1）周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間（2）帶權(quán)周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間第三章處理機(jī)調(diào)度與死鎖 吞吐

11、量吞吐量吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。評(píng)價(jià)批處理系統(tǒng)性能的重要指標(biāo) 。與作業(yè)的平均長(zhǎng)度有關(guān)。對(duì)于大型作業(yè)，一般吞吐量約為每小時(shí)一道作業(yè)，對(duì)于中、小型作業(yè)，其吞吐量則可達(dá)到數(shù)十道作業(yè)。第三章處理機(jī)調(diào)度與死鎖 響應(yīng)時(shí)間響應(yīng)時(shí)間 響應(yīng)時(shí)間是從用戶通過鍵盤提交一個(gè)請(qǐng)求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間間隔。它包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間；處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；將響應(yīng)信息回送到終端顯示器的時(shí)間。l 是分時(shí)系統(tǒng)中的重要原則。第三章處理機(jī)調(diào)度與死鎖 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 從從作業(yè)被提交給系統(tǒng)作業(yè)被提交給系統(tǒng)開始，到開始，到作業(yè)完成作業(yè)完成為止的這段時(shí)間為止的這段時(shí)間間

12、隔稱為間隔稱為作業(yè)周轉(zhuǎn)時(shí)間作業(yè)周轉(zhuǎn)時(shí)間。包括四部分時(shí)間：。包括四部分時(shí)間：l 在外存后備隊(duì)列上等待調(diào)度的時(shí)間在外存后備隊(duì)列上等待調(diào)度的時(shí)間l 進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間l 進(jìn)程在進(jìn)程在CPU上執(zhí)行的時(shí)間上執(zhí)行的時(shí)間l 進(jìn)程等待進(jìn)程等待I/O操作完成的時(shí)間操作完成的時(shí)間 周轉(zhuǎn)時(shí)間定義實(shí)際服務(wù)時(shí)間實(shí)際服務(wù)時(shí)間等待時(shí)間實(shí)際服務(wù)時(shí)間周轉(zhuǎn)時(shí)間siiTTWinisiinTTW11周轉(zhuǎn)時(shí)間Ti平均周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 平均帶權(quán)周轉(zhuǎn)時(shí)間 niinTT11Ti：作業(yè)的周轉(zhuǎn)時(shí)間；：作業(yè)的周轉(zhuǎn)時(shí)間；Tsi：系統(tǒng)為提供為它提系統(tǒng)為提供為它提 供服務(wù)的時(shí)間（真正供服務(wù)的時(shí)間（真正 運(yùn)行

13、時(shí)間）。運(yùn)行時(shí)間）。第三章處理機(jī)調(diào)度與死鎖 例例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序 是：是：1、2、3。求平均周轉(zhuǎn)時(shí)間和平均。求平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間。第三章處理機(jī)調(diào)度與死鎖 解：解：第三章處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：T=(2+2.9+3)/3=2.63hT=(2+2.9+3)/3=2.63h平均帶權(quán)周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間：W=(2+2.9+12)/3=5.3hW=(2+2.9+12)/3=5.3h。第三章處理機(jī)調(diào)度與死鎖 截止時(shí)間截止時(shí)間 是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的

14、最遲時(shí)間。 對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn) 。選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則 面向用戶的準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快 截止時(shí)間的保證 優(yōu)先權(quán)準(zhǔn)則 系統(tǒng)吞吐量高處理機(jī)利用率好 資源的平衡利用 第三章處理機(jī)調(diào)度與死鎖 (1)(1)僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 (2)(2)有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型(3)(3)同時(shí)有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)有三級(jí)調(diào)度的調(diào)度隊(duì)列模型3.1.3 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型第三章處理機(jī)調(diào)度與死鎖 通常，把就緒進(jìn)程組織成FIFO隊(duì)列，每當(dāng)創(chuàng)建新進(jìn)程時(shí)排在

15、就緒隊(duì)列的末尾，按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。進(jìn)程在執(zhí)行時(shí)，出現(xiàn)三種情況：1 任務(wù)在時(shí)間片內(nèi)完成，進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；2 任務(wù)在時(shí)間片內(nèi)未完成，OS便將該任務(wù)再放入就緒隊(duì)列的末尾；3 在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OS放入阻塞隊(duì)列。(1)(1)僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型第三章處理機(jī)調(diào)度與死鎖 就緒隊(duì)列就緒隊(duì)列阻塞隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成用戶用戶事件出現(xiàn)事件出現(xiàn)23第三章處理機(jī)調(diào)度與死鎖 (2)(2)有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 與前一模型的差別：（1）就緒隊(duì)列的形

16、式。批處理系統(tǒng)中最常用的是優(yōu)先權(quán)隊(duì)列。也可采用無序鏈表方式。（2）設(shè)置多個(gè)阻塞隊(duì)列。就緒隊(duì)列就緒隊(duì)列阻塞隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成作業(yè)作業(yè)調(diào)度調(diào)度后備隊(duì)列后備隊(duì)列第三章處理機(jī)調(diào)度與死鎖 （3）有三級(jí)調(diào)度的調(diào)度隊(duì)列模型）有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 調(diào)出時(shí)，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w，由內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?在中級(jí)調(diào)度使外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。3.1.4調(diào)度算法調(diào)度算法v調(diào)度算法是指：根據(jù)系統(tǒng)的調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略資源分配策略所規(guī)定的所規(guī)定的資資源分配算法源分配算法 。v不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法

17、不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法 。第二章進(jìn) 程 管 理 補(bǔ)：進(jìn)程的三種基本狀態(tài)轉(zhuǎn)換補(bǔ)：進(jìn)程的三種基本狀態(tài)轉(zhuǎn)換 就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O請(qǐng)求I/O完成時(shí)間片完進(jìn)程調(diào)度第二章進(jìn) 程 管 理 掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換1.掛起操作的引入掛起操作的引入（1）終端用戶請(qǐng)求）終端用戶請(qǐng)求（2）父進(jìn)程請(qǐng)求）父進(jìn)程請(qǐng)求（3）負(fù)荷調(diào)節(jié)需要）負(fù)荷調(diào)節(jié)需要（4）操作系統(tǒng)的需要）操作系統(tǒng)的需要第二章進(jìn) 程 管 理 掛起引起的狀態(tài)轉(zhuǎn)換掛起引起的狀態(tài)轉(zhuǎn)換靜止?fàn)顟B(tài)靜止?fàn)顟B(tài)活動(dòng)狀態(tài)活動(dòng)狀態(tài)掛起狀態(tài)掛起狀態(tài)非掛起狀態(tài)非掛起狀態(tài)第二章進(jìn) 程 管 理 有掛起狀態(tài)的進(jìn)程狀態(tài)圖有掛起狀態(tài)的進(jìn)程

18、狀態(tài)圖靜止靜止就緒就緒活動(dòng)活動(dòng)阻塞阻塞執(zhí)行執(zhí)行I/O請(qǐng)求活動(dòng)活動(dòng)就緒就緒靜止靜止阻塞阻塞掛起掛起激活掛起激活調(diào)度釋放釋放1、先來先服務(wù)調(diào)度算法（、先來先服務(wù)調(diào)度算法（FCFS）（）（作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度） 2、短作業(yè)（進(jìn)程）優(yōu)先法（、短作業(yè)（進(jìn)程）優(yōu)先法（作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度） 3 3、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度） 優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度作業(yè)調(diào)度） 4 4、時(shí)間片輪轉(zhuǎn)法（、時(shí)間片輪轉(zhuǎn)法（進(jìn)程調(diào)度進(jìn)程調(diào)度）5 5、多級(jí)反饋隊(duì)列

19、調(diào)度算法（多級(jí)反饋隊(duì)列調(diào)度算法（進(jìn)程調(diào)度進(jìn)程調(diào)度）1 1、先來先服務(wù)調(diào)度算法（先來先服務(wù)調(diào)度算法（FCFSFCFS）可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中。可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中。l 作業(yè)調(diào)度中每次從后備作業(yè)隊(duì)列中，選擇作業(yè)調(diào)度中每次從后備作業(yè)隊(duì)列中，選擇一個(gè)或多一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的個(gè)最先進(jìn)入該隊(duì)列的作業(yè)調(diào)入內(nèi)存，為它們分配資作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。l 進(jìn)程調(diào)度時(shí)每次從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入進(jìn)程調(diào)度時(shí)每次從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻該隊(duì)列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻塞后

20、，才放棄處理機(jī)。塞后，才放棄處理機(jī)。1、先來先服務(wù)調(diào)度算法、先來先服務(wù)調(diào)度算法l 是一種最簡(jiǎn)單的調(diào)度算法既可用于作業(yè)調(diào)度也可用是一種最簡(jiǎn)單的調(diào)度算法既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度。于進(jìn)程調(diào)度。l FCFS( first come first serve)FCFS( first come first serve)算法算法l 有利長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。有利長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。 l 有利有利CPUCPU繁忙型作業(yè)，而不利于繁忙型作業(yè)，而不利于I/OI/O繁忙型作業(yè)。繁忙型作業(yè)。開始開始+運(yùn)行運(yùn)行決定服務(wù)順序決定服務(wù)順序1 1101101102102202202

21、開始開始+運(yùn)行運(yùn)行完成完成-到達(dá)到達(dá)周轉(zhuǎn)周轉(zhuǎn)/ /運(yùn)行運(yùn)行100/1100/1100/1100/12、短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法、短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 短作業(yè)優(yōu)先（SJF）法：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短估計(jì)運(yùn)行時(shí)間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）調(diào)度算法：從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，分配處理機(jī)使它立即執(zhí)行直到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度?？捎糜谧鳂I(yè)調(diào)度和進(jìn)程調(diào)度中可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中 進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間FCFS 完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間SJF完成時(shí)間完成時(shí)

22、間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1

23、 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 6周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 3帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)

24、間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 9 6周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 8 3帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 9 6 13周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 8 3 9帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3

25、4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 9 18 6 13周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 8 16 3 9帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E平均 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 9 18 6 13周轉(zhuǎn)時(shí)間周

26、轉(zhuǎn)時(shí)間4 8 16 3 9帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2.673.1 1.5 2.25作業(yè)作業(yè)算法算法 進(jìn)程名進(jìn)程名A B C D E 到達(dá)時(shí)間到達(dá)時(shí)間0 1 2 3 4 服務(wù)時(shí)間服務(wù)時(shí)間4 3 5 2 4FCFS 完成時(shí)間完成時(shí)間4 7 12 14 18周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 6 10 11 14帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2 2 5.5 3.5SJF完成時(shí)間完成時(shí)間4 9 18 6 13周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4 8 16 3 9帶權(quán)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)間間1 2.673.1 1.5 2.25作業(yè)作業(yè)算法算法SJ （P）F法缺點(diǎn)法缺點(diǎn)（1 1）對(duì)長(zhǎng)作業(yè)不利對(duì)長(zhǎng)作業(yè)不利。如果有一長(zhǎng)作業(yè)進(jìn)入系統(tǒng)的后。如果有一

27、長(zhǎng)作業(yè)進(jìn)入系統(tǒng)的后備隊(duì)列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），備隊(duì)列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），將導(dǎo)致長(zhǎng)作業(yè)長(zhǎng)期不被調(diào)度。將導(dǎo)致長(zhǎng)作業(yè)長(zhǎng)期不被調(diào)度。（2 2）完全）完全未考慮未考慮作業(yè)的作業(yè)的緊迫程度緊迫程度，不能保證緊迫性，不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。（3 3）作業(yè)（進(jìn)程）的長(zhǎng)短根據(jù)）作業(yè)（進(jìn)程）的長(zhǎng)短根據(jù)用戶所提供的估計(jì)用戶所提供的估計(jì)執(zhí)執(zhí)行時(shí)間而定的，不一定能真正做到短作業(yè)優(yōu)先調(diào)行時(shí)間而定的，不一定能真正做到短作業(yè)優(yōu)先調(diào)度。度。3 3、 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法（1）優(yōu)先權(quán)調(diào)度算法類型（2 2）優(yōu)先權(quán)的類型）優(yōu)先權(quán)的類型（3

28、 3）高響應(yīng)比優(yōu)先調(diào)度算法）高響應(yīng)比優(yōu)先調(diào)度算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中可用于作業(yè)調(diào)度和進(jìn)程調(diào)度中（1 1）優(yōu)先權(quán)調(diào)度算法類型）優(yōu)先權(quán)調(diào)度算法類型 非搶占式非搶占式優(yōu)先權(quán)算法優(yōu)先權(quán)算法 把處理機(jī)分配給就緒隊(duì)列中把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程后便一直執(zhí)的進(jìn)程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程?？稍賹⑻幚頇C(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。 用于用于批處理系統(tǒng)批處理系統(tǒng)和某些和某些對(duì)實(shí)時(shí)性要求不嚴(yán)對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。的實(shí)時(shí)系統(tǒng)中。 搶占式搶占式優(yōu)先權(quán)調(diào)

29、度算法優(yōu)先權(quán)調(diào)度算法 把處理機(jī)分配給把處理機(jī)分配給優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先權(quán)間，只要又出現(xiàn)優(yōu)先權(quán)更高更高的進(jìn)程，就的進(jìn)程，就重新重新將處理機(jī)分配將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。給新到的優(yōu)先權(quán)最高的進(jìn)程。 能更好地滿足緊迫作業(yè)的要求，常用于能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的要求比較嚴(yán)格的實(shí)實(shí)時(shí)系統(tǒng)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。書p94 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)書p94 靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)： 在創(chuàng)建進(jìn)程時(shí)確定在創(chuàng)建進(jìn)程時(shí)確定 在

30、進(jìn)程的整個(gè)運(yùn)行期間保持不變。在進(jìn)程的整個(gè)運(yùn)行期間保持不變。 一般地，用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，一般地，用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0707或或02550255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定優(yōu)先權(quán)依據(jù)：確定優(yōu)先權(quán)依據(jù)：（1 1）進(jìn)程類型：系統(tǒng)進(jìn)程）進(jìn)程類型：系統(tǒng)進(jìn)程高于高于用戶進(jìn)程用戶進(jìn)程（2 2）進(jìn)程對(duì)資源的要求：要求少的進(jìn)程應(yīng)賦予較）進(jìn)程對(duì)資源的要求：要求少的進(jìn)程應(yīng)賦予較高高優(yōu)先權(quán)。優(yōu)先權(quán)。（3 3）用戶要求。這是由用戶進(jìn)程的）用戶要求。這是由用戶進(jìn)程的緊迫程度緊迫程度及所付費(fèi)多少來確定。及所付費(fèi)多少來確定。靜態(tài)優(yōu)先權(quán)法優(yōu)缺

31、點(diǎn)：靜態(tài)優(yōu)先權(quán)法優(yōu)缺點(diǎn)：l簡(jiǎn)單，系統(tǒng)開銷小l不精確，僅在要求不高的系統(tǒng)中使用（2 2）優(yōu)先權(quán)的類型）優(yōu)先權(quán)的類型 動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)優(yōu)先權(quán)隨優(yōu)先權(quán)隨進(jìn)程推進(jìn)進(jìn)程推進(jìn)或隨其或隨其等待時(shí)間等待時(shí)間的增加而改變的，的增加而改變的，以便獲得更好的調(diào)度性能。以便獲得更好的調(diào)度性能。 (3)(3)高響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度）高響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度） 引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級(jí)隨著等待時(shí)間的增引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率加而以速率a a提高。提高。該優(yōu)先權(quán)的變化規(guī)律為：該優(yōu)先權(quán)的變化規(guī)律為：優(yōu)先權(quán)優(yōu)先權(quán) = =（等待時(shí)間（等待時(shí)間+ +要求服務(wù)時(shí)間）要求服務(wù)時(shí)間

32、） / /要求服務(wù)時(shí)間要求服務(wù)時(shí)間優(yōu)先權(quán)優(yōu)先權(quán) = = R RP P = =響應(yīng)時(shí)間響應(yīng)時(shí)間/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間R RP P ：響應(yīng)比：響應(yīng)比分析作業(yè)等待時(shí)間相同，則有利于作業(yè)等待時(shí)間相同，則有利于短作業(yè)短作業(yè)。要求服務(wù)時(shí)間相同，實(shí)現(xiàn)的是要求服務(wù)時(shí)間相同，實(shí)現(xiàn)的是先來先服務(wù)先來先服務(wù)。長(zhǎng)作業(yè)也可獲得處理機(jī)。長(zhǎng)作業(yè)也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長(zhǎng)短作業(yè)。優(yōu)點(diǎn)：兼顧長(zhǎng)短作業(yè)。缺點(diǎn)：由于做響應(yīng)比計(jì)算，故增加了系缺點(diǎn)：由于做響應(yīng)比計(jì)算，故增加了系 統(tǒng)開銷統(tǒng)開銷優(yōu)先權(quán)優(yōu)先權(quán) =(=(等待時(shí)間等待時(shí)間/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間)+1)+1 4 4、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法分時(shí)系統(tǒng)中，多采用時(shí)間片輪轉(zhuǎn)法分時(shí)系統(tǒng)中，多采用時(shí)間片輪轉(zhuǎn)法 把就緒進(jìn)程組織成把就緒進(jìn)程組織成FIFOFIFO隊(duì)列；隊(duì)列； 把