1、死 鎖Deadlock,死鎖 Deadlock,在多道程序系統(tǒng)中，多個進(jìn)程并發(fā)運行，共享資源，從而提高了資源的利用率。但是若對資源的管理和使用不當(dāng)，在一定條件下會導(dǎo)致系統(tǒng)發(fā)生一種隨機(jī)性故障死鎖。在一些系統(tǒng)中，比如實時控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致災(zāi)難性的后果。 死鎖Deadlock：是計算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進(jìn)程由于競爭資源而造成的一種互相等待的現(xiàn)象（僵局），如無外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。,陷入死鎖狀態(tài)的進(jìn)程稱為死鎖進(jìn)程，所占用的資源或者需要它們進(jìn)行某種合作的其它進(jìn)程就會相繼陷入死鎖，最終可能導(dǎo)致整個系統(tǒng)處于癱瘓狀態(tài)。,資源的概念,OS是計算機(jī)系統(tǒng)中資源

2、的管理者，而進(jìn)程是競爭資源的基本單位，故對系統(tǒng)中所有進(jìn)程的資源分配工作，都由OS完成。 研究資源分配時，我們必須搞清該資源是可以被幾個進(jìn)程同時使用，還是只能為一個進(jìn)程使用，資源的不同使用性質(zhì)正是引起系統(tǒng)死鎖的原因。,資源的分類,根據(jù)資源性質(zhì)：可剝奪（搶占）和不可剝奪（搶占）資源。 可搶占資源: 指資源占有進(jìn)程雖然需要使用該資源，但另一個進(jìn)程卻強(qiáng)行把資源從占有者進(jìn)程處搶來。 不可搶占資源: 指只有占用者進(jìn)程不再需要使用該資源而主動釋放資源外，其它進(jìn)程不得在占有者進(jìn)程使用資源過程中強(qiáng)行搶占。,產(chǎn)生死鎖的原因,競爭資源: 當(dāng)系統(tǒng)中供多個進(jìn)程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競

3、爭而產(chǎn)生死鎖； 競爭臨界資源 競爭臨時性資源 2 進(jìn)程推進(jìn)的順序不當(dāng) : 進(jìn)程在運行過程中，請求和釋放資源的順序不當(dāng)，導(dǎo)致進(jìn)程的死鎖。,競爭資源,競爭臨界資源引起死鎖 P1占用資源B, P2占用資源A, P1要求使用資源A, P2要求使用資源B,競爭資源,競爭臨時性資源(如進(jìn)程通信中的消息),P1：Release(S1);Request(S3) P2：Release(S2);Request(S1) P3：Release(S3);Request(S2) 不可能發(fā)生死鎖,P1：Request(S3);Release(S1) P2：Request(S1);Release(S2) P3：Request

4、(S2);Release(S3) 可能發(fā)生死鎖,S1、S2、S3是臨時資源,進(jìn)程推進(jìn)順序不當(dāng),3和4推進(jìn)方式將引發(fā)死鎖,不會發(fā)生死鎖的情況,永久性資源產(chǎn)生死鎖的必要條件,1 互斥條件:進(jìn)程訪問的是臨界資源，那個資源一次只能被一個進(jìn)程所使用。 2 請求和保持條件:（部分分配）一個進(jìn)程在請求新的資源的同時，保持對某些資源的占有。 3 不剝奪條件:一個資源僅能被占有它的進(jìn)程所釋放，而不能被其他進(jìn)程剝奪。 4 環(huán)路等待條件:存在一個進(jìn)程的環(huán)路鏈，鏈中每一個進(jìn)程占用有著某個或某些資源，又在等待鏈中的另一個進(jìn)程占有的資源。,涉及死鎖的四個問題,1 預(yù)防死鎖 設(shè)法不讓系統(tǒng)產(chǎn)生死鎖, 通過設(shè)置某些限制性條件去

5、破壞產(chǎn)生死鎖的4個必要條件中的一個或幾個來實現(xiàn)。易導(dǎo)致系統(tǒng)資源利用利和系統(tǒng)吞吐量的下降。 2 避免死鎖 資源的動態(tài)分配過程中,用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)。 3 檢測死鎖 及時檢測出死鎖的發(fā)生,精確確定與死鎖有關(guān)的進(jìn)程和資源,為解除死鎖創(chuàng)造條件。 4 解除死鎖 常用的方法是撤銷或掛起一些進(jìn)程,以便回收部分資源,再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程,使之繼續(xù)運行。,鴕鳥算法（置之不理） 解決死鎖的最簡單方法就是鴕鳥算法。即像鴕鳥一樣，當(dāng)遇到危險時，將頭埋進(jìn)沙子里，假裝毫無問題。 當(dāng)死鎖在計算機(jī)中很少出現(xiàn)時，比如說每五年或更長時間才出現(xiàn)一次時，人們就不必花費更多的精力去解決它，而是采用類似

6、鴕鳥一樣的辦法忽略它。 以UNIX系統(tǒng)為例，它潛在地存在死鎖，但它并不花功夫去檢測和解除死鎖，而是忽略不去理它。,預(yù)防死鎖,根據(jù)生產(chǎn)死鎖的四個必要條件，只要使用其中之一不能成立，死鎖就不會出現(xiàn)。但必要條件(1)是由設(shè)備的固有特性所決定的，不僅不能改變，相反還應(yīng)加以保證，因此實際上只有三種方法。 預(yù)防死鎖是一種較易實現(xiàn)的方法，已被廣泛使用，但由于所施加的限制條件往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。,1 互斥條件 2 請求和保持條件 3 不剝奪條件 4 環(huán)路等待條件,1.資源靜態(tài)分配法（摒棄請求和保持條件）,系統(tǒng)要求任一進(jìn)程必須預(yù)先申請它所需的全部資源，而且僅當(dāng)該進(jìn)程的全部資源要求

7、能得到滿足時，系統(tǒng)才能給予一次性分配，然后啟動該進(jìn)程運行，但是在分配時只要有一種資源不滿足，系統(tǒng)就不會給進(jìn)程分配資源。進(jìn)程運行期間，不會再請求新的資源，所以，再分配就不會發(fā)生（摒棄了部分分配）。 特點： 資源嚴(yán)重浪費 進(jìn)程延遲進(jìn)行,2.資源暫時釋放法(破壞“不剝奪”條件),采用的策略：一個已經(jīng)保持了某些資源的進(jìn)程，當(dāng)它再提出新的資源要求而不能立即得到滿足時，必須釋放它已經(jīng)保持的所有資源，待以后需要時再重新申請。 實現(xiàn)比較復(fù)雜，且要付出很大代價；此外，還因為反復(fù)地申請和釋放資源，而使進(jìn)程的執(zhí)行無限地推遲，延長了周轉(zhuǎn)時間，增加了系統(tǒng)的開銷，降低了系統(tǒng)吞吐量。（例如打印機(jī)打印的結(jié)果不連續(xù)）,3.資源

8、有序使用法(破壞“環(huán)路等待”條件),采用資源順序使用法，基本思想是：把系統(tǒng)中所有資源類型線性排隊，并按遞增規(guī)則賦予每類資源以唯一的編號。例如輸入機(jī)1，打印機(jī)2，磁帶機(jī)3，磁盤4等等。進(jìn)程申請資源時，必須嚴(yán)格按資源編號的遞增順序進(jìn)行，否則系統(tǒng)不予分配。 優(yōu)點： 資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善。 缺點： 為系統(tǒng)中各種類型的資源所分配的序號必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加 作業(yè)實際使用資源的順序與系統(tǒng)規(guī)定的順序不同而造成資源的浪費,避免死鎖,避免死鎖與預(yù)防死鎖的區(qū)別在于，預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之一，嚴(yán)格地防止死鎖的出現(xiàn)。 避免死鎖，它是在進(jìn)程請求分配資

9、源時，采用銀行家算法(資源安全分配算法)等防止系統(tǒng)進(jìn)入不安全狀態(tài)。,系統(tǒng)的安全狀態(tài),系統(tǒng)狀態(tài)： 安全狀態(tài)：指系統(tǒng)能按照某種順序如 (稱為序列為安全序列)，為每個進(jìn)程分配所需的資源，直至最大需求，使得每個進(jìn)程都能順利完成。 非安全狀態(tài)：即在某個時刻系統(tǒng)中不存在一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)或非安全狀態(tài)。 雖然并非所有不安全狀態(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)。因此，避免死鎖的實質(zhì)是如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。,安全狀態(tài)的例子,例：假定系統(tǒng)有三個進(jìn)程P1、P2、P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)

10、，P2和P3分別要求4臺和9臺。設(shè)在T0時刻，進(jìn)程P1、P2和P3已經(jīng)獲得5臺、2臺和2臺，還有3臺空閑沒有分配。,進(jìn)程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0時刻系統(tǒng)時安全的。這時存在一個安全序列,不安全序列 .,雖然并非所有不安全狀態(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)。因此，避免死鎖的實質(zhì)是如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。 系統(tǒng)的狀態(tài)可能通過下述來描述： 進(jìn)程剩余申請數(shù)最大申請數(shù)占有數(shù)。 可分配資源數(shù)總數(shù)占有數(shù)之和。,銀行家算法,銀行的一個主要業(yè)務(wù)是借貸款, 為了滿足顧客申請借款

11、的要求, 同時又能使銀行在規(guī)定的時限內(nèi)收回自己的投資, 銀行家必須研究一種合理的借貸次序為多個顧客貸款。 銀行家算法是最有代表性的避免死鎖算法，是Dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為實現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。,N: 表示進(jìn)程總數(shù) M: 表示系統(tǒng)資源類型數(shù),銀行家算法中的數(shù)據(jù)結(jié)構(gòu),1 可利用資源向量Available(一維數(shù)組) 是一個含有m個元素，其中的每一個元素代表一類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。如果Availablej=k，表示系統(tǒng)中現(xiàn)有Rj類資源k個。 2 最大需求矩陣Max(二維數(shù)組)

12、 是一個含有nm的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max(i,j)=k，表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。 3 分配矩陣Allocation(二維數(shù)組) 是一個含有nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation(i,j)=k，表示進(jìn)程i當(dāng)前已分得Rj類資源k個。,4 進(jìn)程當(dāng)前資源請求向量Request(一維數(shù)組) 當(dāng)某進(jìn)程i需要系統(tǒng)資源時,就將其對各類資源的請求數(shù)送入Request數(shù)組中 5 布爾向量Finish(一維數(shù)組) 代表每一個進(jìn)程是否能得足夠的系統(tǒng)資源并順利結(jié)束運行。 6 需求矩陣Need (二維數(shù)

13、組) 是一個含有n*m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need(i,j)=k，表示進(jìn)程i還需要Rj類資源k個，方能完成其任務(wù)。 Need(i,j)= Max(i,j)-Allocation(i,j) 7 系統(tǒng)工作向量Work(一維數(shù)組) 代表系統(tǒng)中可供進(jìn)程繼續(xù)運行的各類資源的數(shù)目。,銀行家算法,當(dāng)進(jìn)程Pi需要請求系統(tǒng)資源時,將其對各類資源的需求數(shù)量送入Request數(shù)組中, 并按下述步驟進(jìn)行檢查： 1 如果Request(j)Need(i,j),則轉(zhuǎn)向步驟2；否則認(rèn)為出錯。(因為它所需要的資源數(shù)已超過它所宣布的最大值) 2 如果Request(j)Available(j),則轉(zhuǎn)

14、向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待 3 系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available(j)=Available(j)-Request(j); Allocation(i,j)=Allocation(i,j)+Request(j); Need(i,j)= Need(i,j)- Request(j); 4 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。,j取值為1M,安全性算法,1 工作向量Work初始化。表示系統(tǒng)

15、可提供給進(jìn)程繼續(xù)運行所需要的各類資源的數(shù)目，它含有M個元素， Work(j)=Available(j) (j: 1M) Finish向量表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，開始時Finishi=false ( i : 1 N ) 2 從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：Finishi=false; Need(i,j)Work(j) 。如找到，執(zhí)行步驟3；否則執(zhí)行步驟4。 3 此時若進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并會釋放出分配給它的資源，故執(zhí)行： Work(j)=Work(j)+Allocation(i,j); Finishi:=true;判斷所有的Finish(k)是否為tr

16、ue,若是則系統(tǒng)安全,算法結(jié)束 Goto step2; 4 系統(tǒng)已經(jīng)找不到一個令可以令所有進(jìn)程均執(zhí)行完成的安全分配序列系統(tǒng)處于不安全狀態(tài), 算法結(jié)束。,銀行家算法舉例,銀行家算法的特點 系統(tǒng)資源的利用率比預(yù)防死鎖的方法要高 不能適應(yīng)系統(tǒng)資源數(shù)量和進(jìn)程數(shù)目的變化 要求進(jìn)程必須事先說明它們的最大資源需求量 算法的實現(xiàn)需要一些系統(tǒng)開銷,死鎖的檢測,死鎖的檢測和恢復(fù)技術(shù)是指定期啟動一個軟件檢測系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復(fù)之。 死鎖狀態(tài)的檢測思想 檢查死鎖的辦法就是由軟件檢查系統(tǒng)中由進(jìn)程和資源構(gòu)成的有向圖是否構(gòu)成一個或多個環(huán)路，若是，則存在死鎖，否則不存在。 死鎖的檢測：實質(zhì)是確定是否存

17、在環(huán)路等待現(xiàn)象，一旦發(fā)現(xiàn)這種環(huán)路便認(rèn)定死鎖存在，并識別出該環(huán)路所涉及的有關(guān)進(jìn)程，以供系統(tǒng)采取適當(dāng)?shù)拇胧﹣斫獬梨i。最常用的是一種基于資源分配圖RAG和死鎖定理的檢測死鎖算法,資源分配圖（RAG）,系統(tǒng)死鎖可用資源分配圖來描述，該圖是由一組結(jié)點N和一組邊E所組成的一對偶G=(N,E)。（用圓圈代表一個進(jìn)程，用方框代表一類資源，由于一種類型的資源可能有多個，可用方框中的一個點代表一類資源中的一個資源） 幾個概念：進(jìn)程結(jié)點, 資源結(jié)點, 請求邊，分配邊,P1,P2,R1,R2,請求R2,資源分配圖,P3,獨立結(jié)點 : P3 非獨立結(jié)點: P1, P2,資源分配圖的化簡,封鎖進(jìn)程：是指某個進(jìn)程由于請求

18、了超過了系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進(jìn)程。 非封鎖進(jìn)程：即沒有被系統(tǒng)封鎖的進(jìn)程資源分配圖的化簡方法：假設(shè)某個RAG中存在一個進(jìn)程Pi，此刻Pi是非封鎖進(jìn)程，那么可以進(jìn)行如下化簡：當(dāng)Pi有請求邊時，首先將其請求邊變成分配邊(即滿足Pi的資源請求)，而一旦Pi的所有資源請求都得到滿足，Pi就能在有限的時間內(nèi)運行結(jié)束，并釋放其所占用的全部資源，此時Pi只有分配邊，刪去這些分配邊（實際上相當(dāng)于消去了Pi的所有請求邊和分配邊），使Pi成為孤立結(jié)點。（反復(fù)進(jìn)行） 完全可化簡/不可化簡/非完全可化簡,RAG的化簡,P1,P2,R1,R2,P1,P2,R1,R2,完全可化簡, 非封鎖進(jìn)程P1, P2,P1,P2,R1,R2,不可化簡, P1為封鎖進(jìn)程,死鎖定理,在進(jìn)程申請資源而阻塞, 但進(jìn)程不主動釋放它已占用資源的前提下, 系統(tǒng)在某個時刻的狀態(tài)S為死鎖狀態(tài)的充要條件是S時刻系統(tǒng)的資源分配圖是不可完全簡化的。 在經(jīng)過一系列的簡化后，若能消去圖中的所有邊，使所有的進(jìn)程都成為孤立結(jié)點，則稱該圖是可完全簡化的；反之的是不可完全簡化的。資源分配圖中不能化簡的進(jìn)程即為死鎖進(jìn)程。,檢測算法中的數(shù)據(jù)