產生死鎖的原因和必要條.ppt

1,3.5產生死鎖的原因 和必要條件,2,3.8 死鎖問題,在多道程序系統中，多個進程并發(fā)運行，共享資源，從而提高了資源的利用率。但是若對資源的管理和使用不當，在一定條件下會導致系統發(fā)生一種隨機性故障死鎖。在一些系統中，比如實時控制系統，系統一旦發(fā)生死鎖將導致災難性的后果。,3,3.8.1 死鎖的基本概念,資源 死鎖的定義 產生死鎖的原因 產生死鎖的必要條件 處理死鎖的基本方法,4,資源的概念,OS是計算機系統中資源的管理者，而進程是競爭資源的基本單位，故對系統中所有進程的資源分配工作，都由OS完成。 研究資源分配時，我們必須搞清該資源是可以被幾個進程同時使用，還是只能為一個進程使用，資源的不同使用性質正是引起系統死鎖的原因。,5,根據資源性質：可剝奪（搶占）和不可剝奪（搶占）資源。 可搶占資源指資源占有進程雖然需要使用該資源，但另一個進程卻強行把資源從占有者進程處搶來。 不可搶占資源指只有占用者進程不再需要使用該資源而主動釋放資源外，其它進程不得在占有者進程使用資源過程中強行搶占。,資源的分類,6,根據使用方式：共享資源和獨享資源。 根據使用期限；永久資源和臨時性資源。,可順序重復使用的資源,由一個進程產生，被另外一個進程使用短暫時間 之后便無用的資源,7,死鎖的定義,死鎖Deadlock：是計算機系統中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進程由于競爭資源而造成的一種互相等待的現象（僵局），如無外力作用，這些進程將永遠不能再向前推進。 陷入死鎖狀態(tài)的進程稱為死鎖進程，所占用的資源或者需要它們進行某種合作的其它進程就會相繼陷入死鎖，最終可能導致整個系統處于癱瘓狀態(tài)。,8,產生死鎖的原因,1 競爭資源。當系統中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產生死鎖； 2 進程推進的順序不當 。進程在運行過程中，請求和釋放資源的順序不當，導致進程的死鎖。,9,競爭資源,1 競爭非剝奪性資源： 2 競爭臨時性資源,打印機R1,磁帶機R2,P1,P2,10,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(S2);Release(S3) 可能發(fā)生死鎖,S1、S2、S3是臨時資源,11,若干死鎖的例子(1),例進程推進順序不當產生死鎖 設系統有打印機、讀卡機各一臺，被進程和共享。兩個進程并發(fā)執(zhí)行，按下列次序請求和釋放資源： 進程 進程 請求讀卡機 請求打印機 請求打印機 請求讀卡機 釋放讀卡機 釋放讀卡機 釋放打印機 釋放打印機,12,P2Rel(R1),P2Rel(R2),P2Req(R1),P2Req(R2),P1Req(R1),P1Req(R2),P1Rel(R1),P1Rel(R2),進程P1、P2并發(fā)執(zhí)行。 資源R1、R2,曲線4將進入不安全區(qū)域（進程推進順序非法）,13,R2已經分配給P1、R1已經分配給P2,14,產生死鎖的四個必要條件,互斥條件:進程訪問的是臨界資源，那個資源一次只能被一個進程所使用。 不剝奪條件:一個資源僅能被占有它的進程所釋放，而不能被其他進程剝奪。 部分分配:（請求和保持條件）一個進程在請求新的資源的同時，保持對某些資源的占有。 環(huán)路等待條件:存在一個進程的環(huán)路鏈，鏈中每一個進程占用有著某個或某些資源，又在等待鏈中的另一個進程占有的資源。,15,若干死鎖的例子(2) 例 PV操作使用不當產生死鎖,進程Q1 進程Q2 P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1);,16,若干死鎖的例子(3) 例 資源分配不當引起死鎖,若系統中有m個資源被n個進程共享，每個進程都要求個資源，而m nK時，即資源數小于進程所要求的總數時，如果分配不得當就可能引起死鎖。,17,若干死鎖的例子(4) 例對臨時性資源使用不加限制引起死鎖,進程通信使用的信件是一種臨時性資源，如果對信件的發(fā)送和接收不加限制，可能引起死鎖。 進程P1等待進程P3的信件S3來到后再向進程P2發(fā)送信件S1；P2又要等待P1的信件S1來到后再向P3發(fā)送信件S2；而P3也要等待P2的信件S2來到后才能發(fā)出信件S3。這種情況下形成了循環(huán)等待，產生死鎖。,18,3.6預防死鎖的方法,破壞第一個條件 使資源可同時訪問而不是互斥使用，是個簡單的辦法，磁盤可用這種辦法管理,但有許多資源往往是不能同時訪問，所以這種做法許多場合行不通。,19,死鎖防止,破壞第二個條件或第四個條件 種種死鎖防止辦法施加于資源的限制條件太嚴格,會造成資源利用率和吞吐率低。兩種比較實用的死鎖防止方法，它們能破壞第二個條件或第四個條件。,20,死鎖防止 1.摒棄”請求和保持” 靜態(tài)分配策略（破壞條件2）,靜態(tài)分配是指一個進程必須在執(zhí)行前就申請它所要的全部資源，并且直到它所要的資源都得到滿足后才開始執(zhí)行。,21,死鎖防止,2.摒棄”不剝奪”條件破壞第三個條件 采用剝奪式調度方法可破壞第三個條件，但只適用于對主存資源和處理器資源的分配， 當進程在申請資源未獲準許的情況下,如主動釋放資源(一種剝奪式),然后才去等待，以后再一起向系統提出申請,也能防止死鎖。,22,死鎖的防止 3.摒棄”環(huán)路等待”條件層次分配策略（破壞條件2和4）,資源被分成多個層次 當進程得到某一層的一個資源后，它只能再申請較高層次的資源 當進程要釋放某層的一個資源時，必須先釋放占有的較高層次的資源 當進程得到某一層的一個資源后，它想申請該層的另一個資源時，必須先釋放該層中的已占資源,23,死鎖防止 層次策略的變種按序分配策略,把系統的所有資源排一個順序，例如，系統若共有n個進程,共有m個資源，用ri表示第i個資源，于是這m個資源是： r1,r2,rm 規(guī)定如果進程不得在占用資源ri(1im)后再申請rj(ji)。不難證明，按這種策略分配資源時系統不會發(fā)生死鎖。,24,2 預防死鎖,根據生產死鎖的四個必要條件，只要使用其中之一不能成立，死鎖就不會出現。但必要條件是由設備的固有特性所決定的，不僅不能改變，相反還應加以保證，因此實際上只有三種方法。 預防死鎖是一種較易實現的方法，已被廣泛使用，但由于所施加的限制條件往往太嚴格，可能導致系統資源利用率和系統吞吐量降低。,1 互斥條件 2 請求和保持條件 3 不剝奪條件 4 環(huán)路等待條件,25,1:防止部分分配（摒棄請求和保持條件）,系統要求任一進程必須預先申請它所需的全部資源，而且僅當該進程的全部資源要求能得到滿足時，系統才能給予一次性分配，然后啟動該進程運行，但是在分配時只要由一種資源不滿足，系統就不會給進程分配資源。進程運行期間，不會再請求新的資源，所以，再分配就不會發(fā)生（摒棄了部分分配）。 特點：資源嚴重浪費 進程延遲進行,26,3 防止“不剝奪”條件的出現 采用的策略：一個已經保持了某些資源的進程，當它再提出新的資源要求而不能立即得到滿足時，必須釋放它已經保持的所有資源，待以后需要時再重新申請。 實現比較復雜，且要付出很大代價；此外，還因為反復地申請和釋放資源，而使進程的執(zhí)行無限地推遲，延長了周轉時間，增加了系統的開銷，降低了系統吞吐量。（例如打印機打印的結果不連續(xù)）,27,2.防止“環(huán)路等待”條件的出現。,采用資源順序使用法，基本思想是：把系統中所有資源類型線性排隊，并按遞增規(guī)則賦予每類資源以唯一的編號。例如輸入機1，打印機2，磁帶機3，磁盤4等等。進程申請資源時，必須嚴格按資源編號的遞增順序進行，否則系統不予分配。 優(yōu)點：資源利用率和系統吞吐量與另兩種方法相比有較明顯的改善。 缺點： 1 為系統中各種類型的資源所分配的序號必須相對穩(wěn)定，這就限制了新設備類型的增加 2 作業(yè)實際使用資源的順序與系統規(guī)定的順序不同而造成資源的浪費；,28,3 死鎖避免,避免死鎖與預防死鎖的區(qū)別在于，預防死鎖是設法至少破壞產生死鎖的必要條件之一，嚴格地防止死鎖的出現。 避免死鎖，它是在進程請求分配資源時，采用銀行家算法等防止系統進入不安全狀態(tài)。,29,在資源的動態(tài)分配的過程中，使用某種方法去防止系統進入不安全狀態(tài)，從而避免死鎖的發(fā)生。 系統狀態(tài)： 安全狀態(tài)：指系統能按照某種順序如(稱為序列為安全序列)，為每個進程分配所需的資源，直至最大需求，使得每個進程都能順利完成。 非安全狀態(tài)：即在某個時刻系統中不存在一個安全序列，則稱系統處于不安全狀態(tài)或非安全狀態(tài)。,30,雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當系統進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統處于安全狀態(tài)，系統便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質是如何使系統不進入不安全狀態(tài)。,31,安全狀態(tài)的例子,例：假定系統有三個進程P1、P2、P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和九臺。設在T0時刻，進程P1、P2和P3已經獲得5臺、2臺和2臺，還有3臺空閑沒有分配。,進程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0時刻系統時安全的。這時存在一個安全序列,32,安全狀態(tài)的例子,例：假定系統有三個進程P1、P2、P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和九臺。設在T0時刻，進程P1、P2和P3已經獲得5臺、2臺和2臺，還有3臺空閑沒有分配。,進程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0時刻系統時安全的。這時存在一個安全序列,33,雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當系統進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統處于安全狀態(tài)，系統便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質是如何使系統不進入不安全狀態(tài)。 系統的狀態(tài)可能通過下述來描述： 進程剩余申請數最大申請數占有數。 可分配資源數總數占有數之和。,34,3.6.3利用銀行家算法避免死鎖,銀行家算法 銀行家擁有一筆周轉資金 客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款 銀行家應謹慎的貸款，防止出現壞帳 用銀行家算法避免死鎖 操作系統（銀行家） 操作系統管理的資源(周轉資金) 進程（要求貸款的客戶）,35,銀行家算法,銀行家算法是最有代表性的避免死鎖算法，是Dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統現金貸款的發(fā)放而得名。為實現銀行家算法，系統中必須設置若干數據結構。,36,一、銀行家算法中的數據結構 1 可利用資源向量Available 是一個含有m個元素，其中的每一個元素代表一類可利用的資源數目，其初值是系統中所配置的該類全部可用資源數目。如果Availablej=k， 表示系統中現有Rj類資源k個。 2 最大需求矩陣Max 是一個含有nm的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max(i,j)=k， 表示進程i需要Rj類資源的最大數目為k。,Available= 3 5 4 2 8 3 8 6 1,37,3 分配矩陣Allocation 是一個含有nm的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation(i,j)=k， 表示進程i當前已分得Rj類資源k個。 4 需求矩陣Need 是一個含有nm的矩陣，用以表示每一個進程尚需的各類資源數。如果Need(i,j)=k， 表示進程i還需要Rj類資源k個，方能完成其任務。 Need(i,j)= Max(i,j)-Allocation(i,j),38,二、銀行家算法 設Requesti是進程Pi的請求向量，如果進程Pi需要K個Rj類資源，當Pi發(fā)出資源請求后，系統按下述步驟進行檢查： 1 如果RequestiNeedi,則轉向步驟2；否則認為出錯。（因為它所需要的資源數已超過它所宣布的最大值。 2如果RequestiAvailable,則轉向步驟3；否則，表示系統中尚無足夠的資源，Pi必須等待 3 系統試探把要求的資源分配給進程Pi，并修改下面數據結構中的數值： Available:=Available-Requesti; Allocation:=Allocation+Requesti; Needi:= Needi- Requesti; 4 系統執(zhí)行安全性算法，檢查此次資源分配后，系統是否處于安全狀態(tài)。若安全，正式將資源分配給進程Pi，以完成本次分配；否則，將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。,39,三、安全性算法 系統所執(zhí)行的安全性算法可描述如下： 1 設置兩個向量 工作向量Work.它表示系統可提供給進程繼續(xù)運行所需要的各類資源的數目，它含有m個元素，執(zhí)行安全算法開始時，Work:=Available。 Finish.它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi:=false；當有足夠的資源分配給進程時，令Finishi:=true. 2 從進程集合中找到一個能滿足下述條件的進程：Finishi=false; NeediWork. 如找到，執(zhí)行步驟3；否則執(zhí)行步驟4。 3 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故執(zhí)行： Work:=Work+Allocation; Finishi:=true; Goto step2; 4 如果所有進程的Finishi=true，則表示系統處于安全狀態(tài)；否則，系統處于不安全狀態(tài)。,40,要記住的一些變量的名稱,1 Available（可利用資源向量） 某類可利用的資源數目，其初值是系統中所配置的該類全部可用資源數目。 2 Max最大需求矩陣 某個進程對某類資源的最大需求數 3 Allocation分配矩陣 某類資源當前非配給某進程的資源數。 4 Need需求矩陣 某個進程還需要的各類資源數。 Need= Max-Allocation 系統把進程請求的資源分配給它以后要修改的變量 Available:=Available-Request; Allocation:=Allocation+Request; Need:= Need- Request;,41,銀行家算法之例,假定系統中有五個進程P0、P1、P2、P3、P4和三種類型的資源A，B，C，每一種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖,資源情況,進程,Allocation A B C,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,( 3 0 2 ),3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,( 0 2 0 ),0 0,0 1 1,4 3 1,3 3 2,( 2 3 0 ),42,3 3 2,1 2 2,2 0 0,5 3 2,true,true,true,true,true,0 1 1,2 1 1,5 3 2,7 4 3,7 4 3,4 3 1,0 0 2,7 4 5,7 4 5,6 0 0,3 0 2,10 4 7,10 4 7,7 4 3,0 1 0,10 5 7,最大值,已分配,還需要,可用,若P1發(fā)出請求向量 Request（1，0，2）,工作向量Work.它表示系統可提供給進程繼續(xù)運行所需要的各類資源的數目,10,5 7,43,思考和練習 假定系統中有五個進程P0、P1、P2、P3、P4和 三種類型的資源A，B，C，每一種資源的數量 分別為10、5、7，在T0時刻的資源分配情況如圖 請找出該表中T0時刻以后存在的安全序列（至少2種）,資源情況,進程,Allocation A B C,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,6 0 0,0 1 1,4 3 1,3 3 2,7 5 3,44,3 死鎖的檢測和恢復 死鎖的檢測和恢復技術是指定期啟動一個軟件檢測系統的狀態(tài)，若發(fā)現有死鎖存在，則采取措施恢復之。 (1)死鎖的檢測 檢查死鎖的辦法就是由軟件檢查系統中由進程和資源構成的有向圖是否構成一個或多個環(huán)路，若是，則存在死鎖，否則不存在。,45,死鎖的檢測：實質是確定是否存在環(huán)路等待現象，一旦發(fā)現這種環(huán)路便認定死鎖存在，并識別出該環(huán)路所涉及的有關進程，以供系統采取適當的措施來解除死鎖。最常用的是一種基于資源分配圖RAG和死鎖定理的檢測死鎖算法。,46,資源分配圖（RAG） 系統死鎖可用資源分配圖來描述，該圖是由一組結點N和一組邊E所組成的一對偶G=(N,E)。（用圓圈代表一個進程，用方框代表一類資源，由于一種類型的資源可能有多個，可用方框中的一個點代表一類資源中的一個資源） 幾個概念：請求邊，分配邊,P1,P2,r1,r2,請求r2,資源分配圖,47,封鎖進程：是指某個進程由于請求了超過了系統中現有的未分配資源數目的資源，而被系統封鎖的進程。 非封鎖進程：即沒有被系統封鎖的進程資源分配圖的化簡方法：假設某個RAG中存在一個進程Pi，此刻Pi是非封鎖進程，那么可以進行如下化簡：當Pi有請求邊時，首先將其請求邊變成分配邊(即滿足Pi的資源請求)，而一旦Pi的所有資源請求都得到滿足，Pi就能在有限的時間內運行結束，并釋放其所占用的全部資源，此時Pi只有分配邊，刪去這些分配邊（實際上相當于消去了Pi的所有請求邊和分配邊），使Pi成為孤立結點。（反復進行） 。,48,死鎖定理： 系統中某個時刻S為死鎖狀態(tài)的充要條件是S時刻系統的資源分配圖是不可完全簡化的。 在經過一系列的簡化后，若能消去圖中的所有邊，使所有的進程都成為孤立結點，則稱該圖是可完全簡化的；反之的是不可完全簡化的。,P1,P2,r1,r2,P1,P2,r1,r2,49,死鎖的恢復。是與檢測死鎖相配套的一種措施，用于將進程從死鎖狀態(tài)下解脫出來。常用的方法有： 1撤消進程；最簡單撤消進程的方法是使全部死鎖的進程夭折掉；另一方法是按照某種順序逐個地撤消進程，直至有足夠的資源可用，死鎖狀態(tài)消除為止,2掛起進程（剝奪資源）。使用掛起/激活機構掛起一些進程，剝奪它們的資源以解除死鎖，待條件滿足時，再激活進程。目前掛起法比較受到重視。,50,1（北大95）一個OS有20個進程，競爭使用65個同類資源，申請方式是逐個進行的，一旦某個進程獲得它所需要的全部資源，則立即歸還所有資源。每個進程最多使用三個資源。若僅考慮這類資源，該系統有無可能產生死鎖，為什么？ 2死鎖和饑餓的主要差別是什么？,例題,51,1 答：不可能。因為死鎖產生的原因有兩點：系統資源不足或推進順序不當，在本題中，進程所需的最大資源數為60，而系統共有該類資源65個，其資源數已足夠系統內各進程使用。 2 答：簡言之，死鎖是某進程等待一個不會發(fā)生的事件的一種現象；而饑餓現象是某進程正等待這樣一個事件，它發(fā)生了但總是受到其它進程的影響，以至輪不到（或很難輪到）該進程。,52,銀行家算法的基本思想(1),系統中的所有進程進入進程集合, 在安全狀態(tài)下系統收到進程的資源請求后,先把資源試探性分配給它。 系統用剩下的可用資源和進程集合中其他進程還要的資源數作比較，在進程集合中找到剩余資源能滿足最大需求量的進程,從而,保證這個進程運行完畢并歸還全部資源。,53,銀行家算法的基本思想(2),把這個進程從集合中去掉, 系統的剩余資源更多了,反復執(zhí)行上述步驟。 最后,檢查進程集合,若為空表明本次申請可行,系統處于安全狀態(tài),可實施本次分配;否則,有進程執(zhí)行不完，系統處于不安全狀態(tài),本次資源分配暫不實施,讓申請進程等待。,54,3.7 死鎖的檢測與解除,1 資源分配圖和死鎖定理 2 借助于死鎖的安全性測試算法的死鎖檢測 3 warshall傳遞閉包算法的死鎖檢測,55,簡化進程-資源分配圖檢測系統是否處于死鎖狀態(tài)(1),(1)如果進程-資源分配圖中無環(huán)路，則此時系統沒有發(fā)生死鎖。 (2)如果進程-資源分配圖中有環(huán)路，且每個資源類中僅有一個資源，則系統中發(fā)生了死鎖，此時，環(huán)路是系統發(fā)生死鎖的充要條件，環(huán)路中的進程便為死鎖進程。,56,簡化進程-資源分配圖檢測系統是否處于死鎖狀態(tài)(2),(3)如果進程-資源分配圖中有環(huán)路，且涉及的資源類中有多個資源，則環(huán)路的存在只是產生死鎖的必要條件而不是充分條件。,57,簡化進程-資源分配圖檢測系統是否處于死鎖狀態(tài)