版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、 第四章 死 鎖操作系統(tǒng)課程組 第四章 死 鎖操作系統(tǒng)課程組內(nèi)容回顧UNIX進程模型進程結(jié)構(gòu):proc結(jié)構(gòu),數(shù)據(jù)段,正文段。進程狀態(tài)調(diào)度算法:動態(tài)優(yōu)先級調(diào)度算法。進程創(chuàng)建與終止:fork(), exit()。進程通信:pipe; sleep, wakeup; wait, exit。死鎖2內(nèi)容回顧UNIX進程模型2一、什么是死鎖?死鎖(deadlock)定義:在多道程序中,由于多個并發(fā)進程共享系統(tǒng)的資源,如果使用不當(dāng)可能會造成一種僵局,即當(dāng)某個進程提出資源的使用請求后,使得系統(tǒng)中一些進程處于無休止的阻塞狀態(tài),在無外力的作用下,這些進程將無法繼續(xù)進行下去,這就是死鎖。3一、什么是死鎖?死鎖(dea
2、dlock)定義:在多道程序中,二、為什么會產(chǎn)生死鎖?產(chǎn)生死鎖的環(huán)境多道程序設(shè)計技術(shù)多個并發(fā)進程資源共享(獨占)沒有外力可以借助使用不當(dāng)造成的死鎖示例P、V操作不當(dāng)進程T1:while(true) 啟動讀卡機; 送卡片到緩沖區(qū); P(S2); V(S1);進程T2:while(true) P(S1); 從緩沖區(qū)取卡片; V(S2);semaphore s1,s2;s1=0; s2 = 0;4二、為什么會產(chǎn)生死鎖?產(chǎn)生死鎖的環(huán)境進程T1:進程T2:se二、為什么會產(chǎn)生死鎖?進程申請順序不當(dāng)同類資源分配不當(dāng)123456進程1進程2進程312345675二、為什么會產(chǎn)生死鎖?進程申請順序不當(dāng)1234
3、56進程1進程二、為什么會產(chǎn)生死鎖?進程通信不當(dāng)資源的類型獨占資源 VS 非獨占資源永久性資源 VS 臨時性資源獨占資源分類可剝奪式資源不可剝奪式資源T1T3T2S3S1S26二、為什么會產(chǎn)生死鎖?進程通信不當(dāng)T1T3T2S3S1S26二、為什么會產(chǎn)生死鎖?必要條件(Coffman 1971年指出)資源互斥使用(資源獨占)非剝奪控制(不可強占)零散請求循環(huán)等待破壞其中任何一個條件,就可一防止死鎖的發(fā)生。7二、為什么會產(chǎn)生死鎖?必要條件(Coffman 1971年指三、如何解決死鎖問題?死鎖的危害輕則系統(tǒng)資源利用率嚴(yán)重下降,重則系統(tǒng)崩潰。解決死鎖的策略置之不理法鴕鳥政策優(yōu)點:簡單,簡化系統(tǒng)設(shè)計,
4、節(jié)約成本。缺點:安全性欠佳。8三、如何解決死鎖問題?死鎖的危害優(yōu)點:簡單,簡化系統(tǒng)設(shè)計,節(jié)三、如何解決死鎖問題?積極防御法不讓死鎖發(fā)生思想:以積極的遏制為出發(fā)點。手段:破壞產(chǎn)生死鎖的必要條件。分類:靜態(tài)策略:進程創(chuàng)建時就由系統(tǒng)分配了所有需要的資源,然后才執(zhí)行,并且以后沒有資源申請要求。缺點:系統(tǒng)效率低,并發(fā)性下降,資源浪費嚴(yán)重。動態(tài)策略:執(zhí)行時動態(tài)改變資源分配策略。缺點:實現(xiàn)復(fù)雜。優(yōu)點:靈活,資源利用率高。9三、如何解決死鎖問題?積極防御法不讓死鎖發(fā)生9三、如何解決死鎖問題?事后處理法讓死鎖發(fā)生,事后處理提出原因:預(yù)防策略雖然可以杜絕死鎖發(fā)生,但是它提出的策略可能會或多或少影響到系統(tǒng)效率。思想
5、:可以容忍死鎖的發(fā)生,事后處理。優(yōu)點:靈活,效率高。10三、如何解決死鎖問題?事后處理法讓死鎖發(fā)生,事后處理10四、死鎖的預(yù)防破壞死鎖產(chǎn)生的必要條件破壞互斥條件SPOOLingP1P2P3執(zhí)行上無先后順序剩余票數(shù)n=3P1P2P3執(zhí)行上有先后順序局限:破壞“互斥”比較困難,而且對很多資源行不通。11四、死鎖的預(yù)防破壞死鎖產(chǎn)生的必要條件SPOOLingP1P2四、死鎖的預(yù)防破壞不可剝奪條件思想:允許進程還未執(zhí)行完成時釋放已經(jīng)占有的資源。方法:已經(jīng)占有部分資源,還需要資源,如果得不到滿足,則釋放自己所占有的所有資源,以后再申請。正在使用資源,有高優(yōu)先級的進程請求相同資源,則低優(yōu)先級進程放棄資源。局
6、限:實現(xiàn)困難,為了恢復(fù)現(xiàn)場需要耗費很多時間和空間。因此只適合類似CPU、存儲器這樣的資源。12四、死鎖的預(yù)防破壞不可剝奪條件12四、死鎖的預(yù)防破壞零散請求條件常常采用靜態(tài)策略:進程創(chuàng)建時就由系統(tǒng)分配了所有需要的資源,然后才執(zhí)行,并且以后沒有資源申請要求,進程執(zhí)行完后,釋放資源。缺點:系統(tǒng)效率低,并發(fā)性下降,資源浪費嚴(yán)重。破壞循環(huán)等待條件方法:給資源編號,進程必須按序申請資源。P1P5124712345673334567P1P5P2P3P413四、死鎖的預(yù)防破壞零散請求條件P1P512471234567四、死鎖的預(yù)防局限:資源編號困難:盡管資源的按序分配方法消除了死鎖的問題,但給資源編號很困難,
7、很難滿足每一個進程的要求。資源的編號很難和進程申請資源的順序一致:資源順序分配法是按資源編號申請資源,可能與實際使用資源的順序不一致,使得一些先申請的資源因暫時不用,而長時間閑置,降低了系統(tǒng)資源利用率。結(jié)論死鎖的預(yù)防是以破壞死鎖產(chǎn)生的必要條件為基本方法,從而防止死鎖發(fā)生的。其中由于對資源的申請加上了諸多的限制,因此這種策略雖有一定的效果,但其資源的利用率和效率比較低,很難令人滿意。14四、死鎖的預(yù)防局限:14五、死鎖的避免思想允許死鎖產(chǎn)生的條件存在,但通過動態(tài)的、明智的選擇在分配資源之前,系統(tǒng)判斷假若滿足進程的要求是否會發(fā)生死鎖,如果會,資源就不予分配,從而確保永遠不會到達死鎖點,避免死鎖的發(fā)
8、生。優(yōu)點:比預(yù)防策略更為靈活實用,允許更多的并發(fā),其資源利用率和效率也更高。15五、死鎖的避免思想15五、死鎖的避免系統(tǒng)的狀態(tài)安全狀態(tài)不安全狀態(tài)死鎖安全狀態(tài):指在某個時刻,當(dāng)多個進程動態(tài)的申請資源時,如果存在一種順序,使得系統(tǒng)按照這種順序逐次地為每個進程分配所需資源后每個進程都可以在最終得到最大需求量后,依次順利地完成。避免死鎖的關(guān)鍵就是:讓系統(tǒng)在動態(tài)分配資源的過程中,不要進入不安全狀態(tài)。16五、死鎖的避免系統(tǒng)的狀態(tài)安全狀態(tài)不安全狀態(tài)死鎖安全狀態(tài):指在五、死鎖的避免單銀行家算法(Bankers Algorithm)1965年由Dijkstra為T.H.E系統(tǒng)設(shè)計基本思想:借用了銀行借貸系統(tǒng)的分
9、配策略?;谶@樣一些規(guī)則:客戶銀行1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金3、客戶申請的貸款數(shù)量不超過它自己擁有的 最大值時,銀行要盡量滿足客戶需求進程資源操作系統(tǒng)17五、死鎖的避免單銀行家算法(Bankers Algorit客戶abcd舉例:假設(shè)一個銀行擁有資金數(shù)量為10(單位省略),現(xiàn)在有4個客戶a, b, c, d要來貸款,所需最大資金需求量為8,5,6,7,為方便期間我們用圖形表示如下。已用資金最大需求仍需資金五、死鎖的避免088055066077銀行剩余資金10初始狀態(tài)客戶已用資金最大需求仍需資金abcd187253165275銀行剩余資金4狀態(tài)1Q:如何
10、分配才能保證銀行資金能夠順利周轉(zhuǎn)?18客戶abcd舉例:假設(shè)一個銀行擁有資金數(shù)量為10(單位省略)五、死鎖的避免客戶已用資金最大需求仍需資金abcd187550165275銀行剩余資金1狀態(tài)2客戶已用資金最大需求仍需資金abcd187165275銀行剩余資金6狀態(tài)3客戶已用資金最大需求仍需資金abcd187660275銀行剩余資金1狀態(tài)4客戶已用資金最大需求仍需資金abcd187275銀行剩余資金7狀態(tài)519五、死鎖的避免客戶已用資金最大需求仍需資金abcd18755五、死鎖的避免客戶已用資金最大需求仍需資金abcd880275銀行剩余資金0狀態(tài)6客戶已用資金最大需求仍需資金abcd275銀行
11、剩余資金8狀態(tài)7客戶已用資金最大需求仍需資金abcd770銀行剩余資金3狀態(tài)8分配策略:bcad20五、死鎖的避免客戶已用資金最大需求仍需資金abcd880五、死鎖的避免算法流程21五、死鎖的避免算法流程21五、死鎖的避免以上討論的是單銀行家算法只涉及到了一種資源,實際中資源的種類是多樣的,一個進程往往需要申請多個資源才能完成工作。解決這一問題需要使用多銀行家算法。22五、死鎖的避免以上討論的是單銀行家算法只涉及到了一種資源五、死鎖的避免多項資源銀行家算法舉例:系統(tǒng)中有以下資源:5臺打印機,7個手寫板,8臺掃描儀,9個讀卡器,共有5個進程T1、T2、T3、T4、T5共享這些資源。各進程所需最大
12、資源量和當(dāng)前各進程請求資源情況如下:各進程所需最大資源量當(dāng)前各進程請求資源23五、死鎖的避免多項資源銀行家算法各進程所需最大資源量當(dāng)前各進1、sum向量:表示系統(tǒng)資源總量sum = (5,7,8,9)2、allocation向量:表示當(dāng)前系統(tǒng)已分配資源allocation =(3,5,7,7) 3、available向量:表示系統(tǒng)剩余資源available = sum allocation =(2,2,1,2) 4、claim(i)向量:表示第i個進程還需申請資源數(shù)claim(i) = sum(i) allocation(i)五、死鎖的避免為方面討論,我們用向量來表示資源分配及占用情況:sum
13、allocationclaim(i)241、sum向量:表示系統(tǒng)資源總量五、死鎖的避免為方面討論,我五、死鎖的避免步驟:比較claim(i)和available向量,尋找滿足下列關(guān)系的進程claim(i) availableavailable = (2,2,1,2)allocationavailable = (2,5,5,2)25五、死鎖的避免步驟:available = (2,2,1,2五、死鎖的避免available = (2,6,7,3)allocationavailable = (3,7,7,5)allocation26五、死鎖的避免available = (2,6,7,3)al五、死
14、鎖的避免available = (5,7,7,6)allocationallocationavailable = (5,7,8,9)27五、死鎖的避免available = (5,7,7,6)al五、死鎖的避免28五、死鎖的避免28六、死鎖的檢測和解除死鎖的檢測檢測工具資源分配圖定義:是描述進程申請資源和資源分配情況的關(guān)系模型圖。表示系統(tǒng)中某個時刻進程對資源的申請和占有情況。示例:規(guī)則:(1)圓表示一個進程;(2)方塊表示一個資源類,其中的圓點表示該類型資源中的單個資源;(3)從資源指向進程的箭頭表示資源被分配給了這個進程;(4)從進程指向資源的箭頭表示進程申請一個這類資源;29六、死鎖的檢測
15、和解除死鎖的檢測規(guī)則:29六、死鎖的檢測和解除一張合理的資源分配圖應(yīng)當(dāng)滿足如下條件設(shè)資源類Rj有資源Wj個,用|(Rj, Pi)|表示Rj分配給進程Pi的資源個數(shù);用|(Pi, Rj)|表示進程Pi申請Rj資源的資源個數(shù)。1、資源Rj分配給各進程的資源數(shù)目不能大于Wj,即:2、任何一個進程Pi對某類資源Rj的申請量和已分配數(shù)量之和,不應(yīng)大于該類資源的總數(shù)Wj,即:30六、死鎖的檢測和解除一張合理的資源分配圖應(yīng)當(dāng)滿足如下條件1、六、死鎖的檢測和解除檢測方法化簡算法資源分配圖中的所有進程如果都能化簡成孤立結(jié)點,則這個資源圖就是可完全化簡的(completely reducible);反之,就是不可
16、完全化簡的(irrreducible)。死鎖定理:如果一個系統(tǒng)狀態(tài)為死鎖狀態(tài),當(dāng)且僅當(dāng)資源分配圖是不可完全化簡的。也即,如果資源圖中所有的進程都成為孤立結(jié)點,則系統(tǒng)不會死鎖;否則系統(tǒng)狀態(tài)為死鎖狀態(tài)。31六、死鎖的檢測和解除檢測方法化簡算法資源分配圖中的所有進六、死鎖的檢測和解除舉例結(jié)論:系統(tǒng)不會發(fā)生死鎖。32六、死鎖的檢測和解除舉例結(jié)論:系統(tǒng)不會發(fā)生死鎖。32六、死鎖的檢測和解除臨時資源的死鎖檢測臨時性資源:即可消耗的資源。如信號、消息、郵件等。特點:沒有固定數(shù)目;不需要釋放。一般的資源分配圖無法清楚的描述33六、死鎖的檢測和解除臨時資源的死鎖檢測一般的資源分配圖33六、死鎖的檢測和解除臨時性
17、資源分配的表述方式重定義的資源分配圖定義:圓表示一個進程;方塊表示一個資源類,其中的圓點表示該類型資源中的單個資源;由資源類指向進程的箭頭表示該進程產(chǎn)生這種資源,一個箭頭可表示產(chǎn)生一到多個資源,每個資源類至少有一個生產(chǎn)者進程;由進程指向資源的箭頭表示該進程申請這種資源,一個箭頭只表示申請一個資源。34六、死鎖的檢測和解除臨時性資源分配的表述方式重定義的資源六、死鎖的檢測和解除死鎖判斷標(biāo)準(zhǔn)分析:一個進程死鎖意味著永久被阻塞。對于臨時性資源來講,它有生產(chǎn)者,生產(chǎn)者會源源不斷的生產(chǎn)資源,因此只要生產(chǎn)者進程不被阻塞,可以認(rèn)為資源最終一定是充分的,可以滿足各消費進程的需要。需要的資源可以滿足則進程一定不
18、會死鎖。結(jié)論:判斷系統(tǒng)是否死鎖的關(guān)鍵在于判斷生產(chǎn)者進程的狀態(tài),若生產(chǎn)者進程不被阻塞,則可以認(rèn)為它總會生產(chǎn)出該類資源,也就是說,某類資源的生產(chǎn)者進程只要不被阻塞,申請這類資源的所有申請者進程都可以得到滿足。35六、死鎖的檢測和解除死鎖判斷標(biāo)準(zhǔn)35六、死鎖的檢測和解除檢測方法化簡方法:從那些沒有阻塞的進程入手,刪除那些沒有阻塞的進程的請求邊,并使資源類中資源數(shù)(圖中黑點的數(shù)目)減1。重復(fù)以上步驟直至:a. 圖中所有的請求邊都已經(jīng)刪除,則不會死鎖 b. 圖中仍然存在請求邊但無法再化簡,系統(tǒng)死鎖。36六、死鎖的檢測和解除檢測方法化簡36六、死鎖的檢測和解除死鎖的解除重新啟動:這是一種常用但比較粗暴的方
19、法,雖然實現(xiàn)簡單,但會使之前的工作全部白費,造成很大的損失和浪費。撤消進程:死鎖發(fā)生時,系統(tǒng)撤消造成死鎖的進程,解除死鎖。一次性撤消所有的死鎖進程。損失較大。逐個撤消,分別收回資源。具體做法:系統(tǒng)可以先撤消那些優(yōu)先級低的、已占有資源少或已運行時間短的、還需運行時間較長的進程,盡量減少系統(tǒng)的損失。 37六、死鎖的檢測和解除死鎖的解除37六、死鎖的檢測和解除剝奪資源:死鎖時,系統(tǒng)保留死鎖進程,只剝奪死鎖進程占有的資源,直到解除死鎖。選擇被剝奪資源進程的方法和選擇被撤消進程相同。進程回退:死鎖時,系統(tǒng)可以根據(jù)保留的歷史信息,讓死鎖的進程從當(dāng)前狀態(tài)向后退回到某種狀態(tài),直到死鎖解除。實現(xiàn)方法:可以通過結(jié)
20、合檢查點或回退(checkpoint/Rollback)機制實現(xiàn)。進程某一時刻的瞬間狀態(tài)叫做檢查點,可以定期設(shè)置檢查點。系統(tǒng)保存所有的檢查點。一旦系統(tǒng)檢查到有某個進程卷入了死鎖,該進程就會被終止,剝奪它占有的所有資源。然后,系統(tǒng)查看保存的檢查點信息,重新建立該進程的狀態(tài),從上次檢查點的位置重新執(zhí)行。目前發(fā)展已比較成熟,廣泛用于DBMS中。38六、死鎖的檢測和解除剝奪資源:死鎖時,系統(tǒng)保留死鎖進程,只剝六、死鎖的檢測和解除死鎖檢測舉例例1:以下有兩個資源分配圖,圖a表示的是永久性資源,圖b表示臨時性資源,請分別化簡并說明是否會發(fā)生死鎖。(a)(b)39六、死鎖的檢測和解除死鎖檢測舉例(a)(b)39六、死鎖的檢測和解除(a)Step1.檢測有無環(huán)路Setp2.檢測環(huán)路中每個資源類中是否只有一個資源Step3.在環(huán)路中查找非阻塞也非獨立的進程結(jié)論:此資源分配圖無法化簡,因此必定死鎖。40六、死鎖的檢測和解除(a)Step1.檢測有無環(huán)路Setp2六、死鎖的檢測和解除(b)查找非阻塞進程結(jié)論:會發(fā)生死鎖41六、死鎖的檢測和解除(b)查找非阻塞進程結(jié)論:會發(fā)生死鎖41六、死鎖的檢測和解除例2:某
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 終止調(diào)解協(xié)議書
- 收藏行業(yè)打架私了協(xié)議書
- 學(xué)校體育場照明工程承包協(xié)議
- 一次性土地使用權(quán)賠償協(xié)議
- 專科醫(yī)院醫(yī)師勞動合同范本
- 攝影背景板租賃合同范本
- 木質(zhì)戶外用品制作合同
- 居民小區(qū)保安員招聘合同范本
- 2024知名企業(yè)品牌形象代言合同
- 2024甲方與乙方就智能物流系統(tǒng)建設(shè)與運營的合作合同
- (八省聯(lián)考)2025年高考綜合改革適應(yīng)性演練 物理試卷合集(含答案逐題解析)
- 2025年安徽銅陵市公安局第二批輔警招聘158人歷年高頻重點提升(共500題)附帶答案詳解
- 車間修繕合同模板
- 商會年會策劃方案范例(3篇)
- SQE年終總結(jié)報告
- 《化學(xué)實驗室安全》課程教學(xué)大綱
- 2024年人教版初二地理上冊期末考試卷(附答案)
- 2024文旅景區(qū)秋季稻田豐收節(jié)稻花香里 說豐年主題活動策劃方案
- 高低壓供配電設(shè)備檢查和檢修保養(yǎng)合同3篇
- 2023-2024學(xué)年福建省廈門市八年級(上)期末物理試卷
- (正式版)JBT 9229-2024 剪叉式升降工作平臺
評論
0/150
提交評論