操作系統(tǒng)課件5_2

1、第五章第五章 死鎖與饑餓死鎖與饑餓l5.1 死鎖的概念死鎖的概念 5.2 死鎖的類型死鎖的類型l5.3 死鎖的條件死鎖的條件 5.4 死鎖的處理死鎖的處理l5.5 資源分配圖資源分配圖 5.6 死鎖的預(yù)防死鎖的預(yù)防l5.7 死鎖的避免死鎖的避免 5.8 死鎖的發(fā)現(xiàn)死鎖的發(fā)現(xiàn)l5.9 死鎖的恢復(fù)死鎖的恢復(fù) 5.10 鴕鳥的算法鴕鳥的算法l5.11 有關(guān)問題的討論有關(guān)問題的討論l5.12 饑餓與活鎖饑餓與活鎖 5.13 死鎖與饑餓的例死鎖與饑餓的例子子15.7 死鎖避免死鎖避免l預(yù)防死鎖的方法施加一些較強(qiáng)的限制條件預(yù)防死鎖的方法施加一些較強(qiáng)的限制條件使之在系統(tǒng)中不出現(xiàn)死鎖使之在系統(tǒng)中不出現(xiàn)死鎖l為

2、提高系統(tǒng)資源的利用率，萬一死鎖有可為提高系統(tǒng)資源的利用率，萬一死鎖有可能出現(xiàn)時，應(yīng)避免發(fā)生，著名的算法為銀能出現(xiàn)時，應(yīng)避免發(fā)生，著名的算法為銀行家算法行家算法l避免死鎖的方法，施加的條件較弱，有可避免死鎖的方法，施加的條件較弱，有可能獲得較滿意的系統(tǒng)性能能獲得較滿意的系統(tǒng)性能l該方法把系統(tǒng)分為安全和不安全狀態(tài)該方法把系統(tǒng)分為安全和不安全狀態(tài)l只要系統(tǒng)始終處于安全狀態(tài)便可避免死鎖的只要系統(tǒng)始終處于安全狀態(tài)便可避免死鎖的發(fā)生發(fā)生25.7 死鎖避免死鎖避免l5.7.1 安全狀態(tài)與安全進(jìn)程序列安全狀態(tài)與安全進(jìn)程序列 l5.7.2 銀行家算法銀行家算法(bankers Algorithm)35.7.1

3、安全狀態(tài)與安全進(jìn)程序列安全狀態(tài)與安全進(jìn)程序列l(wèi)安全狀態(tài)安全狀態(tài)l系統(tǒng)處于安全狀態(tài)是指系統(tǒng)中的所有進(jìn)程能夠按照某系統(tǒng)處于安全狀態(tài)是指系統(tǒng)中的所有進(jìn)程能夠按照某一種次序依次地進(jìn)行完一種次序依次地進(jìn)行完l安全狀態(tài)形式化定義安全狀態(tài)形式化定義 ：l如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全進(jìn)程序列如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全進(jìn)程序列，則稱系統(tǒng)處于安全狀態(tài)。，則稱系統(tǒng)處于安全狀態(tài)。l進(jìn)程序列進(jìn)程序列 是安全的是安全的, 則對每個進(jìn)則對每個進(jìn)程程pi(1in), 它尚需要的資源數(shù)不超過系統(tǒng)當(dāng)前它尚需要的資源數(shù)不超過系統(tǒng)當(dāng)前剩余資源數(shù)與所有進(jìn)程剩余資源數(shù)與所有進(jìn)程pj(ji)當(dāng)前占有資源數(shù)之當(dāng)前占有資

4、源數(shù)之和和. l若系統(tǒng)中不存在這樣一個安全序列，則稱系統(tǒng)處若系統(tǒng)中不存在這樣一個安全序列，則稱系統(tǒng)處于于不安全狀態(tài)不安全狀態(tài)。45.7.1 安全狀態(tài)與安全進(jìn)程序列安全狀態(tài)與安全進(jìn)程序列l(wèi)圖圖5-4給出了安全狀態(tài)、不安全狀態(tài)、死鎖給出了安全狀態(tài)、不安全狀態(tài)、死鎖狀態(tài)之間的關(guān)系：狀態(tài)之間的關(guān)系：5安全狀態(tài)之例安全狀態(tài)之例 l設(shè)系統(tǒng)有三個進(jìn)程設(shè)系統(tǒng)有三個進(jìn)程P1、P2、P3，共有，共有12臺磁帶機(jī)。在臺磁帶機(jī)。在T0時刻資源狀況如下表：時刻資源狀況如下表：l經(jīng)分析，在經(jīng)分析，在T0時刻系統(tǒng)是安全的，存在一時刻系統(tǒng)是安全的，存在一個序列個序列，按此順序每個進(jìn)程可，按此順序每個進(jìn)程可以順利完成以順利完成

5、 6由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 l如不按照安全序列分配資源，系統(tǒng)可能會由安全狀態(tài)向不如不按照安全序列分配資源，系統(tǒng)可能會由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換，如在安全狀態(tài)轉(zhuǎn)換，如在T0時刻后，時刻后，P3請求請求1臺，系統(tǒng)分配給臺，系統(tǒng)分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)，則系統(tǒng)進(jìn)入不安全狀態(tài)進(jìn)程進(jìn)程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3 7銀行家算法思想銀行家算法思想 l將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用l當(dāng)用戶對資金的最大申請量不超過現(xiàn)存資當(dāng)用戶對資金的最大申請量不超過現(xiàn)存資金時可接納一個

6、新客戶金時可接納一個新客戶l客戶可以分期借款，但借款總數(shù)不能超過客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。最大的申請量。l銀行家對客戶的借款可推遲支付，但是能銀行家對客戶的借款可推遲支付，但是能夠使客戶在有限的時間內(nèi)得到借款夠使客戶在有限的時間內(nèi)得到借款l客戶得到所有的借款后能在有限的時間內(nèi)客戶得到所有的借款后能在有限的時間內(nèi)歸還歸還 8銀行家算法思想銀行家算法思想l有三個客戶有三個客戶A、B、C, 共享共享10個現(xiàn)金單元（設(shè)一個現(xiàn)金單元（設(shè)一個現(xiàn)金單元為一萬元），它們共需個現(xiàn)金單元為一萬元），它們共需20個現(xiàn)金單個現(xiàn)金單元元l括號外為已借款數(shù)，括號內(nèi)為要求數(shù)括號外為已借款數(shù)，括號內(nèi)為

7、要求數(shù) 9銀行家算法思想銀行家算法思想l優(yōu)點(diǎn)：優(yōu)點(diǎn)：l保證至少有一個進(jìn)程得到所需的全部資源下進(jìn)行資源保證至少有一個進(jìn)程得到所需的全部資源下進(jìn)行資源分配，避免進(jìn)程共享資源時可能產(chǎn)生的死鎖分配，避免進(jìn)程共享資源時可能產(chǎn)生的死鎖l允許資源獨(dú)占、不剝奪條件、請求和保持條件存在，允許資源獨(dú)占、不剝奪條件、請求和保持條件存在，比預(yù)防死鎖的限制條件放松了，資源利用率提高。比預(yù)防死鎖的限制條件放松了，資源利用率提高。l系統(tǒng)可滿足、也可拒絕進(jìn)程提出的資源請求系統(tǒng)可滿足、也可拒絕進(jìn)程提出的資源請求l當(dāng)一個進(jìn)程的資源請求將導(dǎo)致不安全狀態(tài)時，系統(tǒng)拒當(dāng)一個進(jìn)程的資源請求將導(dǎo)致不安全狀態(tài)時，系統(tǒng)拒絕其要求，直到該資源要求

8、不會導(dǎo)致不安全狀態(tài)時才絕其要求，直到該資源要求不會導(dǎo)致不安全狀態(tài)時才滿足此進(jìn)程的資源要求（這主要由于其它進(jìn)程釋放了滿足此進(jìn)程的資源要求（這主要由于其它進(jìn)程釋放了資源）資源）l這樣的系統(tǒng)總是處于安全狀態(tài)。這樣的系統(tǒng)總是處于安全狀態(tài)。10銀行家算法思想銀行家算法思想l缺點(diǎn)：缺點(diǎn)：l要求被分配的每類資源的總數(shù)固定不變，難要求被分配的每類資源的總數(shù)固定不變，難以做到。以做到。l要求用戶數(shù)保持不變，在多道程序設(shè)計中難要求用戶數(shù)保持不變，在多道程序設(shè)計中難以做到以做到l保證所有用戶的要求在有限的時間內(nèi)得到滿保證所有用戶的要求在有限的時間內(nèi)得到滿足，但是實(shí)時用戶要求更好的響應(yīng)足，但是實(shí)時用戶要求更好的響應(yīng)l

9、要求用戶說明最大資源要求，對用戶來說不要求用戶說明最大資源要求，對用戶來說不方便且困難方便且困難11銀行家算法銀行家算法Bankers algorithm, E.W. Dijkstra.進(jìn)程：事先申明所需資源最大量（并不分配）進(jìn)程：事先申明所需資源最大量（并不分配）系統(tǒng)：對每個可滿足的資源申請命令進(jìn)行安全性系統(tǒng)：對每個可滿足的資源申請命令進(jìn)行安全性檢查。檢查。 12銀行家算法銀行家算法l設(shè)設(shè)n為進(jìn)程總數(shù)為進(jìn)程總數(shù), m為資源類總數(shù)為資源類總數(shù)l數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):lint Availablem; 當(dāng)前各類資源中可用資源實(shí)當(dāng)前各類資源中可用資源實(shí)例的個數(shù)例的個數(shù)lAvailablej=k, 資源類

10、資源類rj當(dāng)前有當(dāng)前有k個資源實(shí)例可用，個資源實(shí)例可用，初始時初始時Available為系統(tǒng)資源總量為系統(tǒng)資源總量l int Claimn,m; 每個進(jìn)程所需各類資源的資每個進(jìn)程所需各類資源的資源實(shí)例最大量源實(shí)例最大量lint Allocationn,m; 記錄每個進(jìn)程占有各資記錄每個進(jìn)程占有各資源類中資源實(shí)例個數(shù)源類中資源實(shí)例個數(shù)l初始時初始時Allocationi,j= 013銀行家算法銀行家算法l數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):lint Needn,m; 記錄每個進(jìn)程尚需各資源類中記錄每個進(jìn)程尚需各資源類中資源實(shí)例個數(shù)資源實(shí)例個數(shù)lNeedi, j=k, 進(jìn)程進(jìn)程pi尚需資源類尚需資源類rj中中k個資

11、源實(shí)例個資源實(shí)例 l 初始時初始時Need=Claiml int Requestn,m; 記錄每個進(jìn)程當(dāng)前申請各記錄每個進(jìn)程當(dāng)前申請各資源類中資源實(shí)例個數(shù)資源類中資源實(shí)例個數(shù)lRequesti,j= k, 進(jìn)程進(jìn)程pi申請資源類申請資源類rj中中k個資源個資源實(shí)例實(shí)例14銀行家算法銀行家算法為了方便為了方便, 引入下述記法引入下述記法: 設(shè)設(shè)X,Y為下標(biāo)為下標(biāo)1到到L的一維數(shù)組的一維數(shù)組,C為常量為常量 定義定義 XY 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) j，1jL, XjYj X=Y 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) j，1jL, Xj = Yj X=C 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) j，1jL, Xj = C15資源分配算法資源分配算

12、法Pi請求資源請求資源RequestI NeedI請求超量，錯返請求超量，錯返RequestI Available不滿足，等待不滿足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全安全確認(rèn)，確認(rèn)，pi繼續(xù)繼續(xù)Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待等待FTFTTF16安全性檢測算法安全性檢測算法l為進(jìn)行安全性檢查為進(jìn)行安全性檢查, 需定

13、義數(shù)據(jù)結(jié)構(gòu)需定義數(shù)據(jù)結(jié)構(gòu)lint Workm; 記錄可用資源記錄可用資源lint Finishn; 記錄進(jìn)程是否可進(jìn)行完記錄進(jìn)程是否可進(jìn)行完17安全性檢測算法安全性檢測算法FWork:=AvailableFinish:=false有滿足條件的有滿足條件的jFinishj=falseNeedj WorkFinishj=trueWork:=Work+AllocationjT j ,finishj=trueTF安全安全不安全不安全18銀行家算法例子銀行家算法例子5-4R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 某時刻狀態(tài)某時刻狀態(tài)19銀行家算法例子銀行家算法例子5-4l存在

14、安全序列存在安全序列，處于安全狀態(tài)，處于安全狀態(tài) 20銀行家算法例子銀行家算法例子5-4l設(shè)設(shè)p1發(fā)出新申請發(fā)出新申請, Request1=(1,0,2)l檢查檢查Request1Available是否滿足是否滿足, 由于由于(1,0,2)(3,3,2), 假定分配資源假定分配資源, 系統(tǒng)狀態(tài)變化為系統(tǒng)狀態(tài)變化為 21銀行家算法例子銀行家算法例子5-4l可找到一個進(jìn)程安全序列可找到一個進(jìn)程安全序列, 系統(tǒng)實(shí)施資源分配系統(tǒng)實(shí)施資源分配l在新狀態(tài)下在新狀態(tài)下lp4發(fā)出發(fā)出Request4=(3,3,0)，不能實(shí)施資源分，不能實(shí)施資源分配配, 因?yàn)樗^了系統(tǒng)當(dāng)前的資源數(shù)量因?yàn)樗^了系統(tǒng)當(dāng)前的資源

15、數(shù)量lp0發(fā)出發(fā)出Request0=(0,2,0)，亦不能實(shí)施資源，亦不能實(shí)施資源分配分配l雖然未超過系統(tǒng)當(dāng)前的資源數(shù)量雖然未超過系統(tǒng)當(dāng)前的資源數(shù)量, 但資源分配將導(dǎo)但資源分配將導(dǎo)制一個不安全的狀態(tài)制一個不安全的狀態(tài)22銀行家算法的保守性例銀行家算法的保守性例5-5l考慮考慮R=A(1),B(1)，P=p1,p2l進(jìn)程進(jìn)程p1和和p2的活動序列分別為：的活動序列分別為：lp1：a, b, a, blp2：b, b, b, a, b, alp1和和p2的資源最大需求量均為的資源最大需求量均為A(1)，B(1) 假定假定某時刻系統(tǒng)狀態(tài)如下：某時刻系統(tǒng)狀態(tài)如下： 23銀行家算法的保守性例銀行家算法的

16、保守性例5-5l此時此時p1的的a被接受被接受l其后可能：其后可能：p1請求請求b, 或或p2請求請求bl假定假定p2請求請求b, 因因Request2=(0,1)Need2=(1,1)，該，該請求是合法的請求是合法的l又又Request2=(0,1)Available=(0,1)，該請求系統(tǒng)能夠，該請求系統(tǒng)能夠滿足滿足24銀行家算法的保守性例銀行家算法的保守性例5-5l假定分配系統(tǒng)狀態(tài)變化如下假定分配系統(tǒng)狀態(tài)變化如下 l運(yùn)行安全性檢測算法發(fā)現(xiàn)系統(tǒng)處于不安全狀態(tài)，運(yùn)行安全性檢測算法發(fā)現(xiàn)系統(tǒng)處于不安全狀態(tài)，取消分配，取消分配，p2等待等待25銀行家算法的保守性例銀行家算法的保守性例5-5lp1：

17、a, b, a, blp2：b, b, b, a, b, al實(shí)際上真正實(shí)施分配系統(tǒng)并不進(jìn)入死鎖狀態(tài)，因?qū)嶋H上真正實(shí)施分配系統(tǒng)并不進(jìn)入死鎖狀態(tài)，因?yàn)闉榉峙浜蟀凑辗峙浜蟀凑誰p2(b),p1(b),p1(a),p1(b)p2 (b),p2(a),p2(b),p2(a)的次序兩個的次序兩個進(jìn)程可以執(zhí)行完進(jìn)程可以執(zhí)行完l這是一個這是一個p1和和p2交叉執(zhí)行的次序，不是一個順序執(zhí)行的次序交叉執(zhí)行的次序，不是一個順序執(zhí)行的次序l銀行家算法不能判斷銀行家算法不能判斷l(xiāng)該例驗(yàn)證了前面的論斷：該例驗(yàn)證了前面的論斷：死鎖狀態(tài)是不安全狀態(tài)死鎖狀態(tài)是不安全狀態(tài)的真子集的真子集265.8 死鎖的檢測死鎖的檢測數(shù)據(jù)結(jié)構(gòu)

18、：數(shù)據(jù)結(jié)構(gòu)： Available: array1.mof integer; Allocation: array1.n,1.mof integer; Request: array1.n,1.mof integer;臨時變量：臨時變量： Work: array1.mof integer; Finish: array1.nof boolean;275.8.1 死鎖檢測算法死鎖檢測算法Work:=Available;Finish:=false;有滿足條件的有滿足條件的i:Finishi=falseRequesti WorkFinishi=true;Work:=Work+AllocationiT i ,

19、finishi=trueTFF無死鎖無死鎖死鎖死鎖FinishI=truefor allocationI=028Remarks1. 上述算法可以檢測到參與死鎖的全部進(jìn)程，包括占有資上述算法可以檢測到參與死鎖的全部進(jìn)程，包括占有資 源和不占有資源的進(jìn)程。源和不占有資源的進(jìn)程。如果存在如果存在i，1=i=n，finishi=false，則系統(tǒng)處于死鎖，則系統(tǒng)處于死鎖狀態(tài)，且狀態(tài)，且pi參與了死鎖。參與了死鎖。對當(dāng)前不占有資源的進(jìn)程直接將對當(dāng)前不占有資源的進(jìn)程直接將finish置為置為true2. 定理定理5-2：令令p是系統(tǒng)中所有的進(jìn)程集合，是系統(tǒng)中所有的進(jìn)程集合，p是是p的子集的子集且為系統(tǒng)中占

20、有資源的進(jìn)程集合，則且為系統(tǒng)中占有資源的進(jìn)程集合，則p中存在死鎖的充中存在死鎖的充要條件是要條件是p中存在死鎖。中存在死鎖。29死鎖例子死鎖例子例子：例子：R=A(7),B(2),C(6); P=p0,p1,p2,p3,p4 Allocation Request Available Work Finish A B C A B C A B C A B C p0: 0 1 0 0 0 0 0 0 0p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0p3: 2 1 1 1 0 0p4: 0 0 2 0 0 2 未死鎖。未死鎖。此時，此時，Request2=(0,0,1), 死鎖，參與死鎖

21、進(jìn)程死鎖，參與死鎖進(jìn)程p1,p2,p3,p4305.8.2 死鎖檢測時刻死鎖檢測時刻l何時進(jìn)行死鎖檢測主要取決于兩個因素何時進(jìn)行死鎖檢測主要取決于兩個因素l死鎖發(fā)生的頻率；死鎖發(fā)生的頻率； l死鎖所涉及的進(jìn)程個數(shù)死鎖所涉及的進(jìn)程個數(shù)l通常在如下時刻進(jìn)行死鎖檢測通常在如下時刻進(jìn)行死鎖檢測l 進(jìn)程等待時檢測進(jìn)程等待時檢測 l 定時檢測定時檢測 l 資源利用率降低時檢測資源利用率降低時檢測315.9 死鎖的恢復(fù)死鎖的恢復(fù)l重新啟動重新啟動(system restart) l簡單，代價大，涉及未參與死鎖的進(jìn)程簡單，代價大，涉及未參與死鎖的進(jìn)程l終止進(jìn)程終止進(jìn)程(terminating processe

22、s)l終止參與死鎖的進(jìn)程并收回所占資源終止參與死鎖的進(jìn)程并收回所占資源, 死鎖得以解除死鎖得以解除l兩種處理策略兩種處理策略: l一次性撤銷所有參與死鎖的全部進(jìn)程一次性撤銷所有參與死鎖的全部進(jìn)程, 方法簡單方法簡單, 代價較高代價較高l逐一撤銷參與死鎖的進(jìn)程逐一撤銷參與死鎖的進(jìn)程l按照某種算法選擇一個參與死鎖的進(jìn)程按照某種算法選擇一個參與死鎖的進(jìn)程l將其撤銷并收回其占有的全部資源將其撤銷并收回其占有的全部資源l判斷是否還存在死鎖判斷是否還存在死鎖, 如果是選擇下一個將被淘汰的進(jìn)程如果是選擇下一個將被淘汰的進(jìn)程l重復(fù)直至死鎖解除重復(fù)直至死鎖解除325.9 死鎖的恢復(fù)死鎖的恢復(fù)l剝奪資源剝奪資源(

23、preempting resources)l剝奪死鎖進(jìn)程所占有的全部或部分資源剝奪死鎖進(jìn)程所占有的全部或部分資源l實(shí)現(xiàn)時分為兩種情形實(shí)現(xiàn)時分為兩種情形:l逐步剝奪逐步剝奪: 一次剝奪死鎖進(jìn)程所占有的一個或一組一次剝奪死鎖進(jìn)程所占有的一個或一組資源資源, 如死鎖尚未解除繼續(xù)剝奪如死鎖尚未解除繼續(xù)剝奪, 直至死鎖解除直至死鎖解除l一次剝奪一次剝奪: 一次性地剝奪參與死鎖進(jìn)程所占有的全一次性地剝奪參與死鎖進(jìn)程所占有的全部資源部資源l進(jìn)程回退進(jìn)程回退(process rollback)l讓參與死鎖的進(jìn)程回退到以前沒有發(fā)生死鎖讓參與死鎖的進(jìn)程回退到以前沒有發(fā)生死鎖的某個點(diǎn)處的某個點(diǎn)處, 并由此點(diǎn)開始繼續(xù)

24、并由此點(diǎn)開始繼續(xù), 希望進(jìn)程交希望進(jìn)程交叉執(zhí)行時不再發(fā)生死鎖叉執(zhí)行時不再發(fā)生死鎖335.10 鴕鳥算法鴕鳥算法(ostrich algorithm)l仿鴕鳥遇到危險時將頭埋在沙子里的傳說仿鴕鳥遇到危險時將頭埋在沙子里的傳說而得名而得名l對死鎖采取視而不見的處理方法對死鎖采取視而不見的處理方法l是目前實(shí)際系統(tǒng)采用最多的策略是目前實(shí)際系統(tǒng)采用最多的策略l當(dāng)死鎖真正發(fā)生且影響系統(tǒng)正常運(yùn)行時，手當(dāng)死鎖真正發(fā)生且影響系統(tǒng)正常運(yùn)行時，手工干預(yù)工干預(yù)重新啟動重新啟動 345.10 鴕鳥算法鴕鳥算法l視而不見視而不見l工程師觀點(diǎn)工程師觀點(diǎn)(考慮死鎖發(fā)生的頻率考慮死鎖發(fā)生的頻率,危害危害,處理處理代價代價)l死

25、鎖發(fā)生頻率死鎖發(fā)生頻率 危害危害l數(shù)學(xué)家觀點(diǎn)數(shù)學(xué)家觀點(diǎn)l必須處理，無論代價如何必須處理，無論代價如何355.11 有關(guān)問題的討論有關(guān)問題的討論l關(guān)于充要性算法關(guān)于充要性算法l是一個復(fù)雜的問題是一個復(fù)雜的問題, 不存在完美的死鎖處理方不存在完美的死鎖處理方法法l關(guān)于兩階段封鎖關(guān)于兩階段封鎖l在數(shù)據(jù)庫管理系統(tǒng)中，一個原子事務(wù)可能涉在數(shù)據(jù)庫管理系統(tǒng)中，一個原子事務(wù)可能涉及多個數(shù)據(jù)項(xiàng)及多個數(shù)據(jù)項(xiàng)l為保證數(shù)據(jù)完整性，在訪問數(shù)據(jù)項(xiàng)之前需要為保證數(shù)據(jù)完整性，在訪問數(shù)據(jù)項(xiàng)之前需要對其加鎖對其加鎖(共享鎖或排它鎖共享鎖或排它鎖)l當(dāng)多個事務(wù)同時運(yùn)行時，加鎖沖突可能會導(dǎo)當(dāng)多個事務(wù)同時運(yùn)行時，加鎖沖突可能會導(dǎo)致死鎖

26、致死鎖365.11 有關(guān)問題的討論有關(guān)問題的討論l關(guān)于可剝奪資源問題關(guān)于可剝奪資源問題l進(jìn)程不會因?yàn)樘幚頇C(jī)而死鎖進(jìn)程不會因?yàn)樘幚頇C(jī)而死鎖l當(dāng)內(nèi)存和虛存均不能滿足時會發(fā)生死鎖，如當(dāng)內(nèi)存和虛存均不能滿足時會發(fā)生死鎖，如果有足夠大的虛存，則不會死鎖果有足夠大的虛存，則不會死鎖375.11 有關(guān)問題的討論有關(guān)問題的討論l關(guān)于消耗型資源問題關(guān)于消耗型資源問題l前面有關(guān)死鎖的討論基本針對可重用資源前面有關(guān)死鎖的討論基本針對可重用資源(reusable resource)l這類資源一次只能分給一個進(jìn)程，使用完后這類資源一次只能分給一個進(jìn)程，使用完后資源仍存在，可分配給其它進(jìn)程使用，這是資源仍存在，可分配給其

27、它進(jìn)程使用，這是操作系統(tǒng)管理的主要資源操作系統(tǒng)管理的主要資源l另一類資源稱為消耗型資源另一類資源稱為消耗型資源(consumable resource)，亦稱生滅資源，指在系統(tǒng)運(yùn)行過，亦稱生滅資源，指在系統(tǒng)運(yùn)行過程中動態(tài)產(chǎn)生、動態(tài)消亡的資源程中動態(tài)產(chǎn)生、動態(tài)消亡的資源l對消耗型資源死鎖的處理比較困難對消耗型資源死鎖的處理比較困難385.12 饑餓與餓死饑餓與餓死l當(dāng)?shù)却龝r間給進(jìn)程推進(jìn)和響應(yīng)帶來明顯影當(dāng)?shù)却龝r間給進(jìn)程推進(jìn)和響應(yīng)帶來明顯影響時，稱發(fā)生了響時，稱發(fā)生了進(jìn)程饑餓進(jìn)程饑餓(starvation)，當(dāng)，當(dāng)饑餓到一定程度的進(jìn)程所賦予的任務(wù)即使饑餓到一定程度的進(jìn)程所賦予的任務(wù)即使完成也不再具有

28、實(shí)際意義時稱該完成也不再具有實(shí)際意義時稱該進(jìn)程被餓進(jìn)程被餓死死(starve to death). l 活鎖活鎖(live lock)：l 在忙式等待條件下發(fā)生的饑餓，稱為在忙式等待條件下發(fā)生的饑餓，稱為活鎖活鎖395.12 饑餓與餓死饑餓與餓死l饑餓：沒有時間上界的等待，如：饑餓：沒有時間上界的等待，如：l排隊(duì)等待排隊(duì)等待l忙式等待忙式等待l餓死：等待時間超過極限餓死：等待時間超過極限(deadline)l餓死餓死 vs 死鎖死鎖l死鎖進(jìn)程處于等待狀態(tài)，餓死不然死鎖進(jìn)程處于等待狀態(tài)，餓死不然l死鎖可以檢測，餓死不然死鎖可以檢測，餓死不然l饑餓和餓死與資源分配策略饑餓和餓死與資源分配策略(po

29、licy)有關(guān)有關(guān)l防止饑餓與餓死從公平性考慮，確保所有進(jìn)程不被忽防止饑餓與餓死從公平性考慮，確保所有進(jìn)程不被忽視，如視，如FCFS分配算法分配算法405.12 饑餓與餓死饑餓與餓死l餓死與死鎖有一定聯(lián)系：都是競爭資源而餓死與死鎖有一定聯(lián)系：都是競爭資源而引起，有明顯差別，主要表現(xiàn)在：引起，有明顯差別，主要表現(xiàn)在：l從進(jìn)程狀態(tài)考慮，死鎖進(jìn)程都處于等待狀態(tài)從進(jìn)程狀態(tài)考慮，死鎖進(jìn)程都處于等待狀態(tài)l死鎖進(jìn)程等待永遠(yuǎn)不會被釋放的資源，餓死死鎖進(jìn)程等待永遠(yuǎn)不會被釋放的資源，餓死進(jìn)程等待會被釋放但卻不會分配給自己的資進(jìn)程等待會被釋放但卻不會分配給自己的資源源l死鎖一定發(fā)生循環(huán)等待，餓死則不然，通過死鎖一定

30、發(fā)生循環(huán)等待，餓死則不然，通過資源分配圖可檢測死鎖，不能檢測餓死資源分配圖可檢測死鎖，不能檢測餓死l死鎖一定涉及多個進(jìn)程，饑餓或被餓死的進(jìn)死鎖一定涉及多個進(jìn)程，饑餓或被餓死的進(jìn)程可能只有一個程可能只有一個415.13 可復(fù)用資源死鎖的靜態(tài)分析可復(fù)用資源死鎖的靜態(tài)分析l定義定義5-7 一次只能分配給一個進(jìn)程使用的資源稱為可復(fù)用一次只能分配給一個進(jìn)程使用的資源稱為可復(fù)用資源資源l如打印機(jī)、磁帶機(jī)，釋放后可分配給其它進(jìn)程如打印機(jī)、磁帶機(jī)，釋放后可分配給其它進(jìn)程l定義定義5-8 由相對獨(dú)立的若干資源構(gòu)成的資源集合稱為組合由相對獨(dú)立的若干資源構(gòu)成的資源集合稱為組合資源，其中每個相對獨(dú)立的資源成為子資源資

31、源，其中每個相對獨(dú)立的資源成為子資源l如：如：lp(2)，tape(3)，mouse(1)構(gòu)成的資源集合構(gòu)成的資源集合lp(2)，tape(3)，mouse(1)llp(2)，tape(3)，mouse(1)為子資源為子資源l定義定義5-9 由相同類型的子資源構(gòu)成的組合資源，稱為同種由相同類型的子資源構(gòu)成的組合資源，稱為同種組合資源組合資源42可復(fù)用資源死鎖的靜態(tài)分析算法可復(fù)用資源死鎖的靜態(tài)分析算法(子資源僅含一個實(shí)例子資源僅含一個實(shí)例)條件：已知各個進(jìn)程有關(guān)資源的活動序列；條件：已知各個進(jìn)程有關(guān)資源的活動序列；判斷：有無死鎖可能性。判斷：有無死鎖可能性。步驟步驟1：以每個進(jìn)程占有資源，申請資

32、源作為一個狀態(tài)，：以每個進(jìn)程占有資源，申請資源作為一個狀態(tài)， 記作：記作：(pi：aj：ak1,akn)=(進(jìn)程進(jìn)程：請求：占有：請求：占有);步驟步驟2：以每個狀態(tài)為一個節(jié)點(diǎn)；：以每個狀態(tài)為一個節(jié)點(diǎn)；步驟步驟3：如：如s1所申請資源為所申請資源為s2所占有，則由所占有，則由s1向向s2畫一有向畫一有向 ?。ㄏ嗤M(jìn)程間不畫，因?yàn)橐粋€進(jìn)程不會等待自己弧（相同進(jìn)程間不畫，因?yàn)橐粋€進(jìn)程不會等待自己 占有的資源）；占有的資源）；步驟步驟4：找出所有環(huán)路；：找出所有環(huán)路；可復(fù)用資源死鎖的靜態(tài)分析算法可復(fù)用資源死鎖的靜態(tài)分析算法(子資源僅含一個實(shí)例子資源僅含一個實(shí)例)44步驟步驟5：判斷環(huán)路上狀態(tài)是否能同

33、時到達(dá)，如是有死鎖可能：判斷環(huán)路上狀態(tài)是否能同時到達(dá)，如是有死鎖可能 性，否則無死鎖可能性。性，否則無死鎖可能性。 (1)環(huán)路中有相同進(jìn)程，不能到達(dá)環(huán)路中有相同進(jìn)程，不能到達(dá)(一個進(jìn)程不可以一個進(jìn)程不可以 處于兩種狀態(tài)處于兩種狀態(tài))； (2)環(huán)路中有相同被占有資源，不能到達(dá)環(huán)路中有相同被占有資源，不能到達(dá)(一個簡單一個簡單 資源不可以分配給兩個進(jìn)程資源不可以分配給兩個進(jìn)程)。 如果發(fā)現(xiàn)環(huán)路，且環(huán)路無相同的進(jìn)程，也沒有相同的如果發(fā)現(xiàn)環(huán)路，且環(huán)路無相同的進(jìn)程，也沒有相同的進(jìn)程，不能判斷是否發(fā)生死鎖，需要進(jìn)一步分析進(jìn)程，不能判斷是否發(fā)生死鎖，需要進(jìn)一步分析死鎖分析例子死鎖分析例子(p1:d:c)(p

34、1:a:d)(p1:b:da)(p2:e:d)(p2:b:e)(p2:f:eb)(p3:e:c)(p3:f:c)(p3:a:cf)R=A，B，C，D，E，F(xiàn)，Gp1：c d c a b d a bp2：d e d b f e b f p3：c e c f a c f a死鎖分析例子死鎖分析例子(p1:d:c)(p1:a:d)(p1:b:da)(p2:e:d)(p2:b:e)(p2:f:eb)(p3:e:c)(p3:f:c)(p3:a:cf)R=A，B，C，D，E，F(xiàn)，Gp1：c d c a b d a bp2：d e d b f e b f p3：c e c f a c f a步驟步驟3：如：

35、如s1所申請資所申請資源為源為s2所占有，則由所占有，則由s1向向s2畫一有向弧畫一有向弧死鎖分析例子死鎖分析例子p1：c d c a b d a bp2：d e d b f e b f p3：c e e f a e f a12證明：線證明：線1不可達(dá)；不可達(dá)；反證：假定線反證：假定線1可達(dá)，則線可達(dá)，則線2可達(dá)?？蛇_(dá)。 p2先于先于p1; p3先于先于p2; p1先于先于p3, 矛盾。矛盾。p1:p2:pn:a5.14 同種組合資源死鎖的必要條件同種組合資源死鎖的必要條件M：資源數(shù)量：資源數(shù)量 N：使用該類資源進(jìn)程的數(shù)量：使用該類資源進(jìn)程的數(shù)量 ：所有進(jìn)程所需要該類資源的總量：所有進(jìn)程所需要

36、該類資源的總量假定死鎖，假定死鎖，n個進(jìn)程參與了死鎖個進(jìn)程參與了死鎖(2 n N)參與死鎖的進(jìn)程所需資源的總量參與死鎖的進(jìn)程所需資源的總量 M+n未參與死鎖進(jìn)程所需資源的總量未參與死鎖進(jìn)程所需資源的總量 N-n所有進(jìn)程所需資源的總量所有進(jìn)程所需資源的總量M+n+N-n=M+N當(dāng)當(dāng) M+N時，一定沒有死鎖；時，一定沒有死鎖；當(dāng)當(dāng)M+N時，至少有一個交叉有死鎖。時，至少有一個交叉有死鎖。例子例子例例1. M=15； N=4；P1(4); P2(6); P3(1); P4(7) =4+6+1+7=18M+N=19 無死鎖可能性。無死鎖可能性。例例2. M=15; N=4；P1(5); P2(6); P3(1); P4(7) =5+6+1+7=19 M+N=19 有死鎖可能性。有死鎖可能性。死鎖情況：死鎖情況： P1：a a a a a P2：a a a a a a P3：a P4：a a a a