第六章并發(fā)、死鎖和饑餓浙江工業(yè)大學(xué)第一頁(yè)，共81頁(yè)。死鎖

多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行可改善系統(tǒng)的資源利用率和提高系統(tǒng)的處理能力，但也帶來(lái)一種危險(xiǎn)，即死鎖現(xiàn)象發(fā)生。所謂死鎖是指計(jì)算機(jī)系統(tǒng)和進(jìn)程所處的一種狀態(tài)。在系統(tǒng)中，兩個(gè)或多個(gè)進(jìn)程無(wú)限期地等待永遠(yuǎn)不會(huì)發(fā)生的條件，此時(shí)稱系統(tǒng)處于死鎖狀態(tài)。

一組進(jìn)程因競(jìng)爭(zhēng)系統(tǒng)資源或相互通信所造成的永久性阻塞沒有有效的通用解決辦法涉及到兩個(gè)或更多的進(jìn)程之間因?qū)Y源的需求所引起的沖突第二頁(yè)，共81頁(yè)。汽車以70碼的速度行駛，如果沒有任何的措施，接下來(lái)會(huì)發(fā)生什么？第三頁(yè)，共81頁(yè)。怎么辦？第四頁(yè)，共81頁(yè)。 進(jìn)程A 進(jìn)程B ①申請(qǐng)輸入設(shè)備 ①申請(qǐng)輸出設(shè)備 ②申請(qǐng)輸出設(shè)備 ②申請(qǐng)輸入設(shè)備 ③釋放輸入設(shè)備 ③釋放輸出設(shè)備 ④釋放輸出設(shè)備 ④釋放輸入設(shè)備如果執(zhí)行次序?yàn)椋哼M(jìn)程A①→進(jìn)程B①...，則發(fā)生死鎖。輸入設(shè)備輸出設(shè)備BA輸入設(shè)備輸出設(shè)備占有占有等待等待

A在干什么？

B在干什么？競(jìng)爭(zhēng)外設(shè)死鎖示例第五頁(yè)，共81頁(yè)。ABCDELMNOPQFGHIJKAABBCCDDFGHILLMMNNOOFGHISPOOLing系統(tǒng)死鎖示例輸出井進(jìn)程B進(jìn)程C滿啦！不夠！不夠！不夠！進(jìn)程A第六頁(yè)，共81頁(yè)。系統(tǒng)資源可重用資源(ReusableResources)

一次只能供一個(gè)進(jìn)程安全地使用使用資源順序：請(qǐng)求資源；使用資源；釋放資源進(jìn)程用完資源后可以釋放該資源，供其他進(jìn)程再次使用如處理器、I/O通道、主存和輔存、設(shè)備等可消費(fèi)資源(ConsumableResources)（臨時(shí)資源）可以創(chuàng)建并且可以消費(fèi)的資源進(jìn)程消費(fèi)完資源后，該資源就不存在了如中斷、信號(hào)、消息等第七頁(yè)，共81頁(yè)。系統(tǒng)資源可搶占性資源進(jìn)程在獲得這類資源后，該資源可被其它進(jìn)程或系統(tǒng)搶占。這類資源不會(huì)引起死鎖如處理器、主存等不可搶占性資源一旦系統(tǒng)把某資源分配給該進(jìn)程后，就不能將它強(qiáng)行收回，只能在進(jìn)程用完后自行釋放如磁帶機(jī)、打印機(jī)等第八頁(yè)，共81頁(yè)。資源分配圖用資源分配圖來(lái)表示系統(tǒng)狀態(tài)。資源分配圖由結(jié)點(diǎn)和邊組成，是由一組結(jié)點(diǎn)N和一組邊E所組成的一個(gè)對(duì)偶G=（N，E）。（1）

P是一組進(jìn)程結(jié)點(diǎn)P={P1,P2,…,Pn}，R是資源結(jié)點(diǎn)R={r1,r2,…,rn}，N=PUR，且P∩R={}。（2）

任意一邊e∈E，都連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，我們用圓圈表示進(jìn)程，方框表示一類相同的資源，方框中的小圓表示一類資源中的一個(gè)資源。第九頁(yè)，共81頁(yè)。表示法資源類（資源的不同類型）:用方框表示資源實(shí)例（存在于每個(gè)資源中）：用方框中的黑圓點(diǎn)表示進(jìn)程：用圓圈中加進(jìn)程名表示

P分配邊：

資源實(shí)例進(jìn)程的一條有向邊申請(qǐng)邊：進(jìn)程資源類的一條有向邊PiRjPiRj第十頁(yè)，共81頁(yè)。系統(tǒng)資源分配圖示例○R1R2○P1P2第十一頁(yè)，共81頁(yè)。產(chǎn)生死鎖的原因1.競(jìng)爭(zhēng)資源引起死鎖競(jìng)爭(zhēng)不可搶占性資源：資源不足競(jìng)爭(zhēng)可消耗性資源2.進(jìn)程推進(jìn)順序不合理請(qǐng)求和釋放資源的順序不當(dāng)

第十二頁(yè)，共81頁(yè)。產(chǎn)生死鎖的原因1.競(jìng)爭(zhēng)資源引起死鎖

在多道程序系統(tǒng)，多個(gè)進(jìn)程共享系統(tǒng)的資源。對(duì)于可重用的資源，當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，不能強(qiáng)行收回，只能在進(jìn)程用完后自動(dòng)釋放。當(dāng)多個(gè)進(jìn)程競(jìng)爭(zhēng)這類資源時(shí)就可能引起死鎖。第十三頁(yè)，共81頁(yè)。競(jìng)爭(zhēng)資源申請(qǐng)P2

R1

R2P1分配分配申請(qǐng)例如系統(tǒng)只有一臺(tái)打印機(jī)R1和一臺(tái)磁帶機(jī)R2，可供進(jìn)程P1和P2共享。兩個(gè)進(jìn)程都在等待對(duì)方釋放出自己所需要的資源，但它們又都因不能獲得所需的資源而不能繼續(xù)推進(jìn)，從而也不能釋放出自己占有的資源，以致進(jìn)入死鎖狀態(tài)。第十四頁(yè)，共81頁(yè)。2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

在多道程序系統(tǒng)中，并發(fā)執(zhí)行的進(jìn)程推進(jìn)序列不可預(yù)測(cè)，有些推進(jìn)順序，進(jìn)程可以順利完成，這些推進(jìn)順序是合法的；而有的推進(jìn)順序會(huì)引起進(jìn)程無(wú)限期地等待永遠(yuǎn)不會(huì)發(fā)生的條件而不能向前推進(jìn)，造成了死鎖。產(chǎn)生死鎖的原因第十五頁(yè)，共81頁(yè)。[例1]進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

進(jìn)程P和Q并發(fā)執(zhí)行，競(jìng)爭(zhēng)兩個(gè)資源A和B。每個(gè)進(jìn)程需要獨(dú)占使用這兩個(gè)資源。

進(jìn)程P和Q程序如下：ProcessPProcessQ…….GetAGetB…….GetBGetA……ReleaseAReleaseB…….ReleaseBReleaseA第十六頁(yè)，共81頁(yè)。進(jìn)程P和Q按路徑1、2、5、6推進(jìn)順序合法，按3、4推進(jìn)順序非法第十七頁(yè)，共81頁(yè)。ProcessPProcessQ…….GetAGetB…….ReleaseAGetA……GetBReleaseB…….ReleaseBReleaseA修改P程序，可避免死鎖第十八頁(yè)，共81頁(yè)。第十九頁(yè)，共81頁(yè)。[例2]競(jìng)爭(zhēng)可重用性資源引起死鎖

進(jìn)程P、Q并發(fā)執(zhí)行，競(jìng)爭(zhēng)訪問(wèn)磁盤D和磁帶T。假設(shè)按以下執(zhí)行序列執(zhí)行：p0p1q0q1p2q2解決辦法：定義資源請(qǐng)求的先后次序√√√√√√第二十頁(yè)，共81頁(yè)。解決辦法：使用虛擬存儲(chǔ)機(jī)制P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;[例3]競(jìng)爭(zhēng)可重用性資源引起死鎖

進(jìn)程P1、P2并發(fā)執(zhí)行，請(qǐng)求主存空間。假設(shè)可用的主存空間初始為200KB，P1、P2按以下順序請(qǐng)求：第二十一頁(yè)，共81頁(yè)。P1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);[例4]競(jìng)爭(zhēng)可消耗資源引起死鎖

進(jìn)程P1、P2并發(fā)執(zhí)行，通過(guò)信號(hào)量機(jī)制進(jìn)行同步。假設(shè)采用的是Receive阻塞機(jī)制（即未收到信息則該進(jìn)程被阻塞）第二十二頁(yè)，共81頁(yè)。死鎖的條件死鎖的三個(gè)必要條件互斥(Mutualexclusion)一次只有一個(gè)進(jìn)程可以使用一個(gè)資源占有且等待(Hold-and-wait)當(dāng)一個(gè)進(jìn)程在等待分配得到其他資源時(shí)，將繼續(xù)占有已分配到的資源非剝奪(Nopreemption)（不可搶占）不能強(qiáng)行搶占進(jìn)程已占有的資源Q:上述三個(gè)條件是不是一定會(huì)導(dǎo)致死鎖的發(fā)生?第二十三頁(yè)，共81頁(yè)。死鎖的條件循環(huán)等待(Circularwait)存在一個(gè)封閉的進(jìn)程-資源鏈，每個(gè)進(jìn)程至少占有一個(gè)該鏈中下一個(gè)進(jìn)程所需要的資源第二十四頁(yè)，共81頁(yè)。死鎖的三種處理辦法死鎖的預(yù)防（Prevention）靜態(tài)方法：在進(jìn)程執(zhí)行前采取的措施，通過(guò)設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件之一，防止發(fā)生死鎖。

死鎖的避免（Avoidance）動(dòng)態(tài)的方法：在進(jìn)程執(zhí)行過(guò)程中采取的措施，不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件，而是在進(jìn)程申請(qǐng)資源時(shí)用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。死鎖的檢測(cè)（Detection）和解除這種方法預(yù)先并不采用任何限制措施，允許系統(tǒng)在運(yùn)行過(guò)程中發(fā)生死鎖，但可通過(guò)系統(tǒng)設(shè)置的檢測(cè)機(jī)構(gòu)及時(shí)檢測(cè)死鎖的發(fā)生（定期執(zhí)行死鎖檢測(cè)算法），如檢測(cè)到死鎖，則采用撤消進(jìn)程等死鎖解除方法使系統(tǒng)恢復(fù)正常工作。第二十五頁(yè)，共81頁(yè)。第二十六頁(yè)，共81頁(yè)。死鎖的預(yù)防(DeadlockPrevention)預(yù)防死鎖的方法是破壞四個(gè)產(chǎn)生死鎖的必要條件之一。破壞互斥條件互斥使用是資源本身特征所決定的。使用硬軟件結(jié)合可改變資源本身特性，例如采用SPOOLing技術(shù)可將“獨(dú)享”打印機(jī)改變?yōu)椤肮蚕怼钡拇蛴C(jī)。破壞不可搶占條件可采用搶占式調(diào)度，但搶占式調(diào)度法主要用于處理機(jī)和存儲(chǔ)器資源調(diào)度，它們的狀態(tài)容易保存和恢復(fù)。此法對(duì)外部設(shè)備和私有數(shù)據(jù)不宜使用。第二十七頁(yè)，共81頁(yè)。破壞請(qǐng)求和保持條件系統(tǒng)可采用資源靜態(tài)預(yù)先全分配方式來(lái)破壞請(qǐng)求保持條件。系統(tǒng)要求所有進(jìn)程一次性地申請(qǐng)?jiān)谡麄€(gè)運(yùn)行過(guò)程中全部資源，若系統(tǒng)有足夠資源滿足給進(jìn)程，則在運(yùn)行前，一次性將其所需要的所有資源分配給該進(jìn)程。這樣該進(jìn)程在整個(gè)運(yùn)行期間，便不再提出資源要求，從而摒棄了請(qǐng)求條件。優(yōu)點(diǎn)是簡(jiǎn)單、易于實(shí)現(xiàn)且很安全，但其資源利用率很低，進(jìn)程也延遲運(yùn)行。死鎖的預(yù)防第二十八頁(yè)，共81頁(yè)。破壞循環(huán)等待條件有序資源使用法該方法將所有的資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)。例如令輸入機(jī)的序號(hào)為1，打印機(jī)序號(hào)為2，磁盤機(jī)序號(hào)為3等。所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按資源序號(hào)遞增的次序提出。這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路，因而摒棄了“循環(huán)等待”條件，在采用這種策略時(shí)總有一個(gè)進(jìn)程占據(jù)了較高序號(hào)的資源，它繼續(xù)請(qǐng)求的資源必然是空閑的，因而進(jìn)程可以一直向前推進(jìn)。可提高資源利用率，但在進(jìn)程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時(shí)會(huì)造成資源浪費(fèi)的情況。死鎖的預(yù)防第二十九頁(yè)，共81頁(yè)。反證：若出現(xiàn)循環(huán)等待，則必會(huì)有小序號(hào)資源序號(hào)大于大序號(hào)資源序號(hào)。令R={r1,r2,…,rm}表示一組資源類型。我們定義一個(gè)一對(duì)一的函數(shù)F(R)=N,N是一組自然數(shù)。例：一組資源包括磁盤機(jī)、磁帶機(jī)、讀卡機(jī)和打印機(jī)。函數(shù)F可定義如下：

F(讀卡機(jī))=1,F(磁盤機(jī))=5,F(磁帶機(jī))=7,F(打印機(jī))=12

若存在環(huán)路等待，則必然有F(r1)<F(r2)<…<F(ri)<F(r1)

由傳遞性得到：F(r1)<F(r1)矛盾第三十頁(yè)，共81頁(yè)。有序資源使用法

R1R2R3R4R5R6R7A***B***C****A、B、C三個(gè)進(jìn)程對(duì)于資源的請(qǐng)求只能按照資源排列的先后次序請(qǐng)求第三十一頁(yè)，共81頁(yè)。XX如果紅綠燈壞了，或者沒裝紅綠燈，怎么辦？第三十二頁(yè)，共81頁(yè)。駕駛員在行駛過(guò)程中實(shí)時(shí)地判斷安不安全。如果不安全就減速或停車等待，安全后再通過(guò)。小心！注意安全！第三十三頁(yè)，共81頁(yè)。死鎖的避免(DeadlockAvoidance)允許三個(gè)條件的存在，但通過(guò)動(dòng)態(tài)的選擇，確保永遠(yuǎn)不會(huì)到達(dá)死鎖點(diǎn)。允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)從安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換，便可將資源分配給進(jìn)程；否則不分配資源，進(jìn)程必須阻塞等待。從而避免發(fā)生死鎖。需要知道將來(lái)的進(jìn)程資源請(qǐng)求情況第三十四頁(yè)，共81頁(yè)。資源分配拒絕系統(tǒng)的安全狀態(tài)是指系統(tǒng)的一種狀態(tài)，在此狀態(tài)下系統(tǒng)能按某種順序（例如P1、P2……Pn）來(lái)為各個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序地一個(gè)個(gè)地完成。這個(gè)序列（P1、P2…….Pn）稱為安全序列。若系統(tǒng)在某個(gè)狀態(tài)下不存在一個(gè)安全序列，使所有進(jìn)程能運(yùn)行結(jié)束，則稱系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)并不是死鎖狀態(tài)，而是存在死鎖的可能性。系統(tǒng)只有在安全狀態(tài)下才滿足進(jìn)程對(duì)于資源的請(qǐng)求，否則拒絕。第三十五頁(yè)，共81頁(yè)。

設(shè)銀行家有10萬(wàn)貸款，P,Q,R分別需要8,3,9萬(wàn)元搞項(xiàng)目，如果P已申請(qǐng)到了4萬(wàn)，Q要申請(qǐng)2萬(wàn)，顯然，如果滿足Q的申請(qǐng)，有安全序列<P,Q,R>/<Q,P,R>。

客戶最大需求量已分配還需要可用P8444Q321R909還需要可用客戶910R18Q44P第三十六頁(yè)，共81頁(yè)?？蛻糇畲笮枨罅恳逊峙溥€需要可用P8442Q303R945還需要可用客戶2若滿足R的申請(qǐng)，顯然不存在安全序列。如果R要申請(qǐng)4萬(wàn)第三十七頁(yè)，共81頁(yè)。注意安全狀態(tài)不是死鎖狀態(tài)；死鎖狀態(tài)是不安全狀態(tài)。不安全狀態(tài):不存在一個(gè)安全序列不安全狀態(tài)可能導(dǎo)致死鎖，但不安全狀態(tài)不一定是死鎖狀態(tài)。第三十八頁(yè)，共81頁(yè)。銀行家算法最具代表的避免死鎖算法是Dijkstra的銀行家算法，這是由于該算法用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。某銀行共有資金100萬(wàn)元和三個(gè)借貸客戶甲、乙、丙,他們的最大借款額分別為100,80,70(萬(wàn)元).他們已借得的金額分別為10,20,50(萬(wàn)元).銀行還有資金多少?各客戶還需多少資金?按目前狀況,銀行可能收回全部貸款嗎?如果乙提出借10萬(wàn),可以滿足嗎?如果丙提出借10萬(wàn),可以滿足嗎?(假設(shè)客戶獲得最大借款額后就返還銀行所有借款)第三十九頁(yè)，共81頁(yè)。算法的數(shù)據(jù)結(jié)構(gòu)考慮一個(gè)具有n個(gè)進(jìn)程和m種不同類型資源系統(tǒng)。Resource=R=(R1,R2,…,Rm)：向量，表示系統(tǒng)中每種資源的總量Available=V=(V1,V2,…,Vm)：向量，未分配給進(jìn)程的每種資源的總量，即可用的資源數(shù)Claim=C：矩陣，Cij表示進(jìn)程i對(duì)資源j的最大需求Allocation=A：矩陣，Aij表示當(dāng)前進(jìn)程i已分配到的資源j的數(shù)量Need=N：矩陣，表示每個(gè)進(jìn)程尚需的各類資源數(shù)，Need[i,j]=k表示進(jìn)程i還需要j類資源k個(gè)。Need[i,j]=Claim[i,j]-Allocation[i,j]第四十頁(yè)，共81頁(yè)。安全狀態(tài)檢測(cè)（1）是否為安全狀態(tài)?第四十一頁(yè)，共81頁(yè)。P2運(yùn)行結(jié)束，并釋放所占用的資源第四十二頁(yè)，共81頁(yè)。P1運(yùn)行結(jié)束，并釋放所占用的資源第四十三頁(yè)，共81頁(yè)。P3運(yùn)行結(jié)束，并釋放所占用的資源第四十四頁(yè)，共81頁(yè)。安全狀態(tài)檢測(cè)（2）是否為安全狀態(tài)?第四十五頁(yè)，共81頁(yè)。算法思想假設(shè)在進(jìn)程并發(fā)執(zhí)行時(shí)，進(jìn)程i提出請(qǐng)求j類資源k個(gè)后，表示為Request

[i,j]=k。系統(tǒng)按下述步驟進(jìn)行安全檢查：1.如果alloc[i,j]+Request[i,j]≤claim[i,j]i則繼續(xù)以下檢查，否則顯示需求申請(qǐng)超出最大需求值的錯(cuò)誤。2.如果Request[i]≤Available則繼續(xù)以下檢查，否則顯示系統(tǒng)無(wú)足夠資源，Pi阻塞等待。3.系統(tǒng)假設(shè)同意進(jìn)程i的請(qǐng)求，將系統(tǒng)狀態(tài)修改為滿足請(qǐng)求之后的狀態(tài)，然后對(duì)此狀態(tài)執(zhí)行安全性算法檢測(cè)，判斷在此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給進(jìn)程i，以完成本次分配；否則將恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待，即進(jìn)程Pi置為阻塞狀態(tài)。因此，在圖6.8b,中，P1的請(qǐng)求將被拒絕，P1將從運(yùn)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。第四十六頁(yè)，共81頁(yè)。

安全性算法思想執(zhí)行步驟如下：A.初始化設(shè)置工作向量currentavail[m]表示系統(tǒng)可提供的各類資源數(shù)目，用以保護(hù)原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。currentavail=Available。設(shè)置完成標(biāo)志向量Finish[n]，F(xiàn)inish[i]=false表示i進(jìn)程尚末完成，如值為true則表示進(jìn)程i已完成。B.從進(jìn)程集合n中找到一個(gè)能滿足下述二個(gè)條件:Finish[i]=false和Need[i]≤currentavail，如找到則執(zhí)行步驟C，如找不到同時(shí)滿足以上二條件的進(jìn)程則執(zhí)行步驟D。C.當(dāng)進(jìn)程i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下：

currentavail=currentavail+allocation[i]

；Finish[i]=true；轉(zhuǎn)執(zhí)行步驟B。D.如果所有的Finish[i]＝true，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。第四十七頁(yè)，共81頁(yè)。死鎖避免算法第四十八頁(yè)，共81頁(yè)。第四十九頁(yè)，共81頁(yè)。[例1]假定系統(tǒng)中有五個(gè)進(jìn)程{P0、P1、P2、P3、P4}和三種類型資源{A、B、C}，每一種資源的數(shù)量分別為10、5、7。各進(jìn)程的最大需求、T0時(shí)刻資源分配情況如下所示。

Claim

AllocationNeedAvailable ABCABCABCABCP0753010P1322200P2902302P3222 211P4433002

432200011431332第五十頁(yè)，共81頁(yè)。1.T0時(shí)刻是否安全？解：1).已知：Allocation和Claim要先求Need=Claim-Allocation2).已知：總資源數(shù)和Allocation要先求Available=總資源數(shù)-3).求是不是安全狀態(tài)的關(guān)鍵就在于能否找到一個(gè)進(jìn)程的執(zhí)行序列，使所有的進(jìn)程都能執(zhí)行結(jié)束。該序列稱為安全序列。第五十一頁(yè)，共81頁(yè)。

1T0時(shí)刻的安全序列存在安全性序列{P1，P3，P4，P2，P0}或{P1，P3，P4，P0，P2}。

332P1122200

532True

532P3011211

743true

743P4431002

745trueP0

745743010

755true

745P2600302

1047trueP2

755600302

1057true1047P0743010

1057true資源情況進(jìn)程WorkABCNeedABCAllocationABCWork+AllocationABCFinish第五十二頁(yè)，共81頁(yè)。從表中可找出一個(gè)序列(P1、

P3、P4、

P2、

P0）使各進(jìn)程順序地一個(gè)個(gè)地執(zhí)行完成。

claimAllocation

NeedWork(Available)Work+Allocationi次序

ABC

ABC

ABCABC332

ABCP0

753

010

743

10575P1

322

200

122

5321P2

902

302

600

10474P3

222

211

011

7432P4

433

002

431

7453第五十三頁(yè)，共81頁(yè)。T0時(shí)刻系統(tǒng)是安全的?？赡苡袔讉€(gè)安全序列，只要找出一個(gè)安全序列就可以。注意：Needi=<Available要求數(shù)組每個(gè)元素都成立例：123=<332不成立第五十四頁(yè)，共81頁(yè)。2.P1請(qǐng)求資源Request1(1,0,2)可否允許？Request1(1,0,2)≤Need1(1,2,2)，P1請(qǐng)求在最大需求范圍內(nèi)。Request1(1,0,2)≤Available(3,3,2)，可用資源可滿足P1請(qǐng)求需要。試探把要求的資源分配給進(jìn)程P1并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的數(shù)值：Available=Available(3，3，2)－Request1(1,0,2)=Available(2,3,0)；Need1=Need1(1,2,2)－Request1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法檢查試探將資源分配后狀態(tài)的安全性如下：第五十五頁(yè)，共81頁(yè)。

WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057true存在安全序列{P1，P3，P4，P0，P2}，可以將P1所申請(qǐng)的資源分配給它。第五十六頁(yè)，共81頁(yè)。

claim

AllocationNeedAvailableAvailable(分配資源前)(釋放資源后）

ABCABCABCABC ABCP0753010743=<1047⑤1057P1322302020=<230

①532 P2 902302600=<745④1047 P3 222211011=<532②743 P4 433002431=<743③745

因?yàn)橄确峙滟Y源給P1進(jìn)程符合按安全序列{P1、P3、P4、P2、P0}分配資源，所以試探將資源分配給進(jìn)程P1后的狀態(tài)是安全的，可將資源分配給進(jìn)程P1。第五十七頁(yè)，共81頁(yè)。3.P4請(qǐng)求資源Request4(3,3,0)是否允許？Request4(3,3,0)≤Need4(4,3,1)，P4請(qǐng)求在最大需求范圍內(nèi)。Request4(3,3,0)≤Available(2,3,0)不成立，即可用資源暫不能滿足P4請(qǐng)求資源需要，P4阻塞等待。

第五十八頁(yè)，共81頁(yè)。[例2]進(jìn)程P1、P2和P3共享12個(gè)相同資源，它們對(duì)于資源的最大需求分別是：8，6，9。如果它們按以下步驟請(qǐng)求資源：StepsProcessResourcesRequest1P142P243P324P115P326P22………………使用銀行家算法解決：（1）哪一步將導(dǎo)致不安全狀態(tài)？（2）在第六步之后，P1、P2和P3的狀態(tài)分別是什么？它們所占用的資源數(shù)為多少？第五十九頁(yè)，共81頁(yè)。step1,P1請(qǐng)求4個(gè)資源，4<=8&&4<=12，可以滿足；

Claim

AllocationNeedAvailableP18448P2606P3909

假設(shè)分配給P1，則系統(tǒng)可用資源數(shù)為8，P1還需的資源數(shù)為4，顯然是安全狀態(tài)；第六十頁(yè)，共81頁(yè)。step2,P2請(qǐng)求4個(gè)資源，4<=6&&4<=8，可以滿足；假設(shè)分配給P2，則系統(tǒng)可用資源數(shù)為4，P2還需的資源數(shù)為2，顯然是安全狀態(tài)；

Claim

AllocationNeedAvailableP18448P2606P3909

Claim

AllocationNeedAvailableP18444P2642P3909

第六十一頁(yè)，共81頁(yè)。step3,P3請(qǐng)求2個(gè)資源，2<=9&&2<=2，可以滿足；假設(shè)分配給P3，則系統(tǒng)可用資源數(shù)為2，P3還需的資源數(shù)為7。分配之后，此時(shí)系統(tǒng)仍然可以沿著P2、P1、P3的序列執(zhí)行，因此仍然是安全狀態(tài)；

Claim

AllocationNeedAvailableP18444P2642P3909

Claim

AllocationNeedAvailableP18442P2642P3927第六十二頁(yè)，共81頁(yè)。step4,P1請(qǐng)求1個(gè)資源，1<=4&&1<=2，可以滿足；假設(shè)分配給P1，則系統(tǒng)可用資源數(shù)為1，P1還需的資源數(shù)為3。分配之后，此時(shí)系統(tǒng)所剩的資源數(shù)不能滿足任何一個(gè)進(jìn)程執(zhí)行所需，故不存在一條安全序列，即如果進(jìn)行分配，則系統(tǒng)將進(jìn)入不安全狀態(tài)，因此，第4步將導(dǎo)致系統(tǒng)變成不安全狀態(tài)。采用銀行家算法將避免這種分配，即將P1置為阻塞狀態(tài)。

Claim

AllocationNeedAvailableP18442P2642P3927第六十三頁(yè)，共81頁(yè)。Step5,P3請(qǐng)求2個(gè)資源，2<=7&&2<=2，可以滿足；假設(shè)分配給P3，則系統(tǒng)可用資源數(shù)為0，P3還需的資源數(shù)為5。分配之后，此時(shí)系統(tǒng)所剩的資源數(shù)不能滿足任何一個(gè)進(jìn)程執(zhí)行所需，故不存在一條安全序列，即如果進(jìn)行分配，則系統(tǒng)將進(jìn)入不安全狀態(tài)，采用銀行家算法將避免這種分配，即將P3置為阻塞狀態(tài)。

Claim

AllocationNeedAvailableP18442P2642P3927第六十四頁(yè)，共81頁(yè)。Step6,P2請(qǐng)求2個(gè)資源，2<=2&&2<=2，可以滿足；假設(shè)分配給P2，則系統(tǒng)可用資源數(shù)為0，P2還需的資源數(shù)為0。這種分配符合我們先前所說(shuō)的安全序列執(zhí)行順序，因此可以滿足。P2處于運(yùn)行狀態(tài)，占用的資源數(shù)為6。因此，在第六步之后，P1的狀態(tài)為阻塞，占用資源數(shù)為4；P2狀態(tài)為運(yùn)行，占用資源數(shù)為6；P3的狀態(tài)為阻塞，占用資源數(shù)為2

Claim

AllocationNeedAvailableP18442P2642P3927

Claim

AllocationNeedAvailableP18440P2660P3927第六十五頁(yè)，共81頁(yè)。死鎖避免方法的限制必須事先聲明每個(gè)進(jìn)程請(qǐng)求的最大資源數(shù)考慮的進(jìn)程必須是無(wú)關(guān)的，即進(jìn)程之間不存在同步關(guān)系分配的資源數(shù)目必須是固定的在占有資源時(shí)，進(jìn)程不能退出第六十六頁(yè)，共81頁(yè)。堵車是不可避免的？怎么辦？

交警來(lái)疏通第六十七頁(yè)，共81頁(yè)。死鎖檢測(cè)(DeadlockDetection)不限制資源訪問(wèn)或約束進(jìn)程的行為只要系統(tǒng)資源能滿足進(jìn)程的請(qǐng)求就立即滿足操作系統(tǒng)定期執(zhí)行一個(gè)算法（死鎖檢測(cè)算法），檢測(cè)當(dāng)前