操作系統(tǒng)原理第六章

1、1/19第第6章章 并發(fā)性并發(fā)性:死鎖死鎖6.1 6.1 死鎖的概念死鎖的概念 6.2 6.2 產(chǎn)生死鎖的條件和處理產(chǎn)生死鎖的條件和處理 6.3 6.3 死鎖的預(yù)防死鎖的預(yù)防 6.4 6.4 死鎖的避免死鎖的避免6.5 6.5 死鎖的檢測與解除死鎖的檢測與解除 6.6 6.6 死鎖的綜合處理策略死鎖的綜合處理策略2/196.1 6.1 死鎖的概念死鎖的概念死鎖死鎖: : 指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。即：一組進程中，每個進程都無限等待被該一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠組進程中另一進程所占有的資源

2、，因而永遠無法得到的資源，這種現(xiàn)象無法得到的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。3/196.1 6.1 死鎖的概念死鎖的概念死鎖例子：有一臺打印機R1和一臺卡片閱讀機R2，進程P1占用打印機R1，進程P2占用卡片閱讀機R2。如果Pl要求閱讀機，P2要求打印機，則P1，P2便處于死鎖狀態(tài)。 4/196.1 6.1 死鎖的概念死鎖的概念產(chǎn)生死鎖的原因：n1競爭系統(tǒng)資源競爭系統(tǒng)資源 ：如上例所示：如上例所示n2進程的推進順序不當(dāng)進程的推進順序不當(dāng) 5/192進程的推進順序不當(dāng)進程的推進順序不當(dāng)在進程在進程P1P1和和P2P2并發(fā)執(zhí)行時，按照左圖曲線并發(fā)執(zhí)行時，按照左圖曲線所示順序推

3、進時，兩進程會順利完成，所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。若按曲線的我們稱這種推進順序是合法的。若按曲線的順序推進時，進入不安全區(qū)順序推進時，進入不安全區(qū)D D內(nèi)，兩進程再推進內(nèi)，兩進程再推進會產(chǎn)生死鎖。會產(chǎn)生死鎖。6/196.2 6.2 產(chǎn)生死鎖的條件和處理產(chǎn)生死鎖的條件和處理互斥條件互斥條件（資源獨占）請求和保持條件請求和保持條件（部分分配，占有申請）非非剝奪條件剝奪條件（不可強占）循環(huán)循環(huán)等待條件等待條件6.2.1 6.2.1 必要條件必要條件 7/191) 互斥使用（資源獨占）互斥使用（資源獨占）一個資源每次只能給一個進程使用2) 不可強占（不可剝奪）不可強

4、占（不可剝奪） 資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放6.2.1 6.2.1 必要條件必要條件 6.2 6.2 產(chǎn)產(chǎn)生死鎖的條件和處理生死鎖的條件和處理8/19 3) 請求和保持請求和保持（部分分配，占有申請）一個進程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態(tài)申請，動態(tài)分配）6.2.1 6.2.1 必要條件必要條件 6.2 6.2 產(chǎn)產(chǎn)生死鎖的條件和處理生死鎖的條件和處理9/19 4) 循環(huán)等待循環(huán)等待 存在一個進程等待隊列 P1 , P2 , , Pn, 其中P1等待P2占有的資源，P2等待P3占有的資源，Pn等待P1占有的資源，形成一個進程等

5、待環(huán)路6.2.1 6.2.1 必要條件必要條件 6.2 6.2 產(chǎn)產(chǎn)生死鎖的條件和處理生死鎖的條件和處理10/196.2 6.2 產(chǎn)生死鎖的條件和處理產(chǎn)生死鎖的條件和處理6.2.2 6.2.2 處理死鎖的基本方法處理死鎖的基本方法 不讓死鎖發(fā)生n預(yù)防死鎖預(yù)防死鎖（靜態(tài)策略）n避免死鎖避免死鎖（動態(tài)策略）讓死鎖發(fā)生n檢測死鎖檢測死鎖n解除死鎖解除死鎖11/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防通過破壞死鎖的四個必要條件中的一個或多個以確保系統(tǒng)絕不會產(chǎn)生死鎖。n1互斥條件互斥條件 ：無法破環(huán)n2破壞請求和保持條件破壞請求和保持條件 ：采用預(yù)先分配的策略，詳見6.3.1 。n3破壞循環(huán)等待條件破壞

6、循環(huán)等待條件：采用有序分配的策略，詳見6.3.2。 12/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防n4破壞非剝奪條件破壞非剝奪條件 ：可以收回已分給進程且尚未使用完畢的資源。2個方案：方案方案1 1：進程在申請新的資源不能得到滿足，必須釋放已占有的全部資源，進入等待隊列。13/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防方案方案2 2：進程在請求資源得不到滿足，則檢查這些資源是否分給了某個進程，如果此進程正在等待更多資源，則剝奪等待進程的這些資源以滿足請求進程的需要；否則請求進程等待。在等待過程中，它的某些資源也有可能被剝奪。 適用資源：適用資源：狀態(tài)容易保存和恢復(fù)的，例如CPU寄存器、存儲器空間

7、等。14/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防方法有兩種：方法有兩種：n一種是要求每個進程在運行之前便申請它所需的全部資源n另一種是，規(guī)定每個進程在請求新的資源之前必須釋放其已占用的全部資源。6.3.1 6.3.1 預(yù)先分配策略預(yù)先分配策略 15/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防缺點：缺點：n一是資源利用率較低；n二是有可能產(chǎn)生“饑餓”現(xiàn)象，即如果一個進程需要幾種競爭較激烈的資源，而總不能完全得到滿足的話，則該進程將無限期地等待。所以，這種方法在實際中用得較少。所以，這種方法在實際中用得較少。6.3.1 6.3.1 預(yù)先分配策略預(yù)先分配策略 16/196.3 6.3 死鎖的預(yù)防死鎖

8、的預(yù)防把系統(tǒng)中所有資源編號，進程在申請資源時必須按資源編號的遞增次序進行，否則操作系統(tǒng)不予分配6.3.2 6.3.2 有序分配策略有序分配策略 -破壞“循環(huán)等待”條件17/196.3 6.3 死鎖的預(yù)防死鎖的預(yù)防6.3.2 6.3.2 有序分配策略有序分配策略例如：資源編號1，2，3，10P1：申請申請1申請申請3申請申請9P2：申請申請1申請申請2申請申請5P3 P1018/196.4 6.4 死鎖的避免死鎖的避免定義定義:系統(tǒng)運行過程中， 允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程； 否則，令進程

9、等待。 最具有代表性的避免死鎖算法是銀行家算法。19/196.4.1 6.4.1 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 安全狀態(tài)：安全狀態(tài)：如果系統(tǒng)能按某種順序（如如P4，P1，,Pn, 稱為安全序列稱為安全序列）為每個進程分配其所需的資源，直至每個進程都能順利地完成，稱系統(tǒng)處于安全狀態(tài)。若不存在這樣一個安全序列稱系統(tǒng)處于不安全狀態(tài)。 安全狀態(tài)一定是沒有死鎖發(fā)生的。20/196.4.1 6.4.1 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 安全狀態(tài)之例安全狀態(tài)之例： 有三個進程p1,p2,p3，有12臺磁帶機。P1共要求10臺，P2共要求4臺，P3共要求9臺。在T0時刻，p1,p2,p3分別獲得5、2、2臺，尚有3臺空閑

10、。進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223 經(jīng)分析，在經(jīng)分析，在T0時刻，系統(tǒng)是安全的。因為時刻，系統(tǒng)是安全的。因為存在一個安全序列存在一個安全序列p2、p1、p3。21/196.4.1 6.4.1 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換：如在T0以后，P3要求1臺磁帶機，若系統(tǒng)分給它一臺，則系統(tǒng)進入不安全狀態(tài)。進程最大需求已分配還需可用p110552p2422p3936 因為其余因為其余2 2臺分給臺分給P2P2，P2P2完成后，只能釋完成后，只能釋放放4 4臺，這既不能滿足臺，這既不能滿足P1P1（5 5臺），也不

11、能滿足臺），也不能滿足P3P3（6 6臺），將導(dǎo)致死鎖。臺），將導(dǎo)致死鎖。22/196.4.2 6.4.2 銀行家算法銀行家算法 1.1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （1）可利用資源向量可利用資源向量AvailableAvailable。它是一個含有m個元素的數(shù)組，其中每個元素代表一類可利用資源的數(shù)目。如： ABC52323/196.4.2 6.4.2 銀行家算法銀行家算法 1.1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （2）最大需求矩陣）最大需求矩陣Max。n*m矩陣，表示n個進程的每一個對m類資源的最大需求。ABCP1562P2331P3425P433224/19

12、6.4.2 6.4.2 銀行家算法銀行家算法 1.1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （3）分配矩陣）分配矩陣Allocation 。n*m矩陣，表示每個進程分配的資源數(shù)。ABCP1212P2121P3222P413225/196.4.2 6.4.2 銀行家算法銀行家算法 1.1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （4）需求矩陣）需求矩陣Need 。n*m矩陣，表示每個進程還需要各類資源數(shù)。ABCP1352P2211P3223P423226/196.4.2 6.4.2 銀行家算法銀行家算法 2.2.銀行家算法銀行家算法 當(dāng)進程pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：（1

13、）若）若RequestiNeedi,轉(zhuǎn)（轉(zhuǎn)（2）；）； 否則錯誤返回否則錯誤返回(需要資源數(shù)超過最大值)（2）若若RequestiAvailable, 轉(zhuǎn)（轉(zhuǎn)（3）；否則進程等待）；否則進程等待(無足夠資源)27/196.4.2 6.4.2 銀行家算法銀行家算法 2.2.銀行家算法銀行家算法 （3）系統(tǒng)試試分配資源，則有：Available:=Available- Request i;Allocation i:= Allocation i+ Request i;Need i :=Need i Request i（4）執(zhí)行安全性算法安全性算法，若系統(tǒng)新狀態(tài)是安全的，則分配完成，若系統(tǒng)新狀態(tài)是不安

14、全的，則恢復(fù)原狀態(tài)，進程等待28/196.4.2 6.4.2 銀行家算法銀行家算法 3.3.安全性算法安全性算法 為進行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;m代表資源的數(shù)量，n代表進程的數(shù)量 29/196.4.2 6.4.2 銀行家算法銀行家算法 3.3.安全性算法安全性算法(1) Work:=Available; Finish:=false;(2) 尋找滿足條件的 i ： a.Finishi=false; b.NeediWork;如果不存在，則轉(zhuǎn)(4)30/196.4.2 6.4.2 銀行家算法銀行

15、家算法 3.3.安全性算法安全性算法(3) Work:=Work+Allocationi; Finishi:=true; 轉(zhuǎn)(2)(4) 若對所有所有i, Finishi=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)31/194. 4. 銀行家算法舉例：銀行家算法舉例： 設(shè)系統(tǒng)有五個進程和三類資源，每類資源分別有10、5、7。在T0時刻資源分配情況如圖: 資源情況資源情況進程進程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30

16、 1 00 1 07 4 37 4 33 3 23 3 2P1P13 2 23 2 22 0 02 0 01 2 21 2 2P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1(1) T0時刻可以找到一個安全序列時刻可以找到一個安全序列p1,p3,p4,p2,p0, 系統(tǒng)是安全的系統(tǒng)是安全的32/194. 4. 銀行家算法舉例：銀行家算法舉例： (2) P1發(fā)出請求發(fā)出請求Request(1,0,2)，執(zhí)行銀行家算法，執(zhí)行銀行家算法: 資源情

17、況資源情況進程進程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 33 3 23 3 22 3 02 3 0P1P13 2 23 2 22 0 02 0 03 0 23 0 21 2 21 2 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 2

18、4 3 14 3 1可以找到一個安全序列可以找到一個安全序列p1,p3,p4,p0,p2，系統(tǒng)是安全的，可以將可以將P1的請求分配給它。的請求分配給它。33/194. 4. 銀行家算法舉例：銀行家算法舉例： () P4發(fā)出請求發(fā)出請求Request(3,3,0), 執(zhí)行銀行家算法執(zhí)行銀行家算法: 資源情況資源情況進程進程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 32 3 02 3 0P1P

19、13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available=（2, 3, 0），RequestiAvailable ），所以P4等待。34/194. 4. 銀行家算法舉例：銀行家算法舉例： (4) P0請求資源請求資源Request（0，2，0），執(zhí)行銀行），執(zhí)行銀行家算法，家算法，試試分配后分配后: 資源情況資源情況進程進程MaxMaxA B CA B CAllocati

20、onAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 3 00 3 07 2 37 2 32 1 02 1 0P1P13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available(2,1,0) 不能滿足任何進程需要，所以系統(tǒng)進入不安全狀態(tài)，P0的請求不能分配的請求不

21、能分配35/196.5 6.5 死鎖的檢測與解除死鎖的檢測與解除 允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進展情況，判斷死鎖是否發(fā)生 一旦死鎖發(fā)生則采取專門的措施，解除死鎖解除死鎖并以最小的代價恢復(fù)操作系統(tǒng)運行36/196.5.1 6.5.1 死鎖的檢測死鎖的檢測 1.資源分配圖（資源分配圖（SRAG） 由二元組G=G=（V V，E E） V V：結(jié)點集，分為P(進程)，R(資源)兩部分 P=p1,p2,pn,P=p1,p2,pn, R=r1,r2,rm R=r1,r2,rm E E：邊的集合，其元素為有序二元組: (pi,rj)(pi,rj)或(rj,pi)(rj,pi) 37/196.5.1 6

22、.5.1 死鎖的檢測死鎖的檢測 1.資源分配圖（資源分配圖（SRAG） 表示法表示法資源類資源類: :用方框表示（資源的不同類型）資源實例資源實例: :用方框中的黑圓點表示（存在于每個資源中） 進程進程 : :用圓圈中加進程名表示分配邊：分配邊：資源實例進程的一條有向邊申請邊：申請邊：進程資源類的一條有向邊 38/196.5.1 6.5.1 死鎖的檢測死鎖的檢測 資源分配圖示例39/196.5.1 6.5.1 死鎖的檢測死鎖的檢測 2. 死鎖判定法則死鎖判定法則 (1)如果資源分配圖(SRAG)中沒有環(huán)路沒有環(huán)路，則系統(tǒng)內(nèi)沒有死鎖沒有死鎖。(2)如果SRAG中有環(huán)有環(huán)路，且每類資源只有一資源只

23、有一個個，則有環(huán)有環(huán)是系統(tǒng)存在死鎖存在死鎖的必要充分條件。(3)如果SRAG中有環(huán)路有環(huán)路，但每類資源的個數(shù)每類資源的個數(shù)不全為不全為1 1，則可以利用對對SRAGSRAG化簡化簡的方法，來檢測系統(tǒng)是否存在死鎖 40/19資源分配圖示例資源分配圖示例有環(huán)無死鎖41/19資源分配圖示例資源分配圖示例 有環(huán)有死鎖42/196.5.1 6.5.1 死鎖的檢測死鎖的檢測資源分配圖化簡資源分配圖化簡1）找一個非孤立進程結(jié)點且只有分配邊，去掉分配邊，將其變?yōu)楣铝⒔Y(jié)點2）再把相應(yīng)的資源分配給一個等待該資源的進程，即將某進程的申請邊變?yōu)榉峙溥?）重復(fù)以上步驟，若所有進程成為孤立結(jié)點，稱該圖是可完全簡化的，否則

24、稱該圖是不可完全簡化的。死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)資源分配圖是不死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)資源分配圖是不可完全簡化的?？赏耆喕?。( (死鎖定理死鎖定理) )43/196.5.1 6.5.1 死鎖的檢測死鎖的檢測 資源分配圖化簡示例：資源分配圖化簡示例：44/196.5.1 6.5.1 死鎖的檢測死鎖的檢測 3.死鎖檢測算法死鎖檢測算法 算法的策略是查找一個進程，使得可用資源可以滿足該進程的資源請求，然后假設(shè)同意這些資源，讓進程運行直到完成，再釋放它的所有資源，然后算法尋找另一個可以滿足資源請求的進程。45/19死鎖的檢測算法死鎖的檢測算法 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：nAvailable：

25、每類資源的可用數(shù)目 nAllocation：進程所分得的資源個數(shù) nRequest ：進程的資源請求 46/19死鎖的檢測算法死鎖的檢測算法 算法步驟：算法步驟：1 令Work：=Available。對于i1，2，n，如果Allocationi=0則Finishitrue，否則Finishifalse。2找到一個下標(biāo)i，使得 Finishifalse，并且 RequestiWork 如果不存在這樣的i，則轉(zhuǎn)向步驟轉(zhuǎn)向步驟4；47/19死鎖的檢測算法死鎖的檢測算法 3Work：=Work + Allocationi Finishi:=true 轉(zhuǎn)步驟步驟2；4如果對于所有的i=1，2，n，存在一

26、個或以上Finishi:=false, 則系統(tǒng)出現(xiàn)了死鎖，死鎖進程為該Pi進程。48/19死鎖檢測算法示例：死鎖檢測算法示例：假設(shè)有資源R1、R2、R3、R4、R5和進程P1、P2、P3、P4的需求矩陣、分配矩陣，可用資源向量如表所示。 1. Allocation4=0, 所以Finish4=ture, Finish1-3=false 資源資源進程進程RequestRequestR1 R2 R3 R4 R5R1 R2 R3 R4 R5AllocationAllocationR1 R2 R3 R4 R5R1 R2 R3 R4 R5AvailableAvailableR1 R2 R3 R4 R5R

27、1 R2 R3 R4 R5P1P10 1 0 0 10 1 0 0 11 0 1 1 01 0 1 1 00 0 0 0 10 0 0 0 1P2P20 0 1 0 10 0 1 0 11 1 0 0 01 1 0 0 0P3P30 0 0 0 10 0 0 0 10 0 0 1 00 0 0 1 0P4P41 0 1 0 11 0 1 0 10 0 0 0 00 0 0 0 049/19死鎖檢測算法示例：死鎖檢測算法示例：2. Work=(0 0 0 0 1) 3. Request3 Work，因此Finish3=ture，可用資源Work (0 0 0 0 1) (0 0 0 1 0) （

28、 0 0 0 1 1 ）。 資源資源進程進程RequestRequestR1 R2 R3 R4 R5R1 R2 R3 R4 R5AllocationAllocationR1 R2 R3 R4 R5R1 R2 R3 R4 R5AvailableAvailableR1 R2 R3 R4 R5R1 R2 R3 R4 R5P1P10 1 0 0 10 1 0 0 11 0 1 1 01 0 1 1 00 0 0 0 10 0 0 0 10 0 0 1 10 0 0 1 1P2P20 0 1 0 10 0 1 0 11 1 0 0 01 1 0 0 0P3P30 0 0 0 10 0 0 0 10 0 0 0 00 0 0 0 00 0 0 1 00 0 0 1 00 0 0 0 00 0 0 0 0P4P41 0 1 0 11 0 1 0 10 0 0 0 00 0 0 0 050/19死鎖檢測