產(chǎn)生死鎖的原因和必要條件

3.5.1產(chǎn)生死鎖的原因系統(tǒng)產(chǎn)生死鎖的根本原因可歸結(jié)為兩點：競爭資源當系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖。進程推進順序非法進程在運行過程中，請求和釋放資源的順序不當，導(dǎo)致了進程死鎖。第1頁/共63頁一、競爭資源引起死鎖1、可將系統(tǒng)中的資源分為兩類：可剝奪性資源和非剝奪性資源。

可剝奪性資源是指：某進程在獲得這類資源后，該資源可被其他進程搶占。如處理機、內(nèi)存。優(yōu)先權(quán)高的進程可以剝奪優(yōu)先權(quán)低的進程的處理機；內(nèi)存區(qū)可由內(nèi)存管理程序把一個進程從一個存儲區(qū)移到另一個存儲區(qū)，即剝奪了該進程原來占有的存儲區(qū)。第2頁/共63頁

非剝奪性資源是指：進程一旦占有該資源，就不可搶占，不管其它進程的優(yōu)先權(quán)是否高于當前進程，只能在該進程用完后自行釋放。如打印機、磁帶機等。大多數(shù)情況下，我們所講引起的死鎖的資源競爭，是指對于非剝奪性資源的競爭。第3頁/共63頁2、競爭非剝奪性資源

若系統(tǒng)中只有一臺打印機R1和一臺磁帶機R2，可供進程P1和P2共享。假定P1已占用了打印機R1，P2占用了磁帶機R2。此時，若P2繼續(xù)要求打印機，P2將阻塞；P1若又要求磁帶機，P1也將阻塞。于是，P1與P2之間便形成了僵局，兩個進程都在等待對方釋放出自己所需的資源，但它們又都因不能獲得所需的資源而不能繼續(xù)推進，從而也不釋放自己已占用的資源，就進入了死鎖狀態(tài)。第4頁/共63頁I/O設(shè)備共享時的死鎖情況P2P1R1R2

方塊代表資源圓圈代表進程箭頭從進程指向資源，表示進程請求該資源箭頭從資源指向進程，表示該資源已分配給進程第5頁/共63頁3、競爭臨時性資源

臨時性資源，也稱為消耗性資源，是指由一個進程產(chǎn)生，被另一進程使用一短暫時間后便無用的資源，如消息等。競爭臨時性資源也可能引起死鎖。第6頁/共63頁例：S1、S2、S3是臨時性資源，進程P1產(chǎn)生消息S1，又要求接收S3；P3產(chǎn)生消息S3，又要求接收S2；P2產(chǎn)生消息S2，又要求接收S1。若消息通信按以下順序進行：P1:……Release(S1);Request(S3);……P2:……Release(S2);Request(S1);……P3:……Release(S3);Request(S1);……并不可能發(fā)生死鎖。第7頁/共63頁若按以下運行順序：P1:…Request(S3);Release(S1);…P2:…Request(S1);Release(S2);…P3:…Request(S2);Release(S3);…則可能發(fā)生死鎖P3P1S2S2P2S1進程通信時的死鎖第8頁/共63頁二、進程推進順序不當引起死鎖1、進程推進順序合法例：在進程P1和P2并發(fā)執(zhí)行時，如果按以下順序推進：

P1Request(R1);P1Request(R2);P1Release(R1);P1Release(R2); P2Request(R2);P2Request(R1);P2Release(R2);P2Release(R1);

則兩個進程可順利完成。如下圖4-16中的曲線1所示。第9頁/共63頁第10頁/共63頁第11頁/共63頁第12頁/共63頁2、進程推進順序非法

若并發(fā)進程P1和P2按曲線條所示的順序推進，P1保持了資源R1，P2保持了資源R2，系統(tǒng)處于不安全狀態(tài)。當P1運行到P1Request(R2)時，將因R2已被P2占用而阻塞；當P2運行到P2Request(R1)時，又因R1已被P1占用而阻塞，于是發(fā)生了進程死鎖。第13頁/共63頁第14頁/共63頁3.5.2產(chǎn)生死鎖的必要條件系統(tǒng)中如果死鎖發(fā)生，則一定同時存在下列四個條件，即死鎖的必要條件：（1）互斥條件（2）占有且申請條件

（3）不可搶占條件（4）環(huán)路條件第15頁/共63頁（1）互斥條件對于一個排它性資源，某一時刻最多只能由一個進程占有，不能同時分配給兩個以上的進程。如果此時還有其它進程要求該資源，要求者只能阻塞，直到占有該資源的進程放棄該資源后，其它進程才能占有該資源。如打印機是臨界資源，各進程必須互斥地使用。第16頁/共63頁（2）請求和保持條件進程已經(jīng)保持了至少一個資源，但又申請新的資源；而該資源已被另外進程占有，此時該進程阻塞；但是，它在等待新資源時，仍不釋放已保持的資源。（3）不剝奪條件進程所獲得的資源，在未使用完畢之前，不能被強行剝奪該資源；只能在該進程釋放已獲得的資源后，其它進程才可以使用。第17頁/共63頁（4）環(huán)路等待條件如果死鎖產(chǎn)生，則一定存在一個“進程-資源”的環(huán)形鏈。即進程集合{P0,P1,…Pn}，其中P0等待P1所占有的資源，P1等待P2所需的資源，…，Pn-1等待Pn所占有的資源，Pn等待P0所占有的資源。

以上四個條件是在死鎖發(fā)生時同時出現(xiàn)的，我們可以利用它的逆否命題，即：四個條件中只要有一個不滿足，則死鎖不會發(fā)生。這正是我們預(yù)防死鎖所需考慮的方法。第18頁/共63頁3.5.3解決死鎖問題的基本方法為保證系統(tǒng)的正常運行，應(yīng)事先采取措施，預(yù)防或避免死鎖的發(fā)生。在系統(tǒng)已出現(xiàn)死鎖后，要及時檢測到死鎖并解除死鎖。目前用于處理死鎖問題的方法有以下幾種：

1．死鎖的預(yù)防

2．死鎖的避免

3．死鎖的檢測

4．死鎖的解除第19頁/共63頁3.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖一、摒棄“請求和保持”條件1、實現(xiàn)方法要求進程一次性申請整個運行進程中的全部資源，只有申請到全部資源后，方可投入運行；這樣進程運行期間不會再提出資源要求。只要有一種資源要求不能滿足，則全部其它資源都不分配給進程，而讓該進程等待；這樣，進程等待期間未占有任何資源。第20頁/共63頁一、摒棄“請求和保持”條件優(yōu)點： 簡單，易于實現(xiàn)，安全。缺點： 資源嚴重浪費，進程延遲運行。第21頁/共63頁二、摒棄“不剝奪”條件1、實現(xiàn)方法：一個已保持了某些資源的進程，當它在提出新的資源要求而不能得到立即滿足時，必須釋放它已經(jīng)保持的所有資源，待以后需要時再重新申請。2、缺點： 實現(xiàn)復(fù)雜、代價高。第22頁/共63頁三、摒棄“環(huán)路等待”條件1、實現(xiàn)方法：將所有的資源按類型進行線性排隊，并賦予不同的序號；并規(guī)定進程的資源請求必須按資源序號遞增的次序提出。這樣在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路；在采用這種策略時，總有一個進程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，因而進程可以一直向前推進。第23頁/共63頁優(yōu)點： 資源利用率和系統(tǒng)吞吐量得到了提高。缺點： ⑴、限制了新設(shè)備的增加。 ⑵、系統(tǒng)為資源分配的序號與進程實際使用資源的順序不同而造成資源浪費。 ⑶、給用戶編程帶來了麻煩。第24頁/共63頁3.6.2系統(tǒng)的安全狀態(tài)

預(yù)防死鎖的方法都是施加了較強的限制條件而使實現(xiàn)簡單，但損害了系統(tǒng)的性能。在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在避免死鎖的方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)，就可避免發(fā)生死鎖。第25頁/共63頁一、安全狀態(tài)

在避免死鎖的方法中，允許進程動態(tài)地申請資源，系統(tǒng)在進行資源分配之前，先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，便將資源分配給進程；否則，進程等待。所謂“安全狀態(tài)”，是指系統(tǒng)能按某種順序如<P1,P2,……Pn>序列，來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣的安全序列，則稱系統(tǒng)處于不安全狀態(tài)。第26頁/共63頁

雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當系統(tǒng)進入不安全狀態(tài)時，便可能進而進入死鎖狀態(tài)；反之，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質(zhì)在于：如何使系統(tǒng)不進入不安全狀態(tài)。第27頁/共63頁二、安全狀態(tài)舉例

假定系統(tǒng)有三個進程P1,P2,P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺，如下表所示：進程最大需求已分配可用P11053P242P392第28頁/共63頁

經(jīng)分析可以發(fā)現(xiàn)，在T0時刻，系統(tǒng)是安全的。因為T0時刻存在一個安全序列〈P2,P1,P3〉，即只要系統(tǒng)按此序列分配資源，每個進程都可以順利完成。第29頁/共63頁三、由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換

當系統(tǒng)不按照安全序列分配資源時，則系統(tǒng)可能由安全狀態(tài)進入不安全狀態(tài)。進程最大需求已分配可用P11053P242P392進程最大需求已分配可用P11052P242P393T0時刻安全狀態(tài)T1時刻不安全狀態(tài)第30頁/共63頁3.6.3利用銀行家算法避免死鎖

最具有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由于該算法可能用于銀行現(xiàn)金貸款而得名的。一個銀行家把他的固定資金貸給若干顧客。只要不出現(xiàn)一個顧客借走所有資金后還不夠，銀行家的資金應(yīng)是安全的。銀行家需一個算法保證借出去的資金在有限時間內(nèi)可收回。第31頁/共63頁一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)1．可利用資源向量Available

也稱為空閑向量。這是一個含有m個元素的數(shù)組。其中的每一個元素，代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目。其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。第32頁/共63頁2．最大需求矩陣Max

這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示第i個進程需要Rj類資源的最大數(shù)目為K。3．分配矩陣Allocation

也叫做占有矩陣。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一進程已占有的每一類資源數(shù)。如果Allocation[i,j]=K，則表示第i個進程當前已分得Rj類資源的數(shù)目為K。第33頁/共63頁4．需求矩陣Need

也叫做申請矩陣。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示第i個進程還需要Rj類資源K個，才能完成其任務(wù)。顯然，以上三個矩陣之間存在如下關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]第34頁/共63頁二、銀行家算法設(shè)Requesti是進程Pi的請求向量，如果Requesti[j]=K，表示進程Pi需要Rj類型的資源的個數(shù)為K。這里要提及的是，Requesti與Needi的關(guān)系可能為以下三種情況：（1）Requesti>Need[i]：表示該進程的資源需求已超過它所宣布的最大值，因此認為出錯。（2）Requesti=Need[i]：表示該進程現(xiàn)在對它所還需的全部資源一次申請完成。（3）Requesti<Need[i]：表示該進程現(xiàn)在對它所需資源再進行部分的申請，剩余的資源以后可再次申請。第35頁/共63頁

當進程Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：（1）如果Requesti≤Need[i]，轉(zhuǎn)向步驟(2)；否則認為出錯，因為它所需要的資源數(shù)已超過它所事先要求的最大值。（2）如果Requesti≤Available，轉(zhuǎn)向步驟3；否則，表示尚無足夠資源，Pi須等待。第36頁/共63頁（3）假設(shè)系統(tǒng)將資源分配給Pi，則需修改如下數(shù)據(jù)結(jié)構(gòu)的值：Available:=Available-Requesti;Allocation[i]:=Allocation[i]+Requesti;Need[i]:=Need[i]-Requesti;（4）系統(tǒng)執(zhí)行安全性算法，檢查若此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。如果是安全的，則將資源真正地分配給進程Pi，否則，將本進程的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，進程Pi等待。第37頁/共63頁三、安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（1）設(shè)置兩個向量：

工作向量Work。它表示在算法執(zhí)行過程中，系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，初始置Work:=Available。

完成向量Finish。它表示系統(tǒng)能否運行完成。它有n個分量，分別表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完畢。開始時，F(xiàn)inish[i]:=false；當有足夠資源分配給進程時，令Finish[i]:=true。第38頁/共63頁（2）從進程集合中找到一個能滿足下述條件的進程i：Finish[i]=false;Needi≤Work；

若找到這樣的進程，執(zhí)行步驟（3）；若找不到這樣的進程，則轉(zhuǎn)步驟（4）。（3）當進程Pi獲得資源后，可順序執(zhí)行，直至完成，并釋放出分配給它的資源，即執(zhí)行：Work:=Work+Allocation[i]；Finish[i]:=true；Goto步驟（2）；第39頁/共63頁（4）若所有進程的Finish[i]=true，則表示系統(tǒng)處于安全狀態(tài)，正式將資源分配給進程Pi；否則，系統(tǒng)處于不安全狀態(tài)，系統(tǒng)不能進行這次試探性分配，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。第40頁/共63頁四、銀行家算法舉例

假定系統(tǒng)中有五個進程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如下圖所示。第41頁/共63頁T0時刻的安全性：在T0時刻存在安全序列{P1，P3，P4，P2，P0},因此系統(tǒng)是目前處于安全狀態(tài)。第42頁/共63頁(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖3-16中的圓括號所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。第43頁/共63頁圖3-18P1申請資源時的安全性檢查

由所進行的安全性檢查得知，可以找到一個安全序列{P1，P3，P4，P0，P2}。因此，系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。第44頁/共63頁(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≦Available(2,3,0)，讓P4等待。第45頁/共63頁(4)P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖3-19所示。（5）進行安全性檢查可用資源Availble(2,1,0)已不能滿足任何進程的需要，因此系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。第46頁/共63頁圖3-19為P0分配資源后的有關(guān)資源數(shù)據(jù)第47頁/共63頁請思考：在銀行家算法中，把P0發(fā)出的請求向量改為Requst0(0，1，0)，系統(tǒng)是否能將資源分配給它？第48頁/共63頁3.7死鎖的檢測與解除3.7.1死鎖的檢測資源分配圖(ResourceAllocationGraph)

系統(tǒng)死鎖可利用資源分配圖來描述。該圖由一組結(jié)點N和一組邊E所組成的一對偶G=（N，E）。

第49頁/共63頁（1）N是頂點的集合，它被分為兩個互斥的子集：進程結(jié)點P={P1，P2，…Pn}；資源結(jié)點R={r1，r2，…rn}。(2)E是有向邊的集合。凡屬于E中的一個邊e∈E，都連接著P中的一個結(jié)點和R中的一個結(jié)點。

e={pi,rj}是資源請求邊，由進程pi指向資源rj，表示進程pi請求一個單位的rj資源。

e={rj,pi}是資源分配邊，由資源rj指向進程pi,它表示把一個單位的資源rj分配給進程pi。

第50頁/共63頁圖3-20每類資源有多個時的情況P={P1,P2}R={r1,r2}N={P1,P2}U{r1,r2}E={(p1,r2),(p2,r1)，

(r1,p1),(r1,p2)，

(r2,p2)

}第51頁/共63頁資源分配圖的化簡方法：假設(shè)某個資源分配圖中存在一個進程Pi，此刻Pi是非封鎖進程，對非封鎖進程Pi的化簡即刪除資源分配圖中與Pi連結(jié)的所有有向邊，使Pi變成孤立結(jié)點，重復(fù)上述過程直到不能化簡為止。二、死鎖定理第52頁/共63頁

首先，在圖3-21(a)中找到一個非封鎖進程P1，刪去其所有的有向邊，使之成為孤立結(jié)點。即讓P1獲得所需的資源而繼續(xù)執(zhí)行，直到運行完畢，再釋放期所占有的全部資源；得到如圖3-21(b)所示。(b)P1P2(a)P1P2第53頁/共63頁(c)P1P2(b)P1P2

由于P1進程釋放了R1資源從而喚醒P2進程，使P2也變成了非封鎖進程，然后我們繼續(xù)化簡P2，刪去P2的所有有向邊，使P2也成了孤立結(jié)點，如圖3-21(c)所示。第54頁/共63頁

在進行一系統(tǒng)的簡化后，若能消去圖中所有的邊，使所有進程都成為孤立結(jié)點，則稱該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。不可簡化的資源分配圖第55頁/共63頁通過資源分配圖，我們就可以很直觀地看出系統(tǒng)中的進程使用資源的情況。很顯然，如果圖中不出現(xiàn)封閉的環(huán)路，則系統(tǒng)中不會存在死鎖。但如果系統(tǒng)出現(xiàn)由各有向邊組成的環(huán)路，則是否產(chǎn)生死鎖，還需進一步分析：如果環(huán)路可以通過化簡的方式取消，則系統(tǒng)一定不產(chǎn)生死鎖；如果環(huán)路通過化簡的方式仍不能取消，即不能再進行簡化，則系統(tǒng)一定會產(chǎn)生死鎖。這就是著名的死鎖定理。第56頁/共63頁三、死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available，它表示了m類資源中每一類資源的可用數(shù)目。(2)把不占用資源的進程