死鎖銀行家算法

第3章處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時(shí)調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除1/4/20241山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系關(guān)于死鎖多道程序系統(tǒng)借助并發(fā)執(zhí)行改善資源利用率，提高系統(tǒng)吞吐量，但能夠發(fā)生一種危險(xiǎn)——死鎖。死鎖〔Deadlock〕：指多個(gè)進(jìn)程在運(yùn)轉(zhuǎn)過程中，因爭(zhēng)奪資源而呵斥的一種僵局。當(dāng)進(jìn)程處于這種形狀時(shí)，假設(shè)無外力作用，它們都將無法再向前推進(jìn)。1/4/20242山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系找緣由分析構(gòu)成條件根據(jù)分析，找出處置死鎖的方法四、產(chǎn)生死鎖的緣由和必要條件1/4/20243山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系例：運(yùn)用信號(hào)量呵斥死鎖的典型 P1 P2wait〔D〕 wait〔E〕wait〔E〕 wait〔D〕signal〔D〕 signal〔E〕signal〔E〕 signal〔D〕 死鎖發(fā)生：雙方都擁有部分資源，同時(shí)在懇求對(duì)方已占有的資源。懇求推進(jìn)的次序與對(duì)非剝奪性資源的爭(zhēng)用都是呵斥死鎖的緣由。1/4/20244山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系產(chǎn)生死鎖的緣由可歸結(jié)為如下兩點(diǎn)：競(jìng)爭(zhēng)資源。系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等的數(shù)目不滿足需求時(shí)，會(huì)引起資源競(jìng)爭(zhēng)而產(chǎn)生死鎖。進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)轉(zhuǎn)過程中，懇求和釋放資源的順序不當(dāng)，同樣會(huì)導(dǎo)致死鎖。1/4/20245山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系1、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖可把系統(tǒng)中的資源分為兩類：可剝奪和非剝奪性資源可剝奪性資源：分配給進(jìn)程后可以被高優(yōu)先級(jí)的進(jìn)程剝奪。如CPU和主存。不可剝奪性資源：分配給進(jìn)程后只能在進(jìn)程用完后釋放。如磁帶機(jī)、打印機(jī)等。永久性資源和暫時(shí)性資源永久性：打印機(jī)?？身樞蚍磸?fù)運(yùn)用暫時(shí)性：進(jìn)程產(chǎn)生被其他進(jìn)程短暫運(yùn)用的資源，如數(shù)據(jù)資源：“消費(fèi)者/消費(fèi)者〞算法中的信號(hào)量。。它能夠引起死鎖。1/4/20246山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系2、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程在運(yùn)轉(zhuǎn)中具有異步性特征，多個(gè)進(jìn)程按向前推進(jìn)的順序有兩種情況：推進(jìn)順序合法推進(jìn)順序非法1/4/20247山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系3、產(chǎn)生死鎖的必要條件構(gòu)成死鎖的四個(gè)必要條件〔四個(gè)條件都具備就會(huì)死鎖，缺一就不會(huì)死鎖〕1/4/20248山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系互斥條件：進(jìn)程對(duì)所分配到的資源進(jìn)展排他性運(yùn)用懇求和堅(jiān)持條件：進(jìn)程曾經(jīng)堅(jiān)持了至少一個(gè)資源，又提出新的資源懇求，而新懇求資源被其他進(jìn)程占有只能呵斥本身進(jìn)程阻塞，但對(duì)本人已獲得的其他資源堅(jiān)持不放，必然影響其他進(jìn)程。不剝奪條件：進(jìn)程已獲得的資源未運(yùn)用完之前不能被剝奪，只能在運(yùn)用完時(shí)由本人釋放。環(huán)路等待條件破壞這4個(gè)條件即是處置死鎖的方法1/4/20249山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系如哲學(xué)家就餐問題的一種寫法，wait〔mutex〕wait〔left〕wait〔right〕signal(mutex)signal(left)signal(left)會(huì)死鎖么？1/4/202410山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系4、處置死鎖的根本方法事先預(yù)防：預(yù)防死鎖設(shè)置限制條件，破壞四個(gè)必要條件的一個(gè)或幾個(gè)，預(yù)防發(fā)生死鎖。較易實(shí)現(xiàn)。限制條件的嚴(yán)厲也會(huì)導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。防止死鎖不須事先限制，破壞四個(gè)必要條件，而是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不平安形狀，從而防止發(fā)生死鎖。這種事先加以較弱限制的方法，實(shí)現(xiàn)上有一定難度，但可獲較高的資源利用率及系統(tǒng)吞吐量，目前在較完善的系統(tǒng)中，常用此方法來防止發(fā)生死鎖。1/4/202411山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系事后處置：檢測(cè)死鎖。允許系統(tǒng)運(yùn)轉(zhuǎn)過程中發(fā)生死鎖，但經(jīng)過系統(tǒng)檢測(cè)機(jī)構(gòu)可及時(shí)的檢測(cè)出，能準(zhǔn)確確定與死鎖有關(guān)的進(jìn)程和資源；然后采取適當(dāng)?shù)拇胧瑥南到y(tǒng)中將已發(fā)生的死鎖去除掉。解除死鎖。與死鎖檢測(cè)配套的一種措施。常用的實(shí)施方法：撤銷或掛起一些進(jìn)程，以便回收一些資源并將他們分配給已阻塞進(jìn)程，使之轉(zhuǎn)為就緒以繼續(xù)運(yùn)轉(zhuǎn)。死鎖的檢測(cè)與解除措施，有能夠使系統(tǒng)獲得較好的資源利用率和吞吐量〔死鎖幾率不一定很高〕，但在實(shí)現(xiàn)上難度也最大。1/4/202412山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系第3章處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時(shí)調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除1/4/202413山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系五、預(yù)防死鎖的方法預(yù)防死鎖資源的排他性無法更改，故在其他3個(gè)條件上入手摒棄“懇求和堅(jiān)持〞條件：一切進(jìn)程開場(chǎng)運(yùn)轉(zhuǎn)前，必需一次性的懇求其在整個(gè)運(yùn)轉(zhuǎn)過程所需的全部資源〔AND〕。算法簡(jiǎn)單、易于實(shí)現(xiàn)且很平安。但缺陷是資源浪費(fèi)嚴(yán)重、或進(jìn)程延遲運(yùn)轉(zhuǎn)。摒棄“不剝奪〞條件：允許進(jìn)程先運(yùn)轉(zhuǎn)，但當(dāng)提出的新要求不被滿足時(shí)必需釋放它已堅(jiān)持的一切資源，待以后需求時(shí)再重新懇求。實(shí)現(xiàn)比較復(fù)雜且付出很大代價(jià)。能夠會(huì)呵斥前功盡棄，反復(fù)懇求和釋放等情況。1/4/202414山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系摒棄“環(huán)路等待〞條件有序設(shè)置資源：將一切資源按類型進(jìn)展線性排隊(duì)，賦予不同序號(hào)。一切進(jìn)程對(duì)資源的懇求必需嚴(yán)厲按照資源序號(hào)遞增的次序提出，這樣在所構(gòu)成的資源分配圖中，不能夠會(huì)出現(xiàn)環(huán)路。與前兩種戰(zhàn)略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。但也存在嚴(yán)重問題：資源編號(hào)限制新設(shè)備的添加；運(yùn)用中的運(yùn)用設(shè)備順序與規(guī)定的順序并不協(xié)調(diào)；限制了用戶編程自在。1/4/202415山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系2.防止死鎖上述方法限制條件都太強(qiáng)；呵斥一定的運(yùn)用不便。采用防止死鎖的方法那么是只施加較弱限制條件，從而獲得令人稱心的系統(tǒng)性能。名詞：平安形狀：系統(tǒng)能按某種進(jìn)程順序?yàn)槊總€(gè)進(jìn)程分配所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，并能順利完成。不平安形狀：系統(tǒng)無法找到一種使多個(gè)進(jìn)程可以順利分配資源執(zhí)行完的平安序列。1/4/202416山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系*平安形狀、平安序列舉例假定三個(gè)進(jìn)程A、B和C，共有12臺(tái)磁帶機(jī)。假設(shè)t0時(shí)辰，磁帶機(jī)資源分配情況如下表所示，此時(shí)系統(tǒng)能否處于平安形狀？進(jìn)程最大需求已分配還需可用A10553B422C927是平安的，由于存在一個(gè)平安序列B,A,C只需系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。1/4/202417山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系*由平安形狀向不平安形狀的轉(zhuǎn)換每次資源分配時(shí)，都應(yīng)分析判別資源分配圖，看該次操作后能否有平安序列。假設(shè)沒有，闡明該操作會(huì)使系統(tǒng)進(jìn)入不平安形狀。只需使系一致直處于平安形狀，便可防止發(fā)生死鎖。不是一切的不平安形狀都是死鎖形狀。1/4/202418山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系3.銀行家算法防止死鎖 最有代表性的防止死鎖的算法，是Dijkstra的銀行家算法。由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。 【思緒描畫】：隨時(shí)對(duì)系統(tǒng)中的一切資源信息進(jìn)展統(tǒng)計(jì)，包括每種資源的數(shù)量、已分配給各進(jìn)程的數(shù)量；每當(dāng)進(jìn)程提出某種資源懇求時(shí)判別該懇求分配后能否平安，假設(shè)平安才分配。對(duì)每個(gè)資源懇求的處置都要保證系一致直從一個(gè)平安形狀到另一個(gè)平安形狀。1/4/202419山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系銀行家算法運(yùn)用之例假定系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時(shí)辰的資源分配情況如下圖。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進(jìn)程1/4/202420山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系計(jì)算舉例：當(dāng)前T0時(shí)辰能否平安？利用平安性算法在下表找一個(gè)平安序列{P1,P3,P4,P2,P0}，故是平安的?！沧詈髾z查應(yīng)是資源釋放完后又回到10、5、7〕431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進(jìn)程532743745104710571/4/202421山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系找平安序列的計(jì)算過程表True10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進(jìn)程1/4/202422山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系〔1〕T0時(shí)辰的初始形狀是平安的；〔2〕下面出現(xiàn)P1懇求資源的操作，詳細(xì)懇求向量為Request1(1,0,2)，利用銀行家算法進(jìn)展檢查該操作能否是平安可行的：1〕兩個(gè)根本判別 Request1(1,0,2)<=Need1(1,2,2) Request1(1,0,2)<=Available1(3,3,2)2〕先假設(shè)為P1分配資源，并修正Available,Allocation1和Need1向量。1/4/202423山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系3〕Request1(1,0,2)后新的資源形狀表下再判別新資源形狀能否是平安的。找到一個(gè)平安序列{P1,P3,P4,P0,P2}，因此系統(tǒng)是平安的，該懇求是平安的，可將假設(shè)真正實(shí)施，將P1所懇求的資源分配給它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進(jìn)程200+102122—102332—1021/4/202424山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系問：P4發(fā)出懇求向量Request4(3,3,0)，可否分配資源？1〕Request4(3,3,0)<=Need4(4,3,1);2〕Request4(3,3,0)<=Available(2,3,0),P4等待問：P0發(fā)出懇求向量Request0(0,2,0)，可否分配資源？1〕Request0(0,2,0)<=Need0(7,4,3);2〕Request0(0,2,0)<=Available(2,3,0)；3〕系統(tǒng)暫時(shí)先假定可為P0分配資源，并修正有關(guān)數(shù)據(jù)，見下表：431002P4011211P3600302P2020302P1210723030P0AvailableABCNeedABCAllocationABC資源情況進(jìn)程Available(2,1,0)不能滿足任何finish=false進(jìn)程的需求，假設(shè)分配會(huì)使系統(tǒng)進(jìn)入不平安形狀，所以不能分配資源。假設(shè)把P0發(fā)出的懇求向量改為Request0(0,1,0),系統(tǒng)能否能將資源分配給它，大家思索。7332200201/4/202425山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系算法實(shí)現(xiàn)闡明算法實(shí)現(xiàn):首先：需求的一些數(shù)據(jù)構(gòu)造再次：算法過程中心：平安性判別算法1/4/202426山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系1〕銀行家算法中的數(shù)據(jù)構(gòu)造〔1〕各類可利用資源的數(shù)量向量Available：〔i1，i2，…，im〕，含m個(gè)元素，每個(gè)元素代表一類可利用的資源數(shù)目。動(dòng)態(tài)變化的，初始值是系統(tǒng)配置的該類資源的全部數(shù)目，值隨資源的分配與回收而動(dòng)態(tài)的改動(dòng)。實(shí)現(xiàn)：一維數(shù)組。Available【j】=K，表示系統(tǒng)中Rj類資源現(xiàn)有可用數(shù)量為K個(gè)。m類資源，n個(gè)并發(fā)進(jìn)程對(duì)其產(chǎn)生需求1/4/202427山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系〔2〕每個(gè)進(jìn)程對(duì)每類資源的需求最大需求、已獲得的、還需求的最大需求矩陣Maxn*m，系統(tǒng)中n個(gè)進(jìn)程中每個(gè)進(jìn)程分別對(duì)m類資源的最大需求。取值：根據(jù)進(jìn)程需求賦初始值。實(shí)現(xiàn)：二維數(shù)組。Max【i，j】=K，表示進(jìn)程i需求Rj類資源的最大數(shù)目為K。1/4/202428山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系已分配矩陣Allocation。n*m，定義系統(tǒng)中每一進(jìn)程已獲得的每類資源數(shù)量。Allocation【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個(gè)，方能完成義務(wù)。上述三個(gè)矩陣存在關(guān)系： Max【i，j】=Allocation【i，j】+Need【i，j】每次，給進(jìn)程i分配資源的動(dòng)作，影響上述數(shù)據(jù)構(gòu)造的取值： Available【】，Allocation【i，】，Need【i，】1/4/202429山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系2〕防止死鎖的算法過程〔銀行家算法〕當(dāng)前資源分配形狀如何？構(gòu)建資源分配表判別向下運(yùn)轉(zhuǎn)過程中，各進(jìn)程對(duì)資源的需求能否平安。 在當(dāng)前資源分配形狀根底上，分析進(jìn)程的實(shí)踐懇求Requesti【j】=k。表示進(jìn)程Pi需求K個(gè)Rj類型的資源。進(jìn)程MAXABCAllocationABCNeedABCAvailableABCP0753232521432P1542221321P2211100111資源情況Request0〔2，2，1〕1/4/202430山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系算法過程：

就是對(duì)各進(jìn)程的Request向量及資源數(shù)量進(jìn)展一系列判別及值操作。進(jìn)程Pi發(fā)出資源懇求后，系統(tǒng)按下述步驟進(jìn)展檢查：首先是兩個(gè)根本判別：〔1〕IFRequesti[j]<=Need[i,j] THEN轉(zhuǎn)向步驟2； ELSE以為出錯(cuò)，所需資源數(shù)超越宣布的最大值〔自我矛盾)〔2〕IFRequesti[j]<=Available[j] THEN轉(zhuǎn)向步驟3； ELSE表示尚無足夠資源，Pi需等待〔現(xiàn)實(shí)不滿足〕1/4/202431山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系假設(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í)行平安性算法，判別新的資源分配形狀能否是平安的。 即：找一個(gè)平安序列，使這些進(jìn)程按順序執(zhí)行完〕假設(shè)可以找到，那么將假設(shè)操作真正實(shí)施完成資源分配。Available【j】-Requesti【j】;Allocation【i,j】+Requesti【j】;Need【i,j】 -Requesti【j】;懇求前的資源分配形狀新的資源分配形狀平安性算法1/4/202432山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系3〕平安性算法〔1〕需求一些記錄信息的數(shù)據(jù)構(gòu)造，設(shè)置兩個(gè)向量：任務(wù)向量work算法開場(chǎng)時(shí)work=Available;系統(tǒng)找平安序列的過程需求不斷判別和修正當(dāng)前資源數(shù)量，不能直接修正原始數(shù)據(jù)記錄Aailable。標(biāo)志向量Finish表示每個(gè)進(jìn)程能否有足夠的資源使之運(yùn)轉(zhuǎn)完成。開場(chǎng)時(shí)所以進(jìn)程都設(shè)置初值Finish[i]:=false;找平安序列的過程相當(dāng)于使一切Finish[i]:=true。1/4/202433山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系〔2〕找平安序列的過程 從Finish[i]=false的進(jìn)程集合中找一個(gè)進(jìn)程 IFNeed[i,j]<=work[j] THEN執(zhí)行步驟a; ELSE執(zhí)行步驟b; a〕假設(shè)Pi獲得資源順利執(zhí)行完，釋放出分配給它的資源，修正相應(yīng)的值：work【j】=work【i】+Allocation【i，j】;Finish【i】=true;gotostep〔2〕;//前往去繼續(xù)找下一個(gè)進(jìn)程。 b〕當(dāng)算法不再在〔2〕、a〕步間循環(huán)找進(jìn)程，到達(dá)本步時(shí)，假設(shè)一切Finish[i]=true都滿足，那么表示一切進(jìn)程都按某個(gè)順序執(zhí)行完了，系統(tǒng)處于平安形狀；否那么，系統(tǒng)當(dāng)前所處的資源分配形狀是不平安形狀。1/4/202434山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系第3章處置機(jī)調(diào)度與死鎖處置機(jī)調(diào)度相關(guān)根本概念常用調(diào)度算法實(shí)時(shí)調(diào)度產(chǎn)生死鎖的緣由和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除1/4/202435山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系六、死鎖的檢測(cè)與解除當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，假設(shè)未采取任何限制性措施，那么系統(tǒng)必需提供檢測(cè)和解除死鎖的手段，為此系統(tǒng)必需：保管有關(guān)資源的懇求和分配信息；提供一種算法，以利用這些信息來檢測(cè)系統(tǒng)能否已進(jìn)入死鎖形狀。1/4/202436山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系1、資源分配圖系統(tǒng)死鎖可利用資源分配圖來描畫。圓圈表示進(jìn)程方框表示一類資源，其中的一個(gè)點(diǎn)代表一個(gè)該類資源懇求邊由進(jìn)程指向方框中的資源分配邊那么由方框中的一個(gè)點(diǎn)即資源。r1r2P2P11/4/202437山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系2、死鎖定理利用資源分配圖簡(jiǎn)化法來檢測(cè)死鎖。簡(jiǎn)化方法如下： 1.在資源分配圖中找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi，在順利的情況下運(yùn)轉(zhuǎn)終了，釋放其占有的全部資源。 2.由于釋放了資源，這樣能使其它被阻塞的進(jìn)程獲得資源繼續(xù)運(yùn)轉(zhuǎn)。消去了Pi的邊。 3.經(jīng)過一系列簡(jiǎn)化后，假設(shè)能消去圖中一切邊，使結(jié)點(diǎn)都孤立，稱該圖是可完全簡(jiǎn)化的。S形狀為死鎖形狀的充分條件是當(dāng)且僅當(dāng)S形狀的資源分配圖是不可完全簡(jiǎn)化的。<死鎖定理>1/4/202438山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系例：根據(jù)死鎖定理判別如下所示的資源分配圖能否存在死鎖?！稹稹稹餚1P2P3R1R2R3P1P3P2○○R1