第四章-死鎖及其對(duì)策課件

第四章死鎖及其對(duì)策4.1死鎖的基本概念4.2死鎖原理及對(duì)策4.3鴕鳥(niǎo)算法4.4死鎖的檢測(cè)和恢復(fù)4.5死鎖預(yù)防4.6死鎖避免今天日期：9/18/20231第四章死鎖及其對(duì)策第四章死鎖及其對(duì)策4.1死鎖的基本概念今天日期：8/4.1死鎖的基本概念在計(jì)算機(jī)系統(tǒng)中，產(chǎn)生死鎖的直接原因是多個(gè)進(jìn)程的并發(fā)執(zhí)行。多個(gè)進(jìn)程的并發(fā)執(zhí)行改善了系統(tǒng)資源的利用率，提高了系統(tǒng)的處理能力，但由于每個(gè)系統(tǒng)資源都由多個(gè)進(jìn)程共享，有些資源本身又要求互斥的使用，所以如果處理不當(dāng)就可能產(chǎn)生死鎖。今天日期：9/18/20232第四章死鎖及其對(duì)策4.1死鎖的基本概念在計(jì)算機(jī)系統(tǒng)中，產(chǎn)生死鎖的直接原因是4.1.1資源依資源的性質(zhì)：可剝奪和非可剝奪資源

可剝奪資源：處理機(jī)和內(nèi)存

非可剝奪資源：磁帶和打印機(jī)依資源的使用方式：共享資源和獨(dú)享資源

共享資源：處理機(jī)、內(nèi)存、磁盤(pán)等

獨(dú)享資源：磁帶機(jī)、讀卡機(jī)和打印機(jī)等依資源的使用期限：永久資源和臨時(shí)資源

永久資源：硬資源和可重入的純代碼過(guò)程

臨時(shí)資源：進(jìn)程同步和通信過(guò)程中出現(xiàn)的消息、信號(hào)的數(shù)據(jù)。在進(jìn)行資源分配時(shí)，一定要先認(rèn)清相應(yīng)資源的特性，以便選擇合適的分配策略，在競(jìng)爭(zhēng)非剝奪資源和臨時(shí)性資源時(shí)都可能產(chǎn)生死鎖。在并發(fā)進(jìn)程的活動(dòng)中，若選擇一種合理的推進(jìn)順序就可以避免死鎖的發(fā)生。今天日期：9/18/20233第四章死鎖及其對(duì)策4.1.1資源今天日期：8/6/20233第四章死4.1.2死鎖的定義死鎖是計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或兩個(gè)以上的進(jìn)程由于競(jìng)爭(zhēng)系統(tǒng)資源而出現(xiàn)的一種互相等待的現(xiàn)象。此時(shí)，每個(gè)進(jìn)程都“占用”一些其他進(jìn)程正在等待的資源，而用，每個(gè)進(jìn)程都沒(méi)有完全得到所有的資源，結(jié)果所有這些進(jìn)程互相等待，誰(shuí)也無(wú)法繼續(xù)，我們稱這些進(jìn)程是死鎖的，相應(yīng)的計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)。今天日期：9/18/20234第四章死鎖及其對(duì)策4.1.2死鎖的定義今天日期：8/6/20234第四章4.1.3產(chǎn)生死鎖的原因系統(tǒng)競(jìng)爭(zhēng)臨界資源。當(dāng)系統(tǒng)所擁有的某種臨界資源個(gè)數(shù)比各個(gè)進(jìn)程要求該資源的總數(shù)要少時(shí)，則有可能引起多個(gè)并發(fā)進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。進(jìn)程推進(jìn)順序不當(dāng)，進(jìn)程運(yùn)行過(guò)程中，由于請(qǐng)示和釋放資源的順序不當(dāng)，而產(chǎn)生死鎖。今天日期：9/18/20235第四章死鎖及其對(duì)策4.1.3產(chǎn)生死鎖的原因今天日期：8/6/20235第四1、競(jìng)爭(zhēng)臨界資源引起的死鎖

競(jìng)爭(zhēng)非剝奪性資源引起的死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖競(jìng)爭(zhēng)同一類資源引起的死鎖2、進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖今天日期：9/18/20236第四章死鎖及其對(duì)策1、競(jìng)爭(zhēng)臨界資源引起的死鎖今天日期：8/6/20236第四章0G1G2G3A1B1C1D1P1進(jìn)展P2進(jìn)展A2B2C2D2占用R2占用R21DN2占用R1占用R23占用R1占用R1R2(讀卡機(jī))R1（打印機(jī)）今天日期：9/18/20237第四章死鎖及其對(duì)策0G1G2G3A1B1C1D1P1進(jìn)展P2進(jìn)展A2B2C2D4.2死鎖原理及對(duì)策4.2.1死鎖原理及產(chǎn)生死鎖的必要條件

死鎖是與時(shí)間有關(guān)的一種現(xiàn)象，它涉及到多進(jìn)程的并發(fā)，并發(fā)進(jìn)程對(duì)一些特殊資源的共享，以及具體進(jìn)行并發(fā)進(jìn)程資源調(diào)度的時(shí)機(jī)等。綜上所述，產(chǎn)生死鎖的四個(gè)必要條件如下：互斥條件、不可剝奪條件、部分分配條件、環(huán)路等待條件今天日期：9/18/20238第四章死鎖及其對(duì)策4.2死鎖原理及對(duì)策4.2.1死鎖原理及產(chǎn)生死鎖的必要4.2.2死鎖的描述1、資源分配圖P2P1R1R2今天日期：9/18/20239第四章死鎖及其對(duì)策4.2.2死鎖的描述P2P1R1R2今天日期：8/6/22、死鎖舉例競(jìng)爭(zhēng)非剝奪性資源引起的死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖競(jìng)爭(zhēng)同一類資源引起的死鎖R1P1R2P2S1P1S3P3P2S2P1P2P3今天日期：9/18/202310第四章死鎖及其對(duì)策2、死鎖舉例競(jìng)爭(zhēng)非剝奪性資源引起的死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起的死4.2.3解決死鎖的方法1.預(yù)防死鎖：為了使系統(tǒng)不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計(jì)初期即選擇一些限制條件，來(lái)破壞產(chǎn)生死鎖的四個(gè)必要條件之一或其中幾個(gè)。這樣，系統(tǒng)中就不會(huì)出現(xiàn)死鎖現(xiàn)象。2.避免死鎖：一方面預(yù)防死鎖的方法會(huì)降低系統(tǒng)資源利用率；另一方面死鎖的必要條件在存在未必就一定會(huì)使系統(tǒng)發(fā)生死鎖。因此為提高系統(tǒng)資源的利用率，避免死鎖并不嚴(yán)格限制死鎖必要條件的存在，而是在資源的動(dòng)態(tài)分配過(guò)程中，使用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的最終出現(xiàn)。今天日期：9/18/202311第四章死鎖及其對(duì)策4.2.3解決死鎖的方法今天日期：8/6/202311第3.檢測(cè)和解除死鎖：在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防和避免死鎖而增加的系統(tǒng)開(kāi)銷，又因?yàn)樗梨i產(chǎn)生的概率總是比較小的，所以系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門(mén)設(shè)置了一個(gè)檢測(cè)機(jī)構(gòu)，可以隨時(shí)檢測(cè)出死鎖的發(fā)生，并能確定與死鎖有關(guān)的進(jìn)程和資源，然后采用適當(dāng)?shù)姆椒ń獬到y(tǒng)中的死鎖狀態(tài)。常用的方法有：一是強(qiáng)制性的撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其余進(jìn)程；一是使用一個(gè)有效的掛起和解除掛起機(jī)構(gòu)來(lái)掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪一些資源用來(lái)解除死鎖。今天日期：9/18/202312第四章死鎖及其對(duì)策3.檢測(cè)和解除死鎖：在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防和避免4.4死鎖的檢測(cè)與恢復(fù)檢測(cè)系統(tǒng)中是否存在死鎖產(chǎn)生的必要條件：環(huán)路等待4.4.1利用資源分配圖描述系統(tǒng)狀態(tài)1、死鎖狀態(tài)的推斷思想封鎖進(jìn)程：是指某個(gè)進(jìn)程由于請(qǐng)求了超過(guò)系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進(jìn)程。非封鎖進(jìn)程：沒(méi)有被系統(tǒng)封鎖的進(jìn)程今天日期：9/18/202313第四章死鎖及其對(duì)策4.4死鎖的檢測(cè)與恢復(fù)檢測(cè)系統(tǒng)中是否存在死鎖產(chǎn)生的必要條2、資源分配圖的化簡(jiǎn)

假設(shè)某個(gè)資源分配圖中存在一個(gè)進(jìn)程Pi，此刻Pi是非封鎖進(jìn)程，那么可對(duì)此資源分配圖作以下化簡(jiǎn)：當(dāng)Pi有請(qǐng)求邊時(shí)，首先將其請(qǐng)求邊變成分配邊，即滿足Pi進(jìn)程的相應(yīng)資源請(qǐng)求，而一旦Pi進(jìn)程的所有資源請(qǐng)求都得到滿足，Pi進(jìn)程就能在有限時(shí)間內(nèi)運(yùn)行結(jié)束，并釋放它所占用的所有資源。所以此時(shí)Pi只有分配邊，可以將所有這些分配邊刪去。

總之，對(duì)非封鎖進(jìn)程Pi的化簡(jiǎn)即刪除資源分配圖中與Pi連接的所有有向邊，使Pi成為孤立結(jié)點(diǎn)。P2P1R1R2P2P1R1R2P2P1R1R2(a)(b)(c)今天日期：9/18/202314第四章死鎖及其對(duì)策2、資源分配圖的化簡(jiǎn)總之，對(duì)非封鎖進(jìn)程Pi的化簡(jiǎn)即刪除假如一個(gè)資源分配圖可以被其上的所有進(jìn)程所化簡(jiǎn)，則稱該圖為完全可化簡(jiǎn)的。反之，若一個(gè)資源分配圖不能被其上的任一進(jìn)程化簡(jiǎn)，則稱其為不可化簡(jiǎn)的。若某個(gè)資源分配圖只能被其上的一些進(jìn)程所化簡(jiǎn)，則該圖為非完全可化簡(jiǎn)的。P2P1R1R2圖完全可化簡(jiǎn)的資源分配圖P2P1R1R2圖不可化簡(jiǎn)的資源分配圖今天日期：9/18/202315第四章死鎖及其對(duì)策假如一個(gè)資源分配圖可以被其上的所有進(jìn)程所化簡(jiǎn)，則稱該圖為完全3、死鎖定理：當(dāng)一個(gè)資源分配圖是完全可化簡(jiǎn)時(shí)，該資源分配圖能被其上所有的進(jìn)程所化簡(jiǎn)。也就是此時(shí)系統(tǒng)中存在一個(gè)進(jìn)程序列，按此安全序列的順序運(yùn)行，可使每個(gè)進(jìn)程都順利完成，所以此時(shí)系統(tǒng)處于安全狀態(tài)，即系統(tǒng)不會(huì)發(fā)生死鎖。反之當(dāng)某資源分配圖是非完全可化簡(jiǎn)的時(shí)候，說(shuō)明該資源分配圖不能被中的一些進(jìn)程所化簡(jiǎn)。也就是此刻系統(tǒng)中出現(xiàn)了一些互相等待的封鎖進(jìn)程，系統(tǒng)中不存在一個(gè)進(jìn)程的安全序列。這些互相等待的封鎖進(jìn)程永遠(yuǎn)無(wú)法運(yùn)行到終點(diǎn)，所以此時(shí)系統(tǒng)處于死鎖狀態(tài)。資源分配圖中不能化簡(jiǎn)的進(jìn)程即為死鎖進(jìn)程。死鎖定理：系統(tǒng)中某個(gè)時(shí)刻S為死鎖狀態(tài)的充分必要條件是，S時(shí)刻系統(tǒng)的資源分配圖是非完全可化簡(jiǎn)的。今天日期：9/18/202316第四章死鎖及其對(duì)策3、死鎖定理：當(dāng)一個(gè)資源分配圖是完全可化簡(jiǎn)時(shí)，該資源分配圖能4.4.2死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)假設(shè)系統(tǒng)中的N個(gè)進(jìn)程P1,P2,…,Pn，有M種資源，R1,R2,…,Rm，則請(qǐng)求矩陣和分配矩陣都是一個(gè)N×M的二維數(shù)組：(1)請(qǐng)求矩陣Re：是一個(gè)N×M的二維數(shù)組，每行代表一個(gè)進(jìn)程當(dāng)前對(duì)各類資源的請(qǐng)求數(shù)目。若Re(i,j)=k,則代表第i個(gè)進(jìn)程Pi請(qǐng)求了Rj類資源k個(gè)分配單位。(2)分配矩陣Al：是一個(gè)N×M的二維數(shù)組，代表某個(gè)時(shí)刻系統(tǒng)中資源的分配情況。若Al(i,j)=k,則代表第i個(gè)進(jìn)程Pi已分配到了Rj類資源k個(gè)分配單位。P1PnP2R1R2Rm今天日期：9/18/202317第四章死鎖及其對(duì)策4.4.2死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)(3)可利用資源向量Av，是一個(gè)長(zhǎng)度為M的一維數(shù)組，表示系統(tǒng)中各類資源的可利用數(shù)目。

(4)工作向量Work：是一個(gè)長(zhǎng)度為M的一維數(shù)組，動(dòng)態(tài)的反映系統(tǒng)中可讓進(jìn)程運(yùn)行的各類資源的數(shù)目。(5)進(jìn)程向量L：是一個(gè)集合，所有已運(yùn)行結(jié)束的進(jìn)程都送入L中，若最后L中包括了所有的N個(gè)進(jìn)程，則說(shuō)明系統(tǒng)處于安全狀態(tài)。今天日期：9/18/202318第四章死鎖及其對(duì)策(3)可利用資源向量Av，是一個(gè)長(zhǎng)度為M的一維數(shù)組，表示4.4.3死鎖檢測(cè)算法1、在某個(gè)時(shí)刻T，j從1到M執(zhí)行Work(j)=Av(j)。2、檢查Al矩陣和Re矩陣，是否存在某個(gè)i(i從1到M)使Al矩陣第i行中所有的Al(i,j)和Re矩陣第i行中所有的Re(i,j)均為零。若存在這個(gè)i說(shuō)明在資源分配圖中Pi進(jìn)程已成為孤立結(jié)點(diǎn)，將Pi進(jìn)程送入進(jìn)程向量L中。3、在系統(tǒng)中除已送入L之外的所有進(jìn)程中逐個(gè)尋找，若某個(gè)i使Re(i,j)<=Work(j)，(j的取值從1到M)，則執(zhí)行：1)j從1到M，Work(j)=Work(j)+Al(i,j)2)j從1到M，令所有的Al(i,j)=0，所有的Re(i,j)=03)將當(dāng)前的這個(gè)進(jìn)程也送入進(jìn)程向量L中這樣反復(fù)執(zhí)行，直到所有L以外的進(jìn)程中再?zèng)]有滿足上述條件為止。4、檢查L(zhǎng)向量，若N個(gè)進(jìn)程都在L中，說(shuō)明系統(tǒng)中不會(huì)發(fā)生死鎖，反之，系統(tǒng)中存在死鎖，那些沒(méi)能進(jìn)入L向量的進(jìn)程均為死鎖進(jìn)程。今天日期：9/18/202319第四章死鎖及其對(duì)策4.4.3死鎖檢測(cè)算法今天日期：8/6/202319第四章由于當(dāng)系統(tǒng)中有了新的請(qǐng)求，而這種請(qǐng)求又不能立即滿足時(shí)才可能發(fā)生死鎖。所以在一個(gè)非死鎖狀態(tài)的前提下，要判斷下一個(gè)狀態(tài)是否為死鎖，只需要在某個(gè)進(jìn)程執(zhí)行新的進(jìn)程請(qǐng)求而又不能立即滿足時(shí)，進(jìn)行死鎖檢測(cè)，由于死鎖檢測(cè)算法執(zhí)行時(shí)間長(zhǎng)、系統(tǒng)開(kāi)銷大，可以在較長(zhǎng)時(shí)間間隔后，執(zhí)行一次檢測(cè)算法。今天日期：9/18/202320第四章死鎖及其對(duì)策由于當(dāng)系統(tǒng)中有了新的請(qǐng)求，而這種請(qǐng)求又不能立即滿足時(shí)才可4.4.4死鎖的恢復(fù)強(qiáng)制性地從系統(tǒng)中撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其余進(jìn)程。使用一個(gè)有效的掛起和解除機(jī)構(gòu)來(lái)掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪一些資源用來(lái)解除死鎖1、撤銷進(jìn)程：為了保證系統(tǒng)所受到的影響最小，可以逐個(gè)撤銷進(jìn)程，直到死鎖不復(fù)存在為止。一般依次選擇撤銷代價(jià)最小的進(jìn)程。撤銷代價(jià)包括：進(jìn)程的優(yōu)先數(shù)、運(yùn)行代價(jià)（從重新啟動(dòng)該進(jìn)程并運(yùn)行到此撤銷時(shí)刻所需要的時(shí)間）、該進(jìn)程對(duì)應(yīng)作業(yè)的外部代價(jià)。2、掛起進(jìn)程今天日期：9/18/202321第四章死鎖及其對(duì)策4.4.4死鎖的恢復(fù)今天日期：8/6/202321第四章4.5死鎖的預(yù)防4.5.1打破“不剝奪”條件強(qiáng)迫那些請(qǐng)求新資源而沒(méi)有立即得到滿足的進(jìn)程釋放它已保持的其它資源，即一個(gè)進(jìn)程已占用的資源在運(yùn)行過(guò)程中可能要暫時(shí)釋放。實(shí)現(xiàn)復(fù)雜，只適用于CPU和內(nèi)存。4.5.2打破“部分分配”條件對(duì)某進(jìn)程所要求的資源一次性地分配完畢，又稱預(yù)先靜態(tài)分配法。4.5.3打破“環(huán)路等待”條件在資源的分配過(guò)程中，對(duì)資源的請(qǐng)求作出某種限制，使環(huán)路不可能出現(xiàn)。今天日期：9/18/202322第四章死鎖及其對(duì)策4.5死鎖的預(yù)防4.5.1打破“不剝奪”條件今天日期：具體的方法是：為系統(tǒng)中每種資源規(guī)定一個(gè)唯一的序號(hào)，例如，輸入機(jī)為1，打印機(jī)為2，穿孔機(jī)為3，磁帶機(jī)為4，磁盤(pán)機(jī)為5等，而且要求每個(gè)進(jìn)程都要嚴(yán)格按照遞增的順序請(qǐng)求資源。若能認(rèn)真的安排資源序號(hào)，將各作業(yè)經(jīng)常使用的、比較普通的資源安排成低序號(hào)，不常使用的資源、比較繁重的資源安排成高序號(hào)，便能提高資源的利用率。但在各資源的序號(hào)安排好后，不能經(jīng)常變動(dòng)。今天日期：9/18/202323第四章死鎖及其對(duì)策具體的方法是：為系統(tǒng)中每種資源規(guī)定一個(gè)唯一的序號(hào)，例如，輸入4.6死鎖避免4.6.1系統(tǒng)狀態(tài)的安全性1、安全狀態(tài)：是指系統(tǒng)能按照某種順序?yàn)槊總€(gè)進(jìn)程分配所需的資源，使每個(gè)進(jìn)程都能順利完成。當(dāng)且僅當(dāng)系統(tǒng)中存在此安全序列時(shí)，系統(tǒng)處于安全狀態(tài)。假設(shè)系統(tǒng)中有3個(gè)進(jìn)程，10個(gè)可供分配的資源單位進(jìn)程已分配資源還需申請(qǐng)的資源P144P222P3272、不安全狀態(tài)：某個(gè)時(shí)刻系統(tǒng)中不存在一個(gè)安全序列，能使所有的進(jìn)程都順利完成。不安全狀態(tài)不是死鎖狀態(tài)，進(jìn)入不安全狀態(tài)的進(jìn)程有可能進(jìn)入死鎖。今天日期：9/18/202324第四章死鎖及其對(duì)策4.6死鎖避免4.6.1系統(tǒng)狀態(tài)的安全性假設(shè)系統(tǒng)中有

銀行家算法是最有代表性的避免死鎖算法，由Dijkstrn提出。1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Av

它是一個(gè)含有m個(gè)元素的數(shù)組，其中每個(gè)元素代表一類可利用資源的數(shù)目。例如：Av數(shù)組4.6.2銀行家算法

前提條件：假設(shè)分配資源的單位是固定的，請(qǐng)求資源的進(jìn)程數(shù)也固定不變，而且每個(gè)進(jìn)程必須先告訴系統(tǒng)對(duì)某類資源的最大需求量，當(dāng)某個(gè)進(jìn)程要求的資源數(shù)量小于系統(tǒng)所擁有的該類資源的最大量時(shí)，系統(tǒng)會(huì)在有限的時(shí)間內(nèi)滿足進(jìn)程的要求。今天日期：9/18/202325第四章死鎖及其對(duì)策銀行家算法是最有代表性的避免死鎖算法，由Dijkstrn(2)最大需求矩陣Max

n×m矩陣，表示n個(gè)進(jìn)程對(duì)m類資源的最大需求。例如：假設(shè)n=5,m=3Max矩陣為：今天日期：9/18/202326第四章死鎖及其對(duì)策(2)最大需求矩陣Maxn×m矩陣，表示n個(gè)進(jìn)程對(duì)m類(3)分配矩陣Al

n×m矩陣，表示每個(gè)進(jìn)程已經(jīng)分配到的資源的數(shù)目。例如：設(shè)n=5,m=3Al矩陣為：今天日期：9/18/202327第四章死鎖及其對(duì)策(3)分配矩陣Aln×m矩陣，表示每個(gè)進(jìn)程已經(jīng)分配到(4)需求矩陣Need

n×m矩陣，表示每個(gè)進(jìn)程還需要各類資源的數(shù)目。例如：n=5,m=3Need矩陣為：今天日期：9/18/202328第四章死鎖及其對(duì)策(4)需求矩陣Needn×m矩陣，表示每個(gè)進(jìn)程還需要2.銀行家算法描述當(dāng)進(jìn)程Pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟：所有Re(i,j)<=Need(i,j)？(j=1,2,…,m)所有Re(i,j)<=Av(j)？(j=1,2,…,m)Av(j)=Av(j)-Re(i,j)Al(i,j)=Al(i,j)+Re(i,j)Need(i,j)=Need(i,j)-Re(i,j)(j=1,2,…,m)Av(j)=Av(j)+Re(i,j)Al(i,j)=Al(i,j)-Re(i,j)Need(i,j)=Need(i,j)+Re(i,j)(j=1,2,…,m)出錯(cuò)處理系統(tǒng)是否處于安全狀態(tài)？斷定分配可以進(jìn)行否否是是是否結(jié)束Pi必須等待執(zhí)行安全性算法恢復(fù)分配前資源狀態(tài)Re：請(qǐng)求矩陣Need：需求矩陣Av：可利用資源向量Al：分配矩陣Max：最大需求矩陣今天日期：9/18/202329第四章死鎖及其對(duì)策2.銀行家算法描述當(dāng)進(jìn)程Pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟3.安全性算法Work(j)=Av(i,j)(j=1,2,…,m)Finish(i)=False(i=1,2,…,n)找能滿足Finish(i)=False(i=1,2,…,n)且Need(i,j)<=Work(j)(j=1,2,…,m)的進(jìn)程PiWork(j)=Work(j)+Al(i,j)(j=1,2,…,m)令Finish(i)=True說(shuō)明系統(tǒng)處于不安全狀態(tài)即、至少有一個(gè)Pi，使Finish(i)=False所有的Finish(i)=True？(i=1,2,…,n)則系統(tǒng)為安全狀態(tài)安全性算法結(jié)束找到是找不到否今天日期：9/18/202330第四章死鎖及其對(duì)策3.安全性算法Work(j)=Av(i,j)Finish(4.6.3銀行家算法舉例

設(shè)系統(tǒng)有五個(gè)進(jìn)程和三類資源，每類資源分別有10、5、7。在T1時(shí)刻資源分配情況如下圖：Al矩陣：Need矩陣：Av數(shù)組：今天日期：9/18/202331第四章死鎖及其對(duì)策4.6.3銀行家算法舉例設(shè)系統(tǒng)有五個(gè)進(jìn)程和三類資源１．假設(shè)T1時(shí)刻初始狀態(tài)為Work(j)=[332]Finish(i)=[FFFFF]的話。首先，判斷它是否處于安全狀態(tài)：①由于i=2時(shí)，存在一個(gè)P2，使Finish(2)=F，且故由Work(j)=Work(j)+Al(2,j)得到Work(J)=[532]Finish(i)=[FTFFF]②由于i=4時(shí)，存在一個(gè)P4，使Finish(4)=F，且故由Work(j)=Work(j)+Al(4,j)得到Work(J)=[743]Finish(i)=[FTFTF]③由于i=5時(shí)，存在一個(gè)P5，使Finish(5)=F，且故由Work(j)=Work(j)+Al(5,j)得到Work(J)=[745]Finish(i)=[FTFT

T]<=Work(j)=[332]<=Work(j)=[532]<=Work(j)=[743]Need=今天日期：9/18/202332第四章死鎖及其對(duì)策１．假設(shè)T1時(shí)刻初始狀態(tài)為Work(j)=[33④由于i=3時(shí)，存在一個(gè)P3，使Finish(3)=F，且故由Work(j)=Work(j)+Al(3,j)得到Work(J)=[1047]Finish(i)=[FT

T

T

T]⑤由于i=1時(shí)，存在一個(gè)P1，使Finish(1)=F，且故由Work(j)=Work(j)+Al(1,j)得到Work(J)=[1057]Finish(i)=[T

T

T

T

T]

此時(shí)、安全標(biāo)志為真，存在一個(gè)安全序列（P2,P4,P5,P3,P1）,所以系統(tǒng)是安全的。<=Work(j)=[745]<=Work(j)=[1047]今天日期：9/18/202333第四章死鎖及其對(duì)策<=Work(j)=[745]<=Work(j)=[２.假設(shè)T2時(shí)刻P2請(qǐng)求資源，即Re(2,j)=[102]的話，使用銀行家算法來(lái)判斷，此時(shí)i=2，Need(2,j)=[122]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010

200302211002743

122600011431

332

…

102………①滿足Re(j)<=Need(2,j)②滿足Re(j)<=Av(j)AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010

302302211002743

020600011431

230

…

102………③執(zhí)行Av(j)=Av(j)-Re(2,j)Al(2,j)=Al(2,j)+Re(2,j)Need(2,j)=Need(2,j)-Re(2,j)(j=1,2,…,m)今天日期：9/18/202334第四章死鎖及其對(duì)策２.假設(shè)T2時(shí)刻P2請(qǐng)求資源，即Re(2,j)=[102然后，對(duì)T2時(shí)刻進(jìn)行安全性檢查，方法同T1時(shí)刻。檢查結(jié)果，可以找到一個(gè)安全序列（P2,P4,P5,P1,P3)。可以得出P2的請(qǐng)求不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不了安全狀態(tài)。所以可以將P2申請(qǐng)的資料分配給他。今天日期：9/18/202335第四章死鎖及其對(duì)策然后，對(duì)T2時(shí)刻進(jìn)行安全性檢查，方法同T1時(shí)刻。檢查結(jié)果，可3.假設(shè)T3時(shí)刻P5請(qǐng)求資源，即Re(5,j)=[330]的話，使用銀行家算法來(lái)判斷，此時(shí)i=5，Need(5,j)=[431]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010302302211002743020600011

431

230

…………330①滿足Re(j)<=Need(5,j)②Re(j)<=Av(j)不滿足所以P5必須等待今天日期：9/18/202336第四章死鎖及其對(duì)策3.假設(shè)T3時(shí)刻P5請(qǐng)求資源，即Re(5,j)=[3304.假設(shè)T4時(shí)刻P1請(qǐng)求資源，即Re(1,j)=[020]的話，使用銀行家算法來(lái)判斷，此時(shí)i=1，Need(1,j)=[743]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5

010

302302211002

743

020600011431

230

020…………①滿足Re(j)<=Need(1,j)②滿足Re(j)<=Av(j)AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5

030302302211002