第7講死鎖與銀行家算法ppt課件

1、第七講死鎖與銀行家算法華軟軟件工程系內(nèi)容回想操作系統(tǒng)概述進程及進程間的通訊軟中斷、管道通訊IPC機制、音訊緩沖通訊、共享內(nèi)存通訊、信號量集(PV操作)本次課內(nèi)容資源分配、死鎖銀行家算法主要內(nèi)容第一部分內(nèi)容回想OS概述用戶界面進程進程間通訊主要內(nèi)容內(nèi)容回想操作系統(tǒng)概述從概念上講述了操作系統(tǒng)的內(nèi)涵從類型上引見了操作系統(tǒng)的分類從技術(shù)上了解了操作系統(tǒng)的根底用戶界面引見了各種操作界面(interface)程序界面：系統(tǒng)提供應(yīng)編程人員的接口，也稱系統(tǒng)調(diào)用界面。內(nèi)容回想(2)進程重點了解進程的概念：程序的一次運轉(zhuǎn)過程了解進程控制塊PCB的構(gòu)造Unix、Linux以及作用掌握進程的三種根本形狀及其轉(zhuǎn)換，以及進

2、程的創(chuàng)建、撤銷、睡眠、喚醒掌握進程的同步與互斥，包括臨界資源的概念進程間通訊軟中斷信號機制、管道通訊分類IPC機制音訊緩沖、共享內(nèi)存、信號量集掌握這些對象的創(chuàng)建、運用、撤銷等操作針對信號量集，需掌握信號量的PV操作第二部分死鎖與銀行家算法資源分配死鎖處置機的多級調(diào)度作業(yè)調(diào)度進程調(diào)度主要內(nèi)容資源分配資源分配的根本概念系統(tǒng)中一切進程共享并競爭系統(tǒng)中的一切資源操作系統(tǒng)對其一切的資源進展一致管理和分配用戶進程提出資源需求懇求，系統(tǒng)采用某種合理的規(guī)那么分配資源目的：滿足一切進程對資源的需求，并使系統(tǒng)資源的利用率到達最高資源競爭的結(jié)果提高資源的利用率導(dǎo)致系統(tǒng)死鎖資源分配(2)資源管理和分配的目的保證資源有

3、高的利用率在合理的時間內(nèi),使各進程有獲取所需資源的時機對“不可共享的資源實行互斥運用防止因資源的不合理分配引起系統(tǒng)死鎖資源分配的根本方法靜態(tài)資源分配：指作業(yè)級的資源分配。作業(yè)開場分配資源，作業(yè)終了釋放資源。利用率低。動態(tài)資源分配：指進程級的資源分配。懇求時分配，運用完釋放。利用率高。死鎖死鎖的根本概念一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源,因此永遠無法得到的資源,這種景象稱為進程死鎖,這一組進程稱為死鎖進程產(chǎn)生死鎖的緣由系統(tǒng)資源缺乏進程推進的順序不合理進程死鎖舉例打印機攝像頭進程A進程B占有占有等待等待死鎖(2)產(chǎn)生死鎖的必要條件：互斥:臨界資源為互斥運用不可剝奪(非搶

4、占)：一旦占有就直到運用終了,由進程釋放部分分配：允許部分懇求，系統(tǒng)可部分分配環(huán)路循環(huán)等待：各進程對資源的占有和懇求構(gòu)成環(huán)路處理死鎖：破壞4個必要條件中的任何一個“互斥條件普通是資源本身的特性，很難破壞普通從破壞其他三個條件思索處理方案死鎖的處置方法1預(yù)防死鎖：經(jīng)過某些限制條件的設(shè)置，去破壞產(chǎn)生死鎖的四個必要條件；2防止死鎖：在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不平安形狀；3檢測死鎖：及時檢測死鎖的發(fā)生，并確定與之相關(guān)的進程、資源，從而采取措施去除死鎖；4解除死鎖：吊銷或掛起某些進程以回收一些資源，用于解脫另一些處于死鎖的進程。預(yù)防死鎖破壞環(huán)路條件靜態(tài)資源分配有序資源分配法：要求將

5、資源編號，資源懇求只能按編號遞增進展。舉例：有資源R1、R2、R3，比如有A、B兩進程都懇求R1、R2資源，必需先懇求R1，勝利后才可懇求R2缺陷：不方便運用、資源利用率低因此采用靜態(tài)預(yù)防的方式來處理死鎖問題犧牲了資源的利用率，而資源利用率的降低直接導(dǎo)致并發(fā)度的降低。為了保證資源的利用率，操作系統(tǒng)往往采用動態(tài)分配方式來防止死鎖。死鎖防止是指操作系統(tǒng)在動態(tài)分配過程中對每一次的分配都要采取某種戰(zhàn)略去判別一下當前的分配有沒有導(dǎo)致死鎖的能夠性，沒有那么實施分配，有那么回絕分配，從而動態(tài)地防止死鎖的產(chǎn)生。防止死鎖銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P, Q, R分別需求8,3,9萬元搞工程，假設(shè)P已懇求

6、到了4萬，Q要懇求2萬，R要懇求4萬.Q1：客戶要求分期貸款，一旦得到每期貸款，就可以歸還貸款Q2：銀行家應(yīng)謹慎的貸款，防止出現(xiàn)壞帳什么是銀行家問題？銀行家-操作系統(tǒng) 周轉(zhuǎn)資金-系統(tǒng)資源 貸款客戶-進程當某進程懇求分配資源時，系統(tǒng)假定先分配給它，之后假設(shè)能找到一個進程完成序列平安序列，闡明系統(tǒng)是平安的，可進展實踐分配；否那么，讓懇求者等待。銀行家算法的實現(xiàn)思想算法原理我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)懇求分配資源相當于用戶向銀行家貸款。為保證資金的平安，銀行家規(guī)定：(1) 當一個顧客對資金的最大需求量不超越銀行家現(xiàn)有的資金時就可接納該顧客；

7、(2) 顧客可以分期貸款，但貸款的總數(shù)不能超越最大需求量；(3) 當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；(4) 當顧客得到所需的全部資金后，一定能在有限的時間里歸還一切的資金.表 示 形 式含 義Available（可用資源數(shù)組）Available j k現(xiàn)有資源 j 的數(shù)目為 k Max（最大需求矩陣）Max i, j k進程 i 對資源 j 的最大需求數(shù)目為 k Allocation（分配矩陣）Allocation i, j k進程 i 當前已分得的資源 j 的數(shù)目為 kNeed（需求矩陣）Need i, j k進程 i

8、 尚需分配的資源 j 的數(shù)目為 k銀行家算法中的數(shù)據(jù)構(gòu)造銀行家算法當Pi發(fā)出資源懇求，分配一個Request向量然后系統(tǒng)按下述流程進展執(zhí)行：Requesti：是進程Pi的懇求向量假設(shè)Requestij=K，表示進程i需求K個Rj類型的資源。銀行家算法實現(xiàn)過程平安性算法實現(xiàn)過程平安性算法兩個向量：Work和FinishWork表示系統(tǒng)可提供應(yīng)進程繼續(xù)運轉(zhuǎn)所需的各類資源數(shù)目即在分配過程中，系統(tǒng)的可用資源數(shù)。初始值 Work=Available;Finish表示系統(tǒng)能否有足夠的資源分配給進程i，使之運轉(zhuǎn)完成。初始值 Finishi:=false當有足夠資源分配給進程時 Finishi:=true 假

9、定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時辰的資源分配情況如以下圖所示。 P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 02, 0, 03, 0, 22, 1, 10, 0, 27, 4, 31, 2, 26, 0, 00, 1, 14, 3, 13, 3, 2銀行家算法實例1T0時辰系統(tǒng)能否平安？執(zhí)行平安性算法進展檢查： 向量初值 Wo

10、rk :Available(3, 3, 2)； Finish i :false；i0, 1, , 4 在進程集合中找到 Need1(1, 2, 2) Work 且 Finish 1 false； 那么設(shè) P1 順利執(zhí)行完成，從而有： Work :WorkAllocation1 (3, 3, 2)(2, 0, 0)(5, 3, 2) Finish 1 :true銀行家算法實例Chapter 3 處置機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue5 3 22 0 01 2 23 3 2P1AllocationNeedP00 1 07 4 3P12

11、 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 處置機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue7 4 35 3 22 1 10 1 1P3true5 3 22 0 01 2 23 3 2P1AllocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 處置機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue7 5 37 4 30

12、 1 07 4 3true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P3P1AllocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 處置機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1A

13、llocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 處置機調(diào)度與死鎖AllocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1true10 5 70 0 24 3 110 5 5P4FinishWork+AllocationAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 1

14、5 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1發(fā)現(xiàn)：目前可執(zhí)行的一切資源分配任務(wù)完成之后，各個進程對應(yīng)的形狀向量 Finish i true；且對應(yīng)于該向量置為 “true 的進程編號依次為：1 3 0 2 4，故： 系統(tǒng)存在平安序列 P1，P3，P0，P2，P4 所以，T0 時辰系統(tǒng)處于平安形狀！銀行家算法實例Chapter 3 處置機調(diào)度與死鎖 由分析知：執(zhí)行完 P1、P3 的資源分配懇求之后，系統(tǒng)可用的資源數(shù)量可以滿足其它 3 個進程的資源懇求，那么此時的資源分配順序已無關(guān)緊要。所以：平安序列可以不獨一！true10 5 70 0 24 3 110 5 5P4

15、FinishWork+AllocationAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P12P1 發(fā)出懇求Request(1, 0, 2)，系統(tǒng)能分配資源嗎？ 執(zhí)行銀行家算法： Request1 (1, 0, 2)Need1 (1, 2, 2)； Request1 (1, 0, 2)Available (3, 3, 2)； 系統(tǒng)為P1進展預(yù)分配，并修正Available，Allocation1 和

16、Need1向量：銀行家算法實例Request1 (1, 0, 2)，Need1 ，Available Available :AvailableRequest1 (3, 3, 2)(1, 0, 2)(2, 3, 0) Allocation1 :Allocation1Request1 (2, 0, 0)(1, 0, 2)(3, 0, 2) Need1 :Need1Request1 (1, 2, 2)(1, 0, 2)(0, 2, 0)銀行家算法實例Chapter 3 處置機調(diào)度與死鎖FinishAvailableAllocationNeedWorktrue5 3 23 0 20 2 02 3 0P

17、1P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 0Chapter 3 處置機調(diào)度與死鎖FinishAvailableAllocationNeedWorktrue7 4 32 1 1true5 3 23 0 20 2 02 3 0P1P35 3 20 1 1P4P3P2P1P0Av

18、ailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 15, 3, 2Chapter 3 處置機調(diào)度與死鎖FinishAvailableAllocationNeedWorktrue7 5 30 1 07 4 37 4 3true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P1P35 3 20 2

19、0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 17, 4, 3Chapter 3 處置機調(diào)度與死鎖FinishAvailableAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 1t

20、rue5 3 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 17, 5, 3Chapter 3 處置機調(diào)度與死鎖true10 5 70 0 24 3 110 5 5P4FinishAvailableAllocationNeed

21、Worktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 110, 5, 5Chapte

22、r 3 處置機調(diào)度與死鎖P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 110, 5, 7 執(zhí)行平安性算法檢查時，仍可以得到平安序列 P1，P3，P0，P2，P4 ，故懇求向量 Request1 (1, 0, 2) 發(fā)出時系統(tǒng)平安！分配后資源P4P3P2P1P0AvailableA, B, CN

23、eedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 03P4發(fā)出懇求Request(3, 2, 1)，系統(tǒng)能分配資源嗎？ 執(zhí)行銀行家算法進展檢查： Request4(3, 2, 0)Need4(4, 3, 1)； Request4(3, 2, 1) Available(2, 3, 0) 故：P4 資源懇求失敗，讓其等待！銀行家算法實例分配

24、后資源P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C進 程資源 情況7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 04P0發(fā)出懇求Request(0, 2, 0)，系統(tǒng)能分配資源嗎？ 執(zhí)行銀行家算法進展檢查： Request0(0, 2, 0)Need0(7, 4, 3)； Request0(0, 2, 0)Available(2, 3,

25、0)； 系統(tǒng)為 P0 作預(yù)分配，并修正有關(guān)數(shù)據(jù)： 銀行家算法實例 Available :AvailableRequest0 (2, 3, 0)(0, 2, 0)(2, 1, 0) Allocation0 :Allocation0Request0 (0, 1, 0)(0, 2, 0)(0, 3, 0) Need0 :Need0Request0 (7, 4, 3)(0, 2, 0)(7, 2, 3)銀行家算法實例MaxAllocationNeedAvailableP07 5 30 3 07 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1 顯然，對于一切進程，條件NeediAvailable，均不成立。因此， P0 此次資源懇求預(yù)分配的結(jié)果，使系統(tǒng)進入不平安形狀，故應(yīng)吊銷此次預(yù)分配。銀行家算法實例死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù)檢查方法： 類似于銀行家算法，假設(shè)某時辰不是一切進程都進入平安序列，這些進程將發(fā)生死鎖恢復(fù)方法：將產(chǎn)生死鎖的進程全部撤銷逐個撤銷死鎖的進程，直至死鎖解除從發(fā)生死鎖的進程中剝奪其占有的資源，破壞死鎖的“不可剝奪條件。餓死餓死是死鎖的另一種表現(xiàn)方式。假設(shè)有三個進程：Pa、Pb、Pc，每個進程都周期性地訪問資源R。存在這樣一種情況：Pa擁有資源R，Pb、