計算機(jī)操作系統(tǒng)第2章并發(fā)與進(jìn)程-死鎖

計算機(jī)操作系統(tǒng)主要內(nèi)容調(diào)度

scheduling死鎖deadlock同步

synchronization進(jìn)程

process操作系統(tǒng)系統(tǒng)原理2.11

進(jìn)程死鎖進(jìn)程的并發(fā)控制不僅要控制若干進(jìn)程的同步與互斥，確保進(jìn)程之間正常通信，還需要解決進(jìn)程死鎖問題。一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個系統(tǒng)將處于癱瘓狀態(tài)，造成系統(tǒng)“死機(jī)”。操作系統(tǒng)系統(tǒng)原理2.11

進(jìn)程死鎖生活中的死鎖現(xiàn)象操作系統(tǒng)系統(tǒng)原理2.11

進(jìn)程死鎖進(jìn)程死鎖現(xiàn)象P1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);操作系統(tǒng)系統(tǒng)原理2.11

進(jìn)程死鎖死鎖（Deadlock）概念多個進(jìn)程因?yàn)楦偁庂Y源或執(zhí)行時推進(jìn)的順序不當(dāng)，或相互通信出現(xiàn)永久阻塞現(xiàn)象，如果沒有外力作用，這種現(xiàn)象將永遠(yuǎn)保持下去。產(chǎn)生死鎖的原因資源不足導(dǎo)致的資源競爭多個進(jìn)程所共享的資源不足，引起它們對資源的競爭而產(chǎn)生死鎖。并發(fā)執(zhí)行的順序不當(dāng)進(jìn)程運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，而導(dǎo)致進(jìn)程死鎖。操作系統(tǒng)系統(tǒng)原理2.11

進(jìn)程死鎖進(jìn)程死鎖現(xiàn)象PP(A);P(B);...V(A);V(B);QP(B);P(A);...V(B);V(A);操作系統(tǒng)系統(tǒng)原理82.11.1

引起死鎖的原因系統(tǒng)模型資源（R1,R2,...,Rm）

CPU,memory,I/Odevices資源Ri擁有的實(shí)例數(shù)Wi（instance）進(jìn)程使用資源的方式請求（request）占用/使用（use）釋放（release）操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源剝奪性質(zhì)可剝奪性資源非剝奪性資源存在時間可重用資源可消耗資源操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分類（剝奪性質(zhì)）可剝奪性資源指某進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪。如CPU、主存等。非剝奪性資源當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放。如打印機(jī)、磁帶機(jī)等。操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因競爭非剝奪性資源可能會導(dǎo)致死鎖操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分類（存在時間）可重用資源（永久性資源）一次只能供一個進(jìn)程安全地使用,不會由于使用而耗盡。例:CPU、I/O通道、主存和輔存、設(shè)備、文件、數(shù)據(jù)庫、信號量等數(shù)據(jù)結(jié)構(gòu)。可消耗資源（臨時性資源）可以創(chuàng)建并且可以銷毀的資源。數(shù)目沒有限制,當(dāng)一個進(jìn)程得到一個可消費(fèi)資源時,這個資源就不再存在了。例:中斷、信號、消息、I/O緩沖區(qū)中的信息。操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因競爭可消耗資源可能會導(dǎo)致死鎖P1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分配圖RAGResource-AllocationGraph進(jìn)程P={P1,P2,…,Pn}資源R={R1,R2,…,Rm}資源請求邊（request）Pi

Rj資源分配邊（assignment）Rj

Pi操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分配圖的表示進(jìn)程

具有4個實(shí)例的資源進(jìn)程Pi請求資源Rj進(jìn)程Pi已獲取資源RjPiRjPiRj操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分配圖實(shí)例操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分配圖實(shí)例——死鎖操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因資源分配圖實(shí)例——存在環(huán)但不會導(dǎo)致死鎖操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因產(chǎn)生死鎖的必要條件循環(huán)等待

CircularWait互斥

MutualExclusion占有且等待

HoldandWait非剝奪

NonPreemption操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因互斥條件指進(jìn)程對所分配到的資源進(jìn)行排它性使用。如果此時還有其它進(jìn)程申請?jiān)撡Y源，則它只能阻塞，直至占有該資源的進(jìn)程釋放。占有且等待（請求和保持條件）進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它進(jìn)程占有，此時請求進(jìn)程阻塞，但又對已經(jīng)獲得的其它資源保持不放。操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因非搶占（非剝奪）條件進(jìn)程已獲得的資源，在未使用完之前,不能被剝奪，只能在使用完時由自己釋放。循環(huán)等待條件在發(fā)生死鎖時,必然存在一個進(jìn)程-資源的封閉的環(huán)形鏈。操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因循環(huán)等待條件示例R1P1占用P2R2占用申請申請死鎖操作系統(tǒng)系統(tǒng)原理2.11.1

引起死鎖的原因互斥、占有且等待、非剝奪條件是死鎖產(chǎn)生的必要條件，但不是充分條件。循環(huán)等待條件實(shí)際上是互斥、占有且等待、非剝奪條件的可能導(dǎo)致的結(jié)果。只要系統(tǒng)出現(xiàn)循環(huán)等待，則一定出現(xiàn)死鎖?；コ狻⒄加星业却?、非剝奪條件和循環(huán)等待條件構(gòu)成了死鎖產(chǎn)生的充分必要條件。操作系統(tǒng)系統(tǒng)原理2.11.2

解決死鎖的方法解決死鎖的基本方法預(yù)防

(Prevention)避免

(Avoidance)忽略（Ignorance）檢測解除

(Detection/Recovery)操作系統(tǒng)系統(tǒng)原理2.11.2

解決死鎖的方法解決死鎖的基本方法預(yù)防死鎖通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預(yù)防發(fā)生死鎖。避免死鎖在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。檢測死鎖并解除死鎖允許死鎖發(fā)生，系統(tǒng)定期或不定期檢測是否有死鎖發(fā)生。若檢測到死鎖，則解除死鎖。忽略死鎖

鴕鳥策略操作系統(tǒng)系統(tǒng)原理2.11.3

預(yù)防死鎖預(yù)防死鎖在申請資源時，添加限制條件，以此來破壞產(chǎn)生死鎖的條件。互斥條件

由資源的固有特性所決定，不能被破壞。破壞占有和等待條件進(jìn)程開始運(yùn)行前一次性地申請全部資源，啟動后不再申請。優(yōu)點(diǎn):簡單、易于實(shí)現(xiàn)、安全缺點(diǎn):無法預(yù)知所需資源的全集進(jìn)程可能被阻塞很長時間，等待資源，發(fā)生饑餓資源嚴(yán)重浪費(fèi)操作系統(tǒng)系統(tǒng)原理2.11.3

預(yù)防死鎖放棄“非搶占”條件

一個已經(jīng)保持了某些資源的進(jìn)程,當(dāng)它再提出新的資源請求而不能立即得到滿足時,必須釋放它已經(jīng)保持的所有資源,待以后需要時再重新申請。放棄“非搶占”條件的前提資源的狀態(tài)可保存和恢復(fù)，如CPU寄存器、內(nèi)存空間，不適用于打印機(jī)、磁帶機(jī)。放棄“非搶占”條件的缺點(diǎn)實(shí)現(xiàn)復(fù)雜、代價大,反復(fù)申請/釋放資源,周轉(zhuǎn)時間長，系統(tǒng)吞吐量低。操作系統(tǒng)系統(tǒng)原理2.11.3

預(yù)防死鎖摒棄“環(huán)路等待”條件系統(tǒng)把所有資源按類型進(jìn)行線性排隊(duì)

如輸入機(jī)=1，打印機(jī)=2，磁帶機(jī)=3，磁盤機(jī)=4;所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的順序提出,保證任何時刻的資源分配圖不出現(xiàn)環(huán)路。即：如果一個進(jìn)程已經(jīng)分配了R類型的資源，它接下來請求的資源只能是那些排在R類型之后的資源操作系統(tǒng)系統(tǒng)原理2.11.3

預(yù)防死鎖摒棄“環(huán)路等待”方法的問題資源變化

資源序號要穩(wěn)定，難以處理資源變化情況。資源浪費(fèi)

如某進(jìn)程只用第一個和最后一個資源程序設(shè)計

需要考慮申請順序，編寫困難。操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件。在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個資源申請進(jìn)行檢查，并根據(jù)檢查結(jié)果決定是否分配資源。若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配（阻塞），否則予以分配——動態(tài)檢查。防止系統(tǒng)進(jìn)入不安全狀態(tài),從而避免發(fā)生死鎖。操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全序列

一個進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與進(jìn)程P1、P2、…、Pi-1當(dāng)前占有資源量之和。安全狀態(tài)

存在安全序列的狀態(tài)。操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全狀態(tài)示例

下圖中是否存在安全序列？

進(jìn)程最大需求已分配可用P11053P242P392安全序列：P2P1P3安全序列是否唯一？安全狀態(tài)一定沒有死鎖發(fā)生？操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖不安全序列

不存在安全序列的狀態(tài)。安全狀態(tài)

無死鎖：死鎖

不安全狀態(tài)不安全狀態(tài)一定導(dǎo)致死鎖么？操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全——不安全的轉(zhuǎn)換：不按安全序列分配資源

進(jìn)程最大需求已分配可用P11052P242P393進(jìn)程最大需求已分配可用P11053P242P392再為P3分配1個資源操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全狀態(tài)vs.

不安全狀態(tài)若系統(tǒng)處于安全狀態(tài)，且按照某個安全序列分配資源，可以保證系統(tǒng)不會出現(xiàn)死鎖。并非所有不安全狀態(tài)都是死鎖狀態(tài)。當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)以后，便可能進(jìn)入死鎖狀態(tài)。避免死鎖的實(shí)質(zhì)在于：

如何避免系統(tǒng)進(jìn)入不安全狀態(tài)操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖銀行家算法（Banker’sAlgorithm）Dijkstra,1965設(shè)計思想：當(dāng)用戶申請一組資源時，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分配這些資源；否則，暫時不分配，阻塞進(jìn)程。

按安全序列為進(jìn)程分配資源操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)設(shè)系統(tǒng)中有m種不同資源,n個進(jìn)程Available向量:系統(tǒng)中尚未分配的每種資源的總量Available[j]:尚未分配的資源j的數(shù)量Max矩陣:各個進(jìn)程對每種資源的最大需求量(進(jìn)程事先聲明)Max[i,j](Claim[i,j]):進(jìn)程i對資源j的最大需求量Allocation矩陣:當(dāng)前資源分配狀況Allocation[i,j]:進(jìn)程i獲得的資源j的數(shù)量Need矩陣:每個進(jìn)程還需要的剩余資源的數(shù)量Need[i,j]:進(jìn)程i尚需的資源j的數(shù)量操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖

各數(shù)據(jù)間的關(guān)系

操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全性算法設(shè)Work和Finish分別是長度為m和n的向量，按如下方式進(jìn)行初始化:Work=Available；Finish[i]=falsefori=1,2,…,n.查找這樣的i使其滿足:Finish[i]=false

且

Need[i]

Work若未找到，轉(zhuǎn)第④步.Work=Work+Allocation[i];Finish[i]=True；返回第②步若對所有的i,Finish[i]==True成立，則系統(tǒng)處于安全狀態(tài)；反之，則系統(tǒng)處于不安全狀態(tài)。操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖安全性算法示例假定系統(tǒng)中有4個進(jìn)程P1、P2、P3和P4；3類資源R1、R2和R3,其資源數(shù)量分別為9、3和6。T0時刻的資源分配情況如下，試問是否存在安全序列？MaxAllocationR1R2R3R1R2R3P1322100P2613612P3314211P4422002操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613612001P3314211103P4422002420WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueT0時刻的資源分配表T0時刻的安全序列WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueWorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueP4723420002725TrueWorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueP4723420002725TrueP3725103211936True操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖

銀行家算法：Requesti為進(jìn)程Pi的請求向量

若Requesti≤Needi，則轉(zhuǎn)向步驟②；否則，出錯退出。若Requesti≤Available，則轉(zhuǎn)向步驟③；否則，Pi阻塞。試探性地為Pi分配資源，并修改相關(guān)數(shù)據(jù)結(jié)構(gòu)：Available:＝Available一RequestiAllocation:＝Allocation＋RequestiNeedi:=Needi一Requesti執(zhí)行安全性算法檢查

若處于安全狀態(tài)，則分配；否則，試分配失效，恢復(fù)試分配前狀態(tài)，Pi阻塞。操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖銀行家算法示例1假定系統(tǒng)中有4個進(jìn)程P1、P2、P3和P4；3類資源R1、R2和R3,其資源數(shù)量分別為9、3和6。T0時刻的資源分配情況如下，此時若進(jìn)程P4的請求向量為<1，2，0>。若采用銀行家算法，可否分配資源？MaxAllocationR1R2R3R1R2R3P1322100P2613612P3314211P4422002操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖計算可用資源向量Available=(0,1,1)判斷

Request4=(1,2,0)Need4=(4,2,0)Request4<Need4

Request4<Available不成立

P4請求的資源不能分配！操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖銀行家算法示例2假定系統(tǒng)中有4個進(jìn)程P1、P2、P3和P4；3類資源R1、R2和R3,其資源數(shù)量分別為9、3和6。T0時刻的資源分配情況如下，此時若進(jìn)程P1申請1個R3資源。若采用銀行家算法，可否分配資源？MaxAllocationR1R2R3R1R2R3P1322100P2613612P3314211P4422002操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖計算可用資源向量Available=(0,1,1)判斷

Request1=(0,0,1),Request1<Need1,Request1<Available嘗試分配

為P1分配1個R3后的資源分配表系統(tǒng)進(jìn)入不安全狀態(tài)，P1請求的資源不能分配！MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322101221010P2613612001P3314211103P4422002420操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖銀行家算法示例3假定系統(tǒng)中有4個進(jìn)程P1、P2、P3和P4；3類資源R1、R2和R3,其資源數(shù)量分別為9、3和6。T0時刻的資源分配情況如下，此時若進(jìn)程P4的請求向量為<0，1，0>。若采用銀行家算法，可否分配資源？MaxAllocationR1R2R3R1R2R3P1322100P2613612P3314211P4422002操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖計算可用資源向量Available=(0,1,1)判斷

Request4=(0,1,0),Request4<Need4,Request4<Available嘗試分配

為P4分配1個R2后的資源分配表MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222001P2613612001P3314211103P4422012410操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222001P2613612001P3314211103P4422012410WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2001001612613True安全性算法檢查為P4分配1個R2后的資源分配表WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2001001612613TrueP3613103211824TrueWorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2001001612613TrueP3613103211824TrueP4824410012836TrueWorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2001001612613TrueP3613103211824TrueP4824410012836TrueP1836222100936True操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖

銀行家算法的優(yōu)點(diǎn)比死鎖預(yù)防限制少無死鎖檢測方法中的資源剝奪,進(jìn)程重啟。銀行家算法的缺點(diǎn)預(yù)先必須聲明每個進(jìn)程需要的資源總量。進(jìn)程之間相互獨(dú)立，其執(zhí)行順序取決于系統(tǒng)安全，而非進(jìn)程間的同步要求。系統(tǒng)必須提供固定數(shù)量的資源供進(jìn)程使用。若系統(tǒng)占有資源，則不能讓其退出系統(tǒng)。操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖如果系統(tǒng)不愿意附加太多約束條件預(yù)防死鎖，也不希望系統(tǒng)額外開銷預(yù)測并避免死鎖，那么，只能允許死鎖出現(xiàn)，然后再解除它。系統(tǒng)需要利用某種方法來檢測死鎖——簡化資源分配圖。從死鎖狀態(tài)中恢復(fù)的方法。操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖死鎖檢測沒有任何預(yù)先限制措施資源分配時不檢查系統(tǒng)是否會進(jìn)入不安全狀態(tài)，被請求的資源都被授予給進(jìn)程系統(tǒng)可能出現(xiàn)死鎖檢測是否出現(xiàn)死鎖（執(zhí)行檢測算法）檢測時機(jī)在每個資源請求時都進(jìn)行：盡早地檢測，其缺點(diǎn)是系統(tǒng)的開銷大（CPU）定時檢測系統(tǒng)資源利用率下降時檢測死鎖操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖資源分配圖結(jié)點(diǎn)N分為兩個互斥的子集P和R進(jìn)程結(jié)點(diǎn)P={P1,P2,…,Pn}資源結(jié)點(diǎn)R={r1,r2,…,rn}

邊E中的任一個邊e∈E都連接著P中的一個結(jié)點(diǎn)和R中的一個結(jié)點(diǎn)

e={Pi,rj}表示進(jìn)程pi請求一個單位的rj資源e={rj,Pi}表示已把一個單位的資源rj分配給進(jìn)程Pi操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖資源分配圖示例P1P2r1r2申請分配申請分配分配分配操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖資源分配圖的化簡在資源分配圖中，找出其全部請求都能滿足的進(jìn)程節(jié)點(diǎn)Pi，消去Pi所有的請求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。重復(fù)步驟①，直至無法化簡為止。資源分配圖的化簡示例操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖可完全簡化圖能消去圖中所有的邊，使所有的進(jìn)程結(jié)點(diǎn)都成為孤立結(jié)點(diǎn)的資源分配圖。不可完全簡化圖不能通過任何過程使該圖完全簡化，則稱該資源分配圖是不可完全簡化圖。P1r1r2P2操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖死鎖定理

狀態(tài)S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件被稱為死鎖定理。P1r1r2P2P1r1r2P2操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)可用資源向量Available

表示m類資源中每一類資源的可用數(shù)目請求矩陣Request一個n×m矩陣，表示進(jìn)程當(dāng)前對各類資源的請求數(shù)目。分配矩陣Allocation一個n×m矩陣，表示某一時刻的資源分配情況。工作向量Work表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目。進(jìn)程向量L表示當(dāng)前已不占有資源的進(jìn)程的集合，各進(jìn)程滿足條件Allocationi=0操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖死鎖檢測流程操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖死鎖檢測偽碼work=availableL:={Li|alloci=0,reqi=0}(孤立進(jìn)程點(diǎn))ForallLinot∈LdoBegin Forallreqi<=workdo Begin Work=work+alloci L=Li∪L end EndDeadlock=~(L={p1…pn})操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖

死鎖的解除撤銷進(jìn)程資源剝奪進(jìn)程回退操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖

撤銷進(jìn)程終止所有的死鎖進(jìn)程

OS中常用方法一次只終止一個進(jìn)程直到取消死鎖循環(huán)為

基于某種最小代價原則選擇原則已消耗CPU時間最少到目前為止產(chǎn)生的輸出量最少預(yù)計剩余的時間最長目前為止分配的資源總量最少優(yōu)先級最低操作系統(tǒng)系統(tǒng)原理2.11.5

檢測并解除死鎖

資源剝奪：逐步從進(jìn)程中搶占資源給其它進(jìn)程，直到死鎖環(huán)被打破為止。選擇一個犧牲品：搶占哪些資源和哪個進(jìn)程，確定搶占順序以使代價最小。饑餓：確保資源不會總是從同一個進(jìn)程中被搶占進(jìn)程回退：把每個死鎖進(jìn)程備份到前面定義的某些檢查點(diǎn),并且重新啟動所有進(jìn)程－需要系統(tǒng)構(gòu)造重新運(yùn)行和重新啟動機(jī)制操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問題DinningPhilosopherProblem1965年，Dijkstra出了一道同步考試題：假設(shè)有五臺計算機(jī)都試圖訪問五份共享的磁帶驅(qū)動器。后來，這個問題被Hoare重新表述為哲學(xué)家就餐問題。這個問題可以用來解釋死鎖和資源耗盡。描述5個哲學(xué)家圍坐一張餐桌5只餐叉間隔擺放思考或進(jìn)餐進(jìn)餐時必須同時拿到兩邊的餐叉思考時將餐叉放回原處操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問題操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問題semaphorefork[5]={1,1,1,1,1};voidmain(){cobegin{philosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);}coend;}voidphilosopher(inti){while(true){think;//思考wait(fork[i]);//拿起左邊的叉子wait(fork[(i+1)%5]);//拿起右邊的叉子signal(fork[i]);//放回左邊的叉子signal(fork[(i+1)%5]);//放回右邊的叉子}}有無問題？方案一死鎖操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問題semaphorefork[5]={1,1,1,1,1};voidmain(){cobegin{philosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);}coend;}voidphilosopher(inti){while(true){think;//思考wait(fork[i]);//拿起左邊的叉子

timeout(wait(fork[(i+1)%5],[0,T])//若右邊的叉子被占用，則等待一段隨機(jī)時間后再拿signal(fork[i]);//放回左邊的叉子signal(fork[(i+1)%5]);//放回右邊的叉子}}有無問題？方案二活鎖操作系統(tǒng)系統(tǒng)原理方案三——資源分級Resourcehierarchysolution為資源（這里是餐叉）分配一個偏序（partialorder）或者分級（hierarchy）的關(guān)系，并約定所有資源都按照這種順序獲取，按相反順序釋放，而且保證不會有兩個無關(guān)資源同時被同一項(xiàng)工作所需要。2.12哲學(xué)家就餐問題操作系統(tǒng)系統(tǒng)原理方案三——資源分級方法一為餐叉編號；就餐前，先取用編號較低的餐叉，再取用編號較高的餐叉；就餐畢，先放下編號較高的餐叉，再放下編號較低的餐叉。2.12哲學(xué)家就餐問題操作系統(tǒng)系統(tǒng)原理方案三——資源分級方法一2.12哲學(xué)家就餐問題semaphorefork[5]={1,1,1,1,1};voidmain(){cobegin{philosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);}coend;}voidphilosopher(inti){while(true){think();//思考if(i!=4){wait(fork[i]);wait(fork[(i+1)%5]);}//先左后右else{wait(fork[(i+1)%5]);wait(fork[i]);}//先右后左eat();if(i!=4){signal(fork[(i+1)%5]);signal(fork[i]);}//先右后左else{signal(fork[i]);wait(fork[(i+1)%5]);}//先左后右}}操作系統(tǒng)系統(tǒng)原理方案三——資源分級方法二為哲學(xué)家編號；奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子；偶數(shù)號的哲學(xué)家必須首先拿右邊的筷子。2.12哲學(xué)家就餐問題操作系統(tǒng)系統(tǒng)原理方案三——資源分級方法二2.12哲學(xué)家就餐問題semaphorefork[5]={1,1,1,1,1};voidmain(){cobegin{philosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);}coend;}voidphilosopher(inti){while(true){think();//思考if(i%2==0){wait(fork[i]);wait(fork[(i+1)%5]);}//先左后右else{wait(fork[(i+1)%5]);wait(fork[i]);}eat();signal(fork[(i+1)%5]);