【正文】 { P(SP)。 //測試 M是否已將信息加工好 從 B中取 M加工后的信息 Y。 V(SR)。 //通知 R，緩沖區(qū) B已可房信息 Print(Y)。 //打印信息 Y } } parend 第二章 進程管理 17 6. 若 一只盤子一次只能放一個水果， A只往盤中放蘋果， B只往盤中放梨子， C只從盤中取蘋果， D只從盤中取梨子。試用： (1) 信號量和 P、 V操作； (2) 管程 ，寫出同步算法。 解： (1) 采用 P、 V操作的同步算法如下： semaphore SAB=1。 //A、 B的資源信號量，同時又是它們的互斥信號量 semaphore SC=0。 //C的資源信號量 (用于與 A同步 ) semaphore SD=0。 //D的資源信號量 (用于與 B同步 ) begin parbegin process A: //進 程 A的算法描述 { while(true) { 取一個蘋果； wait(SAB)。 //測試盤子是否為空 將一蘋果放入盤中； signal(SC) //通知 C盤中已有蘋果 (可能喚醒 C) } } process C: { while(true) { wait(SC)。 //測試盤子是否有蘋果 從盤中取出蘋果 。 signal(SAB)。 //通知 A(或 B)盤子一空 (可能喚醒 A或 B) 消費該蘋果 。 } } process B: //進程 B的算法描述 { while(true) { 取一個梨子； wait(SAB)。 //測試盤子是否為空 將一梨子放入盤中； signal(SD) //通知 D盤中已有梨子 (可能喚醒 D) } } process D: { while(true) { wait(SD)。 //測試盤子是否有梨子 從盤中取出梨子 。 signal(SAB)。 //通知 A(或 B)盤子一空 (可能喚醒 A或 B) 消費該梨子 。 } } parend 第二章 進程管理 18 end (2) 采用管程的同步算法如下： 首先定義管程 MPC，該管程可描述如下： type MPC=monitor var flag: integer。 //flag=0:盤中無水果； =1盤中有蘋果； =2盤中有梨子 full, empty: condition。 procedure entry put(integer k) begin if flag0 then 。 //生產(chǎn)者 A或 B進程阻塞 flag=k。 放一 k號水果如盤中 。 //設(shè) 1號水果為蘋果， 2號水果為梨子 if then 。 //若等待隊列非空，則喚醒隊首的一個消費 者進程 end procedure entry get(integer k) begin if flagk then 。 //消費者 C或 D進程阻塞 從盤中取 k號水果 。 flag := 0。 if then 。 //若等待隊列非空，則喚醒隊首的一個生產(chǎn)者進程 end begin flag :=0。 //初始化內(nèi)部數(shù)據(jù) end A、 B、 C、 D四個進程的同步算法可描述如下： parbegin Process A begin 任取一個蘋果 。 (1)。 end Process B begin 任取一個梨子 。 (2)。 end Process C begin (1)。 吃蘋果 。 end Process D begin (2)。 吃梨子 。 end 第二章 進程管理 19 parend 7. 設(shè)自行車生產(chǎn)車間有兩個貨架，貨架 A可以存放 8個車架，貨架 B可以存放 20個車輪；又設(shè)有 4個工人，他們的活動是重復(fù)勞動，分別為：工人 1 加工一個車架放入貨架 A中；工人 3分別加工車輪放入貨架 B中（每人每次放入 1個車輪）；工人 4從貨架 A中取一個車架，再從貨架 B中取兩個車輪，組裝成一輛自行車。試用 PV操作實現(xiàn)四個工人的合作。 【分析】 信號量 Aempty表示貨架 A的空位數(shù)，其初值為 8；信號量 Afull表示貨架 A上存放的車架數(shù)，其初值為 0；信號量 Bempty表示貨架 B的空位數(shù)，其初值為 20；信號量 Bfull表示貨架 B上存放的車輪數(shù)，其初值為 0；信號量 mutex用于互斥（初值為 1）。 解： BEGIN semaphore Aempty， Bempty， Afull， Bfull， mutex； Aempty ： = 8； Bempty ： = 20； Afull ： = 0； Bfull ： = 0； mutex ： =1； PARBEGIN Worker1： BEGIN L1： 生產(chǎn) 1個車架 ； P（ Aempty）； //測試貨架 A是否有空位置 P（ mutex）； //互斥使用貨架 A 車架放到貨架 A； V（ Afull）； //貨架 A上的車架數(shù)增 1，必要時喚醒等待的進程 V（ mutex）； goto L1； END Worker 3： BEGIN L2：生產(chǎn) 1個車輪； P（ Bempty）； //測試貨架 B是否有空位置 P（ mutex）； //互斥使用貨架 B 車輪放到貨架 B； V（ Bfull）； //貨架 B上的車輪數(shù)增 1，必要時喚醒等待的進程 V（ mutex）； goto L2； END Worker4： BEGIN L3： P（ Afull）； //測試貨架 A上是否有車架 P（ Bfull）； P（ Bfull）； //測試貨架 B上是否有 2個車輪 P（ mutex）； 取 1個車架；取 2個車輪； V（ Aempty）； //貨架 A空位置增 1 V（ Bempty）； V（ Bempty）； //貨架 B空位置增 2 V（ mutex）； 組裝成一輛自行車； goto L3； END PAREND END 8. 假定有一個成品倉庫，總共能存放 8臺成品，生產(chǎn)者進程把生產(chǎn)成品放入倉庫，消費者進程從倉庫中取出成品消費。為了防止積壓，倉庫滿時就停止生產(chǎn)。由于倉庫搬運設(shè)備只有一套，故成品的存入第二章 進程管理 20 和取出只能分別進行，試用 P、 V操作來實現(xiàn)該方案。 解： semaphore mutex, empty, full 。 mutex=1。 //互斥信號量 empty=8。 //生產(chǎn)者進程的同步信號量 full=0。 //消費者進程的同步信號量 parbegin process Pi //生產(chǎn)者進程 { while (1) { 生產(chǎn)一個成品 x。 P(empty) //看看倉庫是否還有空間可放成品 P(mutex)。 //互斥使用搬運設(shè)備 用搬運設(shè)備將成品放入倉庫 。 V(full)。 //倉庫中成品數(shù)增 1(可能喚醒一個消費者 ) V(mutex)。 } } process Cj //消費者進程 { while (1) { P(full) //看看倉庫是否有成品 P(mutex)。 //互斥使用搬運設(shè)備 用搬運設(shè)備將成 品從倉庫取出 。 V(emtpy)。 //倉庫中可放成品數(shù)增 1(可能喚醒一個生產(chǎn)者 ) V(mutex)。 } } parend 9. 有三個進程 R、 W W2 共享一個緩沖器Ｂ，而 B 中每次只能存放一個數(shù)。當(dāng) B 中無數(shù)時，進程 R可將從輸入設(shè)備上讀入的數(shù)存放到緩沖器 B 中；若存放到 B 中的是奇數(shù)，則允許進程 W1 將其取出打?。蝗舸娣诺?B 中的是偶數(shù)，則允許進程Ｗ 2 將其取出打??；同時規(guī)定：進程 R 必須等緩沖器中的數(shù)被取出后才能再存放下一個數(shù)；進程 W1 或 W2 對每次存入緩沖器的數(shù)只能打印一次；Ｗ 1 和Ｗ 2 都不能從空的緩沖器中取數(shù)。用 P、 V 操作作為同步機制寫出三個并發(fā)進程的同步算法。 (動作部分可用文字描述 ) 解： semaphore S,S1,S2。 S=1。 S1=S2=0。 parbegin Process R { while (1) { 從輸入設(shè)備上讀入的數(shù) x。 P(S)。 B=x。 if (x%2==1) V(S1)。 //若是奇數(shù)，則通知 W1 else V(S2)。 //若是偶數(shù)，則通知 W2 第二章 進程管理 21 } } Process W1 { while (1) { P(S1)。 //看看緩沖器 B 中是否有奇數(shù) y=B。 //從緩沖器 B 中取奇數(shù)存 于 y V(S)。 //通知 R，緩沖器已空，可以在往里存數(shù)了 Print(y)。 //打印 } } Process W2 { while (1) { P(S2)。 //看看緩沖器 B 中是否有偶數(shù) y=B。 //從緩沖器 B 中取偶數(shù)存于 y V(S)。 //通知 R，緩沖器已空，可以在往里存數(shù)了 Print(y)。 } } parend 10. 進程 P1 使用緩沖區(qū) buffer 向進程 P2， P3， P4 發(fā)送消息（如圖 21 所示），要求每當(dāng) Pl 向 buffer 中發(fā)消息時，只有當(dāng) P2， P3， P4 進程都讀取這條消息后 P1 才可向 buffer 中 發(fā)送新的消息。試用信號量機制描述如下圖所示進程的動作過程。 （本題是 下 題的特例） 圖 21 解： 設(shè) P P P P4的資源信號量分別為 S S S S4 semaphore S1,S2,S3,S4。 =3。===0。 （ 3分） parbegin process P1 { while (condition) { P1生成一個消息； P（ S1）； P（ S1）； P（ S1）； P1將消息存入緩沖區(qū) buffer； V（ S2）； V（ S3）； V（ S4）； } P1 buffer P2 P3 P4 第二章 進程管理 22 } process Pi(i=2,3,4) { while （ condition） { P（ Si）； Pi從 buffer中取出消息； V（ S1）； Pi消費（使用）該消息； } } parend 另一解法如下（此法更一般化 ，可用來解下題 ）： semphore S1[3], S[3]。 for (i=0。i3。i++) { S1[i]=1。 S[i]=0。 } parbegin process P1 { while (1) { P1 生成一個消息； for (i=0。i3。i++) P(S1[i])。 //看看 P2～ P4 是否將消息取走 P1 將消息存入緩沖區(qū) buffer； for (i=0。i3。i++) V(S[i])。 //通知 P2～ P4 緩沖區(qū) buffer 中已有消息 } } Process P2 { while(1) { P(S[0])。 //看看 buffer 中是否已有消息 從 buffer 中取出消息 。 V(S1[0])。 //通知 P1, P2 已從緩沖區(qū) buffer 中取走消息 消費（使用）該消息 。 } } Process P3 { while(1) { P(S[1])。 //看看 buffer 中是否 已有消息 從 buffer 中取出消息 。 V(S1[1])。 //通知 P1, P3 已從緩沖區(qū) buffer 中取走消息 消費（使用）該消息 。 } 第二章 進程管理 23 } Process P4 { while(1) { P(S[2])。 //看看 buffer 中是否已有消息 從 buffer 中取出消息 。 V(S1[2])。 //通知 P1, P4 已從緩沖區(qū) buffer 中取走消息 消費（使用）該消息 。 } } parend 11. (北大 1994 年試題 )進程 A1， A2， ...， An1 通過 m 個緩沖區(qū)向進程 B1， B2， ...， Bn2 不斷地發(fā)送消息。發(fā)送和接 收工作遵循如下規(guī)則： ① 每個發(fā)送進程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小與消息長度一樣； ② 對每個消息， B1， B2， ...， Bn2都需各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)； ③ m個緩沖區(qū)都滿時，發(fā)送進程等待，沒有可讀的消息時，接收進程等待。 試用 P、 V操作組織正確的發(fā)送和接收操作。 （ 上 題是本題的特例） 【分析】 這是 PC問題變形。把這一組緩沖區(qū)看成 n2組緩沖區(qū)。 解： 設(shè)置一個信號量 mutex實現(xiàn)諸進程對緩沖區(qū)