【正文】 防死鎖限制條件太強(qiáng) ， 不利于提高系統(tǒng)吞吐量和資源利用率 ， 而且增加了程序設(shè)計(jì)難度 。 因此 ，該方法在死鎖解決中不常用 。 ? 避免死鎖方法通過(guò)資源分配之前預(yù)測(cè)是否會(huì)導(dǎo)致死鎖 ， 決定是否進(jìn)行此次資源分配 。 只有不會(huì)導(dǎo)致死鎖的資源請(qǐng)求才實(shí)施分配 ， 否則 ， 讓請(qǐng)求進(jìn)程阻塞等待 。 ? 首先介紹系統(tǒng)的兩個(gè)狀態(tài)：安全狀態(tài)和不安全狀態(tài) 。 安全狀態(tài) vs. 不安全狀態(tài) ? 是指系統(tǒng)能按某種進(jìn)程順序 ， 如 P1，P2,… ， Pn ， 分別為這 n個(gè)進(jìn)程分配其所需資源 ， 直至最大需求 ， 使每個(gè)進(jìn)程都能順利完成 。 ? 稱 P1， P2， … ， Pn序列為安全序列 ? 若系統(tǒng)不存在這樣一個(gè)安全序列 ， 則稱系統(tǒng)處于不安全狀態(tài) 。 安全狀態(tài) vs. 不安全狀態(tài) ? 若系統(tǒng)處于安全狀態(tài) ， 且按照某個(gè)安全序列分配資源 ， 可以保證系統(tǒng)不會(huì)出現(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) 。 經(jīng)典進(jìn)程互斥與同步問題 ? 生產(chǎn)者 /消費(fèi)者問題 ? 讀者 /寫者問題 ? 哲學(xué)家進(jìn)餐問題 ? 生產(chǎn)者與消費(fèi)者是一個(gè)廣義的概念，可以代表一類具有相同屬性的進(jìn)程。 ? 生產(chǎn)者和消費(fèi)者進(jìn)程共享一個(gè)大小固定的緩沖區(qū)，其中，一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)數(shù)據(jù)，并將生產(chǎn)的數(shù)據(jù)存入緩沖區(qū)，并有一個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)。 (a) 生產(chǎn)者 (b) 消費(fèi)者 無(wú) 阻塞 等待資源 被喚醒 否 被喚醒 是否有數(shù)據(jù)單元 消費(fèi)數(shù)據(jù) 是否 可用 取一條數(shù)據(jù) 有 是 歸還使用權(quán) 空單元加 1 喚醒一個(gè)生產(chǎn)者 阻塞 等待資源 阻塞 等待使用權(quán) 被喚醒 否 被喚醒 是否有空 存儲(chǔ)單元 生產(chǎn)一條數(shù)據(jù) 是否 可用 有 存入一條數(shù)據(jù) 歸還使用權(quán) 是 數(shù)據(jù)單元加 1 喚醒一個(gè)消費(fèi)者 圖 生產(chǎn)者 /消費(fèi)者執(zhí)行流程圖 無(wú) 阻塞 等待使用權(quán) program producer_consumer。 const sizeofbuffer =… 。 /* 緩沖區(qū)大小 */ var s: semaphore(:= 1)。 /* 互斥信號(hào)量 s， 初始化為 1 */ n : semaphore(:= 0)。 /* 資源信號(hào)量 n， 數(shù)據(jù)單元 ， 初始化為 0 */ e : semaphore(:= sizeofbuffer)。 /* 資源信號(hào)量 e， 空存儲(chǔ)單元 */ procedure producer 。 procedure consumer 。 begin begin repeat repeat 生產(chǎn)一條數(shù)據(jù) 。 wait(n)。 wait(e)。 wait(s)。 wait(s)。 取一條數(shù)據(jù)； 存入一條數(shù)據(jù) 。 signal(s)。 signal(s)。 signal(e)。 signal(n)； 消費(fèi)數(shù)據(jù)； forever forever end。 end。 begin /* 主程序 */ parbegin producer 。 consumer 。 parend end. 圖 利用信號(hào)量實(shí)現(xiàn)生產(chǎn)者 /消費(fèi)者同步與互斥 問題描述 ? 該問題為多個(gè)進(jìn)程訪問一個(gè)共享數(shù)據(jù)區(qū)，如數(shù)據(jù)庫(kù)、文件、內(nèi)存區(qū)及一組寄存器等的數(shù)據(jù)問題建立了一個(gè)通用模型，其中若干讀進(jìn)程只能讀數(shù)據(jù)，若干寫進(jìn)程只能寫數(shù)據(jù)。 ? 例如，一個(gè)聯(lián)網(wǎng)售票系統(tǒng)，數(shù)據(jù)的查詢和更新非常頻繁，不可避免會(huì)出現(xiàn)多個(gè)進(jìn)程試圖查詢或修改（讀 /寫）其中某一條數(shù)據(jù)的情形。多個(gè)進(jìn)程同時(shí)讀一條記錄是可以的，但如果一個(gè)進(jìn)程正在更新數(shù)據(jù)庫(kù)中的某條記錄，則所有其他進(jìn)程都不能訪問（讀或?qū)懀┰撚涗?，否則可能會(huì)將同一個(gè)座位銷售多次。 讀者 /寫者進(jìn)程滿足的條件 ? 允許多個(gè)讀者進(jìn)程可以同時(shí)讀數(shù)據(jù)； ? 不允許多個(gè)寫者進(jìn)程同時(shí)寫數(shù)據(jù)，即只能互斥寫數(shù)據(jù)； ? 若有寫者進(jìn)程正在寫數(shù)據(jù)，則不允許讀者進(jìn)程讀數(shù)據(jù)。 讀者優(yōu)先 ? 當(dāng)一個(gè)讀者正在讀數(shù)據(jù)時(shí)，另一個(gè)讀者也需要讀數(shù)據(jù)，應(yīng)允許第二個(gè)讀者進(jìn)入，同理第三個(gè)及隨后更多的讀者都被允許進(jìn)入。 ? 現(xiàn)在假設(shè)一個(gè)寫者到來(lái)，由于寫操作是排他的，所以它不能訪問數(shù)據(jù)，需要阻塞等待。如果一直都有新的讀者陸續(xù)到來(lái)，寫者的寫操作將被嚴(yán)重推遲。 ? 該方法稱為“讀者優(yōu)先”。即，一旦有讀者正在讀數(shù)據(jù)，允許多個(gè)讀者同時(shí)進(jìn)入讀數(shù)據(jù)，只有當(dāng)全部讀者退出，才允許寫者進(jìn)入寫數(shù)據(jù)。用信號(hào)量實(shí)現(xiàn)的具體過(guò)程見圖 program readers_writers。 const readcount: integer。 /* 統(tǒng)計(jì)讀者個(gè)數(shù) */ var x,wsem: semaphore(:= 1)。 /* 互斥信號(hào)量 ， 初始化為 1 */ procedure reader 。 procedure writer。 begin begin repeat repeat wait(x)。 wait(wsem)。 readcount : = readcount + 1。 寫數(shù)據(jù)； if readcount = 1 then wait (wsem)。 signal(wsem)。 signal(x)。 forever 讀數(shù)據(jù)； end。 wait(x)。 readcount : = readcount 1。 if readcount = 0 then signal(wsem)。 signal(x)。 forever end。 begin /* 主程序 */ readcount := 0。 parbegin reader。 writer 。 parend end. 問題描述 五個(gè)哲學(xué)家圍坐在一張圓桌周圍，每個(gè)哲學(xué)家面前都有一碗面，相鄰兩碗面條之間有一只筷子，只有同時(shí)獲得兩只筷子，才能開始吃面條，如圖 。 改進(jìn) ? 可以在新買 5只筷子（對(duì)于計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)，需要增加資源，似乎不可能的），或教會(huì)哲學(xué)家用一只筷子吃面條。 ? 另一種有效的方法是，增加一位服務(wù)員，讓他安排其中的四位哲學(xué)家先入座，四位哲學(xué)家競(jìng)爭(zhēng)五只筷子，必然有一位哲學(xué)家能同時(shí)獲得兩只筷子，當(dāng)他進(jìn)餐完畢，再安排剩下的那位哲學(xué)家入座，參與五只筷子的競(jìng)爭(zhēng)。這樣，五位哲學(xué)家都能順利進(jìn)餐。 ? 實(shí)現(xiàn)該算法的偽代碼如圖 。 Program diningphilosophers。 Var fork:array [0..4] of semaphore (:= 1)。 room : semaphore (:= 4)。 i : integer。 procedure philosopher (i : integer)。 begin repeat think。 wait(room)。 wait(fork[i])。 wait(fork[(i + 1) mod 5])。 eat。 signal(fork[(i + 1) mod 5])。 signal(fork[i])。 signal(room)。 forever end。 begin parbegin philosopher(0)。 philosopher(1)。 philosopher(2)。 philosopher(3)。 philosopher(4)。 parend end.