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

計(jì)算機(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)程死鎖問(wèn)題。一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無(wú)法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個(gè)系統(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）概念多個(gè)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源或執(zhí)行時(shí)推進(jìn)的順序不當(dāng)，或相互通信出現(xiàn)永久阻塞現(xiàn)象，如果沒(méi)有外力作用，這種現(xiàn)象將永遠(yuǎn)保持下去。產(chǎn)生死鎖的原因資源不足導(dǎo)致的資源競(jìng)爭(zhēng)多個(gè)進(jìn)程所共享的資源不足，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。并發(fā)執(zhí)行的順序不當(dāng)進(jìn)程運(yùn)行過(guò)程中，請(qǐng)求和釋放資源的順序不當(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)程使用資源的方式請(qǐng)求（request）占用/使用（use）釋放（release）操作系統(tǒng)系統(tǒng)原理2.11.1

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

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

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

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

引起死鎖的原因競(jìng)爭(zhēng)可消耗資源可能會(huì)導(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}資源請(qǐng)求邊（request）Pi

Rj資源分配邊（assignment）Rj

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

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

具有4個(gè)實(shí)例的資源進(jìn)程Pi請(qǐng)求資源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)但不會(huì)導(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)程對(duì)所分配到的資源進(jìn)行排它性使用。如果此時(shí)還有其它進(jìn)程申請(qǐng)?jiān)撡Y源，則它只能阻塞，直至占有該資源的進(jìn)程釋放。占有且等待（請(qǐng)求和保持條件）進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源要求，而該資源又已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)已經(jīng)獲得的其它資源保持不放。操作系統(tǒng)系統(tǒng)原理2.11.1

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

引起死鎖的原因循環(huán)等待條件示例R1P1占用P2R2占用申請(qǐng)申請(qǐng)死鎖操作系統(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）檢測(cè)解除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

避免死鎖安全序列

一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過(guò)系統(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)一定沒(méi)有死鎖發(fā)生？操作系統(tǒng)系統(tǒng)原理2.11.4

避免死鎖不安全序列

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

無(wú)死鎖：死鎖

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

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

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

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

不安全狀態(tài)若系統(tǒng)處于安全狀態(tài)，且按照某個(gè)安全序列分配資源，可以保證系統(tǒng)不會(huì)出現(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è)計(jì)思想：當(dāng)用戶申請(qǐng)一組資源時(shí)，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分配這些資源；否則，暫時(shí)不分配，阻塞進(jìn)程。

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

避免死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)設(shè)系統(tǒng)中有m種不同資源,n個(gè)進(jìn)程Available向量:系統(tǒng)中尚未分配的每種資源的總量Available[j]:尚未分配的資源j的數(shù)量Max矩陣:各個(gè)進(jìn)程對(duì)每種資源的最大需求量(進(jìn)程事先聲明)Max[i,j](Claim[i,j]):進(jìn)程i對(duì)資源j的最大需求量Allocation矩陣:當(dāng)前資源分配狀況Allocation[i,j]:進(jìn)程i獲得的資源j的數(shù)量Need矩陣:每個(gè)進(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分別是長(zhǎng)度為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；返回第②步若對(duì)所有的i,Finish[i]==True成立，則系統(tǒng)處于安全狀態(tài)；反之，則系統(tǒng)處于不安全狀態(tài)。操作系統(tǒng)系統(tǒng)原理2.11.4

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

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

避免死鎖

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

若Requesti≤Needi，則轉(zhuǎn)向步驟②；否則，出錯(cuò)退出。若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個(gè)進(jìn)程P1、P2、P3和P4；3類(lèi)資源R1、R2和R3,其資源數(shù)量分別為9、3和6。T0時(shí)刻的資源分配情況如下，此時(shí)若進(jìn)程P4的請(qǐng)求向量為<1，2，0>。若采用銀行家算法，可否分配資源？MaxAllocationR1R2R3R1R2R3P1322100P2613612P3314211P4422002操作系統(tǒng)系統(tǒng)原理2.11.4

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

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

Request4<Available不成立

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

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

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

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

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

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

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

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

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

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

避免死鎖

銀行家算法的優(yōu)點(diǎn)比死鎖預(yù)防限制少無(wú)死鎖檢測(cè)方法中的資源剝奪,進(jìn)程重啟。銀行家算法的缺點(diǎn)預(yù)先必須聲明每個(gè)進(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

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

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

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

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

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

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

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

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

檢測(cè)并解除死鎖死鎖定理

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

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

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

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

檢測(cè)并解除死鎖死鎖檢測(cè)偽碼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

檢測(cè)并解除死鎖

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

檢測(cè)并解除死鎖

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

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

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

檢測(cè)并解除死鎖

資源剝奪：逐步從進(jìn)程中搶占資源給其它進(jìn)程，直到死鎖環(huán)被打破為止。選擇一個(gè)犧牲品：搶占哪些資源和哪個(gè)進(jìn)程，確定搶占順序以使代價(jià)最小。饑餓：確保資源不會(huì)總是從同一個(gè)進(jìn)程中被搶占進(jìn)程回退：把每個(gè)死鎖進(jìn)程備份到前面定義的某些檢查點(diǎn),并且重新啟動(dòng)所有進(jìn)程－需要系統(tǒng)構(gòu)造重新運(yùn)行和重新啟動(dòng)機(jī)制操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問(wèn)題DinningPhilosopherProblem1965年，Dijkstra出了一道同步考試題：假設(shè)有五臺(tái)計(jì)算機(jī)都試圖訪問(wèn)五份共享的磁帶驅(qū)動(dòng)器。后來(lái)，這個(gè)問(wèn)題被Hoare重新表述為哲學(xué)家就餐問(wèn)題。這個(gè)問(wèn)題可以用來(lái)解釋死鎖和資源耗盡。描述5個(gè)哲學(xué)家圍坐一張餐桌5只餐叉間隔擺放思考或進(jìn)餐進(jìn)餐時(shí)必須同時(shí)拿到兩邊的餐叉思考時(shí)將餐叉放回原處操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問(wèn)題操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問(wèn)題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]);//放回右邊的叉子}}有無(wú)問(wèn)題？方案一死鎖操作系統(tǒng)系統(tǒng)原理2.12哲學(xué)家就餐問(wèn)題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ī)時(shí)間后再拿signal(fork[i]);//放回左邊的叉子signal(fork[(i+1)%5]);//放回右邊的叉子}}有無(wú)問(wèn)題？方案二活鎖操作系統(tǒng)系統(tǒng)原理方案三——資源分級(jí)Resourcehierarchysolution為資源（這里是餐叉）分配一個(gè)偏序（partialorder）或者分級(jí)（hierarchy）的關(guān)系，并約定所有資源都按照這種順序獲取，按相反順序釋放，而且保證不會(huì)有兩個(gè)無(wú)關(guān)資源同時(shí)被同一項(xiàng)工作所需要。2.12哲學(xué)家就餐問(wèn)題操作系統(tǒng)系統(tǒng)原理方案三——資源分級(jí)方法一為餐叉編號(hào)；就餐前，先取用編號(hào)較低的餐叉，再取用編號(hào)較高的餐叉；就餐畢，先放下編號(hào)較高的餐叉，再放下編號(hào)較低的餐叉。2.12哲學(xué)家就餐問(wèn)題操作系統(tǒng)系統(tǒng)原理方案三——資源分級(jí)方法一2.12哲學(xué)家就餐問(wèn)題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)原理方案三——資源分級(jí)方法二為哲學(xué)家編號(hào)；奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子；偶數(shù)號(hào)的哲學(xué)家必須首先拿右邊的筷子。2.12哲學(xué)家就餐問(wèn)題操作系統(tǒng)系統(tǒng)原理方案三——資源分級(jí)方法二2.12哲學(xué)家就餐問(wèn)題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]);