操作系統(tǒng)死鎖實用教案

1、12021-12-15死鎖的概念(ginin) 死鎖舉例 產(chǎn)生(chnshng)死鎖的原因 產(chǎn)生(chnshng)死鎖的必要條件 處理死鎖的基本方法 第1頁/共46頁第一頁，共47頁。22021-12-15死鎖現(xiàn)象(xinxing)第2頁/共46頁第二頁，共47頁。32021-12-15死鎖舉例(j l) 【 例 】設(shè)系統(tǒng)有打印機、掃描儀各一臺，被進(jìn)程1 1和P2P2共享。兩個進(jìn)程并發(fā)執(zhí)行，按下列次序(cx)(cx)請求和釋放資源：P1：申請打印機申請打印機申請掃描儀申請掃描儀使用使用釋放打印機釋放打印機釋放掃描儀釋放掃描儀P2：申請掃描儀申請掃描儀申請打印機申請打印機使用使用釋放打印機釋放打

2、印機釋放掃描儀釋放掃描儀第3頁/共46頁第三頁，共47頁。42021-12-15死鎖定義(dngy)(dngy) 死鎖 是指多個進(jìn)程在運行過程中因爭奪資源而造成的一種僵持局面。即，一組進(jìn)程中，每個進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到該資源，這種現(xiàn)象稱為死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。 關(guān)于死鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是兩個（兩個以上進(jìn)程才會出現(xiàn)死鎖） 參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集 注：如果死鎖發(fā)生，會浪費大量(dling)(dling)系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。 如果沒有外力作

3、用，死鎖是無法解除的。第4頁/共46頁第四頁，共47頁。52021-12-15產(chǎn)生(chnshng)死鎖的原因 競爭資源（系統(tǒng)內(nèi)的資源數(shù)量(shling)不足） 進(jìn)程推進(jìn)的順序不當(dāng) 進(jìn)程推進(jìn)順序合法 不會造成死鎖的進(jìn)程推進(jìn)順序 進(jìn)程推進(jìn)順序非法 會造成死鎖的進(jìn)程推進(jìn)順序第5頁/共46頁第五頁，共47頁。62021-12-15產(chǎn)生(chnshng)(chnshng)死鎖的必要條件 互斥條件（資源本身的性質(zhì)） 涉及的資源是非共享的，必須存在需要(xyo)互斥使用的資源。 請求和保持條件 （進(jìn)程的行為） 進(jìn)程在等待一新資源時繼續(xù)占有已分配的資源。 不剝奪條件（系統(tǒng)規(guī)定） 不能強行剝奪進(jìn)程擁有的資源。

4、 環(huán)路等待條件（進(jìn)程/資源之間的關(guān)系） 存在一個進(jìn)程等待隊列 P1 , P2 , , Pn , 其中P1等待P2占有的資源，P2等待P3占有的資源，Pn等待P1占有的資源，形成一個進(jìn)程等待環(huán)路。第6頁/共46頁第六頁，共47頁。72021-12-15處理(chl)死鎖的基本方法 預(yù)防死鎖 避免(bmin)死鎖 檢測死鎖 解除死鎖第7頁/共46頁第七頁，共47頁。82021-12-15預(yù)防(yfng)死鎖 通過設(shè)置某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。優(yōu)點較易實現(xiàn)缺點由于所施加的限制往往(wngwng)太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。第8頁/共46頁第

5、八頁，共47頁。92021-12-15避免(bmin)(bmin)死鎖 不事先采取限制去破壞產(chǎn)生死鎖的條件，而是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而(cng r)避免死鎖的發(fā)生。優(yōu)點只需要較弱的限制條件，可獲得較高的資源利用率和系統(tǒng)吞吐量。缺點實現(xiàn)較難第9頁/共46頁第九頁，共47頁。102021-12-15檢測(jin c)死鎖 事先并不采取任何限制，也不檢查系統(tǒng)是否進(jìn)入不安全區(qū)，允許死鎖發(fā)生，但可通過檢測機構(gòu)(jgu)及時檢測出死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。第10頁/共46頁第十頁，共47頁。112021-12-15解除(jich)死鎖 與檢測死

6、鎖相配套，用于將進(jìn)程從死鎖狀態(tài)解脫出來。 優(yōu)點可獲得較高的資源利用率和系統(tǒng)吞吐量。缺點(qudin)實現(xiàn)難度大 第11頁/共46頁第十一頁，共47頁。122021-12-15死鎖的預(yù)防(yfng) 死鎖的預(yù)防一般是從破壞導(dǎo)致發(fā)生死鎖的必要條件著手(zhushu)(zhushu)，只要能使四個必要條件其中的任何一個不成立，就可防止死鎖。 破壞互斥條件：改變把獨享資源變?yōu)楣蚕碣Y源； 破壞請求和保持條件：采用靜態(tài)分配策略； 破壞不可剝奪條件：主動釋放資源策略和強行剝奪策略； 破壞循環(huán)等待條件：采用資源的有序申請策略； 第12頁/共46頁第十二頁，共47頁。132021-12-15破壞“請求和保持(b

7、och)(boch)”條件采用靜態(tài)分配資源策略 要求(yoqi)每個進(jìn)程在運行前必須一次性申請它所要求(yoqi)的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時才給予一次性分配。優(yōu)點：簡單、安全缺點：資源利用率低； 使進(jìn)程延遲運行 第13頁/共46頁第十三頁，共47頁。142021-12-15破壞(phui)“不可剝奪”條件 破壞不可剝奪條件 一個已擁有資源的進(jìn)程，若它再提出新資源要求而不能立即得到滿足時，它必須釋放已經(jīng)擁有的所有資源。以后需要時再重新申請。 缺點 這種方法(fngf)比較復(fù)雜且系統(tǒng)開銷大。 在剝奪資源時，需要保存中間信息，但也會使進(jìn)程前后兩次運行的信息不連續(xù)。 所以，臨界資源不宜

8、剝奪。第14頁/共46頁第十四頁，共47頁。152021-12-15破壞“循環(huán)等待(dngdi)”條件 采用資源有序分配策略 事先把系統(tǒng)中的所有資源按大多數(shù)進(jìn)程使用資源的順序由小到大進(jìn)行編號，每個進(jìn)程只能按資源編號遞增的順序申請資源。例子 多個進(jìn)程之間只可能存在占據(jù)較低序號資源的進(jìn)程等待占據(jù)較高序號資源的進(jìn)程釋放資源的情況，但不可能存在反向的等待，因此(ync)，它們之間絕對不會形成循環(huán)等待環(huán)路 缺點 資源的編號不容易合理化 限制了用戶簡單自主的編程 當(dāng)系統(tǒng)增加新設(shè)備類型時，要重新對系統(tǒng)資源進(jìn)行合理編號第15頁/共46頁第十五頁，共47頁。162021-12-15資源按序分配(fnpi)示例

9、系統(tǒng)(xtng)中有下列 設(shè)備：輸入機（1），打印機（2），穿孔機（3），磁帶機（4），磁盤（5）。有一進(jìn)程要先后使用輸入機、磁盤、打印機，則它申請設(shè)備時要按輸入機、打印機、磁盤的順序申請。例如(lr)(lr)：1 1，2 2，3 3，5 5P1：申請申請1申請申請5申請申請21 ，2，5第16頁/共46頁第十六頁，共47頁。172021-12-15死鎖的避免(bmin) 避免死鎖的基本思想 允許進(jìn)程動態(tài)申請資源，但在每次分配資源時，都要通過判斷系統(tǒng)狀態(tài)來決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。 系統(tǒng)狀態(tài) 安全狀態(tài) 在某一時刻，如果系統(tǒng)能按某種順序（如P1，P2，

10、,Pn, 稱為安全序列）為每個進(jìn)程分配其所需的資源，直至所有進(jìn)程都能運行完成(wn chng)，稱系統(tǒng)處于安全狀態(tài)。 不安全狀態(tài) 若不存在這樣一個安全序列稱系統(tǒng)處于不安全狀態(tài)。 第17頁/共46頁第十七頁，共47頁。182021-12-15安全(nqun)序列 在某一時刻，存在一個進(jìn)程序列P1，Pn，對每個進(jìn)程Pi(1in），如果滿足它以后尚需要的資源量不超過系統(tǒng)(xtng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i )當(dāng)前占有資源量之和，即Needi則Available+Allicationj (1j i-1 )，則稱P1，Pn為安全序列。 安全狀態(tài)(zhungti)(zhungti)一定是 沒

11、有死鎖發(fā)生的不安全狀態(tài)(zhungti)(zhungti)一定 導(dǎo)致死鎖?第18頁/共46頁第十八頁，共47頁。192021-12-15安全狀態(tài)(zhungti)示例 有三個進(jìn)程P1, P2, P3，有12臺磁帶機 P1共要求10臺 P2共要求4臺 P3共要求9臺 在T0時刻，P1, P2, P3分別獲得5、2、2臺，尚有3臺空閑 分析 經(jīng)分析，在T0時刻，系統(tǒng)是安全(nqun)的。因為存在一個 安 全 ( n q u n ) 序 列 P 2 ( 2 3 ) 、 P 1 ( 5 = 3 + 2 ) 、P3(7=3+2+2)。見下圖進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需還需可用可用P1105P

12、242P392進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需還需可用可用P11055 3P2422P3927第19頁/共46頁第十九頁，共47頁。202021-12-15由安全(nqun)(nqun)狀態(tài)向不安全(nqun)(nqun)狀態(tài)的轉(zhuǎn)換如果不按安全(nqun)序列分配資源，則系統(tǒng)可能會由安全(nqun)狀態(tài)進(jìn)入不安全(nqun)狀態(tài)。如在T0以后，P3要求1臺磁帶機，若系統(tǒng)分給它一臺，則系統(tǒng)進(jìn)入不安全(nqun)狀態(tài)。 因為其余2臺分給P2，P2完成后，只能釋放4臺，這既不能滿足P1（5臺），也不能滿足P3（6臺）。將導(dǎo)致死鎖?？梢姰?dāng)P3申請資源時，盡管系統(tǒng)中有資源也不能分給它。 系統(tǒng)進(jìn)入

13、不安全(nqun)狀態(tài)：進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需還需可用可用P11055（3）2P2422P39（2）3（7）6第20頁/共46頁第二十頁，共47頁。212021-12-15利用銀行家算法(sun f)避免死鎖 銀行家算法 銀行家擁有一筆周轉(zhuǎn)資金 客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款 銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳 用銀行家算法避免死鎖 操作系統(tǒng)(co zu x tn)（銀行家） 操作系統(tǒng)(co zu x tn)管理的資源(周轉(zhuǎn)資金) 進(jìn)程（要求貸款的客戶） 最有代表性的避免死鎖算法，由Dijkstra提出。第21頁/共46頁

14、第二十一頁，共47頁。222021-12-15銀行家算法(sunf)的數(shù)據(jù)結(jié)構(gòu)(1) 可利用資源向量(xingling)Available。 它是一個含有m個元素的數(shù)組，其中每個元素代表一類可利用資源的數(shù)目。 int Availablem-1; 如： ABC523第22頁/共46頁第二十二頁，共47頁。232021-12-15銀行家算法(sunf)的數(shù)據(jù)結(jié)構(gòu)(2) 最大需求矩陣Max：n*m矩陣，表示n個進(jìn)程(jnchng)的每一個對m類資源的最大需求。 int Maxn-1m-1;ABCP1562P2331P3425P4332第23頁/共46頁第二十三頁，共47頁。242021-12-15銀

15、行家算法(sunf)的數(shù)據(jù)結(jié)構(gòu)(3) 分配矩陣Allocation ：n*m矩陣，表示每個進(jìn)程(jnchng)已分配的資源數(shù)。 int Allocationn-1m-1ABCP1212P2121P3222P4132第24頁/共46頁第二十四頁，共47頁。252021-12-15銀行家算法(sunf)的數(shù)據(jù)結(jié)構(gòu)(4) 需求矩陣Need ：n*m矩陣，表示每個進(jìn)程還需要(xyo)各類資源數(shù)。 int Needn-1m-1ABCP1352P2211P3223P4232第25頁/共46頁第二十五頁，共47頁。262021-12-15銀行家算法(sunf)的數(shù)據(jù)結(jié)構(gòu)(5) 進(jìn)程申請資源向量Request

16、 ： 它是一個(y )含有m個元素的數(shù)組，其中每個元素代表進(jìn)程申請資源的數(shù)目。 int Requestm-1; 如： ABC312第26頁/共46頁第二十六頁，共47頁。272021-12-15銀行家算法(sun f)(sun f)描述 當(dāng)進(jìn)程Pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：(1) 若RequestiNeedi, 轉(zhuǎn)（2）；否則錯誤返回(2) 若RequestiAvailable, 轉(zhuǎn)（3）；否則進(jìn)程等待(dngdi)(3) 假設(shè)系統(tǒng)分配了資源，則有： Available=Available-Requesti; Allocationi=Allocationi+Requesti; Need

17、i=Needi-Requesti(4) 執(zhí)行安全性算法，若系統(tǒng)新狀態(tài)是安全的，則分配 完成，若系統(tǒng)新狀態(tài)是不安全的，則恢復(fù)原狀態(tài)， 進(jìn)程等待(dngdi)。第27頁/共46頁第二十七頁，共47頁。282021-12-15安全性算法(sun f)(sun f) 定義數(shù)據(jù)結(jié)構(gòu) int Workm-1; bool Finishn-1; m代表資源的數(shù)量，n代表進(jìn)程的數(shù)量 安全性算法步驟 (1) Work=Available; Finishi=false; (2) 尋找滿足下列條件的i： a. Finishi=false; b. NeediWork;如果不存在，則轉(zhuǎn)(4) (3) Work=Work+

18、Allocationi; Finishi=true; 轉(zhuǎn)(2) (4) 若對所有i, Finishi=true, 則系統(tǒng)處于安全狀態(tài)(zhungti)，否則處于不安全狀態(tài)(zhungti)第28頁/共46頁第二十八頁，共47頁。292021-12-15銀行家算法(sun f)示例(1) 設(shè)系統(tǒng)有五個進(jìn)程P0,P1,P2,P3,P4和三類資源A, B, C，每類資源分別有10、5、7，在T0時刻(shk)資源分配情況如圖第29頁/共46頁第二十九頁，共47頁。302021-12-15銀行家算法(sun f)示例(2) T0時刻可以(ky)找到一個安全序列P1,P3,P4,P2,P0，系統(tǒng)是安全的

19、： （T0時刻安全性檢查）第30頁/共46頁第三十頁，共47頁。312021-12-15銀行家算法(sun f)示例(3) T0時刻，P1發(fā)出請求Request(1,0,2)，執(zhí)行(zhxng)銀行家算法第31頁/共46頁第三十一頁，共47頁。322021-12-15銀行家算法(sun f)示例(4) 可以找到一個安全序列p1,p3,p4,p0,p2系統(tǒng)是安全的，可以將P1的請求分配給它。執(zhí)行(zhxng)安全性算法第32頁/共46頁第三十二頁，共47頁。332021-12-15銀行家算法(sun f)示例(5) P4發(fā)出請求Request(3, 3, 0), 執(zhí)行(zhxng)銀行家算法 A

20、vailable=(2, 3, 0)不能通過算法(sun f)第2步（ RequestiAvailable ），所以P4等待。第33頁/共46頁第三十三頁，共47頁。342021-12-15銀行家算法(sun f)示例(5) P0請求(qngqi)資源Request（0，2，0），執(zhí)行銀行家算法 進(jìn)行安全性檢查：Available(2,1,0)已不能滿足任何進(jìn)程需要，所以系統(tǒng)(xtng)進(jìn)入不安全狀態(tài)，P0的請求不能分配第34頁/共46頁第三十四頁，共47頁。352021-12-15死鎖檢測(jin c) 允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生;一旦死鎖發(fā)生則采取專門的措

21、施，解除死鎖并以最小的代價恢復(fù)操作系統(tǒng)運行檢測(jin c)時機當(dāng)進(jìn)程等待時檢測(jin c)死鎖,其缺點是系統(tǒng)的開銷大定時檢測(jin c)系統(tǒng)資源利用率下降時檢測(jin c)死鎖死鎖的檢測(jin c)和解除第35頁/共46頁第三十五頁，共47頁。362021-12-15進(jìn)程(jnchng)-(jnchng)-資源分配圖PRAGPRAG 構(gòu)成 二元組G=（V，E） V：結(jié)點集，分為P，R兩部分 P=p1,p2,pn R=r1,r2,rm E：邊的集合，其元素為有序二元組或 表示法 資源類：用方框(fn kun)表示 資源實例：用方框(fn kun)中的黑圓點（圈）表示 進(jìn)程： 用圓圈中加

22、進(jìn)程名表示 分配邊：資源實例進(jìn)程的一條有向邊 請求邊：進(jìn)程資源類的一條有向邊第36頁/共46頁第三十六頁，共47頁。372021-12-15資源分配圖示例(shl)第37頁/共46頁第三十七頁，共47頁。382021-12-15死鎖定理(dngl)(dngl)（1 1） 如果進(jìn)程-資源分配圖中無環(huán)路，則此時系統(tǒng)(xtng)沒有發(fā)生死鎖。 如果進(jìn)程-資源分配圖中有環(huán)路，且每個資源類中僅有一個資源，則系統(tǒng)(xtng)中發(fā)生了死鎖，此時，環(huán)路是系統(tǒng)(xtng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程。例 如果進(jìn)程-資源分配圖中有環(huán)路，且涉及的資源類中有多個資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件

23、而不是充分條件。例第38頁/共46頁第三十八頁，共47頁。392021-12-15有環(huán)有死鎖P1P2R1R2第39頁/共46頁第三十九頁，共47頁。402021-12-15有環(huán)有死鎖第40頁/共46頁第四十頁，共47頁。412021-12-15有環(huán)無死鎖第41頁/共46頁第四十一頁，共47頁。422021-12-15死鎖定理(dngl)(dngl)（2 2） 資源分配圖簡化 （1）找出所有只有分配邊的非孤立點進(jìn)程結(jié)點， 去掉分配邊，將其變?yōu)楣铝⒔Y(jié)點 （2）找一個非孤立點進(jìn)程結(jié)點Pi，Pi的請求邊均能立即滿足。 （3）若找到了這樣的Pi，則將與Pi相連的邊全部(qunb)刪去（包括分配邊），轉(zhuǎn)（2） 若所有進(jìn)程結(jié)點成為孤立結(jié)點，稱該圖是可完全簡化的，否