進(jìn)程死鎖怎么辦？手把手教你解決辦法！
一、要點提示
掌握死鎖的概念和產(chǎn)生死鎖的根本原因。
理解產(chǎn)生死鎖的必要條件–以下四個條件同時具備：互斥條件、不可搶占條件、占有且申請條件、循環(huán)等待條件。
記住解決死鎖的一般方法，掌握死鎖的預(yù)防和死鎖的避免二者的基本思想。
掌握死鎖的預(yù)防策略中資源有序分配策略。
理解進(jìn)程安全序列的概念，理解死鎖與安全序列的關(guān)系。
了解銀行家算法。
了解資源分配圖。
了解死鎖的檢測及恢復(fù)的思想。
二、內(nèi)容簡介
在計算機系統(tǒng)中有很多一次只能由一個進(jìn)程使用的資源，如打印機，磁帶機，一個文件的I節(jié)點等。在多道程序設(shè)計環(huán)境中，若干進(jìn)程往往要共享這類資源，而且一個進(jìn)程所需要的資源不止一個。這樣，就會出現(xiàn)若干進(jìn)程競爭有限資源，又推進(jìn)順序不當(dāng)，從而構(gòu)成無限期循環(huán)等待的局面。這種狀態(tài)就是死鎖。系統(tǒng)發(fā)生死鎖現(xiàn)象不僅浪費大量的系統(tǒng)資源，甚至導(dǎo)致整個系統(tǒng)崩潰，帶來災(zāi)難性后果。所以，對于死鎖問題在理論上和技術(shù)上都必須給予高度重視。
死鎖的概念
死鎖是進(jìn)程死鎖的簡稱，是由Dijkstra于1965年研究銀行家算法時首先提出來的。它是計算機操作系統(tǒng)乃至并發(fā)程序設(shè)計中最難處理的問題之一。實際上，死鎖問題不僅在計算機系統(tǒng)中存在，在我們?nèi)粘Ｉ钪兴矎V泛存在。
1.什么是死鎖
我們先看看這樣一個生活中的例子：在一條河上有一座橋，橋面較窄，只能容納一輛汽車通過，無法讓兩輛汽車并行。如果有兩輛汽車A和B分別由橋的兩端駛上該橋，則對于A車來說，它走過橋面左面的一段路（即占有了橋的一部分資源），要想過橋還須等待B車讓出右邊的橋面，此時A車不能前進(jìn)；對于B車來說，它走過橋面右邊的一段路（即占有了橋的一部分資源），要想過橋還須等待A車讓出左邊的橋面，此時B車也不能前進(jìn)。兩邊的車都不倒車，結(jié)果造成互相等待對方讓出橋面，但是誰也不讓路，就會無休止地等下去。這種現(xiàn)象就是死鎖。如果把汽車比做進(jìn)程，橋面作為資源，那麼上述問題就描述為：進(jìn)程A占有資源R1，等待進(jìn)程B占有的資源Rr；進(jìn)程B占有資源Rr，等待進(jìn)程A占有的資源R1。而且資源R1和Rr只允許一個進(jìn)程占用，即：不允許兩個進(jìn)程同時占用。結(jié)果，兩個進(jìn)程都不能繼續(xù)執(zhí)行，若不采取其它措施，這種循環(huán)等待狀況會無限期持續(xù)下去，就發(fā)生了進(jìn)程死鎖。
在計算機系統(tǒng)中，涉及軟件，硬件資源都可能發(fā)生死鎖。例如：系統(tǒng)中只有一臺CD-ROM驅(qū)動器和一臺打印機，某一個進(jìn)程占有了CD-ROM驅(qū)動器，又申請打印機；另一進(jìn)程占有了打印機，還申請CD-ROM。結(jié)果，兩個進(jìn)程都被阻塞，永遠(yuǎn)也不能自行解除。
所謂死鎖，是指多個進(jìn)程循環(huán)等待它方占有的資源而無限期地僵持下去的局面。很顯然，如果沒有外力的作用，那麼死鎖涉及到的各個進(jìn)程都將永遠(yuǎn)處于封鎖狀態(tài)。從上面的例子可以看出，計算機系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng)。即：一種原因是系統(tǒng)提供的資源太少了，遠(yuǎn)不能滿足并發(fā)進(jìn)程對資源的需求。這種競爭資源引起的死鎖是我們要討論的核心。例如：消息是一種臨時性資源。某一時刻，進(jìn)程A等待進(jìn)程B發(fā)來的消息，進(jìn)程B等待進(jìn)程C發(fā)來的消息，而進(jìn)程C又等待進(jìn)程A發(fā)來的消息。消息未到，A，B，C三個進(jìn)程均無法向前推進(jìn)，也會發(fā)生進(jìn)程通信上的死鎖。另一種原因是由于進(jìn)程推進(jìn)順序不合適引發(fā)的死鎖。資源少也未必一定產(chǎn)生死鎖。就如同兩個人過獨木橋，如果兩個人都要先過，在獨木橋上僵持不肯后退，必然會應(yīng)競爭資源產(chǎn)生死鎖；但是，如果兩個人上橋前先看一看有無對方的人在橋上，當(dāng)無對方的人在橋上時自己才上橋，那麼問題就解決了。所以，如果程序設(shè)計得不合理，造成進(jìn)程推進(jìn)的順序不當(dāng)，也會出現(xiàn)死鎖。
2.產(chǎn)生死鎖的必要條件
從以上分析可見，如果在計算機系統(tǒng)中同時具備下面四個必要條件時，那麼會發(fā)生死鎖。換句話說，只要下面四個條件有一個不具備，系統(tǒng)就不會出現(xiàn)死鎖。
上面我們提到的這四個條件在死鎖時會同時發(fā)生。也就是說，只要有一個必要條件不滿足，則死鎖就可以排除。
死鎖的預(yù)防
前面介紹了死鎖發(fā)生時的四個必要條件，只要破壞這四個必要條件中的任意一個條件，死鎖就不會發(fā)生。這就為我們解決死鎖問題提供了可能。一般地，解決死鎖的方法分為死鎖的預(yù)防，避免，檢測與恢復(fù)三種（注意：死鎖的檢測與恢復(fù)是一個方法）。我們將在下面分別加以介紹。
死鎖的預(yù)防是保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的一種策略。它的基本思想是要求進(jìn)程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進(jìn)入死鎖狀態(tài)。
打破互斥條件。即允許進(jìn)程同時訪問某些資源。但是，有的資源是不允許被同時訪問的，像打印機等等，這是由資源本身的屬性所決定的。所以，這種辦法并無實用價值。
打破不可搶占條件。即允許進(jìn)程強行從占有者那里奪取某些資源。就是說，當(dāng)一個進(jìn)程已占有了某些資源，它又申請新的資源，但不能立即被滿足時，它必須釋放所占有的全部資源，以后再重新申請。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強占了。這種預(yù)防死鎖的方法實現(xiàn)起來困難，會降低系統(tǒng)性能。
〈3〉打破占有且申請條件。可以實行資源預(yù)先分配策略。即進(jìn)程在運行前一次性地向系統(tǒng)申請它所需要的全部資源。如果某個進(jìn)程所需的全部資源得不到滿足，則不分配任何資源，此進(jìn)程暫不運行。只有當(dāng)系統(tǒng)能夠滿足當(dāng)前進(jìn)程的全部資源需求時，才一次性地將所申請的資源全部分配給該進(jìn)程。由于運行的進(jìn)程已占有了它所需的全部資源，所以不會發(fā)生占有資源又申請資源的現(xiàn)象，因此不會發(fā)生死鎖。但是，這種策略也有如下缺點：
（1）在許多情況下，一個進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時是動態(tài)的，不可預(yù)測的；
（2）資源利用率低。無論所分資源何時用到，一個進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長期占著不用的狀況。這顯然是一種極大的資源浪費；
（3）降低了進(jìn)程的并發(fā)性。因為資源有限，又加上存在浪費，能分配到所需全部資源的進(jìn)程個數(shù)就必然少了。
（4）打破循環(huán)等待條件，實行資源有序分配策略。采用這種策略，即把資源事先分類編號，按號分配，使進(jìn)程在申請，占用資源時不會形成環(huán)路。所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的順序提出。進(jìn)程占用了小號資源，才能申請大號資源，就不會產(chǎn)生環(huán)路，從而預(yù)防了死鎖。這種策略與前面的策略相比，資源的利用率和系統(tǒng)吞吐量都有很大提高，但是也存在以下缺點：
（4.1）限制了進(jìn)程對資源的請求，同時給系統(tǒng)中所有資源合理編號也是件困難事，并增加了系統(tǒng)開銷；
（4.2）為了遵循按編號申請的次序，暫不使用的資源也需要提前申請，從而增加了進(jìn)程對資源的占用時間。
死鎖的避免
上面我們講到的死鎖預(yù)防是排除死鎖的靜態(tài)策略，它使產(chǎn)生死鎖的四個必要條件不能同時具備，從而對進(jìn)程申請資源的活動加以限制，以保證死鎖不會發(fā)生。下面我們介紹排除死鎖的動態(tài)策略–死鎖的避免，它不限制進(jìn)程有關(guān)申請資源的命令，而是對進(jìn)程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進(jìn)行資源分配。就是說，在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。
1.安全序列
我們首先引入安全序列的定義：所謂系統(tǒng)是安全的，是指系統(tǒng)中的所有進(jìn)程能夠按照某一種次序分配資源，并且依次地運行完畢，這種進(jìn)程序列{P1，P2，…，Pn}就是安全序列。如果存在這樣一個安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這樣一個安全序列，則系統(tǒng)是不安全的。
安全序列{P1，P2，…，Pn}是這樣組成的：若對于每一個進(jìn)程Pi，它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足，則{P1，P2，…，Pn}為一個安全序列，這時系統(tǒng)處于安全狀態(tài)，不會進(jìn)入死鎖狀態(tài)。
雖然存在安全序列時一定不會有死鎖發(fā)生，但是系統(tǒng)進(jìn)入不安全狀態(tài)（四個死鎖的必要條件同時發(fā)生）也未必會產(chǎn)生死鎖。當(dāng)然，產(chǎn)生死鎖后，系統(tǒng)一定處于不安全狀態(tài)。
銀行家算法
這是一個著名的避免死鎖的算法，是由Dijstra首先提出來并加以解決的?！?/p>
[背景知識]
一個銀行家如何將一定數(shù)目的資金安全地借給若干個客戶，使這些客戶既能借到錢完成要干的事，同時銀行家又能收回全部資金而不至于破產(chǎn)，這就是銀行家問題。這個問題同操作系統(tǒng)中資源分配問題十分相似：銀行家就像一個操作系統(tǒng)，客戶就像運行的進(jìn)程，銀行家的資金就是系統(tǒng)的資源。
[問題的描述]
一個銀行家擁有一定數(shù)量的資金，有若干個客戶要貸款。每個客戶須在一開始就聲明他所需貸款的總額。若該客戶貸款總額不超過銀行家的資金總數(shù)，銀行家可以接收客戶的要求?？蛻糍J款是以每次一個資金單位（如1萬RMB等）的方式進(jìn)行的，客戶在借滿所需的全部單位款額之前可能會等待，但銀行家須保證這種等待是有限的，可完成的。
例如：有三個客戶C1，C2，C3，向銀行家借款，該銀行家的資金總額為10個資金單位，其中C1客戶要借9各資金單位，C2客戶要借3個資金單位，C3客戶要借8個資金單位，總計20個資金單位。某一時刻的狀態(tài)如圖所示。
銀行家算法示意
對于a圖的狀態(tài)，按照安全序列的要求，我們選的第一個客戶應(yīng)滿足該客戶所需的貸款小于等于銀行家當(dāng)前所剩余的錢款，可以看出只有C2客戶能被滿足：C2客戶需1個資金單位，小銀行家手中的2個資金單位，于是銀行家把1個資金單位借給C2客戶，使之完成工作并歸還所借的3個資金單位的錢，進(jìn)入b圖。同理，銀行家把4個資金單位借給C3客戶，使其完成工作，在c圖中，只剩一個客戶C1，它需7個資金單位，這時銀行家有8個資金單位，所以C1也能順利借到錢并完成工作。最后（見圖d）銀行家收回全部10個資金單位，保證不賠本。那麼客戶序列{C1，C2，C3}就是個安全序列，按照這個序列貸款，銀行家才是安全的。否則的話，若在圖b狀態(tài)時，銀行家把手中的4個資金單位借給了C1，則出現(xiàn)不安全狀態(tài)：這時C1，C3均不能完成工作，而銀行家手中又沒有錢了，系統(tǒng)陷入僵持局面，銀行家也不能收回投資。
綜上所述，銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶誰能完成其工作，然后假定其完成工作且歸還全部貸款，再進(jìn)而檢查下一個能完成工作的客戶，……。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。
從上面分析看出，銀行家算法允許死鎖必要條件中的互斥條件，占有且申請條件，不可搶占條件的存在，這樣，它與預(yù)防死鎖的幾種方法相比較，限制條件少了，資源利用程度提高了。
這是該算法的優(yōu)點。其缺點是：
這個算法要求客戶數(shù)保持固定不變，這在多道程序系統(tǒng)中是難以做到的。
這個算法保證所有客戶在有限的時間內(nèi)得到滿足，但實時客戶要求快速響應(yīng)，所以要考慮這個因素。
由于要尋找一個安全序列，實際上增加了系統(tǒng)的開銷。
死鎖的檢測與恢復(fù)
一般來說，由于操作系統(tǒng)有并發(fā)，共享以及隨機性等特點，通過預(yù)防和避免的手段達(dá)到排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開銷，而且不能充分利用資源。為此，一種簡便的方法是系統(tǒng)為進(jìn)程分配資源時，不采取任何限制性措施，但是提供了檢測和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來。因此，在實際的操作系統(tǒng)中往往采用死鎖的檢測與恢復(fù)方法來排除死鎖。
死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機構(gòu)，當(dāng)死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。
圖中所示為一個小的死鎖的例子。這時進(jìn)程P1占有資源R1而申請資源R2，進(jìn)程P2占有資源R2而申請資源R1，按循環(huán)等待條件，進(jìn)程和資源形成了環(huán)路，所以系統(tǒng)是死鎖狀態(tài)。進(jìn)程P1，P2是參與死鎖的進(jìn)程。下面我們再來看一看死鎖檢測算法。算法使用的數(shù)據(jù)結(jié)構(gòu)是如下這些：
算法步驟：
死鎖的恢復(fù)
一旦在死鎖檢測時發(fā)現(xiàn)了死鎖，就要消除死鎖，使系統(tǒng)從死鎖狀態(tài)中恢復(fù)過來。
此外，還有進(jìn)程回退策略，即讓參與死鎖的進(jìn)程回退到?jīng)]有發(fā)生死鎖前某一點處，并由此點處繼續(xù)執(zhí)行，以求再次執(zhí)行時不再發(fā)生死鎖。雖然這是個較理想的辦法，但是操作起來系統(tǒng)開銷極大，要有堆棧這樣的機構(gòu)記錄進(jìn)程的每一步變化，以便今后的回退，有時這是無法做到的。
