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

1、死鎖一組相互競爭系統(tǒng)資源或進(jìn)行通信的進(jìn)程間的“永久”阻塞涉及兩個(gè)或多個(gè)進(jìn)程之間對(duì)資源需求的沖突無有效解決方法 常見：交通死鎖 可重用資源可重用資源+可消耗資源可消耗資源可重用資源可重用資源一次只能供一個(gè)進(jìn)程安全地使用，不會(huì)耗盡可剝奪資源：包括CPU、虛存、磁盤不可剝奪資源：打印機(jī)、文件、數(shù)據(jù)庫和信號(hào)量競爭不可剝奪資源，就會(huì)發(fā)生死鎖死鎖兩進(jìn)程競爭可重用資源可重用資源的例子p0p1q0q1p2q2策略：給系統(tǒng)設(shè)計(jì)施加關(guān)于資源請(qǐng)求順序的約束資源請(qǐng)求順序的約束可重用資源死鎖的另一個(gè)例子：內(nèi)存請(qǐng)求可分配空間200kb第二個(gè)請(qǐng)求時(shí)發(fā)生死鎖 解決：使用虛擬存儲(chǔ)消除死鎖可能性使用虛擬存儲(chǔ)消除死鎖可能性P1.

2、. . . .Request 80 Kbytes;Request 60 Kbytes;P2. . . . .Request 70 Kbytes;Request 80 Kbytes;可消耗資源可消耗資源可以被創(chuàng)建（生產(chǎn)）和銷毀（消耗） 的資源一個(gè)無阻塞的生產(chǎn)進(jìn)程可以創(chuàng)建任意數(shù)目的這類資源例子：中斷、信號(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);一個(gè)有向圖表示，描述資源和進(jìn)程狀態(tài)進(jìn)程：P，圓形

3、表示某類資源：R，方形表示具體資源：原點(diǎn)表示請(qǐng)求：Pi Rj分配：Rj PiP1P2R2 R1 互斥一次只有一個(gè)進(jìn)程可以使用一個(gè)資源，其他進(jì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è)資源 必必要要條條件件充充分分條條件件預(yù)防死鎖預(yù)防死鎖：消除某一個(gè)條件的出現(xiàn)避免死鎖避免死鎖：不破壞條件，允許進(jìn)程資源動(dòng)態(tài)分配，檢查狀態(tài)，保證不出現(xiàn)死鎖 檢測死鎖檢測死鎖：試圖檢測到死鎖的存在并恢復(fù)撤銷死鎖進(jìn)程剝奪資源互斥不可能禁止占有且等待要求進(jìn)程一次性地請(qǐng)求所有需

4、要的資源低效的進(jìn)程阻塞很長時(shí)間，以等待所有資源一個(gè)資源可能被占有很長時(shí)間，而不被使用并不知道自己所需的所有資源 不可搶占一個(gè)進(jìn)程申請(qǐng)新資源被拒絕時(shí)，必須釋放之前占有的資源操作系統(tǒng)搶占某個(gè)進(jìn)程，要求它釋放已占有的資源（不同優(yōu)先級(jí)）循環(huán)等待定義資源類型的線性順序A：Ri-Rj（ij) 死鎖預(yù)防-約束資源請(qǐng)求,至少破壞一個(gè)條件防止前三個(gè)條件，間接完成防止第四個(gè)條件，直接完成導(dǎo)致低效的資源利用和低效的進(jìn)程執(zhí)行死鎖避免允許三個(gè)必要條件明智選擇，確保永不會(huì)到達(dá)死鎖點(diǎn)，允許更多的并發(fā)需要知道將來的進(jìn)程資源請(qǐng)求的情況，以判斷該請(qǐng)求是否可能導(dǎo)致死鎖兩種方法進(jìn)程啟動(dòng)拒絕進(jìn)程啟動(dòng)拒絕：如果一個(gè)進(jìn)程的請(qǐng)求會(huì)導(dǎo)致死鎖，

5、不啟動(dòng)進(jìn)程資源分配拒絕資源分配拒絕：如果一個(gè)進(jìn)程增加的資源請(qǐng)求會(huì)導(dǎo)致死鎖，則不允許分配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)求都不能超過系統(tǒng)中該種資源的總量3. Aij=C(n+1)j+C.j 才啟動(dòng)新進(jìn)程Pn+1銀行家算法銀行家算法安全狀態(tài)：至少有一個(gè)資源分配序列不會(huì)導(dǎo)致死鎖, 即 C

6、ij-Aij=Vj不安全狀態(tài): 不存在任何安全序列RequestiCi-AiF退出TRequesti=ViT預(yù)分配資源Ai=Ai+ RequestiV=V- Requesti測試 分配資源FPi等待 不安全Pi等待，恢復(fù)原來值安全初始狀態(tài)初始狀態(tài)P2 運(yùn)行運(yùn)行P1 運(yùn)行運(yùn)行P3 運(yùn)行運(yùn)行51P 2請(qǐng)求1個(gè)R1和1個(gè)R3，是否安全？P1請(qǐng)求1個(gè)R1和1個(gè)R3，是否安全？全局?jǐn)?shù)據(jù)結(jié)構(gòu)資源分配算法測試安全算法（銀行家算法）必需事先聲明必需事先聲明每個(gè)進(jìn)程請(qǐng)求的最大資源；所討論的進(jìn)程必須是無關(guān)的，不存在同步不存在同步分配資源數(shù)目必須是固定的固定的占有資源時(shí)，進(jìn)程不能退出不限制資源訪問或約束進(jìn)程行為，只

7、要有可能，被請(qǐng)求的資源就被分配給進(jìn)程OS周期性地執(zhí)行一個(gè)算法檢測充分條件：循環(huán)等待循環(huán)等待好處：可以盡早發(fā)現(xiàn)死鎖缺點(diǎn)：耗費(fèi)相當(dāng)多的處理器時(shí)間死鎖檢測算法死鎖檢測算法標(biāo)記所有不會(huì)產(chǎn)生死鎖的進(jìn)程當(dāng)且僅達(dá)算法結(jié)束仍有進(jìn)程未標(biāo)記，則存在死鎖不能保證防止死鎖，只能確定當(dāng)前是否存在死鎖00011Available 步驟：步驟：1、標(biāo)記A矩陣中全為0的一行；2、初始化臨時(shí)向量W=V；3、查找未標(biāo)記的進(jìn)程i，其在請(qǐng)求矩陣Q中小于等于W，若無，終止 ；4、找到，標(biāo)記進(jìn)程i，并把A中相應(yīng)的第i行加到W中，并返回3。P4P3恢復(fù)（復(fù)雜度遞增）取消取消所有的死鎖進(jìn)程所有的死鎖進(jìn)程把每個(gè)死鎖進(jìn)程回滾到前面定義的某些檢查

8、點(diǎn)，重新啟動(dòng)所有進(jìn)程連續(xù)取消死鎖進(jìn)程直到不再存在死鎖連續(xù)搶占資源直到不再存在死鎖選擇原則：選擇原則：消耗的CPU時(shí)間最少產(chǎn)生的輸出最少剩下的時(shí)間最少分配的資源總量最少優(yōu)先級(jí)最低（防止饑餓） 把資源分成幾組不同的資源類預(yù)防資源類之間由于循環(huán)等待產(chǎn)生死鎖，可使用全面定義的線性排序策略在一個(gè)資源類中，使用該類資源最適合的算法對(duì)于每一類資源的策略可交換空間可交換空間：即外存，通過要求一次性分配所有請(qǐng)求的資源來預(yù)防死鎖，如果知道最大存儲(chǔ)需求，此策略合理進(jìn)程資源進(jìn)程資源：如文件等，死鎖避免很有效，或資源排序進(jìn)行預(yù)防內(nèi)存內(nèi)存：基于搶占的預(yù)防最適合。內(nèi)部資源內(nèi)部資源：如I/O通道，可以使用基于資源排序的預(yù)防策

9、略至多允許四人同時(shí)拿刀叉Semaphore fork5=1Semaphore room=4奇號(hào)人先拿左叉偶號(hào)人先拿右叉管道消息共享內(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í)施互斥命名管道和匿名管道消息有類型的一段文本OS提供msgsnd和msgrcv系統(tǒng)調(diào)用每個(gè)進(jìn)程都有一個(gè)消息隊(duì)列，信箱發(fā)送者指定每個(gè)消息的類型，接收者可以用作選擇依據(jù)內(nèi)存共享Unix提供進(jìn)程通信的速度最快的一種方式多個(gè)進(jìn)程共享一個(gè)公共內(nèi)存塊每個(gè)進(jìn)程都有讀寫權(quán)限 互斥約束，不屬于此機(jī)制，但由各個(gè)進(jìn)程提供信號(hào)量是semWait 和semSignal 的

10、擴(kuò)展可同時(shí)進(jìn)行多個(gè)操作，且增量減量可大于1信號(hào)信號(hào)是用于向一個(gè)進(jìn)程通知發(fā)生異步事件的機(jī)制類似于硬件中斷，但沒有優(yōu)先級(jí)死鎖原理資源類型和資源分配圖死鎖條件處理死鎖方法死鎖預(yù)防死鎖避免：銀行家算法死鎖檢測：檢測算法復(fù)習(xí)題：3，7習(xí)題：5，6，151、寫出信號(hào)量定義，semWait和semSignal原語，以及用信號(hào)量實(shí)現(xiàn)互斥的偽代碼。P. 151-圖圖5.3 ： semWait和和semSignal原語原語P. 153-圖圖5.6：信號(hào)量實(shí)現(xiàn)互斥：信號(hào)量實(shí)現(xiàn)互斥2、假設(shè)一個(gè)閱覽室有100個(gè)座位，沒有座位時(shí)讀者在閱覽室外等待；每個(gè)讀者進(jìn)入閱覽室時(shí)都必須在閱覽室門口的一個(gè)登記本上登記座位號(hào)和姓名，然后

11、閱覽，離開閱覽室時(shí)要去掉登記項(xiàng)。每次只允許一個(gè)人登記或去掉登記。用信號(hào)量操作描述讀者的行為讀者的行為。設(shè)兩個(gè)信號(hào)量：設(shè)兩個(gè)信號(hào)量： const int n=/*讀者數(shù)*/count 空位數(shù)，初值=100； mutex 用于登記本的互斥使用，mutex=1。 void reader(int i)semWait(count);semWait(mutex); 登記； semSignal(mutex)； 閱覽； semWait(mutex); 去掉登記； semSignal(mutex)； semSignal(count)； 離開； void main() Parbegin(reader(1)， re

12、ader(2),reader(n); 3、設(shè)公共汽車上，司機(jī)和售票員活動(dòng)如下： 1）司機(jī)：啟動(dòng)汽車，正常行車，到站停車； 2）售票員：關(guān)車門，售票，開門上下客。用信號(hào)量操作描述司機(jī)和售票員的同步。設(shè)信號(hào)量：S1表示是否允許司機(jī)啟動(dòng)汽車（初值0）、S2表示是否允許售票員開車門（初值0）。Void Driver()while T semWait(S1); 啟動(dòng)汽車； 正常行車； 到站停車； semSignal(S2); Void Conductor() while T 關(guān)車門； semSignal(S1); 售票； semWait(S2); 開門上下客； Void main() parbegin(

13、Driver(), Conductor(); 4、(選做)獨(dú)木橋問題：東、西向汽車過獨(dú)木橋。橋上無車時(shí)允許一方汽車過橋，待全部過完后才允許另一方汽車過橋。用信號(hào)量操作寫出同步算法。(提示：參考讀者優(yōu)先的解法)設(shè)信號(hào)量pass表示可以上橋，初值1。東車和西車計(jì)數(shù)的整型變量count1和count2，初值均為0。保護(hù)count1和count2互斥訪問的兩個(gè)信號(hào)量mutex1和mutex2，初值均為1。P1：東車 semWait(mutex1); count1+; if (count1=1) semWait(pass); semSignal(mutex1); 過獨(dú)木橋; semWait(mutex1); count1-; if (