死鎖銀行家算法ppt課件

1、第3章 處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測與解除 .關(guān)于死鎖多道程序系統(tǒng)借助并發(fā)執(zhí)行改善資源利用率，提高系統(tǒng)吞吐量，但能夠發(fā)生一種危險(xiǎn)死鎖。死鎖Deadlock：指多個進(jìn)程在運(yùn)轉(zhuǎn)過程中，因爭奪資源而呵斥的一種僵局。當(dāng)進(jìn)程處于這種形狀時，假設(shè)無外力作用，它們都將無法再向前推進(jìn)。.找緣由分析構(gòu)成條件根據(jù)分析，找出處置死鎖的方法四、產(chǎn)生死鎖的緣由和必要條件.例：運(yùn)用信號量呵斥死鎖的典型P1P2waitDwaitEwaitEwaitDsignalDsignalEsignalEsignalD死鎖發(fā)生：雙方都擁有部分資源，同時在懇求對

2、方已占有的資源。懇求推進(jìn)的次序與對非剝奪性資源的爭用都是呵斥死鎖的緣由。.產(chǎn)生死鎖的緣由可歸結(jié)為如下兩點(diǎn)：競爭資源。系統(tǒng)中供多個進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等的數(shù)目不滿足需求時，會引起資源競爭而產(chǎn)生死鎖。進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)轉(zhuǎn)過程中，懇求和釋放資源的順序不當(dāng)，同樣會導(dǎo)致死鎖。.1、競爭資源引起進(jìn)程死鎖可把系統(tǒng)中的資源分為兩類：可剝奪和非剝奪性資源可剝奪性資源：分配給進(jìn)程后可以被高優(yōu)先級的進(jìn)程剝奪。如CPU和主存。不可剝奪性資源：分配給進(jìn)程后只能在進(jìn)程用完后釋放。如磁帶機(jī)、打印機(jī)等。永久性資源和暫時性資源永久性：打印機(jī)。可順序反復(fù)運(yùn)用暫時性：進(jìn)程產(chǎn)生被其他進(jìn)程短暫運(yùn)用的資源，如數(shù)據(jù)資

3、源：“消費(fèi)者/消費(fèi)者算法中的信號量。它能夠引起死鎖。.2、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程在運(yùn)轉(zhuǎn)中具有異步性特征，多個進(jìn)程按向前推進(jìn)的順序有兩種情況：推進(jìn)順序合法推進(jìn)順序非法.3、 產(chǎn)生死鎖的必要條件構(gòu)成死鎖的四個必要條件四個條件都具備就會死鎖，缺一就不會死鎖.互斥條件：進(jìn)程對所分配到的資源進(jìn)展排他性運(yùn)用懇求和堅(jiān)持條件：進(jìn)程曾經(jīng)堅(jiān)持了至少一個資源，又提出新的資源懇求，而新懇求資源被其他進(jìn)程占有只能呵斥本身進(jìn)程阻塞，但對本人已獲得的其他資源堅(jiān)持不放，必然影響其他進(jìn)程。不剝奪條件：進(jìn)程已獲得的資源未運(yùn)用完之前不能被剝奪，只能在運(yùn)用完時由本人釋放。環(huán)路等待條件破壞這4個條件即是處置死鎖的方法.如哲學(xué)家就

4、餐問題的一種寫法，waitmutex waitleft waitrightsignal(mutex) signal(left) signal(left)會死鎖么？ .4、處置死鎖的根本方法事先預(yù)防：預(yù)防死鎖設(shè)置限制條件，破壞四個必要條件的一個或幾個，預(yù)防發(fā)生死鎖。較易實(shí)現(xiàn)。限制條件的嚴(yán)厲也會導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。防止死鎖不須事先限制，破壞四個必要條件，而是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不平安形狀，從而防止發(fā)生死鎖。這種事先加以較弱限制的方法，實(shí)現(xiàn)上有一定難度，但可獲較高的資源利用率及系統(tǒng)吞吐量，目前在較完善的系統(tǒng)中，常用此方法來防止發(fā)生死鎖。.事后處置：檢測死鎖

5、。允許系統(tǒng)運(yùn)轉(zhuǎn)過程中發(fā)生死鎖，但經(jīng)過系統(tǒng)檢測機(jī)構(gòu)可及時的檢測出，能準(zhǔn)確確定與死鎖有關(guān)的進(jìn)程和資源；然后采取適當(dāng)?shù)拇胧?，從系統(tǒng)中將已發(fā)生的死鎖去除掉。解除死鎖。與死鎖檢測配套的一種措施。常用的實(shí)施方法：撤銷或掛起一些進(jìn)程，以便回收一些資源并將他們分配給已阻塞進(jìn)程，使之轉(zhuǎn)為就緒以繼續(xù)運(yùn)轉(zhuǎn)。死鎖的檢測與解除措施，有能夠使系統(tǒng)獲得較好的資源利用率和吞吐量死鎖幾率不一定很高，但在實(shí)現(xiàn)上難度也最大。.第3章 處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測與解除 .五、預(yù)防死鎖的方法預(yù)防死鎖資源的排他性無法更改，故在其他3個條件上入手摒棄“懇求和堅(jiān)

6、持條件：一切進(jìn)程開場運(yùn)轉(zhuǎn)前，必需一次性的懇求其在整個運(yùn)轉(zhuǎn)過程所需的全部資源AND。算法簡單、易于實(shí)現(xiàn)且很平安。但缺陷是資源浪費(fèi)嚴(yán)重、或進(jìn)程延遲運(yùn)轉(zhuǎn)。摒棄“不剝奪條件：允許進(jìn)程先運(yùn)轉(zhuǎn)，但當(dāng)提出的新要求不被滿足時必需釋放它已堅(jiān)持的一切資源，待以后需求時再重新懇求。實(shí)現(xiàn)比較復(fù)雜且付出很大代價。能夠會呵斥前功盡棄，反復(fù)懇求和釋放等情況。.摒棄“環(huán)路等待條件有序設(shè)置資源：將一切資源按類型進(jìn)展線性排隊(duì)，賦予不同序號。一切進(jìn)程對資源的懇求必需嚴(yán)厲按照資源序號遞增的次序提出，這樣在所構(gòu)成的資源分配圖中，不能夠會出現(xiàn)環(huán)路。與前兩種戰(zhàn)略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。但也存在嚴(yán)重問題：資源編號限制新

7、設(shè)備的添加；運(yùn)用中的運(yùn)用設(shè)備順序與規(guī)定的順序并不協(xié)調(diào)；限制了用戶編程自在。.2.防止死鎖上述方法限制條件都太強(qiáng)；呵斥一定的運(yùn)用不便。采用防止死鎖的方法那么是只施加較弱限制條件，從而獲得令人稱心的系統(tǒng)性能。名詞：平安形狀：系統(tǒng)能按某種進(jìn)程順序?yàn)槊總€進(jìn)程分配所需資源，直至滿足每個進(jìn)程對資源的最大需求，并能順利完成。不平安形狀：系統(tǒng)無法找到一種使多個進(jìn)程可以順利分配資源執(zhí)行完的平安序列。.* 平安形狀、平安序列舉例假定三個進(jìn)程A、B和C，共有12臺磁帶機(jī)。假設(shè) t0 時辰，磁帶機(jī)資源分配情況如下表所示，此時系統(tǒng)能否處于平安形狀？進(jìn)程最大需求已分配還需可用A10553B422C927是平安的，由于存在

8、一個平安序列B,A,C只需系統(tǒng)按此進(jìn)程序列分配資源，就能使每個進(jìn)程都順利完成。.* 由平安形狀向不平安形狀的轉(zhuǎn)換每次資源分配時，都應(yīng)分析判別資源分配圖，看該次操作后能否有平安序列。假設(shè)沒有，闡明該操作會使系統(tǒng)進(jìn)入不平安形狀。只需使系一致直處于平安形狀，便可防止發(fā)生死鎖。不是一切的不平安形狀都是死鎖形狀。.3. 銀行家算法防止死鎖最有代表性的防止死鎖的算法，是Dijkstra的銀行家算法。由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。【思緒描畫】：隨時對系統(tǒng)中的一切資源信息進(jìn)展統(tǒng)計(jì)，包括每種資源的數(shù)量、已分配給各進(jìn)程的數(shù)量；每當(dāng)進(jìn)程提出某種資源懇求時判別該懇求分配后能否平安，假設(shè)平安才分配。對每

9、個資源懇求的處置都要保證系一致直從一個平安形狀到另一個平安形狀。.銀行家算法運(yùn)用之例 假定系統(tǒng)中有五個進(jìn)程P0,P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10、5、7，在T0時辰的資源分配情況如下圖。4 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P21 2 22 0 03 2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C 資源情況進(jìn)程.計(jì)算舉例：當(dāng)前T0時辰能否平安？利用平安性算法在下表找一個平安序列P1,P3,P4,P2,

10、P0，故是平安的。最后檢查應(yīng)是資源釋放完后又回到10、5、7 4 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P21 2 22 0 03 2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C 資源情況進(jìn)程5 3 2 7 4 3 7 4 5 10 4 7 10 5 7 .找平安序列的計(jì)算過程表True10 5 70 1 07 4 310 4 7P0True10 4 73 0 26 0 07 4 5P2True7 4 50 0 24 3 17 4 3P4T

11、rue 7 4 32 1 10 1 15 3 2P3True5 3 22 0 01 2 23 3 2P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 資源情況進(jìn)程.1T0時辰的初始形狀是平安的；2下面出現(xiàn)P1懇求資源的操作，詳細(xì)懇求向量為Request1(1,0,2)，利用銀行家算法進(jìn)展檢查該操作能否是平安可行的：1兩個根本判別Request1(1,0,2)=Need1(1,2,2)Request1(1,0,2)=Available1(3,3,2)2先假設(shè)為P1分配資源，并修正Available,Allocation1和

12、Need1向量。.3 Request1(1,0,2)后新的資源形狀表下再判別新資源形狀能否是平安的。找到一個平安序列P1,P3,P4,P0,P2，因此系統(tǒng)是平安的，該懇求是平安的，可將假設(shè)真正實(shí)施，將P1所懇求的資源分配給它。True10 5 73 0 26 0 07 5 5P2True7 5 50 1 07 4 37 4 5P0True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 23 0 20 2 02 3 0P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA

13、 B C 資源情況進(jìn)程 2 0 0+ 1 0 2 1 2 2 1 0 2 3 3 2 1 0 2.問：P4發(fā)出懇求向量Request4(3,3,0)，可否分配資源？1Request4(3,3,0)=Need4(4,3,1);2Request4(3,3,0)=Available(2,3,0),P4等待問：P0發(fā)出懇求向量Request0(0,2,0)，可否分配資源？1Request0(0,2,0)=Need0(7,4,3); 2Request0(0,2,0)=Available(2,3,0)；3系統(tǒng)暫時先假定可為P0分配資源，并修正有關(guān)數(shù)據(jù)，見下表：4 3 10 0 2P40 1 12 1 1P

14、36 0 03 0 2P20 2 03 0 2P12 1 07 2 30 3 0P0AvailableA B CNeedA B CAllocationA B C 資源情況進(jìn)程Available(2,1,0)不能滿足任何finish=false進(jìn)程的需求，假設(shè)分配會使系統(tǒng)進(jìn)入不平安形狀，所以不能分配資源。假設(shè)把P0發(fā)出的懇求向量改為Request0(0,1,0),系統(tǒng)能否能將資源分配給它，大家思索。7 3 32 2 00 2 0.算法實(shí)現(xiàn)闡明算法實(shí)現(xiàn):首先：需求的一些數(shù)據(jù)構(gòu)造再次：算法過程中心：平安性判別算法.1銀行家算法中的數(shù)據(jù)構(gòu)造1各類可利用資源的數(shù)量向量Available ：i1，i2，i

15、m，含m個元素，每個元素代表一類可利用的資源數(shù)目。動態(tài)變化的，初始值是系統(tǒng)配置的該類資源的全部數(shù)目，值隨資源的分配與回收而動態(tài)的改動。實(shí)現(xiàn)：一維數(shù)組。Available【j】=K，表示系統(tǒng)中Rj類資源現(xiàn)有可用數(shù)量為K個。 m類資源，n個并發(fā)進(jìn)程對其產(chǎn)生需求.2每個進(jìn)程對每類資源的需求最大需求、已獲得的、還需求的最大需求矩陣Maxn*m，系統(tǒng)中n個進(jìn)程中每個進(jìn)程分別對m類資源的最大需求。取值：根據(jù)進(jìn)程需求賦初始值。實(shí)現(xiàn)：二維數(shù)組。Max【i，j】=K，表示進(jìn)程 i 需求Rj類資源的最大數(shù)目為K。.已分配矩陣Allocation。n*m，定義系統(tǒng)中每一進(jìn)程已獲得的每類資源數(shù)量。Allocation

16、【i，j】=K，表示進(jìn)程i當(dāng)前已分得Rj類資源數(shù)為K。還需求的矩陣Need。n*m，表示每一進(jìn)程尚需的各類資源數(shù)。Need【i，j】=K，表示進(jìn)程i還需求Rj類資源K個，方能完成義務(wù)。上述三個矩陣存在關(guān)系：Max【i，j】= Allocation【i，j】+Need【i，j】每次，給進(jìn)程 i 分配資源的動作，影響上述數(shù)據(jù)構(gòu)造的取值：Available【 】，Allocation【i，】，Need【i，】.2防止死鎖的算法過程銀行家算法當(dāng)前資源分配形狀如何？構(gòu)建資源分配表判別向下運(yùn)轉(zhuǎn)過程中，各進(jìn)程對資源的需求能否平安。在當(dāng)前資源分配形狀根底上，分析進(jìn)程的實(shí)踐懇求Requesti【j】= k。表示

17、進(jìn)程Pi需求K個Rj類型的資源。進(jìn)程MAXA B CAllocationA B CNeedA B CAvailableA B CP0 7 5 3 2 3 2 5 2 1 4 3 2P1 5 4 2 2 2 1 3 2 1P2 2 1 1 1 0 0 1 1 1資源情況Request02，2，1.算法過程：就是對各進(jìn)程的Request向量及資源數(shù)量進(jìn)展一系列判別及值操作。進(jìn)程Pi發(fā)出資源懇求后，系統(tǒng)按下述步驟進(jìn)展檢查：首先是兩個根本判別：1IF Requestij= Needi,j THEN 轉(zhuǎn)向步驟2；ELSE 以為出錯，所需資源數(shù)超越宣布的最大值自我矛盾)2IF Requestij= Ava

18、ilablejTHEN 轉(zhuǎn)向步驟3；ELSE 表示尚無足夠資源，Pi需等待現(xiàn)實(shí)不滿足.假設(shè)上面兩步判別都經(jīng)過了，進(jìn)入本質(zhì)的資源分析3系統(tǒng)試探著把資源分配給進(jìn)程Pi ，并修正相應(yīng)數(shù)據(jù)構(gòu)造的值假設(shè)性操作： Available【j】= Allocation【i,j】= Need【i,j】= 4系統(tǒng)執(zhí)行平安性算法，判別新的資源分配形狀能否是平安的。即：找一個平安序列，使這些進(jìn)程按順序執(zhí)行完假設(shè)可以找到，那么將假設(shè)操作真正實(shí)施完成資源分配。Available【j】 - Requesti【j】;Allocation【i,j】+ Requesti【j】;Need【i,j】- Requesti【j】;懇求前的

19、資源分配形狀 新的資源分配形狀平安性算法.3平安性算法1需求一些記錄信息的數(shù)據(jù)構(gòu)造，設(shè)置兩個向量：任務(wù)向量work算法開場時work=Available;系統(tǒng)找平安序列的過程需求不斷判別和修正當(dāng)前資源數(shù)量，不能直接修正原始數(shù)據(jù)記錄Aailable。標(biāo)志向量Finish表示每個進(jìn)程能否有足夠的資源使之運(yùn)轉(zhuǎn)完成。開場時所以進(jìn)程都設(shè)置初值Finishi:=false; 找平安序列的過程相當(dāng)于使一切Finishi:=true。.2找平安序列的過程從 Finishi = false 的進(jìn)程集合中找一個進(jìn)程IF Needi,j = workjTHEN 執(zhí)行步驟 a;ELSE 執(zhí)行步驟 b; a 假設(shè)Pi獲

20、得資源順利執(zhí)行完，釋放出分配給它的資源，修正相應(yīng)的值： work【j】 = work【i】+ Allocation【i，j】; Finish【i】= true; goto step 2; /前往去繼續(xù)找下一個進(jìn)程。b當(dāng)算法不再在2、a步間循環(huán)找進(jìn)程，到達(dá)本步時，假設(shè)一切Finishi=true都滿足，那么表示一切進(jìn)程都按某個順序執(zhí)行完了，系統(tǒng)處于平安形狀；否那么，系統(tǒng)當(dāng)前所處的資源分配形狀是不平安形狀。.第3章 處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測與解除 .六、死鎖的檢測與解除當(dāng)系統(tǒng)為進(jìn)程分配資源時，假設(shè)未采取任何限制性措施

21、，那么系統(tǒng)必需提供檢測和解除死鎖的手段，為此系統(tǒng)必需：保管有關(guān)資源的懇求和分配信息；提供一種算法，以利用這些信息來檢測系統(tǒng)能否已進(jìn)入死鎖形狀。.1、資源分配圖系統(tǒng)死鎖可利用資源分配圖來描畫。圓圈表示進(jìn)程方框表示一類資源，其中的一個點(diǎn)代表一個該類資源懇求邊由進(jìn)程指向方框中的資源分配邊那么由方框中的一個點(diǎn)即資源。 r1r2 P2P1.2、死鎖定理利用資源分配圖簡化法來檢測死鎖。簡化方法如下：1.在資源分配圖中找出一個既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi，在順利的情況下運(yùn)轉(zhuǎn)終了，釋放其占有的全部資源。2.由于釋放了資源，這樣能使其它被阻塞的進(jìn)程獲得資源繼續(xù)運(yùn)轉(zhuǎn)。消去了Pi的邊。3.經(jīng)過一系列簡化后，假設(shè)能消去圖中一切邊，使結(jié)點(diǎn)都孤立，稱該圖是可完全簡化的。S形狀為死鎖形狀的充分條件是當(dāng)且僅當(dāng)S形狀的資源分配圖是不可完全簡化的。.例：根據(jù)死鎖定理判別如下所示的資源分配圖能否存在死鎖。P1P2P3R1R2R3P1P3P2R1R2圖1圖2.3、 死鎖的解除當(dāng)發(fā)現(xiàn)進(jìn)程死鎖時，便應(yīng)立刻把它們從死鎖形狀中解脫出來。常采