操作系統(tǒng)第2部分進(jìn)程死鎖及經(jīng)典問題30409

1、經(jīng)典進(jìn)程互斥與同步問題經(jīng)典進(jìn)程互斥與同步問題 生產(chǎn)者/消費(fèi)者問題 讀者/寫者問題 哲學(xué)家就餐問題2.6 2.6 生產(chǎn)者生產(chǎn)者/ /消費(fèi)者問題消費(fèi)者問題3生產(chǎn)者/消費(fèi)者問題 有一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)（記錄、字符），并放置在緩沖區(qū)中 有一個(gè)或多個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)，每次取一項(xiàng) 每次只能有一個(gè)代理（生產(chǎn)者或消費(fèi)者）可以訪問緩沖區(qū) 假設(shè)緩沖區(qū)是無限的 生產(chǎn)者、消費(fèi)者的過程為：4producer:while (true) /* produce item v */bin = v;in+; 生產(chǎn)者生產(chǎn)者/消費(fèi)者問題5consumer:while (true) while (in = out)

2、 /*do nothing */;w = bout;out+; /* consume item w */消費(fèi)者生產(chǎn)者/消費(fèi)者問題6生產(chǎn)者/消費(fèi)者問題 指針in和out初始化指向緩沖區(qū)的第一個(gè)存儲單元。 生產(chǎn)者通過in指針向存儲單元存放數(shù)據(jù)，一次存放一條數(shù)據(jù)，且in指針向后移一個(gè)位置。 消費(fèi)者從緩沖區(qū)中逐條取走數(shù)據(jù)，一次取一條數(shù)據(jù)，相應(yīng)的存儲單元變?yōu)椤翱铡?。每取走一條數(shù)據(jù)，out指針向后移一個(gè)存儲單元位置。 試想，如果不控制生產(chǎn)者與消費(fèi)者，將會產(chǎn)生什么結(jié)果？ 生產(chǎn)者和消費(fèi)者可能同時(shí)進(jìn)入緩沖區(qū)，甚至可能同時(shí)讀/寫一個(gè)存儲單元，將導(dǎo)致執(zhí)行結(jié)果不確定。 這顯然是不允許的。必須使生產(chǎn)者和消費(fèi)者互斥進(jìn)入緩

3、沖區(qū)。即，某時(shí)刻只允許一個(gè)實(shí)體（生產(chǎn)者或消費(fèi)者）訪問緩沖區(qū)，生產(chǎn)者互斥消費(fèi)者和其它任何生產(chǎn)者。10生產(chǎn)者/消費(fèi)者問題 使用二元信號量來實(shí)現(xiàn) 緩沖區(qū)數(shù)量無限 整型變量n（=in-out）：緩沖區(qū)中的項(xiàng)數(shù) 信號量s：緩沖區(qū)訪問互斥 信號量delay：消費(fèi)者在空緩沖區(qū)時(shí)的等待隊(duì)列 代碼如下：11 是否正確？ 可能會產(chǎn)生什么問題？ 見P155 表5.4(下頁)應(yīng)該阻塞應(yīng)該阻塞而沒有阻塞而沒有阻塞少執(zhí)行了一個(gè)少執(zhí)行了一個(gè)semWaitB(delay)13解決辦法一：?14解決辦法二：增加增加一個(gè)一個(gè)輔助輔助變量變量15生產(chǎn)者/消費(fèi)者問題 使用信號量來實(shí)現(xiàn) 緩沖區(qū)數(shù)量無限 信號量n：緩沖區(qū)中項(xiàng)目個(gè)數(shù) 信號

4、量s：緩沖區(qū)訪問權(quán)限 代碼如下：16生產(chǎn)者/消費(fèi)者問題17緩沖區(qū)的數(shù)量有限，為nproducer:while (true) /* produce item v */while (in + 1) % n = out) /* do nothing */;bin = v;in = (in + 1) % n生產(chǎn)者/消費(fèi)者問題18緩沖區(qū)的數(shù)量有限，為nconsumer:while (true) while (in = out)/* do nothing */;w = bout;out = (out + 1) % n;/* consume item w */生產(chǎn)者/消費(fèi)者問題19緩沖區(qū)的數(shù)量有限，為緩沖區(qū)

5、的數(shù)量有限，為n生產(chǎn)者/消費(fèi)者問題20生產(chǎn)者/消費(fèi)者問題 使用信號量來實(shí)現(xiàn) 緩沖區(qū)數(shù)量有限（=sizeofbuffer） 信號量n：緩沖區(qū)中項(xiàng)目個(gè)數(shù) 信號量s：緩沖區(qū)訪問權(quán)限 信號量e：緩沖區(qū)中空閑空間的數(shù)量 代碼如下：利用信號量實(shí)現(xiàn)生產(chǎn)者利用信號量實(shí)現(xiàn)生產(chǎn)者/消費(fèi)者同步與互斥消費(fèi)者同步與互斥(a) 生產(chǎn)者生產(chǎn)者(b) 消費(fèi)者消費(fèi)者無無阻塞阻塞等待資源等待資源被喚醒被喚醒否否被喚醒被喚醒是 否 有 數(shù)是 否 有 數(shù)據(jù)單元據(jù)單元消費(fèi)數(shù)據(jù)消費(fèi)數(shù)據(jù)是否是否可用可用取一條數(shù)據(jù)取一條數(shù)據(jù)有有是是歸還使用權(quán)歸還使用權(quán)空單元加空單元加1喚醒一個(gè)生產(chǎn)者喚醒一個(gè)生產(chǎn)者阻塞阻塞等待資源等待資源阻塞阻塞等待使用權(quán)等

6、待使用權(quán)被喚醒被喚醒否否被喚醒被喚醒是否有空是否有空存儲單元存儲單元生產(chǎn)一條數(shù)據(jù)生產(chǎn)一條數(shù)據(jù)是否是否可用可用有有存入一條數(shù)據(jù)存入一條數(shù)據(jù)歸還使用權(quán)歸還使用權(quán)是是數(shù)據(jù)單元加數(shù)據(jù)單元加1喚醒一個(gè)消費(fèi)者喚醒一個(gè)消費(fèi)者圖圖 生產(chǎn)者生產(chǎn)者/消費(fèi)者執(zhí)行流程圖消費(fèi)者執(zhí)行流程圖無無阻塞阻塞等待使用權(quán)等待使用權(quán)注意注意1. 進(jìn)程應(yīng)該先申請資源信號量，再申請互斥信號量，順序不能顛倒。2. 對任何信號量的semWait與semSignal操作必須配對。同一進(jìn)程中的多對semWait與semSignal語句只能嵌套，不能交叉。3. 對同一個(gè)信號量的semWait與semSignal可以不在同一個(gè)進(jìn)程中。4. semW

7、ait與semSignal語句不能顛倒順序，semWait語句一定先于semSignal語句。 允許多個(gè)讀者進(jìn)程可以同時(shí)讀數(shù)據(jù)； 不允許多個(gè)寫者進(jìn)程同時(shí)寫數(shù)據(jù)，即只能互斥寫數(shù)據(jù)； 若有寫者進(jìn)程正在寫數(shù)據(jù)，則不允許讀者進(jìn)程讀數(shù)據(jù)。 當(dāng)一個(gè)讀者正在讀數(shù)據(jù)時(shí)，另一個(gè)讀者也需要讀數(shù)據(jù)，應(yīng)允許第二個(gè)讀者進(jìn)入，同理第三個(gè)及隨后更多的讀者都被允許進(jìn)入。 現(xiàn)在假設(shè)一個(gè)寫者到來，由于寫操作是排他的，所以它不能訪問數(shù)據(jù)，需要阻塞等待。如果一直都有新的讀者陸續(xù)到來，寫者的寫操作將被嚴(yán)重推遲。 該方法稱為“讀者優(yōu)先”。即，一旦有讀者正在讀數(shù)據(jù)，允許多個(gè)讀者同時(shí)進(jìn)入讀數(shù)據(jù)，只有當(dāng)全部讀者退出，才允許寫者進(jìn)入寫數(shù)據(jù)。用信

8、號量實(shí)現(xiàn)的具體過程見圖讀讀進(jìn)進(jìn)程程具具有有優(yōu)優(yōu)先先權(quán)權(quán) 寫進(jìn)程具有優(yōu)先權(quán)寫進(jìn)程具有優(yōu)先權(quán)34管程使用信號的管程 semWait、semSignal可能分布于整個(gè)程序中，難以控制 管程（Monitor）是一個(gè)程序設(shè)計(jì)語言結(jié)構(gòu)，它提供與信號量同樣的功能，但更易于操作 管程是一個(gè)軟件模塊 一個(gè)或多個(gè)過程 一個(gè)初始化序列 局部數(shù)據(jù)35使用信號的管程 主要特點(diǎn)： 局部數(shù)據(jù)只能被管程的過程訪問，任何外部過程都不能訪問 一個(gè)進(jìn)程通過調(diào)用管程的一個(gè)過程進(jìn)入管程 在任何時(shí)候，只能有一個(gè)進(jìn)程在管程中執(zhí)行，調(diào)用管程的任何其它進(jìn)程都要被掛起，以等待進(jìn)程變?yōu)榭捎霉艹讨械臄?shù)據(jù)變量每次只能被一個(gè)進(jìn)程訪問到互斥36 管程通過

9、使用條件變量提供對同步的支持 條件變量包含在管程中 只能在管程中被訪問 兩個(gè)操作條件變量的函數(shù)： cwait（c）：調(diào)用進(jìn)程的執(zhí)行在條件c上掛起，管程現(xiàn)在可被另一個(gè)進(jìn)程使用 csignal（c）：恢復(fù)在cwait之后為某條件而掛起的進(jìn)程的執(zhí)行（選一）。 與信號量的semWait、semSignal不同 如果在管程中的一個(gè)進(jìn)程發(fā)信號，但沒有在這個(gè)條件變量上等待的任務(wù)，則該信號丟失使用信號的管程37圖圖5.15 管程的結(jié)構(gòu)管程的結(jié)構(gòu)csignal喚醒喚醒csignal喚醒喚醒使用信號的管程38 使用管程解決生產(chǎn)者/消費(fèi)者問題 緩沖區(qū)的數(shù)量為N在管程中定義使用信號的管程39管程代碼 條件變量：not

10、full、notempty使用信號的管程40 與信號量比較 管程 管程負(fù)責(zé)互斥 程序員負(fù)責(zé)同步 把適當(dāng)?shù)腸wait和csignal放在管程中 信號量 程序員負(fù)責(zé)互斥 程序員負(fù)責(zé)同步使用信號的管程2.9 2.9 互斥與同步解決方法之五互斥與同步解決方法之五消息傳遞消息傳遞發(fā)送進(jìn)程發(fā)送進(jìn)程接收進(jìn)程接收進(jìn)程郵件服務(wù)器郵件服務(wù)器接收進(jìn)程接收進(jìn)程發(fā)送進(jìn)程發(fā)送進(jìn)程終端用戶終端用戶郵件郵件郵件郵件發(fā)送進(jìn)程發(fā)送進(jìn)程接收進(jìn)程接收進(jìn)程郵件服務(wù)器郵件服務(wù)器接收進(jìn)程接收進(jìn)程發(fā)送進(jìn)程發(fā)送進(jìn)程終端用戶終端用戶郵件郵件圖圖 電子郵件的發(fā)送與接收過程電子郵件的發(fā)送與接收過程43消息傳遞 通過消息實(shí)現(xiàn)互斥與同步 兩個(gè)消息原語：

11、send (destination, message)receive (source, message)44同步 發(fā)送者執(zhí)行send原語 接受者執(zhí)行receive原因 發(fā)送者和執(zhí)行者阻塞或不阻塞 排列組合22=4種 send阻塞、receive阻塞 send阻塞、receive不阻塞 send不阻塞、receive阻塞 send不阻塞、receive不阻塞 是否全部可行？會產(chǎn)生什么問題？45尋址 直接尋址 send原語包括目標(biāo)進(jìn)程ID receive原語事先知道源進(jìn)程ID receive原語通過source參數(shù)知道源進(jìn)程ID46 間接尋址 消息發(fā)送到臨時(shí)保存這些消息的隊(duì)列組成的一個(gè)共享數(shù)據(jù)結(jié)構(gòu)

12、 這些隊(duì)列稱為信箱（mailbox） 一個(gè)進(jìn)程發(fā)送消息到信箱，另一個(gè)進(jìn)程從信箱獲取消息尋址47尋址圖5.18 間接的進(jìn)程通信48消息格式49排隊(duì)原則 先進(jìn)先出（FIFO） 優(yōu)先級 允許接受者檢查消息來選擇 例如，當(dāng)進(jìn)程執(zhí)行過程中需要打印輸出，通常讓打印任務(wù)排隊(duì)等待，而請求打印的進(jìn)程無須阻塞等待打印完成。即，每當(dāng)進(jìn)程需要打印時(shí)，都可以以消息形式發(fā)出請求，然后繼續(xù)執(zhí)行。 “不阻塞發(fā)送”方式容易導(dǎo)致消息的無限發(fā)送。無限發(fā)送消息會消耗處理機(jī)時(shí)間，且由于消息需要占用內(nèi)存的消息緩沖區(qū)，無限發(fā)送消息也會消耗其它系統(tǒng)資源。 設(shè)計(jì)并發(fā)程序時(shí)，若采用“不阻塞發(fā)送”方式，就必須在程序中考慮讓接收進(jìn)程發(fā)回應(yīng)答消息，證

13、實(shí)其是否收到消息，這將增加程序設(shè)計(jì)的難度。 使用消息的互斥 “空”消息：代表一條消息體為“空”，但具有消息頭的“真正”的一條消息，不是沒有消息。 當(dāng)?shù)谝粋€(gè)希望進(jìn)入臨界區(qū)的進(jìn)程執(zhí)行receive(box,msg)語句時(shí)，從郵箱box中接收了這條“空”消息，進(jìn)入臨界區(qū)執(zhí)行。這時(shí)，郵箱box變?yōu)椤翱铡?，即沒有消息。其后執(zhí)行receive(box,msg)語句希望進(jìn)入臨界區(qū)的進(jìn)程被阻塞。 當(dāng)進(jìn)入臨界區(qū)的進(jìn)程執(zhí)行完臨界區(qū)的代碼，退出臨界區(qū)時(shí)，執(zhí)行send(box,msg)語句，將這條“空”消息歸還給郵箱box，并喚醒一個(gè)阻塞進(jìn)程，使其取走這條消息，進(jìn)入臨界區(qū)執(zhí)行。 可見，控制進(jìn)程互斥進(jìn)入臨界區(qū)的這條消息

14、本身可以不含任何有用的內(nèi)容，它僅被當(dāng)作進(jìn)程能否進(jìn)入臨界區(qū)的一種憑證，或令牌。 只要保證郵箱中最多只有一條消息，就能保證只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，從而實(shí)現(xiàn)進(jìn)程互斥使用臨界資源。 如果生產(chǎn)者生產(chǎn)數(shù)據(jù)的速度比消費(fèi)者消費(fèi)數(shù)據(jù)的速度快，則所有的“空”消息最終都將被填滿，于是生產(chǎn)者將因?yàn)榻邮詹坏健翱铡毕⒍蛔枞却M(fèi)者取走帶有數(shù)據(jù)的消息，然后返回一條“空”消息。 如果消費(fèi)者消費(fèi)數(shù)據(jù)的速度更快，則消費(fèi)者將因?yàn)榻邮詹坏健皵?shù)據(jù)”消息而阻塞，直到生產(chǎn)者生產(chǎn)并發(fā)送來一條“數(shù)據(jù)”消息。 使用消息的互斥58作業(yè) 復(fù)習(xí)題 5.8、5.11、5.13 習(xí)題 5.2、5.3 習(xí)題5.10 習(xí)題5.13、5.142.10

15、 2.10 進(jìn)程死鎖進(jìn)程死鎖 進(jìn)程的并發(fā)控制不僅要控制若干進(jìn)程的同步與互斥，確保進(jìn)程之間正常通信，還需要解決進(jìn)程死鎖問題。 一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個(gè)系統(tǒng)將處于癱瘓狀態(tài)，造成系統(tǒng)“死機(jī)”。交通中的死鎖現(xiàn)象 Process P Process Q Get A Get B Get B Get A Release A Release B Release B Release A 獲得獲得A獲得獲得B釋放釋放A釋放釋放B獲得獲得B獲得獲得A釋放釋放B釋放釋放AP的推進(jìn)方向的推進(jìn)方向Q的推進(jìn)方向的推進(jìn)方向Q請求請求AQ請求請求BP請求請求

16、AP請求請求B死鎖區(qū)死鎖區(qū)P、Q都申請都申請AP、Q都申請都申請B圖圖2.49 2.49 進(jìn)程競爭資源且推進(jìn)順序不當(dāng)可能產(chǎn)生死鎖進(jìn)程競爭資源且推進(jìn)順序不當(dāng)可能產(chǎn)生死鎖是否可能死鎖？ 死鎖（deadlock）概念可以描述為，多個(gè)進(jìn)程因?yàn)楦偁庂Y源，或執(zhí)行時(shí)推進(jìn)的順序不當(dāng)，或相互通信而永久阻塞現(xiàn)象，如果沒有外力作用，這種現(xiàn)象將永遠(yuǎn)保持下去。 若系統(tǒng)出現(xiàn)死鎖，必須有相應(yīng)的措施進(jìn)行解除。當(dāng)然，如果能提前預(yù)防和避免死鎖的出現(xiàn)，將能提高系統(tǒng)的運(yùn)行效率。 可重用資源死鎖例（兩個(gè)進(jìn)程競爭兩個(gè)資源） 如果每個(gè)進(jìn)程占有一個(gè)資源并申請另外一個(gè)資源 執(zhí)行軌跡：p0p1q0q1p2q2 死鎖 R1P1P2R2占用占用占用

17、占用申請申請申請申請圖圖2.50 2.50 進(jìn)程循環(huán)等待：死鎖進(jìn)程循環(huán)等待：死鎖 避免死鎖 指，當(dāng)進(jìn)程申請資源時(shí)，需要首先判斷（預(yù)測），如果滿足這次資源的請求是否會導(dǎo)致死鎖，可能導(dǎo)致死鎖的資源請求將會被拒絕，讓請求資源的進(jìn)程阻塞等待，直到其所需的資源可分配為止。該方法并不嚴(yán)格限制產(chǎn)生死鎖的四個(gè)必要條件，以提高系統(tǒng)資源的利用率。 .檢測并解除死鎖 指，當(dāng)進(jìn)程申請資源時(shí)，不進(jìn)行任何限制，即允許死鎖發(fā)生。但，要求系統(tǒng)定期或不定期檢測是否有死鎖發(fā)生。當(dāng)檢測到死鎖時(shí)，再力求解除死鎖。實(shí)踐證明，該方法可進(jìn)一步提高資源利用率。 產(chǎn)生死鎖的第一個(gè)條件是“互斥”，而“互斥使用”是臨界資源固有的屬性，保證進(jìn)程互斥

18、訪問臨界資源是必要的。不能因?yàn)榛コ鈺?dǎo)致死鎖而禁止互斥。為了禁止“占有且等待”條件，系統(tǒng)將要求所有進(jìn)程一次性地申請其所需的全部資源。不合理第一，降低了系統(tǒng)吞吐量和資源利用率。第二，浪費(fèi)資源。例如，大家都熟悉的條件判斷語句，程序中往往少不了它，在程序?yàn)閳?zhí)行之前，無法判斷條件為真，還是為假。 指，當(dāng)一個(gè)已經(jīng)獲得了某些資源的進(jìn)程，再申請的新資源不能立即得到滿足時(shí)，必須釋放其已獲得的所有資源，不論是何種資源。 這種預(yù)防死鎖的策略實(shí)現(xiàn)起來比較復(fù)雜，而且要付出很大代價(jià)。為了避免進(jìn)程申請資源形成環(huán)路，首先將系統(tǒng)中的所有資源按類型進(jìn)行線性排序，并賦予不同的序號。 所有進(jìn)程對資源的請求，必須嚴(yán)格按資源序號遞增的

19、次序提出，這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路。 事實(shí)上，采用這種策略時(shí)，總有一個(gè)進(jìn)程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，因此進(jìn)程可一直向前推進(jìn)。 較之前兩種策略，不論是資源利用率，還是系統(tǒng)吞吐量，都有顯著的改善。 但也存在嚴(yán)重問題第一，為系統(tǒng)中各類資源分配的序號必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加；第二，會經(jīng)常發(fā)生作業(yè)使用的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源浪費(fèi)。第三，增加了程序設(shè)計(jì)難度。 預(yù)防死鎖限制條件太強(qiáng)，不利于提高系統(tǒng)吞吐量和資源利用率，而且增加了程序設(shè)計(jì)難度。因此，該方法在死鎖解決中不常用。 避免死鎖方法通過資源分配之前預(yù)測是否會導(dǎo)致死鎖，決定是否進(jìn)行

20、此次資源分配。只有不會導(dǎo)致死鎖的資源請求才實(shí)施分配，否則，讓請求進(jìn)程阻塞等待。 首先介紹系統(tǒng)的兩個(gè)狀態(tài)：安全狀態(tài)和不安全狀態(tài)。 是指系統(tǒng)能按某種進(jìn)程順序，如 ，分別為這n個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都能順利完成。 稱序列為安全序列 若系統(tǒng)不存在這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 若系統(tǒng)處于安全狀態(tài)，且按照某個(gè)安全序列分配資源，可以保證系統(tǒng)不會出現(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)有三個(gè)進(jìn)程P1、P2和P3，共有14臺打印機(jī)。 進(jìn)程P1總共要求12臺打印機(jī)，

21、P2和P3分別要求4臺和9臺。 假設(shè)T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和4臺，尚有3臺空閑未分，如表2.3所示：進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需要還需要可用可用P11257 3P2422P3945T0時(shí)刻系統(tǒng)是安全的時(shí)刻系統(tǒng)是安全的,存在一個(gè)安全序列存在一個(gè)安全序列 該算法可用于銀行發(fā)放一筆貸款前，預(yù)測該筆貸款是否會引起銀行資金周轉(zhuǎn)問題。 這里，銀行的資金就類似于計(jì)算機(jī)系統(tǒng)的資源，貸款業(yè)務(wù)類似于計(jì)算機(jī)的資源分配。銀行家算法能預(yù)測一筆貸款業(yè)務(wù)對銀行是否是安全的，該算法也能預(yù)測一次資源分配對計(jì)算機(jī)系統(tǒng)是否是安全的。 為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。 1. 可利

22、用資源向量Available 是一個(gè)具有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用資源的數(shù)目，其初始值為系統(tǒng)中該類資源的最大可用數(shù)目。其值將隨著該類資源的分配與回收而動(dòng)態(tài)改變。Availablej = k,表示系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。 2. 最大需求矩陣Max 是一個(gè)n * m的矩陣，定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。Max(i,j) = k，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為k個(gè)。 分配矩陣Allocation 是一個(gè)n * m的矩陣，定義了 系 統(tǒng) 中 每 一 類 資 源 的 數(shù) 量 。 例 如 ，Allocation(i,j) = k,表示進(jìn)程i當(dāng)前已分得

23、Rj類資源的數(shù)目為k個(gè)。 需求矩陣Need 是一個(gè)n * m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。例如，Needi,j = k,表示進(jìn)程i還需要Rj類資源k個(gè)，方能完成其任務(wù)。設(shè)Requesti是進(jìn)程Pi的請求向量。Requestij = k,表示進(jìn)程Pi需要k個(gè)Rj類資源。當(dāng)進(jìn)程Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：1. 如果，Requesti Needi,則轉(zhuǎn)向步驟2；否則，出錯(cuò)2. 如果，Requesti Available,則轉(zhuǎn)向步驟3；否則，表示尚無足夠資源可供分配，進(jìn)程Pi必須阻塞等待。3. 系統(tǒng)試探性地將Pi申請的資源分配給它，并修改下列數(shù)據(jù)結(jié)構(gòu)中的值：Availab

24、le :=Availale - Requesti; Allocation := Allocation + Requesti; Needi := Needi-Requesti;4 系統(tǒng)利用安全性算法，檢查此次資源分配以后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，完成本次資源分配；否則，試探分配失效，讓進(jìn)程Pi阻塞等待。 （1）設(shè)置兩個(gè)工作向量設(shè)置一個(gè)數(shù)組Finishn。當(dāng)FinishiTrue（0 i n，n為系統(tǒng)中的進(jìn)程數(shù)）時(shí),表示進(jìn)程Pi可以獲得其所需的全部資源,而順利執(zhí)行完成。 設(shè)置一個(gè)臨時(shí)向量Work，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的資源的集合。安全性算法剛開始執(zhí)行時(shí)，W

25、ork := Available （2）從進(jìn)程集合中找到一個(gè)滿足下列條件的進(jìn)程： Finishi = false； 并且 Need Work；若找到滿足該條件的進(jìn)程，則執(zhí)行步驟（3），否則執(zhí)行步驟（4）；（3） 當(dāng)進(jìn)程Pi獲得資源后，將順利執(zhí)行直至完成，并釋放其所擁有的全部資源，故應(yīng)執(zhí)行以下操作：Work := Work + Allocatoioni； 以及Finishi := True；轉(zhuǎn)向步驟（2）； T0時(shí)刻的資源分配情況 假定系統(tǒng)中有四個(gè)進(jìn)程P1,P2,P3,P4和三種類型的資源R1,R2,R3，每一種資源的數(shù)量分別為9、3、6，T0時(shí)刻的資源分配情況如表2.4所示： 進(jìn)進(jìn)程程資資源源

26、MaxAllocation NeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613612001P3314211103P4422002420利用安全性算法，分析T0時(shí)刻的資源分配情況，可得如表2.5所示的信息。從T0時(shí)刻的安全性分析可知，T0時(shí)刻存在著一個(gè)安全序列,故T0時(shí)刻系統(tǒng)是安全的。 進(jìn)進(jìn)程程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623trueP1623222100723trueP4723420002725TrueP3725

27、103211936True 假設(shè)T0時(shí)刻，進(jìn)程P1申請資源，其請求向量為Request1(0,0,1),系統(tǒng)按銀行家算法進(jìn)行檢查：Request1 (0,0,1) Need1(2,2,2)，且Request1 (0,0,1) Available (0,1,1) 故 ， 系 統(tǒng) 試 探 性 地 為 P 1 分 配 資 源 ， 并 修 改Available,Allocation1和Need1向量如表2.6所示。 進(jìn)程進(jìn)程AllocationNeedAvailableR1R2R3R1R2R3R1R2R3 P1101221010 P2612001 P3211103 P4002420 利用安全性算法檢查

28、此時(shí)系統(tǒng)是否安全:此時(shí)，系統(tǒng)的可用資源向量為Available（0,1,0），比較各進(jìn)程的需求向量Need，系統(tǒng)不能滿足任何進(jìn)程的資源請求，系統(tǒng)進(jìn)入不安全狀態(tài)。所以，P1請求的資源不能分配，只能讓進(jìn)程P1阻塞等待。 避免死鎖不象預(yù)防死鎖那樣需要?jiǎng)儕Z進(jìn)程已獲得的資源，或重新執(zhí)行進(jìn)程。而且，避免死鎖比預(yù)防死鎖施加的限制條件要弱得多 但它仍然有限制條件： a)預(yù)先必須申明每個(gè)進(jìn)程需要的資源總量； b)進(jìn)程之間相互獨(dú)立，其執(zhí)行順序取決于系統(tǒng)安全，而非進(jìn)程間的同步要求； c)系統(tǒng)必須提供固定數(shù)量的資源供進(jìn)程使用 d)若進(jìn)程占有系統(tǒng)資源，則不能讓其退出系統(tǒng) 假設(shè)T0時(shí)刻，進(jìn)程P4申請資源，其請求向量為Request4(1,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查：Request4 (1,2,0) Need4(4,2,0)，且Request4 (1,2,0) Available (0,1,1) P4的請求向量超過系統(tǒng)的可用資源向量，