轉(zhuǎn)進(jìn)程死鎖及解決辦法

1、.轉(zhuǎn) 進(jìn)程死鎖及解決辦法一、要點(diǎn)提示1掌握死鎖的概念和產(chǎn)生死鎖的根本原因。2理解產(chǎn)生死鎖的必要條件-以下四個(gè)條件同時(shí)具備：互斥條件、不可搶占條件、占有且申請(qǐng)條件、循環(huán)等待條件。3記住解決死鎖的一般方法，掌握死鎖的預(yù)防和死鎖的防止二者的根本思想。4掌握死鎖的預(yù)防策略中資源有序分配策略。5理解進(jìn)程平安序列的概念，理解死鎖與平安序列的關(guān)系。6理解銀行家算法。7理解資源分配圖。8理解死鎖的檢測(cè)及恢復(fù)的思想。二、內(nèi)容簡(jiǎn)介在計(jì)算機(jī)系統(tǒng)中有很多一次只能由一個(gè)進(jìn)程使用的資源，如打印機(jī)，磁帶機(jī)，一個(gè)文件的I節(jié)點(diǎn)等。在多道程序設(shè)計(jì)環(huán)境中，假設(shè)干進(jìn)程往往要共享這類(lèi)資源，而且一個(gè)進(jìn)程所需要的資源不止一個(gè)。這樣，就會(huì)出

2、現(xiàn)假設(shè)干進(jìn)程競(jìng)爭(zhēng)有限資源，又推進(jìn)順序不當(dāng)，從而構(gòu)成無(wú)限期循環(huán)等待的場(chǎng)面。這種狀態(tài)就是死鎖。系統(tǒng)發(fā)生死鎖現(xiàn)象不僅浪費(fèi)大量的系統(tǒng)資源，甚至導(dǎo)致整個(gè)系統(tǒng)崩潰，帶來(lái)災(zāi)難性后果。所以，對(duì)于死鎖問(wèn)題在理論上和技術(shù)上都必須給予高度重視。8.1死鎖的概念死鎖是進(jìn)程死鎖的簡(jiǎn)稱(chēng)，是由Dijkstra于1965年研究銀行家算法時(shí)首先提出來(lái)的。它是計(jì)算機(jī)操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最難處理的問(wèn)題之一。實(shí)際上，死鎖問(wèn)題不僅在計(jì)算機(jī)系統(tǒng)中存在，在我們?nèi)粘Ｉ钪兴矎V泛存在。1.什么是死鎖我們先看看這樣一個(gè)生活中的例子：在一條河上有一座橋，橋面較窄，只能包容一輛汽車(chē)通過(guò)，無(wú)法讓兩輛汽車(chē)并行。假設(shè)有兩輛汽車(chē)A和B分別由橋的兩端

3、駛上該橋，那么對(duì)于A車(chē)來(lái)說(shuō)，它走過(guò)橋面左面的一段路即占有了橋的一部分資源，要想過(guò)橋還須等待B車(chē)讓出右邊的橋面，此時(shí)A車(chē)不能前進(jìn)；對(duì)于B車(chē)來(lái)說(shuō)，它走過(guò)橋面右邊的一段路即占有了橋的一部分資源，要想過(guò)橋還須等待A車(chē)讓出左邊的橋面，此時(shí)B車(chē)也不能前進(jìn)。兩邊的車(chē)都不倒車(chē)，結(jié)果造成互相等待對(duì)方讓出橋面，但是誰(shuí)也不讓路，就會(huì)無(wú)休止地等下去。這種現(xiàn)象就是死鎖。假設(shè)把汽車(chē)比做進(jìn)程，橋面作為資源，那么上述問(wèn)題就描繪為：進(jìn)程A占有資源R1，等待進(jìn)程B占有的資源Rr；進(jìn)程B占有資源Rr，等待進(jìn)程A占有的資源R1。而且資源R1和Rr只允許一個(gè)進(jìn)程占用，即：不允許兩個(gè)進(jìn)程同時(shí)占用。結(jié)果，兩個(gè)進(jìn)程都不能繼續(xù)執(zhí)行，假設(shè)不采取

4、其它措施，這種循環(huán)等待狀況會(huì)無(wú)限期持續(xù)下去，就發(fā)生了進(jìn)程死鎖。在計(jì)算機(jī)系統(tǒng)中，涉及軟件，硬件資源都可能發(fā)生死鎖。例如：系統(tǒng)中只有一臺(tái)CD-ROM驅(qū)動(dòng)器和一臺(tái)打印機(jī)，某一個(gè)進(jìn)程占有了CD-ROM驅(qū)動(dòng)器，又申請(qǐng)打印機(jī)；另一進(jìn)程占有了打印機(jī)，還申請(qǐng)CD-ROM。結(jié)果，兩個(gè)進(jìn)程都被阻塞，永遠(yuǎn)也不能自行解除。所謂死鎖，是指多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無(wú)限期地僵持下去的場(chǎng)面。很顯然，假設(shè)沒(méi)有外力的作用，那么死鎖涉及到的各個(gè)進(jìn)程都將永遠(yuǎn)處于封鎖狀態(tài)。從上面的例子可以看出，計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng)。即：一種原因是系統(tǒng)提供的資源太少了，遠(yuǎn)不能滿足并發(fā)進(jìn)程對(duì)資源的需求。這種競(jìng)爭(zhēng)資源引

5、起的死鎖是我們要討論的核心。例如：消息是一種臨時(shí)性資源。某一時(shí)刻，進(jìn)程A等待進(jìn)程B發(fā)來(lái)的消息，進(jìn)程B等待進(jìn)程C發(fā)來(lái)的消息，而進(jìn)程C又等待進(jìn)程A發(fā)來(lái)的消息。消息未到，A，B，C三個(gè)進(jìn)程均無(wú)法向前推進(jìn)，也會(huì)發(fā)生進(jìn)程通信上的死鎖。另一種原因是由于進(jìn)程推進(jìn)順序不適宜引發(fā)的死鎖。資源少也未必一定產(chǎn)生死鎖。就如同兩個(gè)人過(guò)獨(dú)木橋，假設(shè)兩個(gè)人都要先過(guò)，在獨(dú)木橋上僵持不肯后退，必然會(huì)應(yīng)競(jìng)爭(zhēng)資源產(chǎn)生死鎖；但是，假設(shè)兩個(gè)人上橋前先看一看有無(wú)對(duì)方的人在橋上，當(dāng)無(wú)對(duì)方的人在橋上時(shí)自己才上橋，那么問(wèn)題就解決了。所以，假設(shè)程序設(shè)計(jì)得不合理，造成進(jìn)程推進(jìn)的順序不當(dāng)，也會(huì)出現(xiàn)死鎖。2.產(chǎn)生死鎖的必要條件從以上分析可見(jiàn)，假設(shè)在計(jì)

6、算機(jī)系統(tǒng)中同時(shí)具備下面四個(gè)必要條件時(shí)，那么會(huì)發(fā)生死鎖。換句話說(shuō)，只要下面四個(gè)條件有一個(gè)不具備，系統(tǒng)就不會(huì)出現(xiàn)死鎖。1互斥條件。即某個(gè)資源在一段時(shí)間內(nèi)只能由一個(gè)進(jìn)程占有，不能同時(shí)被兩個(gè)或兩個(gè)以上的進(jìn)程占有。這種獨(dú)占資源如CD-ROM驅(qū)動(dòng)器，打印機(jī)等等，必須在占有該資源的進(jìn)程主動(dòng)釋放它之后，其它進(jìn)程才能占有該資源。這是由資源本身的屬性所決定的。如獨(dú)木橋就是一種獨(dú)占資源，兩方的人不能同時(shí)過(guò)橋。2不可搶占條件。進(jìn)程所獲得的資源在未使用完畢之前，資源申請(qǐng)者不能強(qiáng)行地從資源占有者手中奪取資源，而只能由該資源的占有者進(jìn)程自行釋放。如過(guò)獨(dú)木橋的人不能強(qiáng)迫對(duì)方后退，也不能非法地將對(duì)方推下橋，必須是橋上的人自己過(guò)

7、橋后空出橋面即主動(dòng)釋放占有資源，對(duì)方的人才能過(guò)橋。3占有且申請(qǐng)條件。進(jìn)程至少已經(jīng)占有一個(gè)資源，但又申請(qǐng)新的資源；由于該資源已被另外進(jìn)程占有，此時(shí)該進(jìn)程阻塞；但是，它在等待新資源之時(shí)，仍繼續(xù)占用已占有的資源。還以過(guò)獨(dú)木橋?yàn)槔滓覂扇嗽跇蛏舷嘤?。甲走過(guò)一段橋面即占有了一些資源，還需要走其余的橋面申請(qǐng)新的資源，但那部分橋面被乙占有乙走過(guò)一段橋面。甲過(guò)不去，前進(jìn)不能，又不后退；乙也處于同樣的狀況。4循環(huán)等待條件。存在一個(gè)進(jìn)程等待序列P1，P2，.，Pn，其中P1等待P2所占有的某一資源，P2等待P3所占有的某一源，.，而Pn等待P1所占有的的某一資源，形成一個(gè)進(jìn)程循環(huán)等待環(huán)。就像前面的過(guò)獨(dú)木橋問(wèn)題，

8、甲等待乙占有的橋面，而乙又等待甲占有的橋面，從而彼此循環(huán)等待。上面我們提到的這四個(gè)條件在死鎖時(shí)會(huì)同時(shí)發(fā)生。也就是說(shuō)，只要有一個(gè)必要條件不滿足，那么死鎖就可以排除。8.2死鎖的預(yù)防前面介紹了死鎖發(fā)生時(shí)的四個(gè)必要條件，只要破壞這四個(gè)必要條件中的任意一個(gè)條件，死鎖就不會(huì)發(fā)生。這就為我們解決死鎖問(wèn)題提供了可能。一般地，解決死鎖的方法分為死鎖的預(yù)防，防止，檢測(cè)與恢復(fù)三種注意：死鎖的檢測(cè)與恢復(fù)是一個(gè)方法。我們將在下面分別加以介紹。死鎖的預(yù)防是保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的一種策略。它的根本思想是要求進(jìn)程申請(qǐng)資源時(shí)遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，保證系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。1打破互斥條件

9、。即允許進(jìn)程同時(shí)訪問(wèn)某些資源。但是，有的資源是不允許被同時(shí)訪問(wèn)的，像打印機(jī)等等，這是由資源本身的屬性所決定的。所以，這種方法并無(wú)實(shí)用價(jià)值。2打破不可搶占條件。即允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。就是說(shuō)，當(dāng)一個(gè)進(jìn)程已占有了某些資源，它又申請(qǐng)新的資源，但不能立即被滿足時(shí)，它必須釋放所占有的全部資源，以后再重新申請(qǐng)。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地侵占了。這種預(yù)防死鎖的方法實(shí)現(xiàn)起來(lái)困難，會(huì)降低系統(tǒng)性能。3打破占有且申請(qǐng)條件?？梢詫?shí)行資源預(yù)先分配策略。即進(jìn)程在運(yùn)行前一次性地向系統(tǒng)申請(qǐng)它所需要的全部資源。假設(shè)某個(gè)進(jìn)程所需的全部資源得不到滿足，那么不分配任何資源，此

10、進(jìn)程暫不運(yùn)行。只有當(dāng)系統(tǒng)可以滿足當(dāng)前進(jìn)程的全部資源需求時(shí)，才一次性地將所申請(qǐng)的資源全部分配給該進(jìn)程。由于運(yùn)行的進(jìn)程已占有了它所需的全部資源，所以不會(huì)發(fā)生占有資源又申請(qǐng)資源的現(xiàn)象，因此不會(huì)發(fā)生死鎖。但是，這種策略也有如下缺點(diǎn)：1在許多情況下，一個(gè)進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時(shí)是動(dòng)態(tài)的，不可預(yù)測(cè)的；2資源利用率低。無(wú)論所分資源何時(shí)用到，一個(gè)進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長(zhǎng)期占著不用的狀況。這顯然是一種極大的資源浪費(fèi)；3降低了進(jìn)程的并發(fā)性。因?yàn)橘Y源有限，又加上存在浪費(fèi)，能分配到所需全

11、部資源的進(jìn)程個(gè)數(shù)就必然少了。4打破循環(huán)等待條件，實(shí)行資源有序分配策略。采用這種策略，即把資源事先分類(lèi)編號(hào)，按號(hào)分配，使進(jìn)程在申請(qǐng)，占用資源時(shí)不會(huì)形成環(huán)路。所有進(jìn)程對(duì)資源的懇求必須嚴(yán)格按資源序號(hào)遞增的順序提出。進(jìn)程占用了小號(hào)資源，才能申請(qǐng)大號(hào)資源，就不會(huì)產(chǎn)生環(huán)路，從而預(yù)防了死鎖。這種策略與前面的策略相比，資源的利用率和系統(tǒng)吞吐量都有很大進(jìn)步，但是也存在以下缺點(diǎn)：1限制了進(jìn)程對(duì)資源的懇求，同時(shí)給系統(tǒng)中所有資源合理編號(hào)也是件困難事，并增加了系統(tǒng)開(kāi)銷(xiāo)；2為了遵循按編號(hào)申請(qǐng)的次序，暫不使用的資源也需要提早申請(qǐng)，從而增加了進(jìn)程對(duì)資源的占用時(shí)間。8.3死鎖的防止上面我們講到的死鎖預(yù)防是排除死鎖的靜態(tài)策略，它

12、使產(chǎn)生死鎖的四個(gè)必要條件不能同時(shí)具備，從而對(duì)進(jìn)程申請(qǐng)資源的活動(dòng)加以限制，以保證死鎖不會(huì)發(fā)生。下面我們介紹排除死鎖的動(dòng)態(tài)策略-死鎖的防止，它不限制進(jìn)程有關(guān)申請(qǐng)資源的命令，而是對(duì)進(jìn)程所發(fā)出的每一個(gè)申請(qǐng)資源命令加以動(dòng)態(tài)地檢查，并根據(jù)檢查結(jié)果斷定是否進(jìn)展資源分配。就是說(shuō)，在資源分配過(guò)程中假設(shè)預(yù)測(cè)有發(fā)生死鎖的可能性，那么加以防止。這種方法的關(guān)鍵是確定資源分配的平安性。1.平安序列我們首先引入平安序列的定義：所謂系統(tǒng)是平安的，是指系統(tǒng)中的所有進(jìn)程可以按照某一種次序分配資源，并且依次地運(yùn)行完畢，這種進(jìn)程序列P1，P2，.，Pn就是平安序列。假設(shè)存在這樣一個(gè)平安序列，那么系統(tǒng)是平安的；假設(shè)系統(tǒng)不存在這樣一個(gè)平

13、安序列，那么系統(tǒng)是不平安的。平安序列P1，P2，.，Pn是這樣組成的：假設(shè)對(duì)于每一個(gè)進(jìn)程Pi，它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足，那么P1，P2，.，Pn為一個(gè)平安序列，這時(shí)系統(tǒng)處于平安狀態(tài)，不會(huì)進(jìn)入死鎖狀態(tài)。雖然存在平安序列時(shí)一定不會(huì)有死鎖發(fā)生，但是系統(tǒng)進(jìn)入不平安狀態(tài)四個(gè)死鎖的必要條件同時(shí)發(fā)生也未必會(huì)產(chǎn)生死鎖。當(dāng)然，產(chǎn)生死鎖后，系統(tǒng)一定處于不平安狀態(tài)。2.銀行家算法這是一個(gè)著名的防止死鎖的算法，是由Dijstra首先提出來(lái)并加以解決的。背景知識(shí)一個(gè)銀行家如何將一定數(shù)目的資金平安地借給假設(shè)干個(gè)客戶，使這些客戶既能借到錢(qián)完成要干的事，同時(shí)銀行家又能收回

14、全部資金而不至于破產(chǎn)，這就是銀行家問(wèn)題。這個(gè)問(wèn)題同操作系統(tǒng)中資源分配問(wèn)題非常相似：銀行家就像一個(gè)操作系統(tǒng)，客戶就像運(yùn)行的進(jìn)程，銀行家的資金就是系統(tǒng)的資源。問(wèn)題的描繪一個(gè)銀行家擁有一定數(shù)量的資金，有假設(shè)干個(gè)客戶要貸款。每個(gè)客戶須在一開(kāi)場(chǎng)就聲明他所需貸款的總額。假設(shè)該客戶貸款總額不超過(guò)銀行家的資金總數(shù)，銀行家可以接收客戶的要求。客戶貸款是以每次一個(gè)資金單位如1萬(wàn)RMB等的方式進(jìn)展的，客戶在借滿所需的全部單位款額之前可能會(huì)等待，但銀行家須保證這種等待是有限的，可完成的。例如：有三個(gè)客戶C1，C2，C3，向銀行家借款，該銀行家的資金總額為10個(gè)資金單位，其中C1客戶要借9各資金單位，C2客戶要借3個(gè)資

15、金單位，C3客戶要借8個(gè)資金單位，總計(jì)20個(gè)資金單位。某一時(shí)刻的狀態(tài)如以下圖。C1 27C2 21C3 44余額2 C1 27C3 44余額4 C1 27余額8余額10abcd銀行家算法示意對(duì)于a圖的狀態(tài)，按照平安序列的要求，我們選的第一個(gè)客戶應(yīng)滿足該客戶所需的貸款小于等于銀行家當(dāng)前所剩余的錢(qián)款，可以看出只有C2客戶能被滿足：C2客戶需1個(gè)資金單位，小銀行家手中的2個(gè)資金單位，于是銀行家把1個(gè)資金單位借給C2客戶，使之完成工作并歸還所借的3個(gè)資金單位的錢(qián)，進(jìn)入b圖。同理，銀行家把4個(gè)資金單位借給C3客戶，使其完成工作，在c圖中，只剩一個(gè)客戶C1，它需7個(gè)資金單位，這時(shí)銀行家有8個(gè)資金單位，所以

16、C1也能順利借到錢(qián)并完成工作。最后見(jiàn)圖d銀行家收回全部10個(gè)資金單位，保證不賠本。那么客戶序列C1，C2，C3就是個(gè)平安序列，按照這個(gè)序列貸款，銀行家才是平安的。否那么的話，假設(shè)在圖b狀態(tài)時(shí)，銀行家把手中的4個(gè)資金單位借給了C1，那么出現(xiàn)不平安狀態(tài)：這時(shí)C1，C3均不能完成工作，而銀行家手中又沒(méi)有錢(qián)了，系統(tǒng)陷入僵持場(chǎng)面，銀行家也不能收回投資。綜上所述，銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個(gè)按平安序列檢查各客戶誰(shuí)能完成其工作，然后假定其完成工作且歸還全部貸款，再進(jìn)而檢查下一個(gè)能完成工作的客戶，.。假設(shè)所有客戶都能完成工作，那么找到一個(gè)平安序列，銀行家才是平安的。從上面分析看出，銀行家算法允許死鎖必要條

17、件中的互斥條件，占有且申請(qǐng)條件，不可搶占條件的存在，這樣，它與預(yù)防死鎖的幾種方法相比較，限制條件少了，資源利用程度進(jìn)步了。這是該算法的優(yōu)點(diǎn)。其缺點(diǎn)是：1這個(gè)算法要求客戶數(shù)保持固定不變，這在多道程序系統(tǒng)中是難以做到的。2這個(gè)算法保證所有客戶在有限的時(shí)間內(nèi)得到滿足，但實(shí)時(shí)客戶要求快速響應(yīng)，所以要考慮這個(gè)因素。3由于要尋找一個(gè)平安序列，實(shí)際上增加了系統(tǒng)的開(kāi)銷(xiāo)。8.4死鎖的檢測(cè)與恢復(fù)一般來(lái)說(shuō)，由于操作系統(tǒng)有并發(fā)，共享以及隨機(jī)性等特點(diǎn)，通過(guò)預(yù)防和防止的手段到達(dá)排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開(kāi)銷(xiāo)，而且不能充分利用資源。為此，一種簡(jiǎn)便的方法是系統(tǒng)為進(jìn)程分配資源時(shí)，不采取任何限制性措施，但是提供了

18、檢測(cè)和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來(lái)。因此，在實(shí)際的操作系統(tǒng)中往往采用死鎖的檢測(cè)與恢復(fù)方法來(lái)排除死鎖。死鎖檢測(cè)與恢復(fù)是指系統(tǒng)設(shè)有專(zhuān)門(mén)的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時(shí)，該機(jī)構(gòu)可以檢測(cè)到死鎖發(fā)生的位置和原因，并能通過(guò)外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來(lái)。1.放大觀看圖中所示為一個(gè)小的死鎖的例子。這時(shí)進(jìn)程P1占有資源R1而申請(qǐng)資源R2，進(jìn)程P2占有資源R2而申請(qǐng)資源R1，按循環(huán)等待條件，進(jìn)程和資源形成了環(huán)路，所以系統(tǒng)是死鎖狀態(tài)。進(jìn)程P1，P2是參與死鎖的進(jìn)程。下面我們?cè)賮?lái)看一看死鎖檢測(cè)算法。算法使用的數(shù)據(jù)構(gòu)造是如下這些：占有矩陣A：n*m階，其中n表示并發(fā)進(jìn)程的個(gè)數(shù)

19、，m表示系統(tǒng)的各類(lèi)資源的個(gè)數(shù)，這個(gè)矩陣記錄了每一個(gè)進(jìn)程當(dāng)前占有各個(gè)資源類(lèi)中資源的個(gè)數(shù)。申請(qǐng)矩陣R：n*m階，其中n表示并發(fā)進(jìn)程的個(gè)數(shù)，m表示系統(tǒng)的各類(lèi)資源的個(gè)數(shù)，這個(gè)矩陣記錄了每一個(gè)進(jìn)程當(dāng)前要完成工作需要申請(qǐng)的各個(gè)資源類(lèi)中資源的個(gè)數(shù)?？臻e向量T：記錄當(dāng)前m個(gè)資源類(lèi)中空閑資源的個(gè)數(shù)。完成向量F：布爾型向量值為真true或假false，記錄當(dāng)前n個(gè)并發(fā)進(jìn)程能否進(jìn)展完。為真即能進(jìn)展完，為假那么不能進(jìn)展完。臨時(shí)向量W：開(kāi)場(chǎng)時(shí)W：=T。算法步驟：1W：=T，對(duì)于所有的i=1，2，.，n，假設(shè)Ai=0，那么Fi：=true；否那么，F(xiàn)i：=false2找滿足下面條件的下標(biāo)i：Fi：=false并且Ri=W假設(shè)不存在滿足上面的條件i，那么轉(zhuǎn)到步驟4。3W：=W+AiFi：=true轉(zhuǎn)到步驟24假設(shè)存在i，F(xiàn)i：=false，那么系統(tǒng)處于死鎖狀態(tài)，且Pi進(jìn)程參與了死鎖。什么時(shí)候進(jìn)展死鎖的檢測(cè)取決于死鎖發(fā)生的頻率。假設(shè)死鎖發(fā)生的頻率高，那么死鎖檢測(cè)的頻率也要相應(yīng)進(jìn)步，這樣一