操作系統(tǒng)課件：第3章 處理機(jī)的調(diào)度和死鎖

1、v 3.13.1高、中、低三級(jí)調(diào)度高、中、低三級(jí)調(diào)度 v 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)度） 將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCBPCB等，插入就緒等，插入就緒隊(duì)列。隊(duì)列。 一般用于批處理系統(tǒng)，分一般用于批處理系統(tǒng)，分/ /實(shí)時(shí)系統(tǒng)一般直接實(shí)時(shí)系統(tǒng)一般直接入內(nèi)存，無(wú)此環(huán)節(jié)。入內(nèi)存，無(wú)此環(huán)節(jié)。 調(diào)度特性調(diào)度特性 1.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)效率低 2.2.接納策略：即采用何種調(diào)度算法：接納策略：即采用何種調(diào)度算法：FCFSFCFS、短、

2、短作業(yè)優(yōu)先等作業(yè)優(yōu)先等v 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）時(shí)間片原則）時(shí)間片原則（2 2）優(yōu)先權(quán)原則）優(yōu)先權(quán)原則（3 3）短作業(yè)優(yōu)先原則。）短作業(yè)優(yōu)先原則。 v運(yùn)行頻率：低運(yùn)行頻率：低 中中 高高。v三種調(diào)度被引發(fā)的事件？三種調(diào)度被引發(fā)的事件？v事件的表現(xiàn)方式？事件的表現(xiàn)方式？v一、僅有進(jìn)程調(diào)度的隊(duì)列模型一、僅有進(jìn)程調(diào)

3、度的隊(duì)列模型就緒隊(duì)列就緒隊(duì)列CPU阻塞隊(duì)列阻塞隊(duì)列交互用戶交互用戶時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成等待事件等待事件事件出現(xiàn)事件出現(xiàn)v二、具有高二、具有高/ /低級(jí)模型低級(jí)模型就緒隊(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ì)列阻塞隊(duì)列阻塞隊(duì)列等待事件等待事件2事件事件2出現(xiàn)出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度就緒隊(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ì)列等待事件等待事

4、件掛起掛起事件出現(xiàn)事件出現(xiàn)中級(jí)調(diào)度中級(jí)調(diào)度交互型作業(yè)交互型作業(yè)v 一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則1 1 周轉(zhuǎn)時(shí)間短（常用于批處理系統(tǒng)）周轉(zhuǎn)時(shí)間短（常用于批處理系統(tǒng)） 概念：作業(yè)從提交概念：作業(yè)從提交 完成的時(shí)間完成的時(shí)間. .分為：分為： （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)平均帶權(quán) 可見(jiàn)帶權(quán)可見(jiàn)帶權(quán)w w越小越好越小越好,Ts,Ts為實(shí)際服務(wù)時(shí)間。為實(shí)際服務(wù)時(shí)間。11niiTnT11nisiTTnW

5、v 一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則2 2 響應(yīng)時(shí)間快：（對(duì)交互性作業(yè)）響應(yīng)時(shí)間快：（對(duì)交互性作業(yè)） 概念：鍵盤(pán)提交請(qǐng)求到首次響應(yīng)時(shí)間概念：鍵盤(pán)提交請(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)度）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ī)利用率好：（因

6、CPUCPU貴，特別于大中型貴，特別于大中型多用戶系統(tǒng)）多用戶系統(tǒng)）3 3 各類(lèi)資源的平衡利用。（？折算標(biāo)準(zhǔn)）各類(lèi)資源的平衡利用。（？折算標(biāo)準(zhǔn)）v3.2.13.2.1先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 1.FCFS1.FCFS特點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè)特點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè) 即即CPUCPU繁忙性作業(yè)繁忙性作業(yè)2.2.短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：SJ(P)FSJ(P)F提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間（從而提提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間（從而提高了系統(tǒng)吞吐量）高了系統(tǒng)吞吐量）特點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù)（饑餓）特

7、點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù)（饑餓）估計(jì)時(shí)間不易確定估計(jì)時(shí)間不易確定進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99進(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 149帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2 5.5 3.52.8SJF完成時(shí)間完成時(shí)間 4 9 18 6 13周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 4 8 16 3 98帶權(quán)周轉(zhuǎn)

8、時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 1 2.67 3.1 1.5 2.252.1v 1.1.優(yōu)先權(quán)調(diào)度算法類(lèi)型優(yōu)先權(quán)調(diào)度算法類(lèi)型 非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法 搶占式優(yōu)先權(quán)算法，實(shí)時(shí)性更好。搶占式優(yōu)先權(quán)算法，實(shí)時(shí)性更好。v 2.2.優(yōu)先權(quán)類(lèi)型：優(yōu)先權(quán)類(lèi)型：1 1 靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)： 進(jìn)程優(yōu)先權(quán)在整個(gè)運(yùn)行期不變。進(jìn)程優(yōu)先權(quán)在整個(gè)運(yùn)行期不變。 確定優(yōu)先權(quán)依據(jù)確定優(yōu)先權(quán)依據(jù)（1 1）進(jìn)程類(lèi)型）進(jìn)程類(lèi)型（2 2）進(jìn)程對(duì)資源的需求；）進(jìn)程對(duì)資源的需求；（3 3）根據(jù)用戶需求。）根據(jù)用戶需求。 特點(diǎn)：簡(jiǎn)單，但低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被特點(diǎn)：簡(jiǎn)單，但低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被調(diào)度。調(diào)度。v 2 2動(dòng)態(tài)優(yōu)先權(quán)：動(dòng)態(tài)優(yōu)

9、先權(quán)： 如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)間而升高。如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)間而升高。 響應(yīng)比響應(yīng)比RpRp= =（等待時(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ì)算RpRpv 3.3.高響應(yīng)比優(yōu)先算法：高響應(yīng)比優(yōu)先算法： 特點(diǎn)：特點(diǎn)： 響應(yīng)比響應(yīng)比RpRp= =（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í)間仍能得到服

10、務(wù)。）長(zhǎng)作業(yè)等待一段時(shí)間仍能得到服務(wù)。v 1.1.時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn) 時(shí)間片大小的確定時(shí)間片大小的確定 太大：退化為太大：退化為FCFSFCFS； 太?。合到y(tǒng)開(kāi)銷(xiāo)過(guò)大太?。合到y(tǒng)開(kāi)銷(xiāo)過(guò)大 系統(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í)間片處理完常用命令）v 2.2.多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度 特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響應(yīng)時(shí)間特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響應(yīng)時(shí)間 （1 1）短作業(yè)一次完成；）短作業(yè)一次完成； （2 2）中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；）

11、中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)； （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í)間片：S1S2S3圖圖35多級(jí)隊(duì)列反饋調(diào)度算法多級(jí)隊(duì)列反饋調(diào)度算法v 3 3.3.1.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1 1 提供必要的調(diào)度信息提供必要的調(diào)度信息 （1 1）就緒時(shí)間；）就緒時(shí)間； （2 2）開(kāi)始）開(kāi)始/ /完成截止時(shí)間；完成截止時(shí)間； （3 3）處理時(shí)間；）處理時(shí)間； （4 4）資源要求；）資源要求； （5 5）優(yōu)先級(jí)；）優(yōu)

12、先級(jí)；2 2 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng)NPCPCmiiimiii111Ci為處理時(shí)間，為處理時(shí)間，Pi為周期時(shí)間（基于周期性實(shí)時(shí)任務(wù)）為周期時(shí)間（基于周期性實(shí)時(shí)任務(wù)）v 3 3.3.1.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件.3 3.采用搶占調(diào)度方式采用搶占調(diào)度方式 剝奪方式：一般都采用此剝奪方式：一般都采用此 非剝奪方式（實(shí)現(xiàn)簡(jiǎn)單）：一般應(yīng)使實(shí)時(shí)任務(wù)較小，非剝奪方式（實(shí)現(xiàn)簡(jiǎn)單）：一般應(yīng)使實(shí)時(shí)任務(wù)較小，以及時(shí)放棄以及時(shí)放棄CPUCPU。.4 4.具有快速切換機(jī)制具有快速切換機(jī)制 具有快速響應(yīng)外部中斷能力。具有快速響應(yīng)外部中斷能力。 快速任務(wù)分派快速任務(wù)分派v 1 1非搶占式調(diào)度

13、算法非搶占式調(diào)度算法 時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn) 秒級(jí)秒級(jí) 非搶占優(yōu)先權(quán)（協(xié)同）非搶占優(yōu)先權(quán)（協(xié)同） 秒秒 毫秒級(jí)毫秒級(jí)v 2 2搶占式調(diào)度算法搶占式調(diào)度算法 時(shí)鐘中斷搶占優(yōu)先權(quán)時(shí)鐘中斷搶占優(yōu)先權(quán) 毫秒級(jí)毫秒級(jí) 基于搶占點(diǎn)搶占基于搶占點(diǎn)搶占 立即搶占立即搶占immediate preemption immediate preemption 毫秒毫秒 微秒級(jí)微秒級(jí) 只要不在臨界區(qū)即搶占（中斷引發(fā)）只要不在臨界區(qū)即搶占（中斷引發(fā)）進(jìn)程1進(jìn)程2進(jìn)程n實(shí)時(shí)進(jìn)程調(diào)度時(shí)間調(diào)度時(shí)間實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行a 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)

14、程要求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成當(dāng)前進(jìn)程運(yùn)行完成b 非搶占優(yōu)先權(quán)調(diào)度非搶占優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間調(diào)度時(shí)間c 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度搶占時(shí)刻（其它中斷）搶占時(shí)刻（其它中斷）b 立即搶占優(yōu)先權(quán)調(diào)度立即搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度時(shí)鐘中斷到達(dá)時(shí)時(shí)鐘中斷到達(dá)時(shí)調(diào)度時(shí)間調(diào)度時(shí)間調(diào)度時(shí)間調(diào)度時(shí)間v 1.1.最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDFEDF（earliest deadline first)earliest deadline first)算算法法 根據(jù)任務(wù)的截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)根

15、據(jù)任務(wù)的截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí) 截止時(shí)間越早，優(yōu)先級(jí)越高截止時(shí)間越早，優(yōu)先級(jí)越高 可以是搶占式或非搶占式可以是搶占式或非搶占式1342134212 34t開(kāi)始截止時(shí)間開(kāi)始截止時(shí)間任務(wù)到達(dá)任務(wù)到達(dá)任務(wù)執(zhí)行任務(wù)執(zhí)行圖圖37 EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式v 松弛度：松弛度： 若若A A進(jìn)程進(jìn)程需在需在200ms200ms時(shí)完成，其本身運(yùn)行需要時(shí)完成，其本身運(yùn)行需要100ms100ms，當(dāng)，當(dāng)前時(shí)刻是前時(shí)刻是10ms10ms，則，則A A的松弛度為：的松弛度為：20020010010010109090 主要用于可搶占的調(diào)度方式中主要用于可搶占的調(diào)度方式中 例：例：A1A2A3

16、A4A5A6A7A8B1B2B3020406080 100120 140160t圖圖38 A/B任務(wù)每次必須完成的時(shí)間任務(wù)每次必須完成的時(shí)間A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8v 1.1.緊密耦合緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 緊密耦合緊密耦合 共享共享RAMRAM和和I/OI/O 高速總線和交叉開(kāi)關(guān)連接高速總線和交叉開(kāi)關(guān)連接 松弛耦合松弛耦合 獨(dú)立獨(dú)立RAMRAM和和I/OI/O 通道和通信線路連接通道和通信線路連接v 2.2.對(duì)稱(chēng)多處理

17、器系統(tǒng)和非對(duì)稱(chēng)多處理器系統(tǒng)對(duì)稱(chēng)多處理器系統(tǒng)和非對(duì)稱(chēng)多處理器系統(tǒng) 處理器是否結(jié)構(gòu)相同處理器是否結(jié)構(gòu)相同v 1.1.SMPSMP中進(jìn)程分配方式中進(jìn)程分配方式 靜態(tài)分配靜態(tài)分配 動(dòng)態(tài)分配動(dòng)態(tài)分配 可防止系統(tǒng)中多個(gè)處理器忙閑不均可防止系統(tǒng)中多個(gè)處理器忙閑不均v 2.2.非非SMPSMP中進(jìn)程分配方式中進(jìn)程分配方式 進(jìn)程調(diào)度在主處理器上執(zhí)行進(jìn)程調(diào)度在主處理器上執(zhí)行 有潛在的不可靠性有潛在的不可靠性 v 1.1.自調(diào)度自調(diào)度 各個(gè)處理機(jī)自行在就緒隊(duì)列中取任務(wù)。各個(gè)處理機(jī)自行在就緒隊(duì)列中取任務(wù)。 特點(diǎn)；簡(jiǎn)單，分布式調(diào)度，調(diào)度算法可采用特點(diǎn)；簡(jiǎn)單，分布式調(diào)度，調(diào)度算法可采用前述方法，多個(gè)前述方法，多個(gè)CPUC

18、PU利用率都不錯(cuò)（不會(huì)閑）利用率都不錯(cuò)（不會(huì)閑） 但：但： 瓶頸問(wèn)題，（單隊(duì)列）瓶頸問(wèn)題，（單隊(duì)列） 低效性；（需拷貝現(xiàn)場(chǎng)）低效性；（需拷貝現(xiàn)場(chǎng)） 線程切換頻繁（當(dāng)線程合作時(shí)線程切換頻繁（當(dāng)線程合作時(shí), ,各線程并各線程并行的條件不容易滿足）行的條件不容易滿足） v 優(yōu)點(diǎn)：優(yōu)點(diǎn)：（1 1）對(duì)相互合作的進(jìn)（線）程組調(diào)度，可以減小切換，）對(duì)相互合作的進(jìn)（線）程組調(diào)度，可以減小切換，減小系統(tǒng)開(kāi)銷(xiāo)。減小系統(tǒng)開(kāi)銷(xiāo)。（2 2）每次分配一組）每次分配一組CPUCPU，減少了調(diào)度頻率。，減少了調(diào)度頻率。v 分配時(shí)間分配時(shí)間（1 1）面向程序）面向程序（2 2）面向線程：使處理機(jī)利用率更高。）面向線程：使處理機(jī)

19、利用率更高。 應(yīng)用程序應(yīng)用程序A應(yīng)用程應(yīng)用程序序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時(shí)間時(shí)間1/21/2浪費(fèi)浪費(fèi)37.5%應(yīng)用程序應(yīng)用程序A應(yīng)用程應(yīng)用程序序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時(shí)間時(shí)間4/51/5浪費(fèi)浪費(fèi)15%v 引入：多處理機(jī)系統(tǒng)，每個(gè)處理已不再屬寶貴資源。引入：多處理機(jī)系統(tǒng)，每個(gè)處理已不再屬寶貴資源。v 特點(diǎn)：每個(gè)進(jìn)（線）程專(zhuān)用處理機(jī)，使其切換小，特點(diǎn)：每個(gè)進(jìn)（線）程專(zhuān)用處理機(jī)，使其切換小，提高效率。提高效率。v 主要用于大型計(jì)算，

20、實(shí)時(shí)系統(tǒng)主要用于大型計(jì)算，實(shí)時(shí)系統(tǒng)v 3 3.5.5.1.1產(chǎn)生死鎖的原因。產(chǎn)生死鎖的原因。v 一、競(jìng)爭(zhēng)資源引起死鎖。一、競(jìng)爭(zhēng)資源引起死鎖。1 1 可剝奪（可剝奪（CPUCPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源帶機(jī)）資源2 2 競(jìng)爭(zhēng)非剝奪性資源競(jìng)爭(zhēng)非剝奪性資源可造成死鎖可造成死鎖 p1p2R1R2v 3 3競(jìng)爭(zhēng)臨時(shí)性資源競(jìng)爭(zhēng)臨時(shí)性資源 臨時(shí)性資源是指由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用臨時(shí)性資源是指由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一段時(shí)間后便無(wú)用的資源。一段時(shí)間后便無(wú)用的資源。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)

21、P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4v 1 1互斥條件（資源的臨界性）互斥條件（資源的臨界性）v 2 2請(qǐng)求和保持條件請(qǐng)求和保持條件v 3 3不剝奪條件不剝奪條件v 4 4環(huán)路等待環(huán)路等待v 1 1預(yù)防；破壞預(yù)防；破壞4 4個(gè)條件之一：有效，使資源個(gè)條件之一：有效，使資源利用率低。利用率低。v 2 2避免：防止進(jìn)入不安全態(tài)。避免：防止進(jìn)入不安全態(tài)。v 3 3檢測(cè)：檢測(cè)到死鎖再清除。檢測(cè)：檢測(cè)到死鎖再清除。v 4 4解除：與解除：與“檢檢”配套。配套。v 3.6.1 3.6.1 死鎖預(yù)防死鎖預(yù)防 一、互斥條件是資源固有屬性，不能避免。一、互斥條件是資源固有

22、屬性，不能避免。 二、摒棄請(qǐng)求和保持條件二、摒棄請(qǐng)求和保持條件全分配，全釋放（全分配，全釋放（ANDAND）缺點(diǎn)：（缺點(diǎn)：（1 1）延遲進(jìn)程運(yùn)行）延遲進(jìn)程運(yùn)行（2 2）資源嚴(yán)重浪費(fèi)）資源嚴(yán)重浪費(fèi) 三、摒棄三、摒棄“不剝奪不剝奪”條件條件增加系統(tǒng)開(kāi)銷(xiāo)，且進(jìn)程前段工作可能失效。增加系統(tǒng)開(kāi)銷(xiāo)，且進(jìn)程前段工作可能失效。v 3.6.1 3.6.1 死鎖預(yù)防死鎖預(yù)防 四、摒棄四、摒棄“環(huán)路環(huán)路”條件條件有序資源分配法：為資源編號(hào)，申請(qǐng)時(shí)需按編號(hào)進(jìn)有序資源分配法：為資源編號(hào)，申請(qǐng)時(shí)需按編號(hào)進(jìn)行。行。缺點(diǎn)：缺點(diǎn)：（1 1）新增資源不便，（原序號(hào)已排定）新增資源不便，（原序號(hào)已排定）（2 2）用戶不自由）用戶不

23、自由（3 3）資源與進(jìn)程使用順序不同造成浪費(fèi)）資源與進(jìn)程使用順序不同造成浪費(fèi)v在在“避免死鎖避免死鎖”方法中的判斷條件方法中的判斷條件 v1. 1. 安全狀態(tài)安全狀態(tài)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。能找到安全序列的狀態(tài)為安全狀態(tài)。v2.2.安全狀態(tài)例安全狀態(tài)例進(jìn)程進(jìn)程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 v3 3安全安全不安全的轉(zhuǎn)換不安全的轉(zhuǎn)換 上例中，若上例中，若P3P3再申請(qǐng)一臺(tái)，則不安

24、全再申請(qǐng)一臺(tái)，則不安全 進(jìn)程進(jìn)程最大需求最大需求已分配已分配可用可用P11052P242P393v 1 1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) availablejavailablej=k: =k: 系統(tǒng)現(xiàn)有系統(tǒng)現(xiàn)有RjRj類(lèi)資源類(lèi)資源k k個(gè)；個(gè)； maxi,jmaxi,j=k: =k: 進(jìn)程進(jìn)程i i需要需要RjRj的最大數(shù)的最大數(shù)k k個(gè)；個(gè)； alloci,jalloci,j=k: =k: 進(jìn)程進(jìn)程i i已得到已得到RjRj類(lèi)資源類(lèi)資源k k個(gè)；個(gè)； needi,jneedi,j=k:=k: 進(jìn)程進(jìn)程i i需要需要RjRj類(lèi)資源類(lèi)資源k k個(gè)個(gè) 有：有：needi,j= maxi,jneedi,j= ma

25、xi,j alloci,jalloci,j requestirequesti進(jìn)程進(jìn)程i i請(qǐng)求資源數(shù)請(qǐng)求資源數(shù) workiworki：進(jìn)程：進(jìn)程i i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)）執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)） finishifinishi ：布爾量，表進(jìn)程：布爾量，表進(jìn)程i i能否順序完成。能否順序完成。 v 2 2銀行家算法銀行家算法 reqi=needierrorreqi=availiblockavail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinis

26、hi=.T. Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2(2 3 0) p1 3 2 2 2 0 0(3 0 2) 1 2 2(0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 1T0時(shí)刻的資源分配表時(shí)刻的資源分配表Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2 1