1、第三章 處理機(jī)調(diào)度和死鎖 http:/ 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念v3.13.1高、中、低三級(jí)調(diào)度高、中、低三級(jí)調(diào)度 1 1、高級(jí)調(diào)度（作業(yè)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）、高級(jí)調(diào)度（作業(yè)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）v將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCBPCB等，插入就緒隊(duì)列。等，插入就緒隊(duì)列。v一般用于批處理系統(tǒng)，分一般用于批處理系統(tǒng)，分/ /實(shí)時(shí)系統(tǒng)一般直接入內(nèi)存，實(shí)時(shí)系統(tǒng)一般直接入內(nèi)存，無(wú)此環(huán)節(jié)。無(wú)此環(huán)節(jié)。調(diào)度特性調(diào)度特性v1.1.接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）太多太多 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間T T長(zhǎng)長(zhǎng)太少太少 系統(tǒng)效率低系統(tǒng)效率低v2.2.接

2、納策略：即采用何種調(diào)度算法：接納策略：即采用何種調(diào)度算法：FCFSFCFS、短作業(yè)優(yōu)、短作業(yè)優(yōu)先等先等 處理機(jī)調(diào)度的基本概念（處理機(jī)調(diào)度的基本概念（2 2）2 2、低級(jí)調(diào)度（進(jìn)程調(diào)度，短程調(diào)度）、低級(jí)調(diào)度（進(jìn)程調(diào)度，短程調(diào)度）v主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派處理機(jī)。）分派處理機(jī)。1.1.非搶占方式：非搶占方式：簡(jiǎn)單，實(shí)時(shí)性差簡(jiǎn)單，實(shí)時(shí)性差 ( (如如win31)win31)2.2.搶占方式搶占方式（1 1）優(yōu)先權(quán)原則）優(yōu)先權(quán)原則（2 2）短作業(yè)優(yōu)先原則）短作業(yè)優(yōu)先原則（3 3）時(shí)間片原則。）時(shí)間片原則。 v運(yùn)行頻率：低運(yùn)行頻率：低 中中 高高

3、。 v一、僅有進(jìn)程調(diào)度的一、僅有進(jìn)程調(diào)度的調(diào)度調(diào)度隊(duì)列模型隊(duì)列模型就 緒 隊(duì) 列就 緒 隊(duì) 列CPU阻 塞 隊(duì) 列阻 塞 隊(duì) 列交互用戶交互用戶時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件事事件件出出現(xiàn)現(xiàn).2調(diào)度的隊(duì)列模型調(diào)度的隊(duì)列模型進(jìn)程完成進(jìn)程完成.2調(diào)度的隊(duì)列模型調(diào)度的隊(duì)列模型v二、具有高二、具有高/ /低級(jí)調(diào)度的調(diào)度隊(duì)列模型低級(jí)調(diào)度的調(diào)度隊(duì)列模型就 緒 隊(duì) 列就 緒 隊(duì) 列CPU阻 塞 隊(duì) 列阻 塞 隊(duì) 列時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程進(jìn)程完成完成等待事件等待事件1事件事件1出現(xiàn)出現(xiàn)阻 塞 隊(duì) 列阻 塞 隊(duì) 列等待事件等待事件2事件事件2出現(xiàn)出

4、現(xiàn)作業(yè)作業(yè)調(diào)度調(diào)度后備隊(duì)列后備隊(duì)列N三、具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就 緒 隊(duì) 列就 緒 隊(duì) 列CPU就緒、掛起隊(duì)列就緒、掛起隊(duì)列時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程進(jìn)程完成完成后備隊(duì)列后備隊(duì)列阻塞、掛起隊(duì)列阻塞、掛起隊(duì)列事件出現(xiàn)事件出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度阻 塞 隊(duì) 列阻 塞 隊(duì) 列等待事件等待事件掛起掛起事件出現(xiàn)事件出現(xiàn)中級(jí)調(diào)度中級(jí)調(diào)度交互型作業(yè)交互型作業(yè).3選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則 v一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則1 1周轉(zhuǎn)時(shí)間短（常用于批處理系統(tǒng)）周轉(zhuǎn)時(shí)間短（常用于批處理系統(tǒng)）v概念：作業(yè)從提交概念：作業(yè)從提交 完成的時(shí)間完成的時(shí)間. .

5、分為：分為：（1 1）駐外等待調(diào)度時(shí)間）駐外等待調(diào)度時(shí)間（2 2）駐內(nèi)等待調(diào)度時(shí)間）駐內(nèi)等待調(diào)度時(shí)間（3 3）執(zhí)行時(shí)間）執(zhí)行時(shí)間（4 4）阻塞時(shí)間）阻塞時(shí)間v一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 可見帶權(quán)可見帶權(quán)W W越小越好越小越好,Ts,Ts為實(shí)際服務(wù)時(shí)間。為實(shí)際服務(wù)時(shí)間。.3選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則 11niiTnT11nisiiTTnWv一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則2 2響應(yīng)時(shí)間快：（對(duì)交互性作業(yè)）響應(yīng)時(shí)間快：（對(duì)交互性作業(yè)）v概念：鍵盤提交請(qǐng)求到首次響應(yīng)的時(shí)間概念：鍵盤提交

6、請(qǐng)求到首次響應(yīng)的時(shí)間（1 1）輸入傳送時(shí)間）輸入傳送時(shí)間（2 2）處理時(shí)間）處理時(shí)間（3 3）響應(yīng)傳送時(shí)間）響應(yīng)傳送時(shí)間3 3截止時(shí)間的保證（特別于實(shí)時(shí)系統(tǒng)）截止時(shí)間的保證（特別于實(shí)時(shí)系統(tǒng)）4 4優(yōu)先權(quán)準(zhǔn)則：（即需要搶占調(diào)度）優(yōu)先權(quán)準(zhǔn)則：（即需要搶占調(diào)度）.3選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則 v二、面向系統(tǒng)的準(zhǔn)則二、面向系統(tǒng)的準(zhǔn)則1 1吞吐量高（特別于批處理）：?jiǎn)挝粫r(shí)間完成作吞吐量高（特別于批處理）：?jiǎn)挝粫r(shí)間完成作業(yè)數(shù)業(yè)數(shù)2 2處理機(jī)利用率好：（因處理機(jī)利用率好：（因CPUCPU貴，特別于大中型貴，特別于大中型多用戶系統(tǒng)）多用戶系統(tǒng)）3 3各類資源的平衡

7、利用。各類資源的平衡利用。.3選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則 3.2 3.2調(diào)度算法調(diào)度算法 是一個(gè)資源分配問題是一個(gè)資源分配問題 v.1先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法法 1.1.先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法FCFSFCFSv特點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè)特點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè) 即即CPUCPU繁忙性作業(yè)繁忙性作業(yè).1先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法2.2.短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：SJ(P)FSJ(P)F

8、選出估計(jì)運(yùn)行時(shí)間最短的作業(yè)（進(jìn)程）選出估計(jì)運(yùn)行時(shí)間最短的作業(yè)（進(jìn)程） 提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間（從而提高了系統(tǒng)吞吐量）間（從而提高了系統(tǒng)吞吐量） 對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù)（饑對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù)（饑餓）餓） 未考慮作業(yè)的緊迫性未考慮作業(yè)的緊迫性 估計(jì)時(shí)間不易確定估計(jì)時(shí)間不易確定圖3.4 FCFS和SJF比較0417231241418ABCDEFCFS041923184613ABCDESJF.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法v1.1.優(yōu)先權(quán)調(diào)度算法類型優(yōu)先權(quán)調(diào)度算法類型非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法搶占

9、式優(yōu)先權(quán)算法，實(shí)時(shí)性更好。搶占式優(yōu)先權(quán)算法，實(shí)時(shí)性更好。v2.2.優(yōu)先權(quán)類型：優(yōu)先權(quán)類型：1 1靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)：v進(jìn)程優(yōu)先權(quán)在整個(gè)運(yùn)行期不變。進(jìn)程優(yōu)先權(quán)在整個(gè)運(yùn)行期不變。v確定優(yōu)先權(quán)依據(jù)確定優(yōu)先權(quán)依據(jù)（1 1）進(jìn)程類型）進(jìn)程類型（2 2）進(jìn)程對(duì)資源的需求；）進(jìn)程對(duì)資源的需求；（3 3）根據(jù)用戶需求。）根據(jù)用戶需求。v特點(diǎn)：簡(jiǎn)單，但低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被調(diào)度。特點(diǎn)：簡(jiǎn)單，但低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被調(diào)度。.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法(2)(2)v2 2動(dòng)態(tài)優(yōu)先權(quán)：動(dòng)態(tài)優(yōu)先權(quán)：如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)間而升高。如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)

10、間而升高。響應(yīng)比響應(yīng)比Rp=Rp=（等待時(shí)間服務(wù)時(shí)間）（等待時(shí)間服務(wù)時(shí)間）/ /服務(wù)時(shí)間服務(wù)時(shí)間 作為優(yōu)作為優(yōu)先權(quán)先權(quán)優(yōu)點(diǎn)：長(zhǎng)短兼顧優(yōu)點(diǎn)：長(zhǎng)短兼顧 缺點(diǎn)：需計(jì)算缺點(diǎn)：需計(jì)算RpRpv3.3.高響應(yīng)比優(yōu)先算法：高響應(yīng)比優(yōu)先算法：特點(diǎn)：特點(diǎn)：響應(yīng)比響應(yīng)比Rp=Rp=（tw+tstw+ts）/ts/ts（1 1）短作業(yè)）短作業(yè)R RP P大。大。（2 2）tsts（要求服務(wù)時(shí)間）相同的進(jìn)程間相當(dāng)于（要求服務(wù)時(shí)間）相同的進(jìn)程間相當(dāng)于FCFSFCFS。（3 3）長(zhǎng)作業(yè)等待一段時(shí)間仍能得到服務(wù)。）長(zhǎng)作業(yè)等待一段時(shí)間仍能得到服務(wù)。.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法v1.1.

11、時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)時(shí)間片大小的確定時(shí)間片大小的確定v太大：退化為太大：退化為FCFSFCFS；v太?。合到y(tǒng)開銷過大太小：系統(tǒng)開銷過大系統(tǒng)對(duì)響應(yīng)時(shí)間的要求；系統(tǒng)對(duì)響應(yīng)時(shí)間的要求；T=nqT=nq就緒隊(duì)列中進(jìn)程的數(shù)目；就緒隊(duì)列中進(jìn)程的數(shù)目；系統(tǒng)的處理能力：（應(yīng)保證一個(gè)時(shí)間片處理完常用命令）系統(tǒng)的處理能力：（應(yīng)保證一個(gè)時(shí)間片處理完常用命令）v2.2.多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度 多個(gè)就緒隊(duì)列，不同優(yōu)先級(jí)多個(gè)就緒隊(duì)列，不同優(yōu)先級(jí) 新進(jìn)程首先進(jìn)入第一隊(duì)列尾，新進(jìn)程首先進(jìn)入第一隊(duì)列尾，F(xiàn)CFSFCFS；時(shí)間片結(jié)束后；時(shí)間片結(jié)束后未完成的進(jìn)入第二隊(duì)列未完成的進(jìn)入第二隊(duì)列尾尾 第一隊(duì)列空閑時(shí)才調(diào)度第二隊(duì)

12、列，搶占式第一隊(duì)列空閑時(shí)才調(diào)度第二隊(duì)列，搶占式.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（2 2）特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響應(yīng)時(shí)間特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響應(yīng)時(shí)間v（1 1）短作業(yè)一次完成；）短作業(yè)一次完成；v（2 2）中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；）中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；v（3 3）大型作業(yè)不會(huì)長(zhǎng)期不處理。）大型作業(yè)不會(huì)長(zhǎng)期不處理。就緒隊(duì)列就緒隊(duì)列1 1至至CPUS1就緒隊(duì)列就緒隊(duì)列2 2S2至至CPU就緒隊(duì)列就緒隊(duì)列3 3S3至至CPU就緒隊(duì)列就緒隊(duì)列n nSn至至CPU時(shí)間片：時(shí)間片：S1S2Available(2,3,0) (2)Request4(3,3,

13、0)Available(2,3,0)，讓，讓P4P4等待。等待。（4 4） P0 P0請(qǐng)求資源請(qǐng)求資源 P P0 0發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request0(0,2,0),Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢系統(tǒng)按銀行家算法進(jìn)行檢查：查： ( (1 1) )RequestRequest0 0(0,2,0)(0,2,0)N Needeed0 0(7,4,3);(7,4,3); (2)Request (2)Request0 0(0,2,0)Available(2,3,0)(0,2,0)Available(2,3,0)， (3) (3)進(jìn)行安全性檢查進(jìn)行安全性檢查 可用資源可用資源

14、Available2,1,0Available2,1,0已不能滿足任何進(jìn)程的需要，已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。 3.73.7 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除.1、 死鎖的檢測(cè)死鎖的檢測(cè)v系統(tǒng)必須須提供檢測(cè)和解除死鎖的手段：系統(tǒng)必須須提供檢測(cè)和解除死鎖的手段：（1 1）保存有關(guān)資源的請(qǐng)求和分配信息；）保存有關(guān)資源的請(qǐng)求和分配信息；（2 2）提供算法以利用這些信息來(lái)檢測(cè)系統(tǒng)是否進(jìn)入）提供算法以利用這些信息來(lái)檢測(cè)系統(tǒng)是否進(jìn)入死鎖。死鎖。1 1、資源分配圖（、資源分配圖（Resource Ailocat

15、ion GraphResource Ailocation Graph） 系統(tǒng)死鎖可利用資源分配圖來(lái)描述。系統(tǒng)死鎖可利用資源分配圖來(lái)描述。G=G=（N N，E E）：）：（1 1）N N分為兩個(gè)互斥的子集，進(jìn)程結(jié)點(diǎn)分為兩個(gè)互斥的子集，進(jìn)程結(jié)點(diǎn)P=P=（P P1 1，P P2 2,P,Pn n）, ,資源結(jié)點(diǎn)資源結(jié)點(diǎn)R=rR=r1 1,r,r2 2,r,rn n,N=PR,N=PR。（2 2）E E中的邊中的邊eE,eE,都連接著都連接著P P中的一個(gè)結(jié)點(diǎn)和中的一個(gè)結(jié)點(diǎn)和R R中的中的一個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)，e=pe=pi i,r,rj j 是資源請(qǐng)求邊，由進(jìn)程是資源請(qǐng)求邊，由進(jìn)程p pi i指向指向

16、資源資源r rj j, ,它表示進(jìn)程它表示進(jìn)程p pi i請(qǐng)求一個(gè)單位的請(qǐng)求一個(gè)單位的r rj j資源。資源。p1p2R2R1分配請(qǐng)求.1 死鎖的檢測(cè)死鎖的檢測(cè)2 2、死鎖定理、死鎖定理v簡(jiǎn)化資源分配圖來(lái)檢測(cè)系統(tǒng)處于簡(jiǎn)化資源分配圖來(lái)檢測(cè)系統(tǒng)處于S S狀態(tài)時(shí)，是否為死鎖狀狀態(tài)時(shí)，是否為死鎖狀態(tài)。簡(jiǎn)化方法如下：態(tài)。簡(jiǎn)化方法如下：（1 1）在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)）在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)點(diǎn)p pi i。在順利情況下，。在順利情況下，p pi i可獲得所需資源而繼續(xù)執(zhí)行，直可獲得所需資源而繼續(xù)執(zhí)行，直至運(yùn)行完畢，再釋放其所占有的全部資

17、源。這相當(dāng)于消去至運(yùn)行完畢，再釋放其所占有的全部資源。這相當(dāng)于消去p pi i所有的請(qǐng)求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。所有的請(qǐng)求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。p1p2R2R1p1p2R2R1（2 2）p1p1釋放資源后，便可使釋放資源后，便可使p2p2獲得資源而繼續(xù)運(yùn)行，直到獲得資源而繼續(xù)運(yùn)行，直到p2p2完成又釋放出它所占有的全部資源，而形成圖（完成又釋放出它所占有的全部資源，而形成圖（c c）所示的情）所示的情況。況。（3 3）在進(jìn)行一系列的簡(jiǎn)化中，若能消去圖中所有的邊，使所）在進(jìn)行一系列的簡(jiǎn)化中，若能消去圖中所有的邊，使所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖是有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖

18、是可完全簡(jiǎn)化可完全簡(jiǎn)化的，若不能的，若不能通過任何過程使該圖完全簡(jiǎn)化，則稱該圖是不可完全簡(jiǎn)化的。通過任何過程使該圖完全簡(jiǎn)化，則稱該圖是不可完全簡(jiǎn)化的。p1p2R12 2、死鎖定理、死鎖定理vS S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)狀態(tài)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)狀態(tài)S S的資源分配圖是不可完全簡(jiǎn)化的。的資源分配圖是不可完全簡(jiǎn)化的。.1 死鎖的檢測(cè)死鎖的檢測(cè)3 3、死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)、死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)，類似于銀行家算法中的死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)，類似于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 可利用資源向量可利用資源向量AvailableAvailable。它

19、表示了。它表示了m m類資類資源中的每一類資源的可用數(shù)目。源中的每一類資源的可用數(shù)目。 把不占用資源的進(jìn)程向量把不占用資源的進(jìn)程向量AllocationAllocation：=0=0記記入表入表L L中，即中，即LiLLiL。 從進(jìn)程集合中找到一個(gè)從進(jìn)程集合中找到一個(gè)RequestiWorkRequestiWork的進(jìn)的進(jìn)程，做如下處理：程，做如下處理： 將其資源分配圖簡(jiǎn)化，釋放出資源，增加工將其資源分配圖簡(jiǎn)化，釋放出資源，增加工作向量作向量Work Work ：=Work+Allocation=Work+Allocation。 將它記入將它記入L L表中。表中。.1 死鎖的檢測(cè)死鎖的檢測(cè)若不能把所有的進(jìn)程都記入若不能把所有的進(jìn)程都記入L L表中，則表明系統(tǒng)狀態(tài)表中，則表明系統(tǒng)狀態(tài)S S的資源的資源分配圖是不完全簡(jiǎn)化的，因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。分配圖是不完全簡(jiǎn)化的，因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。Work:=Available;Work:=Available;L:=Li Allocationi=0L:=Li Allocationi=0Requesti=0Requesti=0