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

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

2、. . . .Request 80 Kbytes;Request 60 Kbytes;P2. . . . .Request 70 Kbytes;Request 80 Kbytes;可消耗資源可消耗資源可以被創(chuàng)建（生產(chǎn)）和銷毀（消耗） 的資源一個無阻塞的生產(chǎn)進(jìn)程可以創(chuàng)建任意數(shù)目的這類資源例子：中斷、信號、消息和I/O緩沖區(qū)中的信息接收信息信息被阻塞（receive阻塞），出現(xiàn)死鎖-難以發(fā)現(xiàn)接收受阻，死鎖出現(xiàn)P1. . . . .Receive(P2);Send(P2, M1);P2. . . . .Receive(P1);Send(P1, M2);一個有向圖表示，描述資源和進(jìn)程狀態(tài)進(jìn)程：P，圓形

3、表示某類資源：R，方形表示具體資源：原點表示請求：Pi Rj分配：Rj PiP1P2R2 R1 互斥一次只有一個進(jìn)程可以使用一個資源，其他進(jìn)程不能訪問占有且等待當(dāng)一個進(jìn)程等待其他進(jìn)程時，繼續(xù)占有已有資源不可搶占不能強(qiáng)行搶占進(jìn)程已占有資源循環(huán)等待前三個條件的潛在結(jié)果存在一個封閉的進(jìn)程鏈，使每個進(jìn)程至少占有此鏈中下一個進(jìn)程所需要的一個資源 必必要要條條件件充充分分條條件件預(yù)防死鎖預(yù)防死鎖：消除某一個條件的出現(xiàn)避免死鎖避免死鎖：不破壞條件，允許進(jìn)程資源動態(tài)分配，檢查狀態(tài)，保證不出現(xiàn)死鎖 檢測死鎖檢測死鎖：試圖檢測到死鎖的存在并恢復(fù)撤銷死鎖進(jìn)程剝奪資源互斥不可能禁止占有且等待要求進(jìn)程一次性地請求所有需

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

5、不啟動進(jìn)程資源分配拒絕資源分配拒絕：如果一個進(jìn)程增加的資源請求會導(dǎo)致死鎖，則不允許分配Resource=(R1,R2,Rm): 系統(tǒng)中每種資源的總量Available=V=（V1,V2,Vm):未分配給進(jìn)程的每種資源的總量Claim=C= :每個進(jìn)程對每種資源的最大需求Allocation=A= :顯示每個進(jìn)程當(dāng)前的資源分配情況1. Rj=Vj+A.j 所有資源或者可用，或者已經(jīng)被分配2. Cij=Ri 任何一個進(jìn)程對任一種資源的請求都不能超過系統(tǒng)中該種資源的總量3. Aij=C(n+1)j+C.j 才啟動新進(jìn)程Pn+1銀行家算法銀行家算法安全狀態(tài)：至少有一個資源分配序列不會導(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請求1個R1和1個R3，是否安全？P1請求1個R1和1個R3，是否安全？全局?jǐn)?shù)據(jù)結(jié)構(gòu)資源分配算法測試安全算法（銀行家算法）必需事先聲明必需事先聲明每個進(jìn)程請求的最大資源；所討論的進(jìn)程必須是無關(guān)的，不存在同步不存在同步分配資源數(shù)目必須是固定的固定的占有資源時，進(jìn)程不能退出不限制資源訪問或約束進(jìn)程行為，只

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

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

9、略至多允許四人同時拿刀叉Semaphore fork5=1Semaphore room=4奇號人先拿左叉偶號人先拿右叉管道消息共享內(nèi)存信號量信號管道環(huán)形緩沖區(qū)，允許進(jìn)程以生產(chǎn)者/消費(fèi)者的模型進(jìn)行通信先進(jìn)先出隊列創(chuàng)建時獲得一個固定大小的字節(jié)數(shù)，OS強(qiáng)制實施互斥命名管道和匿名管道消息有類型的一段文本OS提供msgsnd和msgrcv系統(tǒng)調(diào)用每個進(jìn)程都有一個消息隊列，信箱發(fā)送者指定每個消息的類型，接收者可以用作選擇依據(jù)內(nèi)存共享Unix提供進(jìn)程通信的速度最快的一種方式多個進(jìn)程共享一個公共內(nèi)存塊每個進(jìn)程都有讀寫權(quán)限 互斥約束，不屬于此機(jī)制，但由各個進(jìn)程提供信號量是semWait 和semSignal 的

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

11、閱覽，離開閱覽室時要去掉登記項。每次只允許一個人登記或去掉登記。用信號量操作描述讀者的行為讀者的行為。設(shè)兩個信號量：設(shè)兩個信號量： 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ī)和售票員活動如下： 1）司機(jī)：啟動汽車，正常行車，到站停車； 2）售票員：關(guān)車門，售票，開門上下客。用信號量操作描述司機(jī)和售票員的同步。設(shè)信號量：S1表示是否允許司機(jī)啟動汽車（初值0）、S2表示是否允許售票員開車門（初值0）。Void Driver()while T semWait(S1); 啟動汽車； 正常行車； 到站停車； semSignal(S2); Void Conductor() while T 關(guān)車門； semSignal(S1); 售票； semWait(S2); 開門上下客； Void main() parbegin(

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