《操作系統(tǒng)課程》ppt課件

1、操作系統(tǒng)概念第八章：死鎖本章主要內(nèi)容n系統(tǒng)模型n死鎖特點n死鎖處置方法n死鎖預防n死鎖防止n死鎖檢測n死鎖恢復死鎖問題n一組阻塞進程分別占有一定的資源并等待獲取另外一些曾經(jīng)被同組其他進程所占有的資源。n實例一n系統(tǒng)擁有兩個磁帶驅(qū)動器nP1 和 P2分別占有其中的一臺，而且相互需求另外的一臺。n實例二n信號量A和B，初始值都為1n P0 P1nwait(A);wait(B)nwait(B);wait(A)過橋的實例8.1 系統(tǒng)模型n資源類型：R1, R2, , RmnCPU 周期， 內(nèi)存空間，I/O設(shè)備n每個資源類型Ri有Wi個實例n每個進程用以下方式利用資源n懇求n運用n釋放8.2 死鎖特點n

2、假設(shè)以下四個條件同時滿足，那么就會引起死鎖n互斥：至少有一個資源必需處于非共享方式；即一次只需一個進程運用。假設(shè)另一資源懇求該資源，那么懇求進程必需延遲直到該資源釋放為止。n占有并等待：一個進程必需占有至少一個資源，并等待另一資源，而該資源為其他進程所占有。n非搶占：資源不能被搶占；即，只需進程完成其義務(wù)之后，才會釋放其資源。n循環(huán)等待：有一組進程P0, P1, , Pn，P0等待的資源為P1所占有，P1等待的資源為P2所占有，Pn-1等待的資源為Pn所占有，Pn等待的資源為P0所占有。資源分配圖n節(jié)點的集合V和邊的集合EnV分為兩類nP P1, P2, , Pn, 系統(tǒng)活動進程的集合nR =

3、 R1, R2, , Rm, 系統(tǒng)一切資源類型的集合n懇求邊：有向邊 P1-Rjn分配邊：有向邊 Rj-Pi 資源分配圖實例有死鎖情況的資源分配圖存在環(huán)但無死鎖的資源分配圖根身手實n假設(shè)圖不包含環(huán)，那么不存在死鎖n假設(shè)圖包含環(huán)，那么n假設(shè)每種資源類型只需一個實例，那么死鎖n假設(shè)每種資源類型存在假設(shè)干個實例，那么只是有能夠會發(fā)生死鎖。8.3 死鎖處置方法n可運用協(xié)議以預防或防止死鎖，確保系統(tǒng)永遠不會進入死鎖形狀n可允許系統(tǒng)進入死鎖形狀，然后檢測它，并加以恢復n可忽略這個問題，以為死鎖不能夠在系統(tǒng)內(nèi)發(fā)生。這種方法為絕大多數(shù)操作系統(tǒng)如UNIX運用。鸼鳥算法8.4 死鎖預防n出現(xiàn)死鎖有四個必要條件，只

4、需確保至少一個必要條件不成立，就能預防死鎖發(fā)生。n互斥n通常不能經(jīng)過否認互斥條件來預防死鎖。有資源本身是非共享的。n占有并等待n當一個進程懇求一個資源時，它不能占有其他資源。n執(zhí)行前懇求并獲得一切資源n懇求其他資源之前，必需釋放其如今已分配的一切資源n缺陷n資源利用率能夠比較低n能夠發(fā)生饑餓 n非搶占：n假設(shè)一個進程占有資源并懇求另一個不能立刻分配的資源，那么其現(xiàn)已分配的資源都被搶占。n通常運用于其形狀可以保管和恢復的資源，如CPU存放器和內(nèi)存空間，不能適用于其他資源如打印機和磁帶驅(qū)動器。n循環(huán)等待n對一切資源進展完全排序，且要求每個進程按遞增順序來懇求資源8.5 死鎖防止n防止死鎖的另一種方

5、法要求有關(guān)如何懇求資源的附加信息n最簡單且有效的模型要求每個進程事先聲明它所需求的每種資源的最大數(shù)量n死鎖防止算法動態(tài)檢查資源分配形狀，以保證不存在循環(huán)等待的條件。n資源分配形狀經(jīng)過可用資源數(shù)量、已分配資源數(shù)量，及進程最大懇求數(shù)量來定義平安形狀n當一個進程懇求一個可用資源的時候，系統(tǒng)必需決議這次分配能否會使系統(tǒng)處在一種平安形狀n假設(shè)存在一切進程的一種平安序列，那么系統(tǒng)是平安的n進程序列，假設(shè)對于每個Pi，Pi懇求的資源小于當前可用資源加上一切進程Pj其中j i所占有的資源，那么這一順序為平安序列。假設(shè)沒有這樣的序列存在，那么系統(tǒng)形狀就處于不平安 n假設(shè)系統(tǒng)是平安的，那么不會死鎖n假設(shè)系統(tǒng)不平安

6、，能夠會發(fā)生死鎖n死鎖防止：確保系統(tǒng)永遠不會進入不平安形狀平安、不平安、死鎖形狀空間例子n思索一個系統(tǒng)，共有12臺磁帶驅(qū)動器和三個進程P0, P1, P2。其最大需求與當前占有量如下表所示n最大需求當前占有nP0105nP142nP292n在時辰t0時，系統(tǒng)處于平安形狀，由于順序滿足平安條件。n假設(shè)在時辰t1時，進程P2懇求并又得到了1臺磁帶驅(qū)動器，系統(tǒng)就不平安了。n為什么？資源分配圖算法n除了懇求邊和分配邊外，可引入一新類型的邊，稱為需求邊。n需求邊Pi-Rj表示進程Pi能夠在未來某個時候懇求資源Rj，用虛線表示n當進程Pi懇求資源Rj時，需求邊Pi-Rj變成了懇求邊。n當進程Pi釋放Rj時

7、，分配邊Rj-Pi變成了需求邊。n系統(tǒng)必需事先要求資源死鎖防止的資源分配圖資源分配圖的不平安形狀銀行家算法n多實例n每個進程必需事先聲明資源最大運用量n當一個進程懇求資源時，有能夠必需等待n進程得到一切資源后，它必需在某個確定的時間之后將資源前往給系統(tǒng)銀行家算法的數(shù)據(jù)構(gòu)造n設(shè)n為系統(tǒng)進程個數(shù)，m為資源類型的種類nAvailable：長度為m的向量。假設(shè)availablej = k，那么資源類型Rj現(xiàn)有k個實例nMax：nm矩陣定義每個進程的最大需求。假設(shè)Maxi, j = k, 那么進程Pi最多可懇求k個資源類型Rj的實例nAllocation：nm矩陣定義每個進程如今所分配的各種資源類型的實

8、例數(shù)量。假設(shè)AllocationI, j = k，那么進程Pi如今已分配了k個資源類型Rj的實例。nNeed：nm矩陣表示每個進程還需求的剩余的資源。假設(shè)Needi, j = k, 那么進程Pi還能夠懇求k個資源類型Rj的實例。nNeedi, j = Maxi, j Allocationi, j平安性算法n設(shè)Work和Finish分別是長度為m和n的向量。按如下方式進展初始化：nWork = AvailablenFinishi = false (i = 1, 2, , n)n查找這樣的i使其滿足nFinishi = falsenNeedi = Workn假設(shè)沒有這樣的i存在，那么就轉(zhuǎn)到第4步n

9、Work := Work + AllocationinFinishi := truen前往到第2步n假設(shè)對一切i，F(xiàn)inishi = true，那么系統(tǒng)處于平安形狀對進程Pi的資源懇求算法n設(shè)Requesti為進程Pi的懇求向量。假設(shè)Requestij = k, 那么進程Pi需求資源類型Rj的實例數(shù)量為k。當進程Pi做出資源懇求時，會采取如下動作。n假設(shè)Requesti = Needi，那么轉(zhuǎn)到第2步，否那么，產(chǎn)生出錯條件，這是由于進程Pi已超越了其懇求。n假設(shè)Requesti = Available，那么轉(zhuǎn)到第3步。否那么，Pi必需等待，這是由于沒有可用資源。n假定系統(tǒng)可以分配給進程Pi所懇

10、求的資源，并按如下方式修正形狀：nAvailable := Available Requesti;nAllocationi := Allocationi + Requesti;nNeedi := Needi Requesti;n假設(shè)平安，那么資源分配給Pin假設(shè)不平安，那么Pi必需等待，并恢復到原來資源分配形狀。算法實例nP0, P1, P2, P3, P4；資源A有10個實例，B有5個實例，C有7個實例n在T0時辰nAllocationMaxAvailablen A B CA B CA B CnP0 0 1 07 5 33 3 2nP1 2 0 03 2 2nP2 3 0 29 0 2nP3

11、 2 1 12 2 2nP4 0 0 24 3 3 n矩陣Need的內(nèi)容定義成Max-AllocationnNeednA B CnP07 4 3nP11 2 2nP26 0 0nP30 1 1nP44 3 1n系統(tǒng)是平安的，由于序列滿足平安條件 n如今假定進程 P1再懇求一個資源類型A和2個資源類型C，這樣Request1 = (1, 0, 2)n由于Request1 = Available，那么假定這個懇求可滿足，會有如下新形狀：AllocationNeedAvailableA B CA B CA B CP00 1 07 4 32 3 0P13 0 20 2 0P23 0 16 0 0P32

12、 1 10 1 1P40 0 24 3 1n執(zhí)行平安算法，并找到順序滿足平安要求。因此，可以立刻允許進程P1的這個懇求。8.6 死鎖檢測n允許系統(tǒng)進入死鎖形狀n檢測算法n恢復機制(一) 每種資源類型只需單個實例n等待圖n從資源分配圖中，刪除一切資源類型節(jié)點，合并適當邊，就可以得到等待圖。n節(jié)點表示進程nPi-Pj表示Pi等待Pj釋放一個Pi所需的資源n周期性地調(diào)用在圖中進展搜索的算法n從圖中檢測環(huán)的算法需求n2級別操作，其中n為圖中的節(jié)點數(shù)。資源分配圖和對應(yīng)的等待圖(二) 每種資源類型的多個實例nAvailable：長度為m的向量，表示各種資源的可用實例nAllocation：nm矩陣，表示當

13、前各進程的資源分配情況nRequest：nm矩陣，表示當前各進程的資源懇求情況。假設(shè)Requesti, j = k, 那么Pi如今需求k個資源Rj檢測算法n設(shè)Work和Finish分別是長m和n的矢量，初始化如下：nWork := Availablen對i = 1, 2, , n，假設(shè)Allocationi不為0,那么Finishi := false，否那么Finishi := truen找出這樣的下標i，使之同時滿足nFinishi = falsenRequesti = Workn假設(shè)沒有這樣的i，那么轉(zhuǎn)到第四步nWork := Work + AllocationinFinishi := t

14、ruen轉(zhuǎn)到第2步n假設(shè)對某個i1= i = n)，F(xiàn)inishi = false，那么系統(tǒng)死鎖。而且，假設(shè)Finishi = false, 那么進程Pi死鎖實例 運用檢測算法n應(yīng)何時調(diào)用檢測算法，取決于兩個要素：n死鎖能夠發(fā)生的頻率是多少？n當死鎖發(fā)生時，有多少進程會受影響？n當某個進程提出懇求且得不到滿足時，才會出現(xiàn)死鎖，這時可以調(diào)用死鎖檢測算法。n但死鎖后的每一個懇求都會呵斥死鎖。因此，能夠需求對于之后的每個懇求都調(diào)用死鎖檢測算法，但會引起相當?shù)挠嬎汩_銷。n只是在一個不頻繁的時間間隔里調(diào)用檢測算法，如每小時一次或當CPU運用率低于40%時。n在不定的時間點調(diào)用檢測算法，通常不能確定死鎖進程中是哪些引起了死鎖。8.7 死鎖恢復n人工處置死鎖n讓系統(tǒng)從死鎖形狀中自動恢復n突破死鎖形狀有兩個方法n簡單地終止一個或多個進程以突破循環(huán)等待n從一個或多個死鎖進程那里搶占一個或多個資源(一) 進程終止n有兩種方法經(jīng)過終止進程以取消死鎖n終止一切進程n一次只終止一個進程直到取消死鎖循環(huán)為止n確定終止哪個進程或哪些進程可以突破死鎖需求