PV練習及參考解答.doc

PV原語操作詳解 PV原語通過操作信號量來處理進程間的同步與互斥的問題（如：經(jīng)典的生產(chǎn)者消費者問題）。其核心就是一段不可分割不可中斷的程序，從而實現(xiàn)進程同步。信號量的概念1965年由著名的荷蘭計算機科學(xué)家Dijkstra提出，其基本思路是用一種新的變量類型(semaphore)來記錄當前可用資源的數(shù)量（如：生產(chǎn)者進程中的資源和消費者中的資源信號量：空位置數(shù)empty和產(chǎn)品數(shù)full）。 semaphore有兩種實現(xiàn)方式： 1) semaphore的取值必須大于或等于0。0表示當前已沒有空閑資源，而正數(shù)表示當前空閑資源的數(shù)量； 2) semaphore的取值可正可負，負數(shù)的絕對值表示正在等待進入臨界區(qū)的進程個數(shù)。 信號量是由操作系統(tǒng)來維護的，用戶進程只能通過初始化和兩個標準原語(P、V原語)來訪問。初始化可指定一個非負整數(shù)，即空閑資源總數(shù)。 P原語：P是荷蘭語Proberen(測試)的首字母。為阻塞原語，負責把當前進程由運行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)，直到另外一個進程喚醒它。操作為：申請一個空閑資源(把信號量減1)，若成功，則退出；若失敗，則該進程被阻塞； V原語：V是荷蘭語Verhogen(增加)的首字母。為喚醒原語，負責把一個被阻塞的進程喚醒，它有一個參數(shù)表，存放著等待被喚醒的進程信息。操作為：釋放一個被占用的資源(把信號量加1)，如果發(fā)現(xiàn)有被阻塞的進程，則選擇一個喚醒之。 P原語操作的動作是： (1)sem減1； (2)若sem減1后仍大于或等于零，則進程繼續(xù)執(zhí)行； (3)若sem減1后小于零，則該進程被阻塞后進入與該信號相對應(yīng)的隊列中，然后轉(zhuǎn)進程調(diào)度。 V原語操作的動作是： (1)sem加1； (2)若相加結(jié)果大于零，則進程繼續(xù)執(zhí)行； (3)若相加結(jié)果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉(zhuǎn)進程調(diào)度。 PV操作必須成對使用。在PV原語執(zhí)行期間不允許有中斷的發(fā)生。 例1： 生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個箱子里，現(xiàn)要用自動分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個并發(fā)執(zhí)行的進程組成，功能如下：(1)進程A專門揀黑子，進程B專門揀白子；(2)每個進程每次只揀一個子，當一個進程在揀子時不允許另一個進程去揀子； 分析進程及關(guān)系： 第一步：確定進程間的關(guān)系。由功能(2)可知進程之間是互斥的關(guān)系。 實現(xiàn)：確定信號量及其值semaphore s; / 箱子個數(shù)，初值為1 /注意以下表示方法，cobegin和coend之間的是并發(fā)進程main()cobeginA();B();coendA()while(1)wait(S);揀黑子；signal(S);B()while(1)wait(S);揀白子；signal（S）； 例2：某超市門口為顧客準備了100輛手推車，每位顧客在進去買東西時取一輛推車，在買完東西結(jié)完帳以后再把推車還回去。試用P、V操作正確實現(xiàn)顧客進程的同步互斥關(guān)系。 分析進程及關(guān)系：把手推車視為某種資源，每個顧客為一個要互斥訪問該資源的進程。因此這個例子為PV原語的第二種應(yīng)用類型。 解：信號量定義semaphoreS_CartNum;/：空閑的手推車數(shù)量，初值為100 void consumer(void)/ 顧客進程 P(S_CartNum); 買東西; 結(jié)帳; V(S_CartNum); 例3：桌子上有一個水果盤，每一次可以往里面放入一個水果。爸爸專向盤子中放蘋果，兒子專等吃盤子中的蘋果。把爸爸、兒子看作二個進程，試用P、V操作使這兩個進程能正確地并發(fā)執(zhí)行。 分析：爸爸和兒子兩個進程相互制約，爸爸進程執(zhí)行完即往盤中放入蘋果后，兒子進程才能執(zhí)行即吃蘋果。因此該問題為進程間的同步問題。 解： 信號量定義semaphore S_PlateNum; / 盤子容量，初值為1 semaphore S_AppleNum;/ 蘋果數(shù)量，初值為0 void father( )/ 父親進程 while(1) P(S_PlateNum); 往盤子中放入一個蘋果; V(S_AppleNum); void son( )/ 兒子進程 while(1) P(S_AppleNum); 從盤中取出蘋果; V(S_PlateNum); 吃蘋果； 思考：如果爸爸也可以放鴨梨，女兒吃鴨梨？以上代碼該如何修改？ 例4：兩個進程PA、PB通過兩個FIFO(先進先出)緩沖區(qū)隊列連接(如圖) PA從Q2取消息，處理后往Q1發(fā)消息；PB從Q1取消息，處理后往Q2發(fā)消息，每個緩沖區(qū)長度等于傳送消息長度。 Q1隊列長度為n，Q2隊列長度為m. 假設(shè)開始時Q1中裝滿了消息，試用P、V操作解決上述進程間通訊問題。 分析： 解： / Q1隊列當中的空閑緩沖區(qū)個數(shù)，初值為0semaphore S_BuffNum_Q1; / Q2隊列當中的空閑緩沖區(qū)個數(shù)，初值為msemaphore S_BuffNum_Q2; / Q1隊列當中的消息數(shù)量，初值為nsemaphore S_MessageNum_Q1; / Q2隊列當中的消息數(shù)量，初值為0semaphore S_MessageNum_Q2; voidPA( ) while(1) P(S_MessageNum_Q2); 從Q2當中取出一條消息; V(S_BuffNum_Q2); 處理消息; 生成新的消息; P(S_BuffNum_Q1); 把該消息發(fā)送到Q1當中; V(S_MessageNum_Q1); voidPB( ) while(1) P(S_MessageNum_Q1); 從Q1當中取出一條消息; V(S_BuffNum_Q1); 處理消息; 生成新的消息; P(S_BuffNum_Q2); 把該消息發(fā)送到Q2當中; V(S_MessageNum_Q2); 思考：此處是否應(yīng)該加上互斥信號量，如何添加？練習：例1： 某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，廳外的購票者可立即進入，否則需要在外面等待。每個購票者可看成一個進程。 分析確定進程間的關(guān)系。售票廳是各進程共享的公有資源，當售票廳中多于20名購票者時，廳外的購票者需要在外面等待。所以進程間是互斥的關(guān)系。第二步：確定信號量及其值。只有一個公有資源：售票廳，所以設(shè)置一個信號量s。售票廳最多容納20個進程，即可用資源實體數(shù)為20，s的初值就設(shè)為20。 實現(xiàn)：/售票廳是各進程共享的公有資源，售票廳最多容納20個進程，即可用資源實體數(shù)為20，s的初值就設(shè)為20。semaphore s;voidPI(I=1,2, ) P(s); 進入售票廳;購票;退出; V(s); 當購票者進入售票廳前要執(zhí)行P(s)操作，執(zhí)行后若s大于或等于零，說明售票廳的人數(shù)還未滿可進入。執(zhí)行后若s小于零，則說明售票廳的人數(shù)已滿不能進入。這個實現(xiàn)中同時最多允許20個進程進入售票廳購票，其余進程只能等待。例2： 生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個箱子里，現(xiàn)要用自動分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個并發(fā)執(zhí)行的進程組成，功能如下：(1)進程A專門揀黑子，進程B專門揀白子；(2)每個進程每次只揀一個子，當一個進程在揀子時不允許另一個進程去揀子； 分析： 第一步：確定進程間的關(guān)系。由功能(2)可知進程之間是互斥的關(guān)系。 第二步：確定信號量及其值。由于進程A和進程B要互斥進入箱子去揀棋子，箱子是兩個進程的公有資源，所以設(shè)置一個信號量s，其值取決于公有資源的數(shù)目，由于箱子只有一個，s的初值就設(shè)為1。 實現(xiàn)：Semaphore s;/互斥信號量，初值為1main()cobeginA();B();coendA()while(1)wait(s);揀白子；signal(s);B()while(1)wait(s);揀黑子；signal（s）；判斷進程間是否互斥，關(guān)鍵是看進程間是否共享某一公有資源，一個公有資源與一個信號量相對應(yīng)。確定信號量的值是一個關(guān)鍵點，它代表了可用資源數(shù)。如下實例：例3： 在例2的基礎(chǔ)之上再添加一個功能：(3)當一個進程揀了一個棋子（黑子或白子）以后，必讓另一個進程揀一個棋子（黑子或白子）。 分析： 第一步：確定進程間的關(guān)系。由功能（1）（2）（3）可知，進程間的關(guān)系為同步關(guān)系。第二步：確定信號量及其值。進程A和B共享箱子這個公有資源，但規(guī)定兩個進程必須輪流去取不同色的棋子，因而相互間要互通消息。對于進程A可設(shè)置一個私有信號量s1，該私有信號量用于判斷進程A是否能去揀黑子，初值為1。對于進程B同樣設(shè)置一個私有信號量s2，該私有信號量用于判斷進程B是否能去揀白子，初值為0。當然你也可以設(shè)置s1初值為0，s2初值為1。 實現(xiàn):Semaphore s1;/同步信號量，初值為1，表示可揀黑子Semaphore s2;/同步信號量，初值為0，表示不可揀白子main()cobeginA();B();coendA()while(1)wait(s2);揀白子；signal(s1);B()while(1)wait(s1);揀黑子；signal（s2）；另外一個問題就是P原語是不是一定在V原語的前面？回答是否定的。下面看一個例子： 例4： 設(shè)在公共汽車上，司機和售票員的活動分別是：司機：啟動車輛，正常行車，到站停車。售票員：上乘客，關(guān)車門，售票，開車門，下乘客。用PV操作對其控制。 分析： 第一步：確定進程間的關(guān)系。司機到站停車后，售票員方可工作。同樣，售票員關(guān)車門后，司機才能工作。所以司機與售票員之間是一種同步關(guān)系。 第二步：確定信號量及其值。由于司機與售票員之間要互通消息，司機進程設(shè)置一個私有信號量run，用于判斷司機能否進行工作（申請run資源，以便啟動車），初值為0（表示沒有run資源）。售票員進程設(shè)置一個私有信號量stop，用于判斷是否停車，售票員是否能夠開車門（申請stop資源以便開門），初值為0（無stop資源可用）。 實現(xiàn)：semaphore stop=0;/初值0表示未到新站（0表示無資源可用）semaphore run=0;/初值0表示車未啟動（0表示無資源可用）main()cobegindriver();conductor();coenddriver()while(1)P(run); 啟動車輛； 正常行車； 到站停車；V(stop);conductor()while(1)上乘客；關(guān)車門； V(run);售票；P(stop); 開車門； 下乘客；/注意以下表示方法，偽pascal語法，cobegin和coend之間是并發(fā)進程，每個進程都有begin和end表示開始和結(jié)束，使用goto進行循環(huán)begin stop ,run:semaphore stop:=0;run:=0; cobegin driver: begin L1: P(run); 啟動車輛； 正常行車； 到站停車； V(stop); gotoL1; end; conductor: begin L2:上乘客； 關(guān)車門； V(run); 售票； P(stop); 開車門； 下乘客； goto L2; end; coend;end;例5：書本P63，讀者寫者問題總結(jié)：- 具體PV原語對信號量的操作可以分為幾種情況： 1) 用于表示前趨關(guān)系。2) 把信號量視為一個加鎖標志位，實現(xiàn)對一個共享變量的互斥訪問。由于用于互斥的信號量sem與所有的并發(fā)進程有關(guān)，所以稱之為公有信號量。公有信號量的值反映了公有資源的數(shù)量。只要把臨界區(qū)置于P(sem)和V(sem)之間，即可實現(xiàn)進程間的互斥。就象火車中的每節(jié)車廂只有一個衛(wèi)生間，該車廂的所有旅客共享這個公有資源：衛(wèi)生間，旅客間必須互斥進入衛(wèi)生間，只要把衛(wèi)生間放在P(sem)和V(sem)之間，就可以到達互斥的效果。 實現(xiàn)過程： P(mutex); / mutex的初始值為1 訪問該共享數(shù)據(jù); V(mutex); 3) 把信號量視為是某種類型的共享資源的剩余個數(shù)，實現(xiàn)對一類共享資源的訪問。判斷進程間是否互斥，關(guān)鍵是看進程間是否共享某一公有資源，一個公有資源與一個信號量相對應(yīng)。確定信號量的值是一個關(guān)鍵點，它代表了可用資源實體數(shù)。 實現(xiàn)過程： P(resource); / resource的初始值為該資源的個數(shù)N 使用該資源； V(resource); 4) 把信號量作為進程間的同步工具 與進程互斥不同，