華南農(nóng)業(yè)大學(xué)-第六章 并發(fā),死鎖和饑餓

第六章并發(fā)：死鎖和饑餓6.1死鎖原理死鎖一組相互競(jìng)爭(zhēng)系統(tǒng)資源或進(jìn)行通信的進(jìn)程間的“永久”阻塞涉及兩個(gè)或多個(gè)進(jìn)程之間對(duì)資源需求的沖突無(wú)有效解決方法常見(jiàn)：交通死鎖6.1.1資源分類(lèi)可重用資源+可消耗資源可重用資源一次只能供一個(gè)進(jìn)程安全地使用，不會(huì)耗盡可剝奪資源：包括CPU、虛存、磁盤(pán)不可剝奪資源：打印機(jī)、文件、數(shù)據(jù)庫(kù)和信號(hào)量競(jìng)爭(zhēng)不可剝奪資源，就會(huì)發(fā)生死鎖兩進(jìn)程競(jìng)爭(zhēng)可重用資源的例子p0p1q0q1p2q2策略：給系統(tǒng)設(shè)計(jì)施加關(guān)于資源請(qǐng)求順序的約束可重用資源死鎖的另一個(gè)例子：內(nèi)存請(qǐng)求可分配空間200kb第二個(gè)請(qǐng)求時(shí)發(fā)生死鎖解決：使用虛擬存儲(chǔ)消除死鎖可能性P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;可消耗資源可以被創(chuàng)建（生產(chǎn)）和銷(xiāo)毀（消耗）的資源一個(gè)無(wú)阻塞的生產(chǎn)進(jìn)程可以創(chuàng)建任意數(shù)目的這類(lèi)資源例子：中斷、信號(hào)、消息和I/O緩沖區(qū)中的信息接收信息被阻塞（receive阻塞），出現(xiàn)死鎖-難以發(fā)現(xiàn)接收受阻，死鎖出現(xiàn)P1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);6.1.2資源分配圖一個(gè)有向圖表示，描述資源和進(jìn)程狀態(tài)進(jìn)程：P，圓形表示某類(lèi)資源：R，方形表示具體資源：原點(diǎn)表示請(qǐng)求：Pi

Rj分配：Rj

PiP1P2R2

R1

6.1.2資源分配圖交通阻塞的資源分配圖6.1.3死鎖的條件互斥一次只有一個(gè)進(jìn)程可以使用一個(gè)資源，其他進(jìn)程不能訪問(wèn)占有且等待當(dāng)一個(gè)進(jìn)程等待其他進(jìn)程時(shí)，繼續(xù)占有已有資源不可搶占不能強(qiáng)行搶占進(jìn)程已占有資源循環(huán)等待前三個(gè)條件的潛在結(jié)果存在一個(gè)封閉的進(jìn)程鏈，使每個(gè)進(jìn)程至少占有此鏈中下一個(gè)進(jìn)程所需要的一個(gè)資源必要條件充分條件6.2處理死鎖預(yù)防死鎖：消除某一個(gè)條件的出現(xiàn)避免死鎖：不破壞條件，允許進(jìn)程資源動(dòng)態(tài)分配，檢查狀態(tài)，保證不出現(xiàn)死鎖檢測(cè)死鎖：試圖檢測(cè)到死鎖的存在并恢復(fù)撤銷(xiāo)死鎖進(jìn)程剝奪資源6.2死鎖預(yù)防互斥不可能禁止占有且等待要求進(jìn)程一次性地請(qǐng)求所有需要的資源低效的進(jìn)程阻塞很長(zhǎng)時(shí)間，以等待所有資源一個(gè)資源可能被占有很長(zhǎng)時(shí)間，而不被使用并不知道自己所需的所有資源不可搶占一個(gè)進(jìn)程申請(qǐng)新資源被拒絕時(shí)，必須釋放之前占有的資源操作系統(tǒng)搶占某個(gè)進(jìn)程，要求它釋放已占有的資源（不同優(yōu)先級(jí)）循環(huán)等待定義資源類(lèi)型的線性順序A：Ri-Rj（i<j)；B：Rj-Ri(i>j)6.3死鎖避免死鎖預(yù)防---約束資源請(qǐng)求,至少破壞一個(gè)條件防止前三個(gè)條件，間接完成防止第四個(gè)條件，直接完成導(dǎo)致低效的資源利用和低效的進(jìn)程執(zhí)行死鎖避免允許三個(gè)必要條件明智選擇，確保永不會(huì)到達(dá)死鎖點(diǎn)，允許更多的并發(fā)需要知道將來(lái)的進(jìn)程資源請(qǐng)求的情況，以判斷該請(qǐng)求是否可能導(dǎo)致死鎖6.3死鎖避免兩種方法進(jìn)程啟動(dòng)拒絕：如果一個(gè)進(jìn)程的請(qǐng)求會(huì)導(dǎo)致死鎖，不啟動(dòng)進(jìn)程資源分配拒絕：如果一個(gè)進(jìn)程增加的資源請(qǐng)求會(huì)導(dǎo)致死鎖，則不允許分配6.3.1進(jìn)程啟動(dòng)拒絕Resource=(R1,R2,…,Rm):系統(tǒng)中每種資源的總量Available=V=（V1,V2,…,Vm):未分配給進(jìn)程的每種資源的總量Claim=C=:每個(gè)進(jìn)程對(duì)每種資源的最大需求Allocation=A=

:顯示每個(gè)進(jìn)程當(dāng)前的資源分配情況1.Rj=Vj+A.j

所有資源或者可用，或者已經(jīng)被分配2.Cij<=Ri

任何一個(gè)進(jìn)程對(duì)任一種資源的請(qǐng)求都不能超過(guò)系統(tǒng)中該種資源的總量3.Aij<=Cij,分配給任何一個(gè)進(jìn)程的任何一種資源都不會(huì)超過(guò)該進(jìn)程最初的請(qǐng)求量所有進(jìn)程的最大需求量加上新進(jìn)程的需求量能夠得到滿足即當(dāng)Rj>=C(n+1)j+C.j才啟動(dòng)新進(jìn)程Pn+16.3.2資源分配拒絕銀行家算法安全狀態(tài)：至少有一個(gè)資源分配序列<P1,P2,…,Pn>不會(huì)導(dǎo)致死鎖,即Cij-Aij<=Vj不安全狀態(tài):不存在任何安全序列銀行家算法流程Requesti<Ci-AiF退出TRequesti<=ViT預(yù)分配資源Ai=Ai+RequestiV=V-Requesti測(cè)試分配資源FPi等待不安全Pi等待，恢復(fù)原來(lái)值安全安全狀態(tài)的確定初始狀態(tài)安全狀態(tài)的確定P2運(yùn)行安全狀態(tài)的確定P1運(yùn)行安全狀態(tài)的確定P3運(yùn)行<P2,P1,P3,P4>不安全狀態(tài)的確定51P2請(qǐng)求1個(gè)R1和1個(gè)R3，是否安全？？？P1請(qǐng)求1個(gè)R1和1個(gè)R3，是否安全？？？全局?jǐn)?shù)據(jù)結(jié)構(gòu)資源分配算法測(cè)試安全算法（銀行家算法）6.3.3死鎖避免限制必需事先聲明每個(gè)進(jìn)程請(qǐng)求的最大資源；所討論的進(jìn)程必須是無(wú)關(guān)的，不存在同步分配資源數(shù)目必須是固定的占有資源時(shí)，進(jìn)程不能退出6.4死鎖檢測(cè)不限制資源訪問(wèn)或約束進(jìn)程行為，只要有可能，被請(qǐng)求的資源就被分配給進(jìn)程O(píng)S周期性地執(zhí)行一個(gè)算法檢測(cè)充分條件：循環(huán)等待好處：可以盡早發(fā)現(xiàn)死鎖缺點(diǎn)：耗費(fèi)相當(dāng)多的處理器時(shí)間死鎖檢測(cè)算法標(biāo)記所有不會(huì)產(chǎn)生死鎖的進(jìn)程當(dāng)且僅達(dá)算法結(jié)束仍有進(jìn)程未標(biāo)記，則存在死鎖不能保證防止死鎖，只能確定當(dāng)前是否存在死鎖死鎖檢測(cè)算法00011Available步驟：1、標(biāo)記A矩陣中全為0的一行；2、初始化臨時(shí)向量W=V；3、查找未標(biāo)記的進(jìn)程i，其在請(qǐng)求矩陣Q中小于等于W，若無(wú)，終止；4、找到，標(biāo)記進(jìn)程i，并把A中相應(yīng)的第i行加到W中，并返回3。P4P3恢復(fù)（復(fù)雜度遞增）取消所有的死鎖進(jìn)程把每個(gè)死鎖進(jìn)程回滾到前面定義的某些檢查點(diǎn)，重新啟動(dòng)所有進(jìn)程連續(xù)取消死鎖進(jìn)程直到不再存在死鎖連續(xù)搶占資源直到不再存在死鎖選擇原則：消耗的CPU時(shí)間最少產(chǎn)生的輸出最少剩下的時(shí)間最少分配的資源總量最少優(yōu)先級(jí)最低（防止饑餓）6.5綜合死鎖策略把資源分成幾組不同的資源類(lèi)預(yù)防資源類(lèi)之間由于循環(huán)等待產(chǎn)生死鎖，可使用全面定義的線性排序策略在一個(gè)資源類(lèi)中，使用該類(lèi)資源最適合的算法對(duì)于每一類(lèi)資源的策略可交換空間：即外存，通過(guò)要求一次性分配所有請(qǐng)求的資源來(lái)預(yù)防死鎖，如果知道最大存儲(chǔ)需求，此策略合理進(jìn)程資源：如文件等，死鎖避免很有效，或資源排序進(jìn)行預(yù)防內(nèi)存：基于搶占的預(yù)防最適合。內(nèi)部資源：如I/O通道，可以使用基于資源排序的預(yù)防策略6.6哲學(xué)家就餐問(wèn)題基于信號(hào)量的解決方案1

至多允許四人同時(shí)拿刀叉Semaphorefork[5]=1Semaphoreroom=4基于信號(hào)量的解決方案2

奇號(hào)人先拿左叉偶號(hào)人先拿右叉Unix的并發(fā)機(jī)制（略）管道消息共享內(nèi)存信號(hào)量信號(hào)管道環(huán)形緩沖區(qū)，允許進(jìn)程以生產(chǎn)者/消費(fèi)者的模型進(jìn)行通信先進(jìn)先出隊(duì)列創(chuàng)建時(shí)獲得一個(gè)固定大小的字節(jié)數(shù)，OS強(qiáng)制實(shí)施互斥命名管道和匿名管道消息有類(lèi)型的一段文本OS提供msgsnd和msgrcv系統(tǒng)調(diào)用每個(gè)進(jìn)程都有一個(gè)消息隊(duì)列，信箱發(fā)送者指定每個(gè)消息的類(lèi)型，接收者可以用作選擇依據(jù)內(nèi)存共享Unix提供進(jìn)程通信的速度最快的一種方式多個(gè)進(jìn)程共享一個(gè)公共內(nèi)存塊每個(gè)進(jìn)程都有讀寫(xiě)權(quán)限互斥約束，不屬于此機(jī)制，但由各個(gè)進(jìn)程提供信號(hào)量是semWait和semSignal的擴(kuò)展可同時(shí)進(jìn)行多個(gè)操作，且增量減量可大于1信號(hào)信號(hào)是用于向一個(gè)進(jìn)程通知發(fā)生異步事件的機(jī)制類(lèi)似于硬件中斷，但沒(méi)有優(yōu)先級(jí)小結(jié)死鎖原理資源類(lèi)型和資源分配圖死鎖條件處理死鎖方法死鎖預(yù)防死鎖避免：銀行家算法死鎖檢測(cè)：檢測(cè)算法習(xí)題復(fù)習(xí)題：3，7習(xí)題：5，6，15第五章習(xí)題1、寫(xiě)出信號(hào)量定義，semWait和semSignal原語(yǔ)，以及用信號(hào)量實(shí)現(xiàn)互斥的偽代碼。P.151-----圖5.3：semWait和semSignal原語(yǔ)P.153-----圖5.6：信號(hào)量實(shí)現(xiàn)互斥

2、假設(shè)一個(gè)閱覽室有100個(gè)座位，沒(méi)有座位時(shí)讀者在閱覽室外等待；每個(gè)讀者進(jìn)入閱覽室時(shí)都必須在閱覽室門(mén)口的一個(gè)登記本上登記座位號(hào)和姓名，然后閱覽，離開(kāi)閱覽室時(shí)要去掉登記項(xiàng)。每次只允許一個(gè)人登記或去掉登記。用信號(hào)量操作描述讀者的行為。設(shè)兩個(gè)信號(hào)量：constintn=/*讀者數(shù)*/count空位數(shù)，初值=100；mutex用于登記本的互斥使用，mutex=1。

voidreader(int

i){semWait(count);semWait(mutex);

登記；semSignal(mutex)；

閱覽；

semWait(mutex);

去掉登記；

semSignal(mutex)；

semSignal(count)；

離開(kāi)；}voidmain(){Parbegin(reader(1)，reader(2),…,reader(n));}3、設(shè)公共汽車(chē)上，司機(jī)和售票員活動(dòng)如下：

1）司機(jī)：?jiǎn)?dòng)汽車(chē)，正常行車(chē)，到站停車(chē)；

2）售票員：關(guān)車(chē)門(mén)，售票，開(kāi)門(mén)上下客。

用信號(hào)量操作描述司機(jī)和售票員的同步。設(shè)信號(hào)量：S1表示是否允許司機(jī)啟動(dòng)汽車(chē)（初值0）、S2表示是否允許售票員開(kāi)車(chē)門(mén)（初值0）。VoidDriver(){whileT{semWait(S1);

啟動(dòng)汽車(chē)；

正常行車(chē)；

到站停車(chē)；semSignal(S2);}}VoidConductor(){whileT{關(guān)車(chē)門(mén)；

semSignal(S1);

售票；semWait(S2);

開(kāi)門(mén)上下客；}}Voidmain(){parbegin(Driver(),Conductor());}4、(選做)獨(dú)木橋問(wèn)題：東、西向汽車(chē)過(guò)獨(dú)木橋。橋上無(wú)車(chē)時(shí)允許一方汽車(chē)過(guò)橋，待全部過(guò)完后才允許另一方汽車(chē)過(guò)橋。用信號(hào)量操作寫(xiě)出同步算法。(提示：參考讀者優(yōu)先的解法)設(shè)信號(hào)量pass表示可以上橋，初值1。東車(chē)和西車(chē)計(jì)數(shù)的整型變量count1和count2，初值均為0。保護(hù)count1和count2互斥訪問(wèn)的兩個(gè)信號(hào)量mutex1和mutex2，初值均為1。

P1：東車(chē){semWait(mutex1);count1++;if(count1==1)

semWait(pass);semSignal(mutex1);

過(guò)獨(dú)木橋;semWait(mutex1);

count1--;if(count1==0)

semSignal(pass);sem