計算機操作系統(tǒng)之處理機調(diào)度與死鎖.

1、西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.1 處理機調(diào)度的基本概念3.13.1高、中、低三級調(diào)度高、中、低三級調(diào)度 1 1、高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）、高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCBPCB等，插入就緒隊列。等，插入就緒隊列。一般用于批處理系統(tǒng)，分一般用于批處理系統(tǒng)，分/ /實時系統(tǒng)一般直接入內(nèi)存，無此實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。環(huán)節(jié)。 調(diào)度特性調(diào)度特性1.1.接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）太多太多 周轉(zhuǎn)時間周轉(zhuǎn)時間T T長長太少太少 系統(tǒng)效率低系統(tǒng)效率低2.2.接納策略：即采用何種調(diào)度

2、算法：接納策略：即采用何種調(diào)度算法：FCFSFCFS、短作業(yè)優(yōu)先等、短作業(yè)優(yōu)先等西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月處理機調(diào)度的基本概念（2） 2 2、低級調(diào)度（進程調(diào)度，短程調(diào)度）、低級調(diào)度（進程調(diào)度，短程調(diào)度） 主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派處理機。）分派處理機。 1.1.非搶占方式：非搶占方式： 簡單，實時性差簡單，實時性差 ( (如如win31)win31) 2. 2.搶占方式搶占方式 （1 1）時間片原則）時間片原則 （2 2）優(yōu)先權(quán)原則）優(yōu)先權(quán)原則 （3 3）短作業(yè)優(yōu)先原則。）短作業(yè)優(yōu)先原則。 運行頻率：低運行頻率：低

3、中中 高高。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月問？三種調(diào)度被引發(fā)的事件？三種調(diào)度被引發(fā)的事件？事件的表現(xiàn)方式？事件的表現(xiàn)方式？西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.1.2調(diào)度的隊列模型一、僅有進程調(diào)度的隊列模型一、僅有進程調(diào)度的隊列模型就緒隊列就緒隊列CPU阻塞隊列阻塞隊列交互用戶交互用戶時間片完時間片完進程調(diào)度進程調(diào)度進程完成進程完成等待事件等待事件事件出現(xiàn)事件出現(xiàn)西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.1.2調(diào)度的隊列模型二、具有高二、具有高/ /低級模型低級模型進程進程完成完成后備隊列后備隊列作業(yè)調(diào)度作業(yè)調(diào)度就緒隊列就緒隊列CPU阻塞隊列阻塞隊列時間片完

4、時間片完進程調(diào)度進程調(diào)度等待事件等待事件1事件事件1出現(xiàn)出現(xiàn)阻塞隊列阻塞隊列等待事件等待事件2事件事件2出現(xiàn)出現(xiàn)西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月三、具有三級調(diào)度后備隊列后備隊列就緒隊列就緒隊列CPU就緒、掛起隊列就緒、掛起隊列時間片完時間片完進程調(diào)度進程調(diào)度進程進程完成完成阻塞、掛起隊列阻塞、掛起隊列事件出現(xiàn)事件出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度阻塞隊列阻塞隊列等待事件等待事件掛起掛起事件出現(xiàn)事件出現(xiàn)中級調(diào)度中級調(diào)度交互型作業(yè)交互型作業(yè)西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.1.3選擇調(diào)度方式和算法的若干準則 一、面向用戶的準則一、面向用戶的準則1 1周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）周

5、轉(zhuǎn)時間短（常用于批處理系統(tǒng)）概念：作業(yè)從提交概念：作業(yè)從提交 完成的時間完成的時間. .分為：分為：（1 1）駐外等待調(diào)度時間）駐外等待調(diào)度時間（2 2）駐內(nèi)等待調(diào)度時間）駐內(nèi)等待調(diào)度時間（3 3）執(zhí)行時間）執(zhí)行時間（4 4）阻塞時間）阻塞時間西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月一、面向用戶的準則一、面向用戶的準則平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間平均帶權(quán)平均帶權(quán) 可見帶權(quán)可見帶權(quán)w w越小越好越小越好,Ts,Ts為實際服務(wù)時間。為實際服務(wù)時間。3.1.3選擇調(diào)度方式和算法的若干準則 11niiTnT11nisiTTnW西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月一、面向用戶的準則一、面向用

6、戶的準則2 2響應(yīng)時間快：（對交互性作業(yè)）響應(yīng)時間快：（對交互性作業(yè)）概念：鍵盤提交請求到首次響應(yīng)時間概念：鍵盤提交請求到首次響應(yīng)時間（1 1）輸入傳送時間）輸入傳送時間（2 2）處理時間）處理時間（3 3）響應(yīng)傳送時間）響應(yīng)傳送時間3 3截止時間的保證（特別于實時系統(tǒng)）截止時間的保證（特別于實時系統(tǒng)）4 4優(yōu)先權(quán)準則：（即需要搶占調(diào)度）優(yōu)先權(quán)準則：（即需要搶占調(diào)度）3.1.3選擇調(diào)度方式和算法的若干準則 西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月二、面向系統(tǒng)的準則二、面向系統(tǒng)的準則1 1吞吐量高（特別于批處理）：單位時間完成吞吐量高（特別于批處理）：單位時間完成作業(yè)數(shù)作業(yè)數(shù)2 2處理機利

7、用率好：（因處理機利用率好：（因CPUCPU貴，特別于大中貴，特別于大中型多用戶系統(tǒng)）型多用戶系統(tǒng)）3 3各類資源的平衡利用。（？折算標準）各類資源的平衡利用。（？折算標準）3.1.3選擇調(diào)度方式和算法的若干準則 西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.2調(diào)度算法是一個資源分配問題 3.2.13.2.1先來先服務(wù)和短作業(yè)（進程）優(yōu)先調(diào)度算先來先服務(wù)和短作業(yè)（進程）優(yōu)先調(diào)度算法法 1.FCFS1.FCFS特點：簡單，有利于長作業(yè)特點：簡單，有利于長作業(yè) 即即CPUCPU繁忙性作業(yè)繁忙性作業(yè)2.2.短作業(yè)進程優(yōu)先調(diào)度算法：短作業(yè)進程優(yōu)先調(diào)度算法：SJ(P)FSJ(P)F提高了平均周轉(zhuǎn)時間

8、和平均帶權(quán)周轉(zhuǎn)時間（從而提高了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）提高了系統(tǒng)吞吐量）特點：對長作業(yè)不利，有可能得不到服務(wù)（饑餓）特點：對長作業(yè)不利，有可能得不到服務(wù)（饑餓）估計時間不易確定估計時間不易確定西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月 例進程名到達時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月圖3.4FCFS和SJF比較進程名進程名 A B C D E平均平均到達時間到達時間 0 1 2 3 4服務(wù)時間服

9、務(wù)時間 4 3 5 2 4FCFS完成時間完成時間 4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間 4 6 10 11 149帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 2 2 5.5 3.52.8SJF完成時間完成時間 4 9 18 6 13周轉(zhuǎn)時間周轉(zhuǎn)時間 4 8 16 3 98帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 2.67 3.1 1.5 2.252.1西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.1.優(yōu)先權(quán)調(diào)度算法類型優(yōu)先權(quán)調(diào)度算法類型非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法，實時性更好。搶占式優(yōu)先權(quán)算法，實時性更好。2.2.優(yōu)先權(quán)類型：優(yōu)先權(quán)類型：1 1靜態(tài)優(yōu)先權(quán)：

10、靜態(tài)優(yōu)先權(quán)：進程優(yōu)先權(quán)在整個運行期不變。進程優(yōu)先權(quán)在整個運行期不變。確定優(yōu)先權(quán)依據(jù)確定優(yōu)先權(quán)依據(jù)（1 1）進程類型）進程類型（2 2）進程對資源的需求；）進程對資源的需求；（3 3）根據(jù)用戶需求。）根據(jù)用戶需求。特點：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度。特點：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法(2)2 2動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)：如：優(yōu)先權(quán)隨執(zhí)行時間而下降，隨等待時間而升高。如：優(yōu)先權(quán)隨執(zhí)行時間而下降，隨等待時間而升高。響應(yīng)比響應(yīng)比RpRp= =（等待時間服務(wù)時間）（等待時間服務(wù)時間）/ /服務(wù)時間服務(wù)時間 作為優(yōu)

11、先權(quán)作為優(yōu)先權(quán)優(yōu)點：長短兼顧優(yōu)點：長短兼顧 缺點：需計算缺點：需計算RpRp3.3.高響應(yīng)比優(yōu)先算法：高響應(yīng)比優(yōu)先算法：特點：特點：響應(yīng)比響應(yīng)比RpRp= =（tw+tstw+ts）/ts/ts（1 1）短作業(yè)）短作業(yè)R RP P大。大。（2 2）tsts（要求服務(wù)時間）相同的進程間相當于（要求服務(wù)時間）相同的進程間相當于FCFSFCFS。（3 3）長作業(yè)等待一段時間仍能得到服務(wù)。）長作業(yè)等待一段時間仍能得到服務(wù)。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.1.時間片輪轉(zhuǎn)時間片輪轉(zhuǎn)時間片大小的確定時間片大小的確定太大：退化為太大：退化為FCFSFCFS；

12、太?。合到y(tǒng)開銷過大太?。合到y(tǒng)開銷過大系統(tǒng)對響應(yīng)時間的要求；系統(tǒng)對響應(yīng)時間的要求；T=nqT=nq就緒隊列中進程的數(shù)目；就緒隊列中進程的數(shù)目；系統(tǒng)的處理能力：（應(yīng)保證一個時間片處理完常用系統(tǒng)的處理能力：（應(yīng)保證一個時間片處理完常用命令）命令）西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法2.2.多級反饋隊列調(diào)度多級反饋隊列調(diào)度特點：長、短作業(yè)兼顧，有較好的響應(yīng)時間特點：長、短作業(yè)兼顧，有較好的響應(yīng)時間（1 1）短作業(yè)一次完成；）短作業(yè)一次完成；（2 2）中型作業(yè)周轉(zhuǎn)時間不長；）中型作業(yè)周轉(zhuǎn)時間不長；（3 3）大型作業(yè)不會長期不處理。）大型作業(yè)不會長期不處理。西華

13、大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月就緒隊列就緒隊列1 1至至CPUS1就緒隊列就緒隊列2 2S2至至CPU就緒隊列就緒隊列3 3S3至至CPU就緒隊列就緒隊列n nSn至至CPU時間片：時間片：S1S2S3圖圖35多級隊列反饋調(diào)度算法多級隊列反饋調(diào)度算法西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3 3.3.1.3.1實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件1 1提供必要的調(diào)度信息提供必要的調(diào)度信息（1 1）就緒時間；）就緒時間；（2 2）開始）開始/ /完成截止時間；完成截止時間；（3 3）處理時間；）處理時間；（4 4）資源要求；）資源要求；（5 5）優(yōu)先級；）優(yōu)先級；2 2

14、系統(tǒng)處理能力強系統(tǒng)處理能力強3.3實時調(diào)度NPCPCmiiimiii111Ci為處理時間，為處理時間，Pi為周期時間（基于周期性實時任務(wù)）為周期時間（基于周期性實時任務(wù)）西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3 3.3.1.3.1實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件3.3.采用搶占調(diào)度方式采用搶占調(diào)度方式剝奪方式：一般都采用此剝奪方式：一般都采用此非剝奪方式（實現(xiàn)簡單）：一般應(yīng)使實時任務(wù)非剝奪方式（實現(xiàn)簡單）：一般應(yīng)使實時任務(wù)較小，以及時放棄較小，以及時放棄CPUCPU。4.4.具有快速切換機制具有快速切換機制具有快速響應(yīng)外部中斷能力。具有快速響應(yīng)外部中斷能力?？焖偃蝿?wù)分派快速

15、任務(wù)分派3.3實時調(diào)度西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.3.2實時調(diào)度算法的分類1 1、非搶占式調(diào)度算法、非搶占式調(diào)度算法時間片輪轉(zhuǎn)時間片輪轉(zhuǎn) 秒級秒級非搶占優(yōu)先權(quán)（協(xié)同）非搶占優(yōu)先權(quán)（協(xié)同） 秒毫秒級秒毫秒級2 2、搶占式調(diào)度算法、搶占式調(diào)度算法時鐘中斷搶占優(yōu)先權(quán)時鐘中斷搶占優(yōu)先權(quán) 毫秒級毫秒級基于搶占點搶占基于搶占點搶占立即搶占立即搶占immediate preemption immediate preemption 毫秒微秒級毫秒微秒級只要不在臨界區(qū)即搶占（中斷引發(fā)）只要不在臨界區(qū)即搶占（中斷引發(fā)）進程1進程2進程n實時進程調(diào)度時間調(diào)度時間實時進程要求調(diào)度實時進程要求調(diào)度

16、調(diào)度實時進程運行調(diào)度實時進程運行a 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度當前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度當前進程運行完成當前進程運行完成b 非搶占優(yōu)先權(quán)調(diào)度非搶占優(yōu)先權(quán)調(diào)度調(diào)度時間調(diào)度時間c 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度搶占時刻（其它中斷）搶占時刻（其它中斷）b 立即搶占優(yōu)先權(quán)調(diào)度立即搶占優(yōu)先權(quán)調(diào)度當前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度時鐘中斷到達時時鐘中斷到達時調(diào)度時間調(diào)度時間調(diào)度時間調(diào)度時間西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.3.3常用的幾種實時調(diào)度算法1.1.最早截止時間優(yōu)

17、先最早截止時間優(yōu)先EDFEDF（earliest deadline earliest deadline first)first)算法算法根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級截止時間越早，優(yōu)先級越高截止時間越早，優(yōu)先級越高可以是搶占式或非搶占式可以是搶占式或非搶占式西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月最早截止時間優(yōu)先EDF例1342134212 34t開始截止時間開始截止時間任務(wù)到達任務(wù)到達任務(wù)執(zhí)行任務(wù)執(zhí)行圖圖37 EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月2. 最低松弛度優(yōu)先LLF算法 松弛度：

18、松弛度： 若若A A進程進程需在需在200ms200ms時完成，其本身運行需要時完成，其本身運行需要100ms100ms，當前時刻是當前時刻是10ms10ms，則，則A A的松弛度為：的松弛度為：20020010010010109090 主要用于可搶占的調(diào)度方式中主要用于可搶占的調(diào)度方式中 例：例：A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t圖圖38 A/B任務(wù)每次必須完成的時間任務(wù)每次必須完成的時間西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月最低松弛度優(yōu)先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050

19、607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.4多處理機系統(tǒng)中的調(diào)度1.1.緊密耦合緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS緊密耦合緊密耦合共享共享RAMRAM和和I/OI/O高速總線和交叉開關(guān)連接高速總線和交叉開關(guān)連接松弛耦合松弛耦合獨立獨立RAMRAM和和I/OI/O通道和通信線路連接通道和通信線路連接2.2.對稱多處理器系統(tǒng)和非對稱多處理器系對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)統(tǒng)處理器是否結(jié)構(gòu)相同處理器是否結(jié)構(gòu)相同西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.4.2進程分

20、配方式1.1.SMPSMP中進程分配方式中進程分配方式靜態(tài)分配靜態(tài)分配動態(tài)分配動態(tài)分配可防止系統(tǒng)中多個處理器忙閑不均可防止系統(tǒng)中多個處理器忙閑不均2.2.非非SMPSMP中進程分配方式中進程分配方式進程調(diào)度在主處理器上執(zhí)行進程調(diào)度在主處理器上執(zhí)行有潛在的不可靠性有潛在的不可靠性西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.4.3進程（線程）調(diào)度方式1.1.自調(diào)度自調(diào)度各個處理機自行在就緒隊列中取任務(wù)。各個處理機自行在就緒隊列中取任務(wù)。特點；簡單，分布式調(diào)度，調(diào)度算法可采用前述方特點；簡單，分布式調(diào)度，調(diào)度算法可采用前述方法，多個法，多個CPUCPU利用率都不錯（不會閑）利用率都不錯（不會閑

21、）但：但：瓶頸問題，（單隊列）瓶頸問題，（單隊列）低效性；（需拷貝現(xiàn)場）低效性；（需拷貝現(xiàn)場）線程切換頻繁（當線程合作時線程切換頻繁（當線程合作時, ,各線程并行的條各線程并行的條件不容易滿足）件不容易滿足） 西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月2.成組調(diào)度 優(yōu)點：優(yōu)點：（1 1）對相互合作的進（線）程組調(diào)度，可以減）對相互合作的進（線）程組調(diào)度，可以減小切換，減小系統(tǒng)開銷。小切換，減小系統(tǒng)開銷。（2 2）每次分配一組）每次分配一組CPUCPU，減少了調(diào)度頻率。，減少了調(diào)度頻率。分配時間分配時間（1 1）面向程序）面向程序（2 2）面向線程：使處理機利用率更高。）面向線程：使處理機利

22、用率更高。 西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月2.成組調(diào)度應(yīng)用程序應(yīng)用程序A應(yīng)用程序應(yīng)用程序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時間時間1/21/2浪費浪費37.5%應(yīng)用程序應(yīng)用程序A應(yīng)用程序應(yīng)用程序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時間時間4/51/5浪費浪費15%西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.專用處理機分配 引入：多處理機系統(tǒng)，每個處理已不再屬寶貴引入：多處理機系統(tǒng)，每個處理已不再屬寶貴資源。資源。特點：每個進（線

23、）程專用處理機，使其切換特點：每個進（線）程專用處理機，使其切換小，提高效率。小，提高效率。主要用于大型計算，實時系統(tǒng)主要用于大型計算，實時系統(tǒng)西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.5產(chǎn)生死鎖的原因和必要條件3 3.5.5.1.1產(chǎn)生死鎖的原因。產(chǎn)生死鎖的原因。一、競爭資源引起死鎖。一、競爭資源引起死鎖。1 1可剝奪（可剝奪（CPUCPU、內(nèi)存，）和非剝奪性（打印機，、內(nèi)存，）和非剝奪性（打印機，磁帶機）資源磁帶機）資源2 2競爭非剝奪性資源競爭非剝奪性資源可造成死鎖可造成死鎖 p1p2R1R2西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.5產(chǎn)生死鎖的原因和必要條件3 3競爭臨

24、時性資源競爭臨時性資源臨時性資源是指由一個進程產(chǎn)生，被另一個進程臨時性資源是指由一個進程產(chǎn)生，被另一個進程使用一段時間后便無用的資源。使用一段時間后便無用的資源。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月二、進程推進順序不當引起死鎖。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.5.2 產(chǎn)生死鎖的必要條件1 1互斥條件（資源的臨界性）互斥條件（資源的臨界性）2 2請求和保持條件請求和保持條件3 3不剝奪條件不剝奪條件4 4環(huán)路等待

25、環(huán)路等待西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.5.3處理死鎖的基本方法 1 1預(yù)防；破壞預(yù)防；破壞4 4個條件之一：有效，個條件之一：有效，使資源利用率低。使資源利用率低。2 2避免：防止進入不安全態(tài)。避免：防止進入不安全態(tài)。3 3檢測：檢測到死鎖再清除。檢測：檢測到死鎖再清除。4 4解除：與解除：與“檢檢”配套。配套。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6 死鎖預(yù)防和避免 3.6.1 3.6.1 死鎖預(yù)防死鎖預(yù)防 一、互斥條件是資源固有屬性，不能避免。一、互斥條件是資源固有屬性，不能避免。二、摒棄請求和保持條件二、摒棄請求和保持條件全分配，全釋放（全分配，全釋放（A

26、NDAND）缺點：（缺點：（1 1）延遲進程運行）延遲進程運行（2 2）資源嚴重浪費）資源嚴重浪費三、摒棄三、摒棄“不剝奪不剝奪”條件條件增加系統(tǒng)開銷，且進程前段工作可能失效。增加系統(tǒng)開銷，且進程前段工作可能失效。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6 死鎖預(yù)防和避免 3.6.1 3.6.1 死鎖預(yù)防死鎖預(yù)防 四、摒棄四、摒棄“環(huán)路環(huán)路”條件條件有序資源分配法：為資源編號，申請時需按編號進有序資源分配法：為資源編號，申請時需按編號進行。行。缺點：缺點：（1 1）新增資源不便，（原序號已排定）新增資源不便，（原序號已排定）（2 2）用戶不自由）用戶不自由（3 3）資源與進程使用順序

27、不同造成浪費）資源與進程使用順序不同造成浪費西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6.2 系統(tǒng)的安全狀態(tài)在在“避免死鎖避免死鎖”方法中的判斷條件方法中的判斷條件 1. 1. 安全狀態(tài)安全狀態(tài)按某種順序并發(fā)進程都能達到獲得最大資源而順按某種順序并發(fā)進程都能達到獲得最大資源而順序完成的序列為安全序列。序完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。能找到安全序列的狀態(tài)為安全狀態(tài)。西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6.2 系統(tǒng)的安全狀態(tài)（2）2.2.安全狀態(tài)例安全狀態(tài)例進程進程最大需最大需求求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2

28、p2p1p1p3 p3 西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6.2 系統(tǒng)的安全狀態(tài)（3）3 3安全安全不安全的轉(zhuǎn)換不安全的轉(zhuǎn)換 上例中，若上例中，若P3P3再申請一臺，則不安全再申請一臺，則不安全 進程進程最大需最大需求求已分配已分配 可用可用P11052P242P393西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6.3利用銀行家算法避免死鎖 1 1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)availablejavailablej=k: =k: 系統(tǒng)現(xiàn)有系統(tǒng)現(xiàn)有RjRj類資源類資源k k個；個；maxi,jmaxi,j=k: =k: 進程進程i i需要需要RjRj的最大數(shù)的最大數(shù)k k個；個；all

29、oci,jalloci,j=k: =k: 進程進程i i已得到已得到RjRj類資源類資源k k個；個； needi,jneedi,j=k:=k:進程進程i i需要需要RjRj類資源類資源k k個個有：有：needi,j= maxi,jneedi,j= maxi,j alloci,jalloci,j requestirequesti 進程進程i i請求資源數(shù)請求資源數(shù)workiworki：進程：進程i i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)）執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)）finishifinishi ：布爾量，表進程：布爾量，表進程i i能否順序完成。能否順序完成。 西華大學(xué)數(shù)學(xué)與計算機學(xué)院

30、 蔣明禮2007年1月3.6.3利用銀行家算法避免死鎖 2 2銀行家算法銀行家算法 reqi=needierrorreqi=availiblock西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月3.6.3利用銀行家算法避免死鎖 avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月4實例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3

31、 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時刻的資源分配表時刻的資源分配表西華大學(xué)數(shù)學(xué)與計算機學(xué)院 蔣明禮2007年1月4實例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 10 4 7 true p