多道程序系統(tǒng)借助并發(fā)執(zhí)行改善資源利用率，提高系統(tǒng)吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。
死鎖（Deadlock）：指多個(gè)進(jìn)程在運(yùn)行過程中，因爭奪資源而造成的一種僵局。當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。
產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：
1.競爭資源。系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等的數(shù)目不滿足需要時(shí)，會(huì)引起資源競爭而產(chǎn)生死鎖。
2.進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，同樣會(huì)導(dǎo)致死鎖。
1.競爭資源引起進(jìn)程死鎖
可把系統(tǒng)中的資源分為兩類：
v可剝奪和非剝奪性資源
?可剝奪性資源：分配給進(jìn)程后可以被高優(yōu)先級(jí)的進(jìn)程剝奪。如CPU和主存。
?不可剝奪性資源：分配給進(jìn)程后只能在進(jìn)程用完后釋放。如磁帶機(jī)、打印機(jī)等。
v永久性資源和臨時(shí)性資源
?永久性：打印機(jī)?？身樞蛑貜?fù)使用
?臨時(shí)性：進(jìn)程產(chǎn)生被其他進(jìn)程短暫使用的資源，如數(shù)據(jù)資源：“生產(chǎn)者/消費(fèi)者”算法中的信號(hào)量。。它可能引起死鎖。
2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖
v進(jìn)程在運(yùn)行中具有異步性特征，多個(gè)進(jìn)程按向前推進(jìn)的順序有兩種情況：
1)推進(jìn)順序合法
2)推進(jìn)順序非法
3.形成死鎖的四個(gè)必要條件
（四個(gè)條件都具備就會(huì)死鎖，缺一就不會(huì)死鎖）
①互斥條件：進(jìn)程對(duì)所分配到的資源進(jìn)行排他性使用
②請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，又提出新的資源請(qǐng)求，而新請(qǐng)求資源被其他進(jìn)程占有只能造成自身進(jìn)程阻塞，但對(duì)自己已獲得的其他資源保持不放，必然影響其他進(jìn)程。
③不剝奪條件：進(jìn)程已獲得的資源未使用完之前不能被剝奪，只能在使用完時(shí)由自己釋放。
④環(huán)路等待條件
4.處理死鎖的基本方法
事先預(yù)防：
①預(yù)防死鎖
v設(shè)置限制條件，破壞四個(gè)必要條件的一個(gè)或幾個(gè)，預(yù)防發(fā)生死鎖。
v較易實(shí)現(xiàn)。限制條件的嚴(yán)格也會(huì)導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。
②避免死鎖
v不須事先限制，破壞四個(gè)必要條件，而是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。
v這種事先加以較弱限制的方法，實(shí)現(xiàn)上有一定難度，但可獲較高的資源利用率及系統(tǒng)吞吐量，目前在較完善的系統(tǒng)中，常用此方法來避免發(fā)生死鎖。
事后處理：
③檢測死鎖。
v允許系統(tǒng)運(yùn)行過程中發(fā)生死鎖，但通過系統(tǒng)檢測機(jī)構(gòu)可及時(shí)的檢測出，能精確確定與死鎖有關(guān)的進(jìn)程和資源；然后采取適當(dāng)?shù)拇胧?，從系統(tǒng)中將已發(fā)生的死鎖清除掉。
④解除死鎖。
v與死鎖檢測配套的一種措施。
v常用的實(shí)施方法：撤銷或掛起一些進(jìn)程，以便回收一些資源并將他們分配給已阻塞進(jìn)程，使之轉(zhuǎn)為就緒以繼續(xù)運(yùn)行。
v死鎖的檢測與解除措施，有可能使系統(tǒng)獲得較好的資源利用率和吞吐量（死鎖幾率不一定很高），但在實(shí)現(xiàn)上難度也最大。
銀行家算法避免死鎖
? 最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。
? 【思路描述】：隨時(shí)對(duì)系統(tǒng)中的所有資源信息進(jìn)行統(tǒng)計(jì)，包括每種資源的數(shù)量、已分配給各進(jìn)程的數(shù)量；每當(dāng)進(jìn)程提出某種資源請(qǐng)求時(shí)判斷該請(qǐng)求分配后是否安全，如果安全才分配。對(duì)每個(gè)資源請(qǐng)求的處理都要保證系統(tǒng)始終從一個(gè)安全狀態(tài)到另一個(gè)安全狀態(tài)。
死鎖的檢測與解除
v當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此系統(tǒng)必須：
1.保存有關(guān)資源的請(qǐng)求和分配信息；
2.提供一種算法，以利用這些信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。
死鎖定理
利用資源分配圖簡化法來檢測死鎖。
簡化方法如下：
? 1.在資源分配圖中找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi，在順利的情況下運(yùn)行完畢，釋放其占有的全部資源。
? 2.由于釋放了資源，這樣能使其它被阻塞的進(jìn)程獲得資源繼續(xù)運(yùn)行。消去了Pi的邊。
? 3.經(jīng)過一系列簡化后，若能消去圖中所有邊，使結(jié)點(diǎn)都孤立，稱該圖是可完全簡化的。
S狀態(tài)為死鎖狀態(tài)的充分條件是當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。<死鎖定理>
死鎖的解除
當(dāng)發(fā)現(xiàn)進(jìn)程死鎖時(shí)，便應(yīng)立即把它們從死鎖狀態(tài)中解脫出來。常采用的方法是：
1.剝奪資源。從其他進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程以解除死鎖狀態(tài)。
2.撤銷進(jìn)程。最簡單的是讓全部進(jìn)程都死掉；溫和一點(diǎn)的是按照某種順序逐個(gè)撤銷進(jìn)程，直至有足夠的資源可用，使死鎖狀態(tài)消除為止。
