操作系統(tǒng)os03死鎖ppt課件

1、操作系統(tǒng)操作系統(tǒng)Operating Systems3.5 產(chǎn)生死鎖的緣由和必要條件產(chǎn)生死鎖的緣由和必要條件死鎖死鎖在多進(jìn)程在運轉(zhuǎn)過程中因爭奪資源而呵斥的一種僵局，當(dāng)在多進(jìn)程在運轉(zhuǎn)過程中因爭奪資源而呵斥的一種僵局，當(dāng)進(jìn)程處于這種僵局形狀時，假設(shè)無外力作用，它們都將無進(jìn)程處于這種僵局形狀時，假設(shè)無外力作用，它們都將無法再向前推進(jìn)。法再向前推進(jìn)。3.5.1 產(chǎn)生死鎖的緣由產(chǎn)生死鎖的緣由 競爭資源競爭資源當(dāng)系統(tǒng)中供多個進(jìn)程共享的資源，其數(shù)目缺乏以滿足諸當(dāng)系統(tǒng)中供多個進(jìn)程共享的資源，其數(shù)目缺乏以滿足諸進(jìn)程的需求時，會引起諸進(jìn)程對資源的競爭而產(chǎn)生死鎖進(jìn)程的需求時，會引起諸進(jìn)程對資源的競爭而產(chǎn)生死鎖。 進(jìn)程

2、間推進(jìn)順序非法。進(jìn)程間推進(jìn)順序非法。進(jìn)程在運轉(zhuǎn)過程中，懇求和釋放資源的順序不當(dāng)，也同進(jìn)程在運轉(zhuǎn)過程中，懇求和釋放資源的順序不當(dāng)，也同樣會導(dǎo)致產(chǎn)生進(jìn)程死鎖。樣會導(dǎo)致產(chǎn)生進(jìn)程死鎖。 3.5.23.5.2產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件互斥條件：互斥條件：進(jìn)程互斥運用資源進(jìn)程互斥運用資源懇求和堅持條件：部分分配條件懇求和堅持條件：部分分配條件懇求新資源時不釋放已占有資源懇求新資源時不釋放已占有資源不剝奪條件：不剝奪條件：一個進(jìn)程不能爭奪其他進(jìn)程占有的資源一個進(jìn)程不能爭奪其他進(jìn)程占有的資源環(huán)路條件：環(huán)路條件：存在一組進(jìn)程循環(huán)等待資源存在一組進(jìn)程循環(huán)等待資源S1S1S3S3S2S23.5.33.5.

3、3處置死鎖的根本方法處置死鎖的根本方法預(yù)防死鎖。預(yù)防死鎖。破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件 防止死鎖。防止死鎖。在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不平安形狀，從而防止發(fā)生死鎖。平安形狀，從而防止發(fā)生死鎖。 檢測死鎖。檢測死鎖。經(jīng)過系統(tǒng)所設(shè)置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生；經(jīng)過系統(tǒng)所設(shè)置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生；采取適當(dāng)措施，從系統(tǒng)中將已發(fā)生的死鎖去除掉。采取適當(dāng)措施，從系統(tǒng)中將已發(fā)生的死鎖去除掉。 解除死鎖。這是與檢測死鎖相配套的一種措施解除死鎖。這是與檢測死鎖

4、相配套的一種措施3.6.1預(yù)防死鎖預(yù)防死鎖一種較簡單和直觀的事先預(yù)防的方法。一種較簡單和直觀的事先預(yù)防的方法。設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預(yù)防發(fā)生死鎖：一個或幾個條件，來預(yù)防發(fā)生死鎖：互斥條件互斥條件懇求和堅持條件懇求和堅持條件不剝奪條件不剝奪條件環(huán)路條件環(huán)路條件3.6.23.6.2系統(tǒng)平安形狀系統(tǒng)平安形狀1. 1. 平安形狀平安形狀指系統(tǒng)能按某種進(jìn)程順序指系統(tǒng)能按某種進(jìn)程順序(P1(P1，P2P2，Pn)Pn)，來為每個進(jìn)程，來為每個進(jìn)程PiPi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使分配其

5、所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。每個進(jìn)程都可順利地完成。假設(shè)系統(tǒng)無法找到這樣一個平安序列，那么稱系統(tǒng)處于不平安假設(shè)系統(tǒng)無法找到這樣一個平安序列，那么稱系統(tǒng)處于不平安形狀。形狀。當(dāng)系統(tǒng)進(jìn)入不平安形狀后，便有能夠進(jìn)而進(jìn)入死鎖形狀。當(dāng)系統(tǒng)進(jìn)入不平安形狀后，便有能夠進(jìn)而進(jìn)入死鎖形狀。防止死鎖的本質(zhì)在于：防止死鎖的本質(zhì)在于：系統(tǒng)在進(jìn)展資源分配時，如何使系統(tǒng)不進(jìn)入不平安形狀系統(tǒng)在進(jìn)展資源分配時，如何使系統(tǒng)不進(jìn)入不平安形狀2平安形狀之例平安形狀之例假定系統(tǒng)中有三個進(jìn)程假定系統(tǒng)中有三個進(jìn)程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。T0時辰是平安的？時辰是平安的

6、？+2-2=12平安形狀之例平安形狀之例假定系統(tǒng)中有三個進(jìn)程假定系統(tǒng)中有三個進(jìn)程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。+5-5=02平安形狀之例平安形狀之例假定系統(tǒng)中有三個進(jìn)程假定系統(tǒng)中有三個進(jìn)程P1、P2和和P3，共有，共有12臺磁帶機。臺磁帶機。平安序列：平安序列：P2 、P1、P3T0時辰是平安的。時辰是平安的。+7-7=33由平安形狀向不平安形狀的轉(zhuǎn)換由平安形狀向不平安形狀的轉(zhuǎn)換假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形狀進(jìn)入不平安形狀。狀進(jìn)入不平安形狀。+1-1=23由平安形狀向不平安形狀的轉(zhuǎn)換由平安形狀向不平

7、安形狀的轉(zhuǎn)換假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形狀進(jìn)入不平安形狀。狀進(jìn)入不平安形狀。+2-2=03由平安形狀向不平安形狀的轉(zhuǎn)換由平安形狀向不平安形狀的轉(zhuǎn)換假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形狀進(jìn)入不平安形狀。狀進(jìn)入不平安形狀。3由平安形狀向不平安形狀的轉(zhuǎn)換由平安形狀向不平安形狀的轉(zhuǎn)換假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形假設(shè)不按照平安序列分配資源，那么系統(tǒng)能夠會由平安形狀進(jìn)入不平安形狀。狀進(jìn)入不平安形狀。從給從給P3P3分配了第分配了第3 3臺磁帶機開場，

8、系統(tǒng)便又進(jìn)入了不平安臺磁帶機開場，系統(tǒng)便又進(jìn)入了不平安形狀。形狀。3.6.33.6.3利用銀行家算法防止死鎖利用銀行家算法防止死鎖1 1銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法中的數(shù)據(jù)構(gòu)造(1) (1) 可利用資源向量可利用資源向量Available Available 每類資源未分配數(shù)量向量每類資源未分配數(shù)量向量含有含有m m個元素的數(shù)組個元素的數(shù)組假設(shè)假設(shè)Availablej=KAvailablej=K，那么表示系統(tǒng)中現(xiàn)有，那么表示系統(tǒng)中現(xiàn)有RjRj類資源類資源K K個。個。銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法中的數(shù)據(jù)構(gòu)造(2) (2) 最大需求矩陣最大需求矩陣MaxMax。一個一個n nm m的矩陣

9、，它定義了系統(tǒng)中的矩陣，它定義了系統(tǒng)中n n個進(jìn)程中的每一個進(jìn)程對個進(jìn)程中的每一個進(jìn)程對m m類資源的最大需求。假設(shè)類資源的最大需求。假設(shè)Maxi,j=KMaxi,j=K，那么表示進(jìn)程，那么表示進(jìn)程i i需求需求RjRj類資源的最大數(shù)目為類資源的最大數(shù)目為K K。Max=Max=M11M11 M12M12M1mM1mM21M21 M21M21M21M21Mn1Mn1Mn1Mn1MnmMnm銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法中的數(shù)據(jù)構(gòu)造(3) 分配矩陣分配矩陣Allocation。也是一個也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源

10、數(shù)。配給每一進(jìn)程的資源數(shù)。假設(shè)假設(shè)Allocationi,j=K，那么表示進(jìn)程，那么表示進(jìn)程i當(dāng)前已分得當(dāng)前已分得R j類資源的類資源的數(shù)目為數(shù)目為K。Allocation=Allocation=A11A11 A12A12A1mA1mA21A21 A21A21A21A21An1An1An1An1AnmAnm銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法中的數(shù)據(jù)構(gòu)造(4) 需求矩陣需求矩陣Need。一個一個nm的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。假設(shè)假設(shè)Needi,j=K，那么表示進(jìn)程，那么表示進(jìn)程i還需求還需求Rj類資源類資源K個，方能個，方能完成其義務(wù)。完

11、成其義務(wù)。上述三個矩陣間存在下述關(guān)系：上述三個矩陣間存在下述關(guān)系：Needi, j=Maxi, j- Allocationi, j 2 2銀行家算法銀行家算法(1)(1)設(shè)設(shè)Requestij=KRequestij=K，表示，表示PiPi需求需求K K個個RjRj類資源。類資源。PiPi發(fā)出資源懇求發(fā)出資源懇求RequestiRequesti后，系統(tǒng)按下述步驟進(jìn)展檢查：后，系統(tǒng)按下述步驟進(jìn)展檢查：(1)(1)假設(shè)假設(shè)RequestijNeedi,jRequestijNeedi,j，轉(zhuǎn)向步驟，轉(zhuǎn)向步驟(2)(2)； 否那么以為出錯，由于它所需求的資源數(shù)已超越它所宣否那么以為出錯，由于它所需求的資

12、源數(shù)已超越它所宣布的布的 最大值。最大值。(2)(2)假設(shè)假設(shè)RequestijAvailablejRequestijAvailablej，轉(zhuǎn)向步驟，轉(zhuǎn)向步驟(3)(3)； 否那么，表示尚無足夠資源，否那么，表示尚無足夠資源，PiPi須等待。須等待。 2 2銀行家算法銀行家算法(2)(2)(3)(3)系統(tǒng)試探把資源分配給進(jìn)程系統(tǒng)試探把資源分配給進(jìn)程PiPi，并修正數(shù)據(jù)構(gòu)造中的值：，并修正數(shù)據(jù)構(gòu)造中的值：Availablej:= Availablej - RequestijAvailablej:= Availablej - Requestij；Allocationi,j:= Allocation

13、i,j + RequestijAllocationi,j:= Allocationi,j + Requestij；Needi,j:= Needi,j - RequestijNeedi,j:= Needi,j - Requestij；(4)(4)執(zhí)行平安性算法，檢查此次資源分配后系統(tǒng)能否處于平安執(zhí)行平安性算法，檢查此次資源分配后系統(tǒng)能否處于平安形狀。形狀。假設(shè)平安，將資源正式分配給進(jìn)程假設(shè)平安，將資源正式分配給進(jìn)程PiPi；否那么，將本次的試探分配作廢，恢復(fù)原來的資源分配形狀，否那么，將本次的試探分配作廢，恢復(fù)原來的資源分配形狀，讓進(jìn)程讓進(jìn)程PiPi等待。等待。3.3.平安性算法平安性算法(1)

14、(1)(1)(1)設(shè)置兩向量：設(shè)置兩向量：可供進(jìn)程繼續(xù)運轉(zhuǎn)所需各類資源數(shù)的可供進(jìn)程繼續(xù)運轉(zhuǎn)所需各類資源數(shù)的WorkWork 初始時初始時 Work:=Available Work:=Available。表示資源能否足夠的表示資源能否足夠的FinishFinish， 初始時令初始時令Finishi:=falseFinishi:=false； 資源足夠時再令資源足夠時再令Finishi:=trueFinishi:=true。Workj=KWorkj=K3.3.平安性算法平安性算法(2)(2)(2)(2)尋覓一個能滿足下述條件的進(jìn)程：尋覓一個能滿足下述條件的進(jìn)程： Finishi=false Fin

15、ishi=false； Needi,jWorkj; Needi,jWorkj;找到執(zhí)行步驟找到執(zhí)行步驟(3)(3)，否那么執(zhí)行步，否那么執(zhí)行步驟驟(4)(4)。(3)(3)進(jìn)程進(jìn)程PiPi獲得資源，執(zhí)行完成后釋放它的資源，故應(yīng)執(zhí)行：獲得資源，執(zhí)行完成后釋放它的資源，故應(yīng)執(zhí)行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=true；go to step 2go to step 2； (4)(4)假設(shè)一切進(jìn)程的假設(shè)一切進(jìn)程的Finishi=trueFinishi=true都滿足，那么表示系統(tǒng)

16、處都滿足，那么表示系統(tǒng)處于平安形狀；否那么，系統(tǒng)處于不平安形狀。于平安形狀；否那么，系統(tǒng)處于不平安形狀。 實例闡明系統(tǒng)所處的平安或不平安形狀實例闡明系統(tǒng)所處的平安或不平安形狀假定系統(tǒng)中有五個進(jìn)程假定系統(tǒng)中有五個進(jìn)程P0P0，P1P1，P2P2，P3P3，P4P4三類資源三類資源AA，B B，C C 。 A A類資源共有類資源共有1010個個B B類資源共有類資源共有5 5個個C C類資源共有類資源共有7 7個。個。1在時辰在時辰T0,系統(tǒng)目前資源分配情況如下：系統(tǒng)目前資源分配情況如下：每個進(jìn)程目前還需資源為每個進(jìn)程目前還需資源為Need 進(jìn)程進(jìn)程 Max Allocation Availabl

17、e A B C A B C A B C P0 7 5 3 0 1 0 3 3 2 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2NeedA B C 7 4 31 2 26 0 00 1 1 4 3 1 進(jìn)程進(jìn)程 Work Need Allocation Work=Work+allocation A B C A B C A B C A B C5 3 23 3 21 2 2 2 0 05 3 20 1 1 2 1 17 4 37 4 3P1P3P4P2P04 3 1 0 0 27 4 57 4 56 0 0 3 0 210 4

18、 710 4 74 3 0 0 1 0 10 5 7Need A B C P0 7 4 3 P1 1 2 2 A B C P2 6 0 0P3 0 1 1 A B C P4 4 3 1可以斷言可以斷言T0時辰，系統(tǒng)處于平安形狀時辰，系統(tǒng)處于平安形狀由于序列由于序列P1,P3,P4,P2,P0能滿足平安性條件。能滿足平安性條件。2進(jìn)程進(jìn)程P1懇求資源懇求資源request1=(1,0,2) ，系統(tǒng)能將資源，系統(tǒng)能將資源分配給它嗎？分配給它嗎？NeedA B C7 4 36 0 00 1 14 3 1 進(jìn)程進(jìn)程 Max Allocation Available A B C A B C A B C

19、P0 7 5 3 0 1 0 P1 3 2 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2檢查檢查: request1(1,0,2) Need1(1,2,2) and request1(1,0,2) Available(3,3,2) 結(jié)果滿足條件，試分配。結(jié)果滿足條件，試分配。3 0 2 0 2 02 3 0得到新形狀：得到新形狀： 2 0 03 3 21 2 2斷定新形狀能否平安斷定新形狀能否平安?找到一個進(jìn)程序列找到一個進(jìn)程序列 可保證進(jìn)程可保證進(jìn)程P1運轉(zhuǎn)終了并歸還資源運轉(zhuǎn)終了并歸還資源進(jìn)程進(jìn)程 Work Need Allocation work+allocation A B C A B C A B C A B C5 3 22 3 00 2 0 3 0 25 3 20 1 1 2 1 17 4 37 4 3P1P3P4P0P24 3 1 0 0 27 4 57 4 57 4 3 0 1 07 5 57 5 56 0 0 3 0 2 10 5 7 A B CP0 7 4 3P1 0 2 0P2 6 0