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

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

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

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

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

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

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

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

8、例數(shù)量。假設(shè)AllocationI, j = k，那么進(jìn)程Pi如今已分配了k個(gè)資源類型Rj的實(shí)例。nNeed：nm矩陣表示每個(gè)進(jìn)程還需求的剩余的資源。假設(shè)Needi, j = k, 那么進(jìn)程Pi還能夠懇求k個(gè)資源類型Rj的實(shí)例。nNeedi, j = Maxi, j Allocationi, j平安性算法n設(shè)Work和Finish分別是長度為m和n的向量。按如下方式進(jì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è)對(duì)一切i，F(xiàn)inishi = true，那么系統(tǒng)處于平安形狀對(duì)進(jìn)程Pi的資源懇求算法n設(shè)Requesti為進(jìn)程Pi的懇求向量。假設(shè)Requestij = k, 那么進(jìn)程Pi需求資源類型Rj的實(shí)例數(shù)量為k。當(dāng)進(jìn)程Pi做出資源懇求時(shí)，會(huì)采取如下動(dòng)作。n假設(shè)Requesti = Needi，那么轉(zhuǎn)到第2步，否那么，產(chǎn)生出錯(cuò)條件，這是由于進(jìn)程Pi已超越了其懇求。n假設(shè)Requesti = Available，那么轉(zhuǎn)到第3步。否那么，Pi必需等待，這是由于沒有可用資源。n假定系統(tǒng)可以分配給進(jìn)程Pi所懇

10、求的資源，并按如下方式修正形狀：nAvailable := Available Requesti;nAllocationi := Allocationi + Requesti;nNeedi := Needi Requesti;n假設(shè)平安，那么資源分配給Pin假設(shè)不平安，那么Pi必需等待，并恢復(fù)到原來資源分配形狀。算法實(shí)例nP0, P1, P2, P3, P4；資源A有10個(gè)實(shí)例，B有5個(gè)實(shí)例，C有7個(gè)實(shí)例n在T0時(shí)辰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如今假定進(jìn)程 P1再懇求一個(gè)資源類型A和2個(gè)資源類型C，這樣Request1 = (1, 0, 2)n由于Request1 = Available，那么假定這個(gè)懇求可滿足，會(huì)有如下新形狀：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í)行平安算法，并找到順序滿足平安要求。因此，可以立刻允許進(jìn)程P1的這個(gè)懇求。8.6 死鎖檢測(cè)n允許系統(tǒng)進(jìn)入死鎖形狀n檢測(cè)算法n恢復(fù)機(jī)制(一) 每種資源類型只需單個(gè)實(shí)例n等待圖n從資源分配圖中，刪除一切資源類型節(jié)點(diǎn)，合并適當(dāng)邊，就可以得到等待圖。n節(jié)點(diǎn)表示進(jìn)程nPi-Pj表示Pi等待Pj釋放一個(gè)Pi所需的資源n周期性地調(diào)用在圖中進(jìn)展搜索的算法n從圖中檢測(cè)環(huán)的算法需求n2級(jí)別操作，其中n為圖中的節(jié)點(diǎn)數(shù)。資源分配圖和對(duì)應(yīng)的等待圖(二) 每種資源類型的多個(gè)實(shí)例nAvailable：長度為m的向量，表示各種資源的可用實(shí)例nAllocation：nm矩陣，表示當(dāng)

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

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