【正文】 N個座位 理發(fā)椅 51 理發(fā)師睡覺問題算法 Semphore seatempty=N,seatfull=0,chair=1,mutex=1。無顧客時，理發(fā)師睡覺；當顧客進入理發(fā)店發(fā)現(xiàn)理發(fā)師睡覺時，則喚醒理發(fā)師。 V(empty)。 P(mutex)。 … }while(1)。 Producer: do{ … produce an item in nextp。 empty:=n。 struct item nextp, nextc。 }while(1)。 V(mutex)。 P(mutex)。 }buffer。 typedef struct{ struct item inst。 ? empty, 初值為 n，表示當前緩沖池中空緩沖區(qū)數(shù)，用于同步。 共享 n個緩沖區(qū) P1 P2 … P m 生產(chǎn)者 消費者 緩沖池 C1 C2 …Cn 47 解： 設置以下信號量 ? mutex, 初值為 1，控制互斥訪問緩沖池。 ? 如果 n個緩沖區(qū)全滿，生產(chǎn)者進程必須等待。} 45 三個經(jīng)典的進程同步問題： 有限緩沖區(qū)問題（生產(chǎn)者 消費者問題）； (The ProducerConsumer Problem) 讀者 寫者問題； (The Read/Write Problem) 哲學家就餐問題； (The Dining Philosophers Problem) 46 有限緩沖區(qū)的生產(chǎn)者 /消費者問題（生產(chǎn)者和消費者共享一個產(chǎn)品緩沖池）。 P(e)。 V(e)。 P(c)。 V(d)。 S2。 V(b)。 P1(){ S1。 解決進程同步問題時關鍵： 44 一般地，定義 n個信號量來描述有 n條 邊的前趨圖，初值都設為 0。 ? 其次是要注意信號量的初值以及意義 。//發(fā)送已關門信息 售車票； P(stop)。//車門是否關好 啟動汽車 正常開車 到站停車 V(stop)。 Semaphore stop=0,close=0。 …… } Parend。 …… } …… P(synch)。設 synch是實現(xiàn)同步的信號量，初值為 0，則兩個進程的同步可以描述為： 4. 利用信號量實現(xiàn)進程同步 Parbegin P2: { P1: { …… S1。 輸出機票已售完 。 輸出一張機票 。 Ri =Xi。 Xi=Ri 。 mutex=1。 產(chǎn)生的錯誤： pi， pj都售出了一張機票，但票務中心記錄機票余額的變量 Ri卻只減了 1。Ri =Xj； ③ pi再執(zhí)行 Xi= Xi1。 輸出一張機票； } else 輸出機票已售完； } 38 ? 存在的問題： 1）存在幾個旅客幾乎同時在不同的售票處要求訂購同天同一次航班的可能。 //將票務中心該次航班的余票 //取出送該進程工作單元 Xi if (Xi=1) { Xi= Xi1。 36 進程 Pi : 信號量 mutex=1 P(mutex) V(mutex) 臨界段 非臨界段 do{ }While(1) 37 ? 例子： 有一飛機機票售票系統(tǒng)，有 m個售票處，各售票處通過計算機與該系統(tǒng)的票務中心連網(wǎng)，中心數(shù)據(jù)區(qū)中用 Ri代表某天某次航班的余票數(shù)。 2）各進程在進入臨界段前先對該信號量進行 P操作，退出臨界段后執(zhí)行 V操作，從而保證各進程互斥的進入相關臨界段。此時， ||表示該信號量上阻塞的進程數(shù)； ? V(s)操作： ① 進程釋放一個 S代表 的資源，執(zhí)行 +1； ② 若 =0， 表示尚有進程因等待 S代表的資源而處于阻塞狀態(tài)，所以應喚醒其中之一。 4. P,V操作的優(yōu)點： 同步能力強 5. P,V操作的缺點： 程序結(jié)構(gòu)差，易產(chǎn)生死鎖。 if 0 then 保存現(xiàn)場， 將本進程掛入 ，等待重新調(diào)度。一個 PCB隊列 } Semaphore Semaphore S。 2. 信號量的具體實現(xiàn) 33 1. 信號量定義 typedef struct{ int:value。 } 32 實現(xiàn)信號量時與進程調(diào)度相結(jié)合，消除忙等待現(xiàn)象。 s=s+1。 enableIntrrupt()。 disableIntrrupt()。 ? P,V操作的實現(xiàn) 31 P(s)， V(s)的實現(xiàn) P(s){ disableIntrrupt()。 30 ? 原語 ：指完成某種功能且不被分割或不被中斷執(zhí)行的操作序列 (又稱原子操作 )。 noncritical section }while(1) 29 信號量 (1965年， Dijkstra提出 ) 信號量機構(gòu)：“信號量”、“ P， V操作”。 while(key ==ture) Swap (Lock, key)。利用Swap指令，可實現(xiàn)對臨界區(qū)的加鎖與解鎖。 //其它部分 }while（ 1） 。 //臨界區(qū) lock=false。 Target =true； Return rv } 如果機器支持 Test_and_Set，可用下列方法解決 ：(Lock=false) do { while（ Test_and_Set(lock)） 。 enableInterrupt()。 進程 2的程序 disableInterrupt()。 Balance=balance+amount。 Entry code exit code Entry code exit code 24 如何實現(xiàn)進入?yún)^(qū)、退出區(qū)代碼 —同步機構(gòu) ? 同步機構(gòu)： 指能實現(xiàn)進程同步的機制，該機制能把其它進程需要的信息發(fā)送出去，也能測試自己需要的信息是否到達。 count:=N。 } P2: { N:=count。 M:=M+1。 Entry code exit code 使用打印機 P1 Entry code exit code 使用打印機 P2 23 例 3: 對共享變量 count的互斥訪問。//剩余區(qū) }； 22 例 2： P1,P2兩進程使用同一打印機。 //臨界段 exit code。 21 一個訪問臨界資源的進程描述如下： While (1) {