計算機操作系統(tǒng)第5章死鎖

1、. 從進程同步的概念可以知道，當并發(fā)進程需要競爭使用資源或需要相互協(xié)作向前推進時，如果不采取同步措施，或同步措施不恰當，則很容易導致并發(fā)進程不能向前推進而陷入僵局，即死鎖現(xiàn)象。死鎖是發(fā)生在一組相互競爭或協(xié)作的進程與線程之間的一個非正?，F(xiàn)象。 死鎖是所有操作系統(tǒng)都面臨著的潛在問題，操作系統(tǒng)除了需要預防死鎖、避免死鎖外，還需要能夠檢測死鎖，并從死鎖中進行恢復。.本章的主要內(nèi)容如下：l 死鎖的產(chǎn)生；l 死鎖的預防；l 死鎖的避免；l 死鎖的檢測和解除；l 線程死鎖。.5.1 5.1 死鎖的產(chǎn)生死鎖的產(chǎn)生5.1.1 5.1.1 死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因 競爭資源引起死鎖競爭資源引起死鎖 在多道程序

2、系統(tǒng)，多個進程共享系統(tǒng)的資源。系統(tǒng)資源分為二類，一類是不可搶占的資源，如打印機、磁帶機等。當系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自動釋放。另一類是可搶占的資源，如CPU、內(nèi)存等。由于系統(tǒng)擁有的不可搶占的資源有限，多個進程共享競爭不可搶占的資源就可能引起死鎖。 進程推進順序不當引起死鎖進程推進順序不當引起死鎖 在多道程序系統(tǒng)中，并發(fā)執(zhí)行的進程推進序列不可予測，有些推進順序，進程可以順利完成，這些推進順序是合法的；而有的推進順序會引起進程無限期地等待永遠不會發(fā)生的條件而不能向前推進，造成了死鎖。.5.1.1 5.1.1 死鎖產(chǎn)生的原因（續(xù)）死鎖產(chǎn)生的原因（續(xù)） 進程推進順

3、序不當引起死鎖例：進程P和Q并發(fā)執(zhí)行，進程P和Q程序如下：Process P Process Q. .Get A Get B. .Get B Get A. .Release A Release B. .Release B Release A. . .5.1.1 5.1.1 死鎖產(chǎn)生的原因（續(xù)）死鎖產(chǎn)生的原因（續(xù)）PAQB當當P、Q按如下次序執(zhí)行時：按如下次序執(zhí)行時：P: GET A Q:GET BP:GET BQ:GET A.ABCS2S1S3哲學家吃面的問題哲學家吃面的問題.A:P(S1)P(S3)EatingV(S3)V(S1)B:P(S2)P(S1)EatingV(S1)V(S2)C:P

4、(S3)P(S2)EatingV(S2)V(S3).A: P(S1), B:P(S2),C:P(S3)A:P(S3) :阻塞阻塞B:P(S1):阻塞阻塞C: P(S2):阻塞阻塞AS1CS3S2B.5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件1.1.產(chǎn)生死鎖的必要條件（產(chǎn)生死鎖的必要條件（ Conditions for Deadlock ） 互斥（互斥（ Mutual exclusion ）條件）條件：一個資源一次只能被一個進程所使用，即是排它性使用。 不可搶占（不可搶占（ No preemption ）條件）條件：一個資源僅能被占有它的進程所釋放，而不能被別的進程強占。 請求和保持（

5、請求和保持（ Hold-and-wait ）條件）條件：進程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對已經(jīng)獲得的其它資源保持不放。 環(huán)路等待（環(huán)路等待（ Circular wait ）條件）條件：當每類資源只有一個時，在發(fā)生死鎖時，必然存在一個進程-資源的環(huán)形鏈。如一系統(tǒng)狀態(tài)的資源分配圖所示，P1正在等待一個P2 占用的資源R2，P2正在等待一個P1占用的資源R1。. 5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件( (續(xù)續(xù)) )2. 資源分配圖由結點和邊組成。結點有二類，一類是進程結點，用園圈表示；另一類是資源結點，用小方框表示

6、一類資源，用方框中的小圈表示資源數(shù)。邊也有二類，一類是分配邊，它由資源結點指向進程結點，另一類是申請邊，它由進程結點指向資源結點。返回 R1R2 P1P2.5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件( (續(xù)續(xù)) )3 3. . 處理死鎖的基本方法處理死鎖的基本方法a. 死鎖的預防 靜態(tài)方法：在進程執(zhí)行前采取的措施，通過設置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件之一，防止發(fā)生死鎖。B.死鎖的避免 動態(tài)的方法：在進程執(zhí)行過程中采取的措施，不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件，而是在進程申請資源時用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖。C.死鎖的檢測和解除 這種方法

7、預先并不采用任何限制措施，允許系統(tǒng)在運行過程中發(fā)生死鎖，但可通過系統(tǒng)設置的檢測機構及時檢測死鎖的發(fā)生，如檢測到死鎖，則采用撤消進程等死鎖解除方法使系統(tǒng)正常工作。.5.2 5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) 預防死鎖的方法是破壞四個產(chǎn)生死鎖的必要條件之一。1。破壞互斥條件破壞互斥條件 互斥使用是資源本身特征所決定的。使用硬軟件結合可改變資源本身特性，例如采用SPOOLing技術可將“獨享” 打印機改變?yōu)椤肮蚕怼钡拇蛴C。2。破壞不可搶占條件破壞不可搶占條件 搶占式調度法主要用于處理機和存貯器資源調度，它們的狀態(tài)容易保存和恢復。但此法對外部設備和私存數(shù)據(jù)不宜使

8、用。.5.2 5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) -13。破壞請求和保持條件破壞請求和保持條件 系統(tǒng)可采用資源靜態(tài)予分配方式資源靜態(tài)予分配方式來破壞請求保持條件。系統(tǒng)要求所有進程一次性地申請在整個運行過程中全部資源，若系統(tǒng)有足夠資源滿足給進程，則在運行前，一次性將其所需要的所有資源分配給該進程。這樣該進程在整個運行期間，便不再提出資源要求，從而摒棄了請求條件。這種預防死鎖的方法，優(yōu)點是簡單、易予實現(xiàn)且很安全，但其資源利用率很低，進程也延遲運行。4。破壞循環(huán)等待條件破壞循環(huán)等待條件 有序資源使用法有序資源使用法 該方法將所有的資源按類型進行線性排隊，并賦予不

9、同的序號。例如令輸入機的序號為1，打印機序號為2，磁盤機序號為3等。.5.2 5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) -2 所有進程對資源的請求必須嚴格按資源序號遞增的次序提出。這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件，在采用這種策略時總有一個進程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，因而進程可以一直向前推進。這種預防死鎖的策略可以提高資源利用率，但在進程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時會造成資源浪費的情況。 資源按級分配法資源按級分配法 該方法是把資源遞增排序成若干等級（如L1、L2.Lm），其中每級可包含

10、幾類資源，要求每個進程在獲得了Lj級中資源之后 ，它才能申請更高級的LK（LKLj）級中的資源；如果它還需申請比LK級低的LI級（LI 4 P2 4 2 2 = 4 因為找不到一個安全序列使所有進程順序地一個個地運行完畢，所以T1狀態(tài)是不安全狀態(tài)，由于實施分配給1臺磁帶機給P3的操作會引起系統(tǒng)狀態(tài)由安全狀態(tài)T0向不安全狀態(tài)下的轉換，所以為了避免死鎖，上述的分配只是安全檢測，檢測后判定這樣的申請不能滿足，P3為申請1臺磁帶機而必須阻塞等待。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖 最具代表的避免死鎖算法是Dijkstra的銀行家算法，這是由于該算法用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。

11、銀行家算法的數(shù)據(jù)結構銀行家算法的數(shù)據(jù)結構可用資源向量 Available m m為系統(tǒng)中資源種類數(shù)，Availablej=k表示系統(tǒng)中第j類資源數(shù)為k個。最大需求矩陣Maxn，m n為系統(tǒng)中進程數(shù)，Maxi,j=k表示進程i對j類資源的最大需求數(shù)為中k。分配矩陣Allocationn，m 它定義了系統(tǒng)中每一類資源當前已分配給每一進程資源數(shù)， Allocationi,j=k表示進程i已分得j類資源的數(shù)目為k個。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖-1-1需求矩陣Needn,m 它表示每個進程尚需的各類資源數(shù)，Needi,j=k 表示進程i還需要j類資源k個。Needi,j=Ma

12、xi,j-Allocationi,j銀行家算法銀行家算法 假設在進程并發(fā)執(zhí)行時進程i提出請求j類資源k個后，表示為Requestij=k。系統(tǒng)按下述步驟進行安全檢查： 如果RequestiNeedi則繼續(xù)以下檢查，否則顯示需求申請超出最大需求值的錯誤。 如果RequestiAvailable則繼續(xù)以下檢查，否則顯示系統(tǒng)無足夠資源，Pi阻塞等待。 系統(tǒng)試探把要求的資源分配給進程i并修改有關數(shù)據(jù)結構的值： Available = Available-Requesti ； Allocationi =Allocationi+Requesti ； Needi=Needi-Requesti ；. 3.3.

13、利用銀行家算法避免死鎖利用銀行家算法避免死鎖-2-2 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給進程i，以完成本次分配；否則將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。安全性算法安全性算法安全性算法執(zhí)行步驟如下：A.初始化設置工作向量Workm表示系統(tǒng)可提供的各類資源數(shù)目，用以保護原數(shù)據(jù)結構有關值。Work = Available，設置完成標志向量 Finishn。Finishi = false 表示i進程尚末完成，如值為true則表示進程i已完成。B.從進程集合n中找到一個能滿足下述二個條件: Finishi = false和Necd

14、iWork，如找到則執(zhí)行步驟C，如找不到同時滿足以上二條件的進程則執(zhí)行步驟D。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖-3-3C.當進程i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下： work = work+Allocationi ； Finishi=true ；轉執(zhí)行步驟B。D.如果所有的Finishiture，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。.銀行家算法銀行家算法例：例： 假定系統(tǒng)中有五個進程P0、P1、P2、P3、P4和三種類型資源A、B、C，每一種資源的數(shù)量分別為10、5、7。各進程的最大需求、T0時刻資源分配情況如下 所示。 Max

15、Allocation Need Available A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1試問： T0時刻是否安全？ P1請求資源Request1(1,0,2)是否允許？ P4請求資源Request4(3,3,0)是否允許？ .銀行家算法銀行家算法例例-1 T0時刻是否安全？從表中可找出一個序列(P1 、 P3、 P4 、 P2 、 P0）使各進程順序地一個個地執(zhí)行完成。 M

16、axMax Allocation Need Available Available (分配資源前分配資源前) (釋放釋放資源資源后）后） A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 2 0 0 1 2 2 = 3 3 2 5 3 2P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3P4 4 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5安全序列為P1、P3、P4、P2、P0，T0時刻系統(tǒng)是安全

17、的。 P1請求資源Request1(1,0,2)可否允許？.銀行家算法銀行家算法例例-2Request1(1,0,2)Need1(1,2,2)，P1請求在最大需求范圍內(nèi)。Request1(1,0,2) Available(3,3,2)，可用資源可滿足P1請求需要。試探把要求的資源分配給進程P1并修改有關數(shù)據(jù)結構的數(shù)值：Available = Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1 = Need1(1,2,2)Request1(1,0,2)= Need1(0,2,0)；Allocation1 =Allocation1(2,0,

18、0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法檢查試探將資源分配后狀態(tài)的安全性如下：.銀行家算法銀行家算法例例-3 Max Max Allocation Need Available Available (分配資源前分配資源前) (釋放釋放資源資源后）后） A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0 = 2 3 0 5 3 2P29 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P32 2 2 2 1 1 0

19、1 1 = 5 3 2 7 4 3P44 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5 因為先分配資源給P1進程符合按安全序列P1、P3、P4、P2、P0分配資源，所以試探將資源分配給進程P1后的狀態(tài)是安全的，可將資源分配給進程P1。 P4請求資源Request4(3,3,0)是否允許？Request4(3,3,0)Need4(4,3,1)，P4請求在最大需求范圍內(nèi)。Request4(3,3,0)Available(2,3,0)不成立，即可用資源暫不能滿足P4請求資源需要，P4阻塞等待。 .5.4 5.4 死鎖的檢測和解除死鎖的檢測和解除(Deadlock DetectionDe

20、adlock Detection) 5.4.1 5.4.1 死鎖的檢測死鎖的檢測 死鎖的避免算法增加了系統(tǒng)的開銷，死鎖的檢測采用資源分配圖的簡化判斷是否發(fā)生了不安全狀態(tài)。如發(fā)現(xiàn)系統(tǒng)處于不安全狀態(tài)時，即執(zhí)行死鎖解除的策略，采用此法開銷相對減少。1 1. .資源分配圖的簡化資源分配圖的簡化： 系統(tǒng)處于某S狀態(tài)時可用資源分配圖表示，可用資源分配圖簡化來判斷系統(tǒng)是否處于死鎖狀態(tài)。資源分配圖簡化的方法如下：在資源分配圖中找一個既不阻塞又非孤立的進程結點PI（如某進程既無已分配的資源也不需申請資源，即既無分配邊又無申請邊，則該進程結點是孤立結點），讓它獲得所需資源而繼續(xù)運行直至完畢，再釋放它擁有的所有的資

21、源，這相當于取消PI的分配邊和請求邊，使它成為孤立結點。 經(jīng)過以上簡化，如所有的進程結點都是孤立結點則稱資源分配圖是可完全簡化的。若不能通過任何過程使該圖完全簡化，則該圖是不可完全簡化的。資源分配圖簡化如下圖：. R R1 1 R R2 2 R R1 1 R R2 2 。P1 資源分配圖的簡化例資源分配圖的簡化例：。 。P1P2。 。 。P1P2。 。P2。R R1 1 R R2 2.5.4.1 5.4.1 死鎖的檢測死鎖的檢測-1-12 2. .死鎖定理：死鎖定理： S為死鎖狀態(tài)的充分條件是：尚且僅當S狀態(tài)的資源分配圖是不可完全簡化的，該充分條件稱為死鎖定理。3. 死鎖檢測的數(shù)據(jù)和算法死鎖檢

22、測的數(shù)據(jù)和算法類似于銀行家算法。.5.4.2 5.4.2 死鎖解除死鎖解除 當檢測死鎖的軟件判別死鎖存在時判別死鎖存在時，就要解除死鎖就要解除死鎖，使系統(tǒng)從死鎖中恢復。1 1利用結束死鎖進程釋放資源利用結束死鎖進程釋放資源 強制性地從系統(tǒng)中撤消一個或多個死鎖的進程以斷開循環(huán)等強制性地從系統(tǒng)中撤消一個或多個死鎖的進程以斷開循環(huán)等待鏈待鏈，并收回分配給終止進程的全部資源供剩下的進程使用。借助于撤消進程來解除死鎖可以使用兩種方法。一種是撤消全部的死鎖進程，這顯然會斷開死鎖環(huán)路，但代價太大。另一種方法是逐個撤消死鎖的進程直至死鎖環(huán)路消除。這里存在一個按照什么原則進行逐個撤消進程的問題。目前較實用而又簡

23、便的方法是撤消那些代價最小的進程。所謂影響一個進程的撤消代價因素有該進程的優(yōu)先權，該進程運行到今的運行代價（包括CPU時間，使用資源的種類和時間等）、與相關的作業(yè)類型和外部代價等。.死鎖的解除死鎖的解除-12 2利用資源搶占利用資源搶占 死鎖恢復的另一種辦法是使用一個有效的掛起和解除機構死鎖恢復的另一種辦法是使用一個有效的掛起和解除機構來掛起一些死鎖的進程來掛起一些死鎖的進程，其實質是從被掛起的進程那里搶占資源以解除死鎖，許多學者認為在此領域的研究工作比起其它死鎖恢復的辦法更為重要。問題：現(xiàn)場（包擴CPU、內(nèi)存、外設的狀態(tài)）保護不好解決3 3利用回退釋放資源利用回退釋放資源 例如一個系統(tǒng)提供了檢查點和重新啟