1、精選優質文檔-傾情為你奉上PV問題：1 生產-消費模型，推廣到多個生產者，多個消費者的生產消費模型；設一個生產者進程P，一個消費者進程Q，他們通過一個緩沖區聯系起來，緩沖區只能容納一個產品，生產者不斷的生產產品，然后往空緩沖區送產品；消費者不斷的從緩沖區中取出產品，并消費。1.1 一個生產者、一個消費者、一個緩沖區的模型：信號量empty=0 full=0專心-專注-專業P：Repeat生產一個產品送產品到緩沖區V(full);P(empty);Until false;Q：Repeat：P(full);從緩沖區拿走一個產品V(empty);消費產品Until false;1.2 一個生產者、一

2、個消費者、一個緩沖區的第二種解法：信號量empty=1 full=0P:RepeatP(empty);生產一個產品送產品到緩沖區V(full);Until false;Q:RepeatP(full);從緩沖區取產品V(empty);消費產品Until false;1.3 一個生產者、一個消費者、n個緩沖區的模型：(不需要考慮互斥)信號量empty=n 空緩沖區的數目full=0 滿緩沖區的數目P:i:=0Repeat生產產品P(empty);送產品到緩沖池bufferiV(full);i:=(i+1)mod n;Until false;Q:j:=0RepeatP(full);從緩沖池buffe

3、ri中取產品V(empty);消費產品j:=(j+1)mod n;Until false;1.4 m個生產者、k個消費者、n個緩沖區的模型：（需要考慮互斥）信號量：empty=n 空緩沖區的數目full=0 滿緩沖區的數目mutex1(P進程互斥),mutex2(Q進程互斥)=1 互斥信號量，實現臨界區（緩沖池）的互斥P:i:=0Repeat生產產品P(empty);P(mutex1);添加產品到緩沖區bufferii:=(i+1)mod n;V(mutex1);V(full);Until false;Q:j:=0RepeatP(full);P(mutex2);從緩沖區bufferj中取產品j

4、:=(j+1)mod n;V(mutex2);V(empty);消費產品Until false;2 讀者-寫者模型，分兩種：讀者優先，寫著優先；某個共享文件F，系統允許若干進程對文件F讀或寫，但規定：1、多個進程可以同時讀文件F；2、任一個進程在對文件F進行寫時不允許其他進程對文件進行讀或寫；3、當有進程在讀文件是不允許任何進程去寫文件。2.1 第一類讀者-寫者問題：讀者優先除非有寫者在寫文件，否則沒有一個讀者需要等待。分析思想：讀者到：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等寫者到：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3

5、）有其它寫者，新寫者等待信息量：readcount = 0 記錄當前正在讀的讀者進程數，這是一個共享變量，需要互斥使用mutex = 1 互斥信息量write = 1 用于寫者互斥，或第一個讀者和最后一個讀者與寫者互斥READ：Repeat;P(mutex);readcount:=readcount+1;if(readcount=1)P(write);V(mutex);讀文件P(mutex);readcount:=readcount-1;if(readcount=0)V(write);V(mutex);Until falseWRITE:RepeatP(write);寫文件V(write);Un

6、til false;2.2 第二類讀者-寫者問題：寫者優先一旦一個寫者到來，它應該盡快對文件進行寫操作。則新來到的讀者不允許進行讀操作。分析思想：讀者到：1） 無讀者且無寫者，新讀者讀2） 有讀者但無寫者等待，新讀者讀3） 有讀者但有寫著等待，讀者等待4） 有寫者在寫，新讀者等待寫者到：1） 無讀者且無寫者，新寫者寫2） 有讀者在讀，新寫者等待3） 有寫者寫，新寫者等待信息量：read:=1 讀者信息量，用于第一個寫者與讀者互斥readcount:=0 記錄當前讀者的進程數mutex:=1 互斥信息量writecount:=0 記錄當前寫者排隊的進程數write:=1 寫者信息量，用于寫者互斥

7、，第一個讀者與寫者互斥mutex2:=1 互斥信息量P:RepeatP(read)P(mutex)V(read)readcount:=readcount+1;if(readcount=1)P(write)V(mutex)讀文件P(mutex)readcount:=readcount-1if(readcount=0)V(write)V(mutex)Until falseQ:RepeatP(mutex2)writecount:= writecount+1if(writecount=1)P(read)V(mutex2)P(write)寫文件V(write)P(mutex2)writecount:=w

8、ritecount-1if(writecount=0)V(read)V(mutex2)Until false;3 哲學家就餐模型，共3種解法；哲學家就餐問題Dijkstra，1965 問題描述：有五個哲學家以思考、用餐交替進行的方式生活，他們坐在一張圓桌邊，桌子上有5個盤子和5只筷子。當一個哲學家思考時，他不與鄰座的哲學家發生聯系，當一個哲學家感覺到餓了，他就試圖拿起他左右兩邊的筷子用餐。如果該哲學家的鄰座已經拿到筷子，則他可能只能拿到一只甚至一支筷子都拿不到。當一個饑餓的哲學家得到了兩只筷子，他就可以用餐。當他用餐完畢，就放下筷子再次進行思考。一般解法：#define chopstick5v

9、oid philosopher (int i)whileP(chopsticki);P(chopstick(i+1)%5);用餐;V(chopsticki);V(chopstick(i+1)%5);思考;3.1 改進解法1最多允許4個哲學家同時坐在桌子周圍。分析思想：1） 當有哲學家進程啟動時，檢查有幾個哲學家進程已經啟動，如果已經啟動四個，則等待。信息量：personcount:=4 記錄已經坐下的哲學家人數，即啟動進程的數量chopstick0-4:=1 筷子的信息量解法：#define chopstick5#define personcountvoid philosopher (int

10、i)P(personcount);whileP(chopsticki);P(chopsticki+1);用餐;V(chopsticki);P(chopsticki+1);思考;V(personcount);3.2 改進解法2僅當一個哲學家左右兩邊的筷子都可用時，才允許他拿筷子參照講義#define N 5#define THINKING 0#define HUNGRY 1#define EATING 2#typedef int semaphore;int stateNsemaphore mutex=1semaphore sNvoid test(int i)if(statei=HUNGRY)&a

11、mp;&(state(i-1)%5!=EATING)&&(state(i+1)%5!=EATING)statei=EATING;V(si);void philosopher(int i)while(true)思考;P(mutex);statei=HUNGRY;test(i);V(mutex);P(si);P(chopsticki);P(chopstick(i+1)%5);用餐;V(chopsticki);V(chopstick(i+1)%5);P(mutex);statei=THINKING;test(i-1)%5);test(i+1)%5);V(mutex);stat

12、ei=THINKING;si=0;3.3 改進解法3給所有哲學家編號，奇數號的哲學家必須首先拿左邊的筷子，偶數號的哲學家則反之信號量：mutex:=1 互斥信息量chopstick5:=1 筷子的信息量void philosopher(int i)while(true)思考;P(mutex);if(0=i%2)P(chopstick(i+1)%5);P(chopsticki);elseP(chopsticki);P(chopstick(i+1)%5);V(mutex);用餐;P(mutex);V(chopsticki);V(chopstick(i+1)%5;V(mutex);4 吸煙者問題，1

13、種解法；吸煙者問題（Patil, 1971) 吸煙者問題或者說是酒吧聽音樂問題三個吸煙者在一間房間內，還有一個香煙供應者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴。供應者有豐富的貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。供應者將兩樣東西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應者，供應者再放兩樣東西（隨機地）在桌面上，然后喚醒另一個吸煙者。試為吸煙者和供應者編寫程序解決問題。酒吧聽音樂問題：在一件酒吧里有三個音樂愛好者隊列，第一隊的音樂愛好者只有隨身聽，第二隊只有音樂磁帶，第三隊只有電池，而要聽音樂就必須

14、隨身聽，磁帶和電池這三種物品俱全。酒吧老板一次出售這三種物品中的任意兩種，當一名音樂愛好者得到這三種物品并聽完一首樂曲后，酒吧老板才能再一次出售這三種物品中的任意兩種。于是第二名音樂愛好者得到這三種物品，并開始聽音樂。全部買賣就這樣進行下去。以吸煙者問題為例：分析思想：供應者每次供應兩種物品，并根據這兩種物品叫相應的吸煙者拿走物品吸煙，其他沒有叫到的吸煙者繼續等待。吸煙者吸完煙后叫醒供應者再次供應物品。信息量：tobacco:=0paper:=0match:=0smoker1:=0smoker2:=0smoker3:=0seller:=0程序：semaphore tobacco=0,paper

15、=0,match=0;semaphore smoker1=0,smoker2=0,smoker3=0,seller=0;int casevoid seller()while(1)P(seller);Randomnize;case = random(0,2);if(case=0)V(tobacco);V(paper);V(smoker1);else if(case=1)V(tobacco);V(match);V(smoker2);else if(cass=2)V(paper);V(match);V(smoker3);void smoker1()while(1)P(smoker1);V(match

16、);P(tobacco);P(paper);P(match);/吸煙V(seller)void smoker2()while(1)P(smoker2);V(paper);P(tobacco);P(paper);P(match);/吸煙V(seller)void smoker3()while(1)P(smoker3);V(tobacco);P(tobacco);P(paper);P(match);/吸煙V(seller)5 面包師問題，1種解法；銀行問題某銀行有人民幣儲蓄業務，由n個柜員負責。每個顧客進入銀行后先取一個號，并且等著叫號。當一個柜員人員空閑下來，就叫下一個號。試用PV操作編寫柜員人

17、員和顧客進程的程序。分析思想：1） 分成兩部分進程，柜員進程和顧客進程2） 顧客進門后P信息量，相當于進入等待隊列。3） 柜員間互斥。當柜員空閑時，進入互斥操作部分，放入一個等待的顧客，推出互斥操作。4） 設置柜員狀態變量，空閑為1，忙碌為0，顧客進入后掃描狀態變量，找到空閑的柜員后過去辦理業務。當顧客掃描空閑柜員的時候互斥。雖然這樣能保證顧客到空閑的柜員處辦理業務，但不能保證他所去的柜員是叫他號的柜員。5） 需要考慮當沒有顧客，但所有柜員進程都啟動的時候，柜員需要等待顧客的到來信息量：ClientQueue:=0 記錄顧客等待的隊列Clerkmutex:=1 柜員的互斥信息量Clientmu

18、tex:=1 顧客的互斥信息量Customer:=0 記錄提供給柜員可以辦理業務的客戶的數量，同時在客戶少于n時表示等待客戶的柜員的數量。程序：#typedef int semaphoresemaphore ClientQueue=0;semaphore Customer=0;semaphore Clerkmutex=1;semaphore Clientmutex=1;int ClerkStaten;for(int i=0;i<n;i+)ClerkStatei=1;void Client()P(ClientQueue);/每個顧客不是循環不停的辦理業務，所以認為不需要循環語句P(Clie

19、ntmutex);/掃描柜員期間互斥，以防與后面的顧客同時掃描到同一柜員V(Customer);/表示提供一個可供服務的客戶for(int i=0;i<n;i+)/掃描到第一個空閑的柜員后推出，即到該柜員出辦理if(ClerkStatei=1)ClerkStatei=0;break;V(Clientmutex);到第i個柜員處辦理業務;void Clerk(int i)while(1)P(mutex);ClerkStatei=1;V(ClientQueue)V(mutex);P(Customer);/等待可供服務的客戶，如果客戶數量少于n，柜員在此排隊辦理業務;6 類似面包師的理發師問題

20、，可以推廣到多個理發師問題；愛睡覺的理發師問題Dijkstra，1968一個理發店有兩間相連的屋子，一間是私室，里面有一把理發椅，另一件是等候室，有一個滑動門和N把椅子。理發師忙的時候，通向私室的門被關閉，新來的顧客找一把空椅子坐下，如果椅子都被占滿了，則顧客只好離去。如果沒有顧客，則理發師在理發椅上睡覺，并打開通向私室的門。理發師睡覺時，顧客可以叫醒他理發。請編寫理發師和顧客的程序，正確實現同步互斥問題。分析思想：1） 當沒有顧客，理發師休息，當有顧客，理發師對最先來的顧客理發。2） 顧客進入理發師有3種狀況：1、理發店沒人，直接進里屋理發，2、理發店有人，找個凳子等，3、理發店有人，n個凳

21、子被占滿，顧客離開。3） 理發師給一個顧客理完發后，打開滑門，即V操作信息量，顧客進入后關上滑門，即P操作信息量，在理發過程中，顧客是互斥的4） 一個顧客進入，即等待室中的凳子空出一把。每個顧客進入理發店需要判斷是否n把椅子滿，即判斷變量chair=n or not。如果椅子滿顧客進程需要退出。信息量：barber:=1 理發師的信息量，同時也是顧客的排隊度隊列Customer:=0 顧客的數量mutex:=1 顧客互斥信息量程序：#define int semaphoresemaphore waiting=0;semaphore cutHair=0;semaphore mutex=1;int

22、 count=0;void Customer()P(mutex);if(count>n)V(mutex);return false;else count+;V(mutex);if(count>1)/got a chair;P(waiting);/等待V(cutHair);/顧客叫醒理發師理發;P(mutex);count-;if(count>0)V(waiting);V(mutex);void Barber()while(true)P(cutHair);/等待顧客理發;解法二：加入了占用椅子資源，顧客付錢理發師收錢的同步過程。from 計算機操作系統課程及考研輔導semaph

23、ore mutex=1,empty=1;semaphore chair=n;semaphore full=0;semaphore cut=0,payment=0,receipt=0;int count=0;guest()P(mutex);if(count>n)V(mutex);return false;elsecount+;V(mutex);if(count>1)P(chair);/sit on a chairP(empty);/on queueV(chair);/get up from a chairelse P(empty);sit on the barbers chair;V

24、(full);P(cut);pay;V(payment);P(receipt);get up from barbers chair;V(empty);P(mutex);count-;V(mutex);exit shop;barber()while(1)P(full);cut hair;V(cut);P(payment);accept payment;V(receipt);/V(empty);二者有一即可7 狒狒過河問題；巴拿馬運河問題巴拿馬運河建在太平洋和大西洋之間，由于太平洋和大西洋水面高度不同，有巨大落差，所以運河中建有T(T2)級船閘，并且只能允許單向通行，船閘依次編號為1,2,T，由大

25、西洋來的船需要經過船閘T,T-1.,2,1通過運河到達太平洋，由太平洋來的船需要經由船閘1,2,T-1,T通過運河到達大西洋。使用P,V操作正確解決大西洋和太平洋的船只通航問題。分析思想：1） 巴拿馬運河大西洋，太平洋兩個方向的船設置為兩個進程。Atlantic(),Pacific();2） 當一側船來到運河，如果另一側船在過河，則等待；如果自己方船在過河，同時己方船只的總過河船數小于T，則過河；如果己方船在過河，同時己方船只過河總數大于T，則等待。3） 為了避免饑餓和死鎖，必須控制一次過河的船數T。信息量：A,P:=1 代表兩邊的船只是否允許通過的閘門。mutex1,mutex2:=1 互斥

26、信息量程序：semaphore A=1;semaphore P=1;semaphore mutex1=1;semaphore mutex2=1;int PshipSum=0,AshipSum=0;int PshipCur=0,AshipCur=0;Pacific()P(P);P(mutex1);PshipSum+; PshipCur+;if(PshipCur=1)P(A);if(PshipSum=T)P(P);V(P);V(mutex1)過河；P(mutex1);PshipCur-;if(PshipCur=0)V(A);PshipSum=0;if(PshipSum=T)V(P);V(mutex

27、1);Atlantic()P(A);P(mutex2);AshipSum+; AshipCur+;if(AshipCur=1)P(P);if(AshipSum=T)P(A);V(A);V(mutex2);過河；P(mutex2);AshipCur-;if(AshipCur=0)V(P);AshipSum=0;if(AshipSum=T)V(A);V(mutex2);8 另類P，V問題。紅客黑客過河問題有紅客和黑客兩組人員需要過河。河上有船，但是每次只能乘坐4人，且每次乘客滿員時才能開船，到河對岸后空船返回。但船上乘客不能同時有3個紅客 、1個黑客 或者 1個紅客 、 3個黑客的組合。（其他組合

28、安全）。請編寫程序，用pv操作解決紅客、黑客過河的問題。并說明所設置的信號量及其初值。分析思想：(from 計算機科學論壇-北大必考題，PV經典案例分析)對同步與互斥的分析： 同步關系：1. 滿員才能開船；2. 紅黑客滿足一定的組合規則,才能有四人上船 互斥關系：紅黑客對請求上船的控制 顯然，此題難點在對同步關系的解決。 下面給出所寫程序的算法思想： Red():每個紅客到來請求上船時執行該程序； 1. 請求進入臨界區； 2. 首先檢查本人的到來是否滿足上船的組合(即4個紅客或2個紅客與2個黑客); 3. 如果滿足2個紅客和2和黑客的組合，則看是否有船可上，有的話該紅客上船并通知另外1個紅客和

29、2個黑客上船，然后通知船滿員，并退出臨界區； 4. 如果滿足4個紅客的組合，則看是否有船可上，有的話該紅客上船并通知另外3個紅客上船，然后通知船滿員，并退出臨界區； 5. 不符合上船的組合，則先退出臨界區，然后在信號量S_red上等待，直到當條件滿足時，有人通知其上船。 6. 完畢。 Black():每個黑客到來請求上船時執行該程序,其算法與Red()完全一致； Boat():河上的船執行該程序； 1.等待滿員后開船過河； 2.空船返回，通知可以上船了，轉而執行1。信息量：mutex:=1S_red,S_black:=0ready:=1 船是否靠岸board:=0上船shipping:=0 程

30、序：semaphore mutex=1;semaphore S_red=0;semaphore S_black=0;semaphore board=0;semaphore shipping=0;int RedCount=0,BlackCount=0;Red()P(mutex);RedCount+;if(RedCount>1 && BlackCount>1)P(ready);V(S_red);V(S_black);V(S_black);上船;V(board);P(shipping);RedCount-=2;BlackCount-=2;開船;V(mutex);else

31、if(RedCount=4)P(ready);V(S_red);V(S_red);V(S_red);上船;V(board);P(shipping);RedCount-=4;開船;V(mutex);else V(mutex);P(S_red);上船;開船;Black()P(mutex);BlackCount+;if(RedCount>1 && BlackCount>1)P(ready);V(S_black);V(S_red);V(S_red);上船;V(board);P(shipping);RedCount-=2;BlackCount-=2;開船;V(mutex);else if(BlackCount=4)P(ready);V(S_black);V(S_black);V(S_black);上船;V(board);