一.死鎖的概念以及產(chǎn)生死鎖的原因
1.死鎖的定義
在多道程序系統(tǒng)中盒齿，由于多個(gè)進(jìn)程的并發(fā)執(zhí)行翎承，改善了系統(tǒng)資源的利用率并提高了系統(tǒng) 的處理能力叨咖。然而，多個(gè)進(jìn)程的并發(fā)執(zhí)行也帶來了新的問題——死鎖趣倾。所謂死鎖是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局（互相等待）誊酌，若無外力作用部凑，這些進(jìn)程都將無法向前推進(jìn)。
下面我們通過一些實(shí)例來說明死鎖現(xiàn)象碧浊。
例如涂邀，某計(jì)算機(jī)系統(tǒng)中只有一臺(tái)打印機(jī)和一臺(tái)輸入設(shè)備，進(jìn)程P1正占用輸入設(shè)備箱锐，同時(shí)又提出使用打印機(jī)的請(qǐng)求比勉，但此時(shí)打印機(jī)正被進(jìn)程P2 所占用，而P2在未釋放打印機(jī)之前驹止，又提出請(qǐng)求使用正被P1占用著的輸入設(shè)備衣洁。這樣兩個(gè)進(jìn)程相互無休止地等待下去环凿，均無法繼續(xù)執(zhí)行，此時(shí)兩個(gè)進(jìn)程陷入死鎖狀態(tài)环肘。
2.死鎖產(chǎn)生的原因
1) 系統(tǒng)資源的競(jìng)爭(zhēng)
通常系統(tǒng)中擁有的不可剝奪資源，其數(shù)量不足以滿足多個(gè)進(jìn)程運(yùn)行的需要驯鳖，使得進(jìn)程在 運(yùn)行過程中，會(huì)因爭(zhēng)奪資源而陷入僵局，如磁帶機(jī)厚满、打印機(jī)等。只有對(duì)不可剝奪資源的競(jìng)爭(zhēng) 才可能產(chǎn)生死鎖，對(duì)可剝奪資源的競(jìng)爭(zhēng)是不會(huì)引起死鎖的拨匆。
2) 進(jìn)程推進(jìn)順序非法
進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)察署，也同樣會(huì)導(dǎo)致死鎖业簿。例如，并發(fā)進(jìn)程 P1邀跃、P2分別保持了資源R1、R2，而進(jìn)程P1申請(qǐng)資源R2诺核，進(jìn)程P2申請(qǐng)資源R1時(shí)，兩者都 會(huì)因?yàn)樗栀Y源被占用而阻塞。
信號(hào)量使用不當(dāng)也會(huì)造成死鎖鞍泉。進(jìn)程間彼此相互等待對(duì)方發(fā)來的消息，結(jié)果也會(huì)使得這 些進(jìn)程間無法繼續(xù)向前推進(jìn)睦刃。例如工育，進(jìn)程A等待進(jìn)程B發(fā)的消息如绸，進(jìn)程B又在等待進(jìn)程A 發(fā)的消息凛膏，可以看出進(jìn)程A和B不是因?yàn)楦?jìng)爭(zhēng)同一資源是己，而是在等待對(duì)方的資源導(dǎo)致死鎖。
3) 死鎖產(chǎn)生的必要條件
產(chǎn)生死鎖必須同時(shí)滿足以下四個(gè)條件粹胯，只要其中任一條件不成立蓖柔，死鎖就不會(huì)發(fā)生。
（1）互斥條件：進(jìn)程要求對(duì)所分配的資源（如打印機(jī)）進(jìn)行排他性控制风纠，即在一段時(shí)間內(nèi)某資源僅為一個(gè)進(jìn)程所占有况鸣。此時(shí)若有其他進(jìn)程請(qǐng)求該資源，則請(qǐng)求進(jìn)程只能等待竹观。
（2）不剝奪條件：進(jìn)程所獲得的資源在未使用完畢之前镐捧，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來釋放（只能是主動(dòng)釋放)臭增。
（3）請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源懂酱，但又提出了新的資源請(qǐng)求，而該資源已被其他進(jìn)程占有誊抛，此時(shí)請(qǐng)求進(jìn)程被阻塞列牺，但對(duì)自己已獲得的資源保持不放。
（4）循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈拗窃，鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中下一個(gè)進(jìn)程所請(qǐng)求瞎领。即存在一個(gè)處于等待狀態(tài)的進(jìn)程集合{Pl, P2, ..., pn}，其中Pi等待的資源被P(i+1)占有（i=0, 1, ..., n-1)随夸，Pn等待的資源被P0占有九默，如圖2-15所示。
直觀上看宾毒，循環(huán)等待條件似乎和死鎖的定義一樣驼修，其實(shí)不然。按死鎖定義構(gòu)成等待環(huán)所要求的條件更嚴(yán)，它要求Pi等待的資源必須由P(i+1)來滿足乙各，而循環(huán)等待條件則無此限制勉躺。 例如，系統(tǒng)中有兩臺(tái)輸出設(shè)備觅丰，P0占有一臺(tái)饵溅，PK占有另一臺(tái)，且K不屬于集合{0, 1, ..., n}妇萄。
Pn等待一臺(tái)輸出設(shè)備蜕企，它可以從P0獲得，也可能從PK獲得冠句。因此轻掩，雖然Pn、P0和其他 一些進(jìn)程形成了循環(huán)等待圈懦底，但PK不在圈內(nèi)唇牧，若PK釋放了輸出設(shè)備，則可打破循環(huán)等待, 如圖2-16所示聚唐。因此循環(huán)等待只是死鎖的必要條件丐重。
資源分配圖含圈而系統(tǒng)又不一定有死鎖的原因是同類資源數(shù)大于1。但若系統(tǒng)中每類資源都只有一個(gè)資源杆查，則資源分配圖含圈就變成了系統(tǒng)出現(xiàn)死鎖的充分必要條件扮惦。
二.死鎖的處理策略
為使系統(tǒng)不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個(gè)必要條件之一亲桦，或者允許死鎖產(chǎn)生崖蜜， 但當(dāng)死鎖發(fā)生時(shí)能檢測(cè)出死鎖，并有能力實(shí)現(xiàn)恢復(fù)客峭。
三個(gè)死鎖處理策略：
（1）預(yù)防死鎖
設(shè)置某些限制條件豫领，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，以防止發(fā)生死鎖舔琅。
（2）避免死鎖
在資源的動(dòng)態(tài)分配過程中等恐，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖搏明。
（3）死鎖的檢測(cè)及解除
無需釆取任何限制性措施鼠锈，允許進(jìn)程在運(yùn)行過程中發(fā)生死鎖闪檬。通過系統(tǒng)的檢測(cè)機(jī)構(gòu)及時(shí) 地檢測(cè)出死鎖的發(fā)生星著，然后釆取某種措施解除死鎖。
預(yù)防死鎖和避免死鎖都屬于事先預(yù)防策略粗悯，但預(yù)防死鎖的限制條件比較嚴(yán)格虚循，實(shí)現(xiàn)起來 較為簡(jiǎn)單，但往往導(dǎo)致系統(tǒng)的效率低，資源利用率低横缔；避免死鎖的限制條件相對(duì)寬松铺遂，資源 分配后需要通過算法來判斷是否進(jìn)入不安全狀態(tài)，實(shí)現(xiàn)起來較為復(fù)雜茎刚。
死鎖的幾種處理策略的比較見表：
三.死鎖預(yù)防和死鎖避免
死鎖預(yù)防
防止死鎖的發(fā)生只需破壞死鎖產(chǎn)生的四個(gè)必要條件之一即可襟锐。
1) 破壞互斥條件
如果允許系統(tǒng)資源都能共享使用，則系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)膛锭。但有些資源根本不能同時(shí)訪問粮坞，如打印機(jī)等臨界資源只能互斥使用。所以初狰，破壞互斥條件而預(yù)防死鎖的方法不太可行莫杈，而且在有的場(chǎng)合應(yīng)該保護(hù)這種互斥性。
2) 破壞不剝奪條件
當(dāng)一個(gè)已保持了某些不可剝奪資源的進(jìn)程奢入，請(qǐng)求新的資源而得不到滿足時(shí)筝闹，它必須釋放已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)腥光。這意味著关顷，一個(gè)進(jìn)程已占有的資源會(huì)被暫時(shí)釋放，或者說是被剝奪了武福，或從而破壞了不可剝奪條件解寝。
該策略實(shí)現(xiàn)起來比較復(fù)雜，釋放已獲得的資源可能造成前一階段工作的失效艘儒，反復(fù)地申請(qǐng)和釋放資源會(huì)增加系統(tǒng)開銷聋伦，降低系統(tǒng)吞吐量。這種方法常用于狀態(tài)易于保存和恢復(fù)的資源界睁，如CPU的寄存器及內(nèi)存資源觉增，一般不能用于打印機(jī)之類的資源。
3) 破壞請(qǐng)求和保持條件
釆用預(yù)先靜態(tài)分配方法翻斟，即進(jìn)程在運(yùn)行前一次申請(qǐng)完它所需要的全部資源逾礁，在它的資源未滿足前，不把它投入運(yùn)行访惜。一旦投入運(yùn)行后嘹履，這些資源就一直歸它所有，也不再提出其他資源請(qǐng)求债热，這樣就可以保證系統(tǒng)不會(huì)發(fā)生死鎖砾嫉。
這種方式實(shí)現(xiàn)簡(jiǎn)單，但缺點(diǎn)也顯而易見窒篱，系統(tǒng)資源被嚴(yán)重浪費(fèi)焕刮，其中有些資源可能僅在運(yùn)行初期或運(yùn)行快結(jié)束時(shí)才使用舶沿，甚至根本不使用。而且還會(huì)導(dǎo)致“饑餓”現(xiàn)象配并，當(dāng)由于個(gè)別資源長(zhǎng)期被其他進(jìn)程占用時(shí)括荡，將致使等待該資源的進(jìn)程遲遲不能開始運(yùn)行。
4) 破壞循環(huán)等待條件
為了破壞循環(huán)等待條件溉旋，可釆用順序資源分配法畸冲。首先給系統(tǒng)中的資源編號(hào)，規(guī)定每個(gè)進(jìn)程观腊，必須按編號(hào)遞增的順序請(qǐng)求資源召夹，同類資源一次申請(qǐng)完。也就是說恕沫，只要進(jìn)程提出申請(qǐng)分配資源Ri监憎，則該進(jìn)程在以后的資源申請(qǐng)中，只能申請(qǐng)編號(hào)大于Ri的資源婶溯。
這種方法存在的問題是鲸阔，編號(hào)必須相對(duì)穩(wěn)定，這就限制了新類型設(shè)備的增加迄委；盡管在為資源編號(hào)時(shí)已考慮到大多數(shù)作業(yè)實(shí)際使用這些資源的順序褐筛，但也經(jīng)常會(huì)發(fā)生作業(yè)使甩資源的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源的浪費(fèi)叙身；此外渔扎，這種按規(guī)定次序申請(qǐng)資源的方法，也必然會(huì)給用戶的編程帶來麻煩信轿。
死鎖避免
避免死鎖同樣是屬于事先預(yù)防的策略晃痴，但并不是事先釆取某種限制措施破壞死鎖的必要條件，而是在資源動(dòng)態(tài)分配過程中财忽，防止系統(tǒng)進(jìn)入不安全狀態(tài)倘核，以避免發(fā)生死鎖。這種方法所施加的限制條件較弱即彪，可以獲得較好的系統(tǒng)性能紧唱。
1. 系統(tǒng)安全狀態(tài)
避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源隶校，但系統(tǒng)在進(jìn)行資源分配之前漏益，應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)深胳，則將資源分配給進(jìn)程绰疤； 否則，讓進(jìn)程等待稠屠。
所謂安全狀態(tài)峦睡，是指系統(tǒng)能按某種進(jìn)程推進(jìn)順序( P1, P2, ..., Pn)，為每個(gè)進(jìn)程Pi分配其所需資源权埠，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求榨了，使每個(gè)進(jìn)程都可順序地完成。此時(shí)稱 P1, P2, ..., Pn 為安全序列攘蔽。如果系統(tǒng)無法找到一個(gè)安全序列龙屉，則稱系統(tǒng)處于不安全狀態(tài)。
假設(shè)系統(tǒng)中有三個(gè)進(jìn)程P1满俗、P2和P3,共有12 臺(tái)磁帶機(jī)转捕。進(jìn)程P1總共需要10臺(tái)磁帶機(jī)，P2和P3 分別需要4臺(tái)和9臺(tái)唆垃。假設(shè)在T0時(shí)刻五芝，進(jìn)程P1、P2 和P3已分別獲得5合辕万、2臺(tái)和2臺(tái)枢步，尚有3臺(tái)未分配，見表：
則在T0時(shí)刻是安全的渐尿，因?yàn)榇嬖谝粋€(gè)安全序列P2醉途、Pl、P3砖茸，即只要系統(tǒng)按此進(jìn)程序列分配資源隘擎，則每個(gè)進(jìn)程都能順利完成。若在T0時(shí)刻后凉夯，系統(tǒng)分配1臺(tái)磁帶機(jī)給P3货葬，則此時(shí)系統(tǒng)便進(jìn)入不安全狀態(tài)，因?yàn)榇藭r(shí)已無法再找到一個(gè)安全序列劲够。
并非所有的不安全狀態(tài)都是死鎖狀態(tài)宝惰，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便可能進(jìn)入死鎖狀態(tài)再沧；反之尼夺，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可以避免進(jìn)入死鎖狀態(tài)炒瘸。
2. 銀行家算法
銀行家算法是最著名的死鎖避免算法淤堵。
銀行家算法的思想是：
把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金顷扩，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款拐邪。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)隘截，要測(cè)試該進(jìn)程對(duì)資源的最大需求量扎阶，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源汹胃，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)东臀，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量着饥。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量惰赋，若能滿足則按當(dāng)前的申請(qǐng)量分配資源宰掉，否則也要推遲分配。
1) 數(shù)據(jù)結(jié)構(gòu)描述
可利用資源矢量Available：含有m個(gè)元素的歎組赁濒，其中的每一個(gè)元素代表一類可用的資源數(shù)目轨奄。Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)拒炎。
最大需求矩陣Max：為n*m矩陣挪拟，定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。Max[i, j]=K击你，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K舞丛。
分配矩陣Allocation：為n*m矩陣抵恋，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)走贪。All0Cati0n[i, j]= K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K迫横。
需求矩陣Need：為n*m矩陣绒障，表示每個(gè)進(jìn)程尚需的各類資源數(shù)吨凑。Need[i, j]=K，則表示進(jìn)程i還需要Rj類資源的數(shù)目為K户辱。
上述三個(gè)矩陣間存在下述關(guān)系：
Need[i, j] = Max[i, j] - Allocation[i, j]
2) 銀行家算法描述
設(shè)Requesti是進(jìn)程Pi的請(qǐng)求矢量鸵钝，如果Requesti[j]K，表示進(jìn)程Pi需要Rj類資源K個(gè)庐镐。當(dāng)Pi發(fā)出資源請(qǐng)求后恩商，系統(tǒng)按下述步驟進(jìn)行檢查：
①如果Requesti[j] <= Need[i, j]，便轉(zhuǎn)向步驟②必逆；否則認(rèn)為出錯(cuò)怠堪，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。
②如果Requesti[j] <= Available[j]名眉，便轉(zhuǎn)向步驟③;否則粟矿，表示尚無足夠資源，Pi須等待损拢。
③系統(tǒng)試探著把資源分配給進(jìn)程Pi陌粹，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：
Available[j]=Available[j]-Requesti[j];
Allocation[i,j]=Allocation[i,j]+Requesti[j];
Need[i,j]=Need[i,j]-Requesti[j];
④系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后福压，系統(tǒng)是否處于安全狀態(tài)掏秩。若安全或舞，才正式將資源分配給進(jìn)程Pi，以完成本次分配蒙幻；否則映凳，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)杆煞，讓進(jìn)程Pi等待魏宽。
3) 安全性算法
①設(shè)置兩個(gè)矢量腐泻。工作矢量Work决乎；它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有所個(gè)元素派桩，在執(zhí)行安全算法開始時(shí)构诚，Work=Available; Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成铆惑。開始時(shí)?Finish[i]=false范嘱；當(dāng)有足夠資源分配給進(jìn)程?Pi?時(shí)，再令?Finish[i]=true员魏。
②從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：Finish[i]=false; ???Need[i, j]<=Work[j];?若找到丑蛤，執(zhí)行下一步驟，否則撕阎，執(zhí)行步驟4受裹。
③當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行虏束，直至完成棉饶，并釋放出分配給它的資源，故應(yīng)執(zhí)行：
Work[j]=Work[j]+Allocation[i,j];
Finish[i]=true;
goto step<2>;
④如果所有進(jìn)程的Finish[i]=tme都滿足镇匀，則表示系統(tǒng)處于安全狀態(tài)照藻；否則，系統(tǒng)處于不安全狀態(tài)汗侵。
3. 銀行家算法舉例
假定系統(tǒng)中有5個(gè)進(jìn)程{P0, P1, P2, P3, P4}和三類資源{A, B, C}幸缕，各種資源的數(shù)量分別為10、5晰韵、7冀值，在T0時(shí)刻的資源分配情況見表2-16。
1) T0時(shí)刻的安全性宫屠。
利用安全性算法對(duì)T0時(shí)刻的資源分配進(jìn)行分析列疗，由表2-17可知，在T0時(shí)刻存在著一個(gè)安全序列{P1, P3, P4, P2, P0}浪蹂，故系統(tǒng)是安全的抵栈。
2) P1請(qǐng)求資源
P1發(fā)出請(qǐng)求矢量Request1(l告材，, 0, 2)，系統(tǒng)按銀行家算法進(jìn)行檢查：
Request1(1, 0, 2) <= Need1(l, 2, 2)古劲。
Request1(1, 0, 2) <= Available1(3, 3, 2)斥赋。
系統(tǒng)先假定可為P1分配資源，并修改Available产艾、Allocation1和Need1矢量疤剑，由此形成的資源變化情況見表2-18。
再利用安全性算法檢查此時(shí)系統(tǒng)是否安全闷堡。
3) P4請(qǐng)求資源
P4發(fā)出請(qǐng)求矢量Request4(3, 3, 0)隘膘，系統(tǒng)按銀行家算法進(jìn)行檢查：
Request4(3, 3, 0) <= Need4(4, 3, 1)。
Request4(3, 3, 0) >?Available(2, 3, 0)杠览，讓?P4?等待弯菊。
4) P0請(qǐng)求資源
P0發(fā)出請(qǐng)求矢量Request0(0, 2, 0)，系統(tǒng)按銀行家算法進(jìn)行檢查：
Request0(0, 2, 0) <= Need0(7, 4, 3)踱阿。
Request0(0, 2, 0) <= Available(2, 3, 0)管钳。
系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)软舌，見表2-19才漆。
5) 進(jìn)行安全性檢測(cè)。
可用資源Available(2, 1, 0)已不能滿足任何進(jìn)程的需要佛点，故系統(tǒng)進(jìn)入不安全狀態(tài)醇滥，此時(shí)系統(tǒng)不分配資源。
四恋脚、死鎖的檢測(cè)和解除
前面紹的死鎖預(yù)防和避免算法腺办，都是在為進(jìn)程分配資源時(shí)施加限制條件或進(jìn)行檢測(cè)，若系統(tǒng)為進(jìn)程分配資源時(shí)不釆取任何措施糟描，則應(yīng)該提供死鎖檢測(cè)和解除的手段怀喉。
資源分配圖
系統(tǒng)死鎖，可利用資源分配圖來描述船响。如圖2-17所示躬拢，用圓圈代表一個(gè)進(jìn)程，用框代表一類資源见间。由于一種類型的資源可能有多個(gè)聊闯，用框中的一個(gè)點(diǎn)代表一類資源中的一個(gè)資源。從進(jìn)程到資源的有向邊叫請(qǐng)求邊米诉，表示該進(jìn)程申請(qǐng)一個(gè)單位的該類資源菱蔬；從資源到進(jìn)程的邊叫分配邊，表示該類資源已經(jīng)有一個(gè)資源被分配給了該進(jìn)程。
在圖所示的資源分配圖中拴泌，進(jìn)程P1已經(jīng)分得了兩個(gè)R1資源魏身，并又請(qǐng)求一個(gè)R2 資源；進(jìn)程P2分得了一個(gè)R1和一個(gè)R2資源蚪腐，并又請(qǐng)求一個(gè)R1資源箭昵。
死鎖定理
可以通過將資源分配圖簡(jiǎn)化的方法來檢測(cè)系統(tǒng)狀態(tài)S是否為死鎖狀態(tài)。簡(jiǎn)化方法如下：
1) 在資源分配圖中回季，找出既不阻塞又不是孤點(diǎn)的進(jìn)程Pi（即找出一條有向邊與它相連家制，且該有向邊對(duì)應(yīng)資源的申請(qǐng)數(shù)量小于等于系統(tǒng)中已有空閑資源數(shù)量。若所有的連接該進(jìn)程的邊均滿足上述條件泡一，則這個(gè)進(jìn)程能繼續(xù)運(yùn)行直至完成颤殴，然后釋放它所占有的所有資源）。消去它所有的請(qǐng)求邊和分配邊瘾杭，使之成為孤立的結(jié)點(diǎn)诅病。在(a)中哪亿，P1是滿足這一條件的進(jìn)程結(jié)點(diǎn)粥烁，將P1的所有邊消去，便得到圖(b)所示的情況蝇棉。
2) 進(jìn)程Pi所釋放的資源讨阻，可以喚醒某些因等待這些資源而阻塞的進(jìn)程，原來的阻塞進(jìn)程可能變?yōu)榉亲枞M(jìn)程篡殷。在上圖中钝吮，進(jìn)程P2就滿足這樣的條件。根據(jù)第1)?條中的方法進(jìn)行一系列簡(jiǎn)化后,若能消去圖中所有的邊板辽，則稱該圖是可完全簡(jiǎn)化的奇瘦，如圖(c)所示。
S為死鎖的條件是當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的,該條件為死鎖定理劲弦。
死鎖的解除
一旦檢測(cè)出死鎖耳标，就應(yīng)立即釆取相應(yīng)的措施，以解除死鎖邑跪。死鎖解除的主要方法有：
1) 資源剝奪法次坡。掛起某些死鎖進(jìn)程，并搶占它的資源画畅，將這些資源分配給其他的死鎖進(jìn)程砸琅。但應(yīng)防止被掛起的進(jìn)程長(zhǎng)時(shí)間得不到資源，而處于資源匱乏的狀態(tài)轴踱。
2) 撤銷進(jìn)程法症脂。強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程并剝奪這些進(jìn)程的資源。撤銷的原則可以按進(jìn)程優(yōu)先級(jí)和撤銷進(jìn)程代價(jià)的高低進(jìn)行诱篷。
3) 進(jìn)程回退法沸版。讓一（多）個(gè)進(jìn)程回退到足以回避死鎖的地步，進(jìn)程回退時(shí)自愿釋放資源而不是被剝奪兴蒸。要求系統(tǒng)保持進(jìn)程的歷史信息视粮，設(shè)置還原點(diǎn)。
