第三章—C死鎖ppt課件

1、1 3.5 3.5 死鎖死鎖 資源資源 死鎖的定義死鎖的定義 產(chǎn)生死鎖的緣由產(chǎn)生死鎖的緣由 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 處置死鎖的根本方法處置死鎖的根本方法2二、死鎖的定義二、死鎖的定義 計算機系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進程由于競爭計算機系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進程由于競爭資源而呵斥的一種相互等待的景象僵局，如無外力作用，這些進程將資源而呵斥的一種相互等待的景象僵局，如無外力作用，這些進程將永遠不能再向前推進。永遠不能再向前推進。死鎖死鎖DeadlockDeadlock：系統(tǒng)中存在一組進程：系統(tǒng)中存在一組進程( (兩個或多個進程兩個或多個進程),),

2、它們中的每一個進它們中的每一個進程都占用了某種資源而又都在等待其中另一進程所占用的資源程都占用了某種資源而又都在等待其中另一進程所占用的資源, ,這種等待永這種等待永遠不能終了遠不能終了, ,那么說系統(tǒng)出現(xiàn)了那么說系統(tǒng)出現(xiàn)了“死鎖死鎖, ,或說這組進程處于死鎖形狀?；蛘f這組進程處于死鎖形狀。 墮入死鎖形狀的進程稱為死鎖進程，所占用的資源或者需求它們進展墮入死鎖形狀的進程稱為死鎖進程，所占用的資源或者需求它們進展某種協(xié)作的其它進程就會相繼墮入死鎖，最終能夠?qū)е抡麄€系統(tǒng)處于癱瘓某種協(xié)作的其它進程就會相繼墮入死鎖，最終能夠?qū)е抡麄€系統(tǒng)處于癱瘓形狀。形狀。死鎖和饑餓的主要差別是什么？死鎖和饑餓的主要差

3、別是什么？ 1死鎖：是一種相互或循環(huán)死鎖：是一種相互或循環(huán)等待的局面，且它們等待的事等待的局面，且它們等待的事件是決不會發(fā)生的；件是決不會發(fā)生的； 被死鎖的進程應(yīng)該是兩個被死鎖的進程應(yīng)該是兩個或兩個以上，一個進程不能夠或兩個以上，一個進程不能夠本人把本人鎖上，除非出現(xiàn)程本人把本人鎖上，除非出現(xiàn)程序設(shè)計錯誤。序設(shè)計錯誤。2饑餓：不是循環(huán)等待的局饑餓：不是循環(huán)等待的局面，而是一種單向等待；面，而是一種單向等待； 它們等待的事件不是沒有它們等待的事件不是沒有發(fā)生，而是總被別的進程搶先發(fā)生，而是總被別的進程搶先以致不斷輪不到很難輪到以致不斷輪不到很難輪到它們。饑餓的進程能夠是一個它們。饑餓的進程能夠是

4、一個或多個?；蚨鄠€。僅涉及一個進程的死鎖有能夠存在嗎僅涉及一個進程的死鎖有能夠存在嗎?為什么為什么? 3圖圖 簡單的死鎖例子簡單的死鎖例子我們先來看一個懇求不同類型資源的死鎖例子：我們先來看一個懇求不同類型資源的死鎖例子：假定有兩個進程假定有兩個進程Pl和和P2，設(shè)，設(shè)F和和T都是可重用資源。于是都是可重用資源。于是Pl和和P2可有如下方式：可有如下方式：4三、產(chǎn)生死鎖的緣由三、產(chǎn)生死鎖的緣由1 競爭資源競爭資源 當(dāng)系統(tǒng)中供多個進程所共享的資源，缺乏當(dāng)系統(tǒng)中供多個進程所共享的資源，缺乏以同時滿足它們的需求時，引起它們對資源的競爭以同時滿足它們的需求時，引起它們對資源的競爭而產(chǎn)生死鎖；而產(chǎn)生死鎖

5、；進程推進的順序不當(dāng)進程推進的順序不當(dāng) 進程在運轉(zhuǎn)過程中，懇求和釋放進程在運轉(zhuǎn)過程中，懇求和釋放資源的順序不當(dāng)，導(dǎo)致進程的死鎖。資源的順序不當(dāng)，導(dǎo)致進程的死鎖。例題：例題： 一個一個OS有有20個進程，競爭運用個進程，競爭運用65個同類資源，個同類資源，懇求方式是逐個進展的，一旦某個進程獲得它所需懇求方式是逐個進展的，一旦某個進程獲得它所需求的全部資源，那么立刻歸還一切資源。每個進程求的全部資源，那么立刻歸還一切資源。每個進程最多運用三個資源。假設(shè)僅思索這類資源，該系統(tǒng)最多運用三個資源。假設(shè)僅思索這類資源，該系統(tǒng)有無能夠產(chǎn)生死鎖，為什么？有無能夠產(chǎn)生死鎖，為什么？ 答：不能夠。由于死鎖產(chǎn)生的緣

6、由有兩點：系統(tǒng)資源缺乏或推進答：不能夠。由于死鎖產(chǎn)生的緣由有兩點：系統(tǒng)資源缺乏或推進順序不當(dāng)，在此題中，進程所需的最大資源數(shù)為順序不當(dāng)，在此題中，進程所需的最大資源數(shù)為60，而系統(tǒng)共有，而系統(tǒng)共有該類資源該類資源65個，其資源數(shù)已足夠系統(tǒng)內(nèi)各進程運用。個，其資源數(shù)已足夠系統(tǒng)內(nèi)各進程運用。5四、產(chǎn)生死鎖的四個必要條件四、產(chǎn)生死鎖的四個必要條件互斥條件互斥條件: :資源在一段時間內(nèi)只能被一個進程資源在一段時間內(nèi)只能被一個進程所運用。臨界資源所運用。臨界資源懇求和堅持條件懇求和堅持條件: :一個進程懇求資源得不到滿一個進程懇求資源得不到滿足而等待足而等待, ,但不釋放已占有的資源。部分分但不釋放已占

7、有的資源。部分分配配) )不剝奪條件不剝奪條件: :一個資源僅能被占有它的進程所一個資源僅能被占有它的進程所釋放，而不能被其他進程剝奪。自動釋放釋放，而不能被其他進程剝奪。自動釋放環(huán)路等待條件環(huán)路等待條件: :存在一個進程資源的環(huán)路鏈，存在一個進程資源的環(huán)路鏈，鏈中每一個進程占用著某些資源，又在等待另鏈中每一個進程占用著某些資源，又在等待另一個進程占有的資源。一個進程占有的資源。 處理死鎖的方法普通可分為處理死鎖的方法普通可分為: :預(yù)防、防止、預(yù)防、防止、檢測和解除四種檢測和解除四種. .6死鎖的排除方法死鎖的排除方法1 鴕鳥算法鴕鳥算法2 預(yù)防死鎖預(yù)防死鎖3 防止死鎖防止死鎖4 檢測和解除

8、死鎖檢測和解除死鎖7 處理死鎖的最簡一方法就是鴕鳥算法。即像處理死鎖的最簡一方法就是鴕鳥算法。即像鴕鳥一樣，當(dāng)遇到危險時，將頭埋進沙子里，偽鴕鳥一樣，當(dāng)遇到危險時，將頭埋進沙子里，偽裝毫無問題。裝毫無問題。 當(dāng)死鎖在計算機中很少出現(xiàn)時，比如說每五年當(dāng)死鎖在計算機中很少出現(xiàn)時，比如說每五年或更長時間才出現(xiàn)一次時，人們就不用破費更多或更長時間才出現(xiàn)一次時，人們就不用破費更多的精神去處理它，而是采用類似鴕鳥一樣的方法的精神去處理它，而是采用類似鴕鳥一樣的方法忽略它。忽略它。 以以UNIXUNIX系統(tǒng)為例，它潛在地存在死鎖，但它系統(tǒng)為例，它潛在地存在死鎖，但它并不花功夫去檢測和解除死鎖，而是忽略不去理

9、并不花功夫去檢測和解除死鎖，而是忽略不去理它。它。1 1鴕鳥算法置之不理鴕鳥算法置之不理8 2 2 預(yù)防死鎖預(yù)防死鎖 根據(jù)產(chǎn)生死鎖的四個必要條件，只需使其中之根據(jù)產(chǎn)生死鎖的四個必要條件，只需使其中之一不能成立，死鎖就不會出現(xiàn)。但必要條件一不能成立，死鎖就不會出現(xiàn)。但必要條件1 1是由是由設(shè)備的固有特性所決議的，不僅不能改動，相反還設(shè)備的固有特性所決議的，不僅不能改動，相反還應(yīng)加以保證，因此實踐上只需三種方法。應(yīng)加以保證，因此實踐上只需三種方法。 預(yù)防死鎖是一種較易實現(xiàn)的方法，已被廣預(yù)防死鎖是一種較易實現(xiàn)的方法，已被廣泛運用，但由于所施加的限制條件往往太嚴(yán)厲，能泛運用，但由于所施加的限制條件往往

10、太嚴(yán)厲，能夠?qū)е孪到y(tǒng)資源利用率和系統(tǒng)吞吐量降低。夠?qū)е孪到y(tǒng)資源利用率和系統(tǒng)吞吐量降低。1破壞懇求和堅持條件破壞懇求和堅持條件2破壞不剝奪條件破壞不剝奪條件3破壞環(huán)路等待條件破壞環(huán)路等待條件9 系統(tǒng)要求任一進程必需預(yù)先懇求它所需的全系統(tǒng)要求任一進程必需預(yù)先懇求它所需的全部資源，而且僅當(dāng)該進程的全部資源要求能得部資源，而且僅當(dāng)該進程的全部資源要求能得到滿足時，系統(tǒng)才干給予一次性分配，然后啟到滿足時，系統(tǒng)才干給予一次性分配，然后啟動該進程運轉(zhuǎn)，但是在分配時只需有一種資源動該進程運轉(zhuǎn)，但是在分配時只需有一種資源不滿足，系統(tǒng)就不會給進程分配資源。進程運不滿足，系統(tǒng)就不會給進程分配資源。進程運轉(zhuǎn)期間，不會

11、再懇求新的資源，所以，再分配轉(zhuǎn)期間，不會再懇求新的資源，所以，再分配就不會發(fā)生摒棄了部分分配。就不會發(fā)生摒棄了部分分配。缺陷：缺陷： 資源嚴(yán)重浪費資源嚴(yán)重浪費 進程運轉(zhuǎn)延遲進程運轉(zhuǎn)延遲1破壞破壞“懇求和堅持條件懇求和堅持條件(靜態(tài)分配戰(zhàn)靜態(tài)分配戰(zhàn)略略)10采用的戰(zhàn)略：一個曾經(jīng)占有了某些資源的進程，當(dāng)采用的戰(zhàn)略：一個曾經(jīng)占有了某些資源的進程，當(dāng)它再提出新的資源要求而不能立刻得到滿足時，必它再提出新的資源要求而不能立刻得到滿足時，必需釋放它曾經(jīng)占有的一切資源，待以后需求時再重需釋放它曾經(jīng)占有的一切資源，待以后需求時再重新懇求。新懇求。 缺陷：缺陷：1 1實現(xiàn)比較復(fù)雜，且要付出很大代價；實現(xiàn)比較復(fù)雜

12、，且要付出很大代價；2 2還由于反復(fù)地懇求和釋放資源，而使進程的執(zhí)行還由于反復(fù)地懇求和釋放資源，而使進程的執(zhí)行無限地推遲，延伸了周轉(zhuǎn)時間，添加了系統(tǒng)的開銷，無限地推遲，延伸了周轉(zhuǎn)時間，添加了系統(tǒng)的開銷，降低了系統(tǒng)吞吐量例如打印機打印的結(jié)果不延續(xù)降低了系統(tǒng)吞吐量例如打印機打印的結(jié)果不延續(xù)2 . 防止防止“不剝奪條件的出現(xiàn)不剝奪條件的出現(xiàn)113. 防止防止“環(huán)路等待條件的出現(xiàn)環(huán)路等待條件的出現(xiàn)(層次分配戰(zhàn)層次分配戰(zhàn)略略)優(yōu)點優(yōu)點: :資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善缺陷：缺陷：1 1為系統(tǒng)中各種類型的資源所分配的序號必需相對穩(wěn)

13、定，這就限為系統(tǒng)中各種類型的資源所分配的序號必需相對穩(wěn)定，這就限制了新設(shè)備類型的添加；制了新設(shè)備類型的添加；2 2 進程實踐運用資源的順序與系統(tǒng)規(guī)定的順序不同而呵斥資源的進程實踐運用資源的順序與系統(tǒng)規(guī)定的順序不同而呵斥資源的浪費；浪費； 這種方法的根本思想是：資源被分成多個層次,一個進程得到某一層的一個資源后,它只能再懇求較高一層的資源;當(dāng)一個進程要釋放某層的一個資源時,必需先釋放所占用的較高層的資源;當(dāng)一個進程獲得了某一層的一個資源后,它想再懇求該層中的另一個資源,就必需先釋放該層中的已占用資源.123 3 死鎖防止死鎖防止 假設(shè)操作系統(tǒng)能保證一切的進程在有限的時間假設(shè)操作系統(tǒng)能保證一切的進

14、程在有限的時間內(nèi)得到需求的全部資源內(nèi)得到需求的全部資源,那么稱系統(tǒng)處于平安形狀那么稱系統(tǒng)處于平安形狀,否否那么稱系統(tǒng)是不平安的那么稱系統(tǒng)是不平安的. 防止死鎖與預(yù)防死鎖的區(qū)別在于防止死鎖與預(yù)防死鎖的區(qū)別在于: 預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之一，嚴(yán)厲地防止死鎖的出現(xiàn)。一，嚴(yán)厲地防止死鎖的出現(xiàn)。 防止死鎖，它是在進程懇求分配資源時，采用銀防止死鎖，它是在進程懇求分配資源時，采用銀行家算法等防止系統(tǒng)進入不平安形狀。行家算法等防止系統(tǒng)進入不平安形狀。 13 在資源的動態(tài)分配的過程中，運用某種方法去防在資源的動態(tài)分配的過程中，運用某種方法去防止系統(tǒng)進

15、入不平安形狀，從而防止死鎖的發(fā)生。止系統(tǒng)進入不平安形狀，從而防止死鎖的發(fā)生。 系統(tǒng)形狀：系統(tǒng)形狀： 平安形狀：指系統(tǒng)能按照某種順序平安形狀：指系統(tǒng)能按照某種順序如如，為每個進程分配所需的資源，直，為每個進程分配所需的資源，直至最大需求，使得每個進程都能順利完成至最大需求，使得每個進程都能順利完成(稱為稱為序列為平安序列序列為平安序列) 。 非平安形狀：非平安形狀：即在某個時辰系統(tǒng)中不存在一個平安序列，那么稱系即在某個時辰系統(tǒng)中不存在一個平安序列，那么稱系統(tǒng)處于不平安形狀或非平安形狀。統(tǒng)處于不平安形狀或非平安形狀。留意留意:1平安序列不一定只需一個平安序列不一定只需一個2系統(tǒng)只需處在平安形狀，就

16、一定不會發(fā)生死鎖系統(tǒng)只需處在平安形狀，就一定不會發(fā)生死鎖3系統(tǒng)處在不平安形狀下時，未必一定會發(fā)生死鎖系統(tǒng)處在不平安形狀下時，未必一定會發(fā)生死鎖 雖然并非一切不平安形狀都是死鎖形狀，雖然并非一切不平安形狀都是死鎖形狀，但當(dāng)系統(tǒng)進入不平安形狀后，便有能夠進入死但當(dāng)系統(tǒng)進入不平安形狀后，便有能夠進入死鎖形狀；反之只需系統(tǒng)處于平安形狀，系統(tǒng)便鎖形狀；反之只需系統(tǒng)處于平安形狀，系統(tǒng)便可防止進入死鎖形狀。因此，防止死鎖的本質(zhì)可防止進入死鎖形狀。因此，防止死鎖的本質(zhì)是如何使系統(tǒng)不進入不平安形狀。銀行家算是如何使系統(tǒng)不進入不平安形狀。銀行家算法法14平安形狀的例子平安形狀的例子例：假定系統(tǒng)有三個進程例：假定系

17、統(tǒng)有三個進程P1、P2、P3，共有，共有12臺磁帶機。臺磁帶機。進程進程P1 、P2和和P3分別需求分別需求10臺、臺、4臺和臺和9臺。設(shè)在臺。設(shè)在T0時辰，進程時辰，進程P1、P2和和P3曾經(jīng)獲得曾經(jīng)獲得5臺、臺、2臺和臺和2臺，還臺，還有有3臺空閑沒有分配。臺空閑沒有分配。進程最大需求已分配可用P11053P2P34229T0時辰系統(tǒng)是平安的。這時存在一個平安序列時辰系統(tǒng)是平安的。這時存在一個平安序列15銀行家算法銀行家算法 銀行家算法是最有代表性的防止死鎖銀行家算法是最有代表性的防止死鎖算法，是算法，是Dijkstra提出的銀行家算法。這是提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)

18、金貸款的發(fā)由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。放而得名。 16 銀行家可以把一定數(shù)量的資金供多個用戶銀行家可以把一定數(shù)量的資金供多個用戶周轉(zhuǎn)運用周轉(zhuǎn)運用,為保證資金的平安為保證資金的平安,銀行家規(guī)定銀行家規(guī)定: (1)當(dāng)一個用戶對資金的最大需求量不超越當(dāng)一個用戶對資金的最大需求量不超越很行家現(xiàn)有的資金時可接納該用戶很行家現(xiàn)有的資金時可接納該用戶. (2)用戶可以分期貸款用戶可以分期貸款,但貸款的總數(shù)不能超但貸款的總數(shù)不能超越最大需求量越最大需求量; (3)當(dāng)銀行家現(xiàn)有的資金不能滿足用戶的尚當(dāng)銀行家現(xiàn)有的資金不能滿足用戶的尚需總數(shù)時需總數(shù)時,對用戶的貸款可推遲支付對用戶的貸款可推遲支付

19、,但總能運但總能運用戶在有限的時間里得到貸款用戶在有限的時間里得到貸款; (4)當(dāng)用戶得到所需的全部資金后當(dāng)用戶得到所需的全部資金后,一定能一定能在有限的時間里歸還一切資金在有限的時間里歸還一切資金 銀行家算法是經(jīng)過動態(tài)地檢測系統(tǒng)中資銀行家算法是經(jīng)過動態(tài)地檢測系統(tǒng)中資源分配情況和進程對資源的需求情況來決議如源分配情況和進程對資源的需求情況來決議如何分配資源的，在能確保系統(tǒng)處于平安形狀時何分配資源的，在能確保系統(tǒng)處于平安形狀時才干把資源分配給懇求者，從而防止系統(tǒng)發(fā)生才干把資源分配給懇求者，從而防止系統(tǒng)發(fā)生死鎖。死鎖。17要記住的一些變量的稱號要記住的一些變量的稱號 1 Available可利用資

20、源總數(shù)可利用資源總數(shù) 某類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部某類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目?？捎觅Y源數(shù)目。 2 Max：某個進程對某類資源的最大需求數(shù)：某個進程對某類資源的最大需求數(shù) 3 Allocation： 某類資源已分配給某進程的資源數(shù)。某類資源已分配給某進程的資源數(shù)。 4 Need：某個進程還需求的各類資源數(shù)。：某個進程還需求的各類資源數(shù)。 Need= Max-Allocation系統(tǒng)把進程懇求的資源系統(tǒng)把進程懇求的資源(Request)分配給它以后要修正的變量分配給它以后要修正的變量Available:=Available-Reques

21、t;Allocation:=Allocation+Request;Need:= Need- Request;18例題：假定系統(tǒng)中有五個進程例題：假定系統(tǒng)中有五個進程P0、P1、P2、P3、P4和三種類型的資源和三種類型的資源A，B，C，每一，每一種資源的數(shù)量分別為種資源的數(shù)量分別為10、5、7，在，在T0時辰的時辰的資源分配情況如圖資源分配情況如圖資源情況進程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 32 0 07 5 3 3 0 22 1 10 0 27 4 31 2 20

22、00 1 14 3 13 3 2193 3 21 2 22 0 0資源情況資源情況進程進程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 32 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 27 5 3資源情況資源情況進程進程NeedA B CworkA B CWorkAllocationA B CAllocationA B CP0finish5 3 2truetruetruetruetrue0 1 12 1 15 3 27 4 37

23、4 34 3 10 0 27 4 57 4 56 0 03 0 210 4 710 4 77 4 30 1 010 5 7最大值最大值已分配已分配還需求還需求可用可用任務(wù)向量Work.它表示系統(tǒng)可提供應(yīng)進程繼續(xù)運轉(zhuǎn)所需求的各類資源的數(shù)目10,5 7P1P3P4P2202 3 00 2 03 0 2資源情況資源情況進程進程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 32 0 0( 3 0 2 )3 0 22 1 10 0 27 4 31 2 2( 0 2 0 )6 0 00 1 1

24、4 3 13 3 2( 2 3 0 )7 5 3資源情況資源情況進程進程NeedA B CworkA B CWorkAllocationA B CAllocationA B CP2finish5 3 2truetruetruetruetrue0 1 12 1 15 3 27 4 37 4 34 3 10 0 27 4 57 4 57 4 30 1 07 5 57 5 56 0 03 0 210 5 7假設(shè)假設(shè)P1發(fā)出懇求向量發(fā)出懇求向量Request1，0，210,5 7P1P3P4P0212 1 0資源情況資源情況進程進程AllocationA B CMaxA B CNeedA B CAva

25、ilableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 33 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0( 2 1 0 )7 5 3資源情況資源情況進程進程NeedA B CworkA B CWorkAllocationA B CAllocationA B Cfinishflase假設(shè)假設(shè)P0發(fā)出懇求向量發(fā)出懇求向量Request0，2，010,5 7(0 3 0)(7 2 3)假設(shè)假設(shè)P1發(fā)出懇求向量發(fā)出懇求向量Request0，2，022 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測與解

26、除技死鎖的檢測與解除技術(shù)是指定期啟動一個軟術(shù)是指定期啟動一個軟件檢測系統(tǒng)的形狀，假件檢測系統(tǒng)的形狀，假設(shè)發(fā)現(xiàn)有死鎖存在，那設(shè)發(fā)現(xiàn)有死鎖存在，那么采取措施恢復(fù)之。么采取措施恢復(fù)之。 (1) (1)死鎖的檢測：本質(zhì)是死鎖的檢測：本質(zhì)是確定能否存在環(huán)路等待確定能否存在環(huán)路等待景象，一旦發(fā)現(xiàn)這種環(huán)景象，一旦發(fā)現(xiàn)這種環(huán)路便認定死鎖存在，并路便認定死鎖存在，并識別出該環(huán)路所涉及的識別出該環(huán)路所涉及的有關(guān)進程，以供系統(tǒng)采有關(guān)進程，以供系統(tǒng)采取適當(dāng)?shù)拇胧﹣斫獬廊∵m當(dāng)?shù)拇胧﹣斫獬梨i。最常用的是一種基鎖。最常用的是一種基于進程于進程-資源分配圖資源分配圖和死鎖定理的檢測死鎖和死鎖定理的檢測死鎖算法。算法。23

27、進程進程-資源分配圖資源分配圖RAG圖圖系統(tǒng)死鎖可用進程系統(tǒng)死鎖可用進程-資源分配圖來描畫，資源分配圖來描畫，該圖是由一組結(jié)點和一組邊所組成的。該圖是由一組結(jié)點和一組邊所組成的。用圓圈代表一個進程，用方框代表一用圓圈代表一個進程，用方框代表一類資源，由于一種類型的資源能夠有多類資源，由于一種類型的資源能夠有多個，可用方框中的一個點代表一類資源個，可用方框中的一個點代表一類資源中的一個資源中的一個資源幾個概念：懇求邊，分配邊幾個概念：懇求邊，分配邊 P1P2r1r2懇求邊資源分配圖分配邊24 封鎖進程：是指某個進程由于懇求了超越系統(tǒng)中現(xiàn)封鎖進程：是指某個進程由于懇求了超越系統(tǒng)中現(xiàn)有的未分配資源數(shù)

28、目的資源，而被系統(tǒng)封鎖的進程。有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進程。 非封鎖進程：即沒有被系統(tǒng)封鎖的進程。非封鎖進程：即沒有被系統(tǒng)封鎖的進程。 進程進程-資源分配圖的化簡方法：資源分配圖的化簡方法： 假設(shè)某個進程假設(shè)某個進程-資源分配圖中存在一個進程資源分配圖中存在一個進程Pi，此，此刻刻Pi是非封鎖進程，那么可以進展如下化簡：當(dāng)是非封鎖進程，那么可以進展如下化簡：當(dāng)Pi有懇有懇求邊時，首先將其懇求邊變成分配邊求邊時，首先將其懇求邊變成分配邊(即滿足即滿足Pi的資源的資源懇求懇求)，而一旦，而一旦Pi的一切資源懇求都得到滿足，的一切資源懇求都得到滿足，Pi就能就能在有限的時間內(nèi)運轉(zhuǎn)終了

29、，并釋放其所占用的全部資源，在有限的時間內(nèi)運轉(zhuǎn)終了，并釋放其所占用的全部資源，此時此時Pi只需分配邊，刪去這些分配邊實踐上相當(dāng)于消只需分配邊，刪去這些分配邊實踐上相當(dāng)于消去了去了Pi的一切懇求邊和分配邊，使的一切懇求邊和分配邊，使Pi成為孤立結(jié)點。成為孤立結(jié)點。反復(fù)進展在經(jīng)過一系列的簡化后，假設(shè)能消去圖中反復(fù)進展在經(jīng)過一系列的簡化后，假設(shè)能消去圖中的一切邊，使一切的進程都成為孤立結(jié)點，那么稱該圖的一切邊，使一切的進程都成為孤立結(jié)點，那么稱該圖是可完全簡化的；反之那么是不可完全簡化的。是可完全簡化的；反之那么是不可完全簡化的。25死鎖定理：死鎖定理： 系統(tǒng)中某個時辰系統(tǒng)中某個時辰S為死鎖形狀的充

30、要條件為死鎖形狀的充要條件是是S時辰系統(tǒng)的資源分配圖是不可完全簡化的。時辰系統(tǒng)的資源分配圖是不可完全簡化的。 P1P2r1r2P1P2r1r2P1P2r1r226斷定死鎖準(zhǔn)那么：斷定死鎖準(zhǔn)那么： (1)假設(shè)假設(shè)RAG中未出現(xiàn)任何環(huán)，那么此時系統(tǒng)內(nèi)不存中未出現(xiàn)任何環(huán)，那么此時系統(tǒng)內(nèi)不存在死鎖；在死鎖； (2)假設(shè)假設(shè)RAG中出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源中出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源均只需一個個體，那么有環(huán)就有死鎖均只需一個個體，那么有環(huán)就有死鎖;此時環(huán)路是存此時環(huán)路是存在死鎖的充分必要條件；在死鎖的充分必要條件； (3)假設(shè)假設(shè)RAG中出現(xiàn)了環(huán)，但處于此環(huán)中的每類資源中出現(xiàn)了環(huán)，但處于此

31、環(huán)中的每類資源的個數(shù)不全為的個數(shù)不全為1，那么環(huán)的存在只是產(chǎn)生死鎖的必要，那么環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件。此時能否有死鎖，還要經(jīng)過條件而不是充分條件。此時能否有死鎖，還要經(jīng)過對對RAG的化簡而定。的化簡而定。 P1P2P3R1R2R3R4P1P2R1R2R327斷定死鎖準(zhǔn)那么：斷定死鎖準(zhǔn)那么： (1)假設(shè)假設(shè)RAG中未出現(xiàn)任何環(huán)，那么此時系統(tǒng)內(nèi)不存在中未出現(xiàn)任何環(huán)，那么此時系統(tǒng)內(nèi)不存在死鎖；死鎖； (2)假設(shè)假設(shè)RAG中出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源均中出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源均只需一個個體，那么有環(huán)就就有死鎖只需一個個體，那么有環(huán)就就有死鎖;此時環(huán)路是存在此時環(huán)路

32、是存在死鎖的必要充分條件；死鎖的必要充分條件； (3)假設(shè)假設(shè)RAG中出現(xiàn)了環(huán)，但處于此環(huán)中的每類資源的中出現(xiàn)了環(huán)，但處于此環(huán)中的每類資源的個數(shù)不全為個數(shù)不全為1，那么環(huán)的存在只是產(chǎn)生死鎖的必要條，那么環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件。此時能否有死鎖，還要經(jīng)過對件而不是充分條件。此時能否有死鎖，還要經(jīng)過對RAG的化簡而定。的化簡而定。P1P2P3R1R2R3R4P4P3P2P1R1R228例題例題:化簡如下圖的資源分配圖，并闡明有無進程處于死鎖形狀？化簡如下圖的資源分配圖，并闡明有無進程處于死鎖形狀？P0P1P2P3P4R0R1R2R3R4R4R3P0P1P2P3P429 資源分配圖中存在環(huán)路并不一定發(fā)生死鎖,由于循環(huán)等待資源僅是死鎖發(fā)生的必要條件,而不是充分條件.如:P1P2P3R1R2R3有環(huán)有死鎖P4P3P2P1R1R2有環(huán)無死鎖30 死鎖的解除：是與檢測死鎖相配套的一種措死鎖的解除：是與檢測死鎖相配套的一種措施，用于將進程從死鎖形狀下解脫出來。施，用于將進程從死鎖形狀下解脫出來。常用的方法有：常用的方法有：1、立刻終了一切進程的執(zhí)行、立刻終了一切進程的執(zhí)行,并重新啟動操作系統(tǒng)并重新啟動操作系統(tǒng).2、吊銷進程：最簡單吊銷進程的方法是使全部死鎖、吊銷進程：最簡單吊銷進