PV原語操作詳解
?
PV原語通過操作信號量來處理進程間的同步與互斥的問題。其核心就是一段不可分割不可中斷的程序。
信號量的概念1965年由著名的荷蘭計算機科學家Dijkstra提出，其基本思路是用一種新的變量類型(semaphore)來記錄當前可用資源的數量。
?
??? semaphore有兩種實現方式：
?
??? 1) semaphore的取值必須大于或等于0。0表示當前已沒有空閑資源，而正數表示當前空閑資源的數量；
??? 2) semaphore的取值可正可負，負數的絕對值表示正在等待進入臨界區的進程個數。
?
??? 信號量是由操作系統來維護的，用戶進程只能通過初始化和兩個標準原語(P、V原語)來訪問。初始化可指定一個非負整數，即空閑資源總數。
?
???
P原語：P是荷蘭語Proberen(測試)的首字母。為阻塞原語，負責把當前進程由運行狀態轉換為阻塞狀態，直到另外一個進程喚醒它。操作為：申請一個空閑資源(把信號量減1)，若成功，則退出；若失敗，則該進程被阻塞；
?
???
V原語：V是荷蘭語Verhogen(增加)的首字母。為喚醒原語，負責把一個被阻塞的進程喚醒，它有一個參數表，存放著等待被喚醒的進程信息。操作為：釋放一個被占用的資源(把信號量加1)，如果發現有被阻塞的進程，則選擇一個喚醒之。
?
??? P原語操作的動作是：
??? (1)sem減1；
??? (2)若sem減1后仍大于或等于零，則進程繼續執行；
??? (3)若sem減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中，然后轉進程調度。
??? V原語操作的動作是：
??? (1)sem加1；
??? (2)若相加結果大于零，則進程繼續執行；
??? (3)若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續執行或轉進程調度。
??? PV操作對于每一個進程來說，都只能進行一次，而且必須成對使用。在PV原語執行期間不允許有中斷的發生。
?
?
---------------------------------------------
?
???
具體PV原語對信號量的操作可以分為三種情況：
?
??? 1) 把信號量視為一個加鎖標志位，實現對一個共享變量的互斥訪問。
?
??? 實現過程：
?
???
P(mutex); // mutex的初始值為1 訪問該共享數據;
???
V(mutex);
???
非臨界區;
?
??? 2) 把信號量視為是某種類型的共享資源的剩余個數，實現對一類共享資源的訪問。
?
??? 實現過程：
?
???
P(resource); // resource的初始值為該資源的個數N 使用該資源；
???
V(resource);
??? 非臨界區;
?
3) 把信號量作為進程間的同步工具
?
??? 實現過程：
?
???
臨界區C1;
???
P(S);
???
V(S);
???
臨界區C2;
?
?
---------------------------------------------
?
舉例說明：
?
?
??? 例1：某超市門口為顧客準備了100輛手推車，每位顧客在進去買東西時取一輛推車，在買完東西結完帳以后再把推車還回去。試用P、V操作正確實現顧客進程的同步互斥關系。
?
??? 分析：把手推車視為某種資源，每個顧客為一個要互斥訪問該資源的進程。因此這個例子為PV原語的第二種應用類型。
?
??? 解：
?
semaphore S_CartNum;?? ?// 空閑的手推車數量，初值為100
void? consumer(void)??? // 顧客進程
{
??? P(S_CartNum);
?? 買東西;
?? 結帳;
?? V(S_CartNum);
}
?
?
??? 例2：桌子上有一個水果盤，每一次可以往里面放入一個水果。爸爸專向盤子中放蘋果，兒子專等吃盤子中的蘋果。把爸爸、兒子看作二個進程，試用P、V操作使這兩個進程能正確地并發執行。
?
??? 分析：爸爸和兒子兩個進程相互制約，爸爸進程執行完即往盤中放入蘋果后，兒子進程才能執行即吃蘋果。因此該問題為進程間的同步問題。
?
??? 解：
?
semaphore? S_PlateNum;? // 盤子容量，初值為1
semaphore? S_AppleNum;? // 蘋果數量，初值為0
void? father( )? // 父親進程
{
??? while(1)
??? {
??????? P(S_PlateNum);
??????? 往盤子中放入一個蘋果;
??????? V(S_AppleNum);
??? }
}
void? son( )?? // 兒子進程
{
??? while(1)
??? {
??????? P(S_AppleNum);
??????? 從盤中取出蘋果;
??????? V(S_PlateNum);
??????? 吃蘋果；
??? }
}
?
---------------------------------------------
?
??? 另附用PV原語解決進程同步與互斥問題的例子:
?
???
??? 例3：兩個進程PA、PB通過兩個FIFO(先進先出)緩沖區隊列連接(如圖)
??? 
??? PA從Q2取消息，處理后往Q1發消息；PB從Q1取消息，處理后往Q2發消息，每個緩沖區長度等于傳送消息長度。 Q1隊列長度為n，Q2隊列長度為m. 假設開始時Q1中裝滿了消息，試用P、V操作解決上述進程間通訊問題。
?
??? 解：
?
// Q1隊列當中的空閑緩沖區個數，初值為0
semaphore? S_BuffNum_Q1;??
// Q2隊列當中的空閑緩沖區個數，初值為m
semaphore? S_BuffNum_Q2;????
// Q1隊列當中的消息數量，初值為n
semaphore? S_MessageNum_Q1;
// Q2隊列當中的消息數量，初值為0
semaphore? S_MessageNum_Q2;
?
void PA( )
{
??? while(1)
???
{
??????? P(S_MessageNum_Q2);
??????? 從Q2當中取出一條消息;
??????? V(S_BuffNum_Q2);
??????? 處理消息;
??????? 生成新的消息;
??????? P(S_BuffNum_Q1);
??????? 把該消息發送到Q1當中;
??????? V(S_MessageNum_Q1);
??? }
}
?
void PB( )
{
??? while(1)
???
{
??????? P(S_MessageNum_Q1);
??????? 從Q1當中取出一條消息;
??????? V(S_BuffNum_Q1);
??????? 處理消息;
??????? 生成新的消息;
??????? P(S_BuffNum_Q2);
??????? 把該消息發送到Q2當中;
??????? V(S_MessageNum_Q2);
???
}
}
?
?
??? 例4：《操作系統》課程的期末考試即將舉行，假設把學生和監考老師都看作進程，學生有N人，教師1人。考場門口每次只能進出一個人，進考場的原則是先來先進。當N個學生都進入了考場后，教師才能發卷子。學生交卷后即可離開考場，而教師要等收上來全部卷子并封裝卷子后才能離開考場。
??? (1)問共需設置幾個進程?
??? (2)請用P、V操作解決上述問題中的同步和互斥關系。
?
??? 解：
?
semaphore? S_Door;???????? // 能否進出門，初值1
semaphore? S_StudentReady; // 學生是否到齊，初值為0
semaphore? S_ExamBegin;?? // 開始考試，初值為0
semaphore? S_ExamOver;??? // 考試結束，初值為0
?
int nStudentNum = 0;?????? // 學生數目
semaphore? S_Mutex1;?????? //互斥信號量，初值為1
int? nPaperNum = 0;?????? // 已交的卷子數目
semaphore? S_Mutex2;?????? //互斥信號量，初值為1
?
void? student( )
{
??? P(S_Door);
??? 進門;
??? V(S_Door);
??? P(S_Mutex1)；
??? nStudentNum ++;?? // 增加學生的個數
??? if(nStudentNum == N)? V(S_StudentReady);
??? V(S_Mutex1);
??? P(S_ExamBegin);? // 等老師宣布考試開始
??? 考試中…
??? 交卷;
??? P(S_Mutex2);
??? nPaperNum ++;??? // 增加試卷的份數
??????? if(nPaperNum == N)?
??????? V(S_ExamOver);
??????? V(S_Mutex2);
??????? P(S_Door);
??????? 出門;
??????? V(S_Door);
}
?
void? teacher( )
{
??? P(S_Door);
??? 進門;
??? V(S_Door);
??? P(S_StudentReady);??? //等待最后一個學生來喚醒
??? 發卷子;
??????? for(i = 1; i <= N; i++)???
??????? V(S_ExamBegin);
??????? P(S_ExamOver);??? //等待考試結束
??????? 封裝試卷;
??????? P(S_Door);
??????? 出門;
??????? V(S_Door);
}
?
?
?
???
例
5：某商店有兩種食品A和B，最大數量均為m個。 該商店將A、B兩種食品搭配出售，每次各取一個。為避免食品變質，遵循先到食品先出售的原則。有兩個食品公司分別不斷地供應A、B兩種食品(每次一個)。為保證正常銷售，當某種食品的數量比另一種的數量超過k(k<m)個時，暫停對數量大的食品進貨，補充數量少的食品。
??? (1) 問共需設置幾個進程?
??? (2) 用P、V操作解決上述問題中的同步互斥關系。
?
??? 解：
?
semaphore? S_BuffNum_A;? //A的緩沖區個數, 初值m
semaphore? S_Num_A;????? // A的個數，初值為0
semaphore? S_BuffNum_B;? //B的緩沖區個數, 初值m
semaphore? S_Num_B;????? // B的個數，初值為0
?
void? Shop( )
{
??? while(1)
??? {
??????? P(S_Num_A);
??????? P(S_Num_B);
??????? 分別取出A、B食品各一個;
??????? V(S_BuffNum_A);
??????? V(S_BuffNum_A);
??????? 搭配地銷售這一對食品;
??? }
}
?
// “A食品加1，而B食品不變”這種情形允許出現的次數(許可證的數量)，其值等于//k-(A-B)，初值為k
semaphore? S_A_B;
// “B食品加1，而A食品不變”這種情形允許出現的次數(許可證的數量)，其值等于//k-(B-A)，初值為k
semaphore? S_B_A;
?
void? Producer_A( )
{
??? while(1)
??? {
??????? 生產一個A食品;
??????? P(S_BuffNum_A);
??????? P(S_A_B);
??????? 向商店提供一個A食品;
??????? V(S_Num_A);
??????? V(S_B_A);
??? }
}
?
void? Producer_B( )
{
??? while(1)
??? {
??????? 生產一個B食品;
??????? P(S_BuffNum_B);
??????? P(S_B_A);
??????? 向商店提供一個B食品;
??????? V(S_Num_B);
??????? V(S_A_B);
??? }
}
?
?
???
例6：在一棟學生公寓里，只有一間浴室，而且這間浴室非常小，每一次只能容納一個人。公寓里既住著男生也住著女生，他們不得不分享這間浴室。因此，樓長制定了以下的浴室使用規則：
???
(1)每一次只能有一個人在使用；
???
(2)女生的優先級要高于男生，即如果同時有男生和女生在等待使用浴室，則女生優先；
???
(3)對于相同性別的人來說，采用先來先使用的原則。
?
??? 假設：
???
(1)當一個男生想要使用浴室時，他會去執行一個函數boy_wants_to_use_bathroom，當他離開浴室時，也會去執行另外一個函數boy_leaves_bathroom；
???
(2)當一個女生想要使用浴室時，會去執行函數girl_wants_to_use_bathroom，當她離開時, 也會執行函數girl_leaves_bathroom;
?
??? 問題：請用信號量和P、V操作來實現這四個函數（初始狀態：浴室是空的）。
?
??? 解：
?
信號量的定義：
semaphore? S_mutex;? // 互斥信號量，初值均為1
semaphore? S_boys; ? // 男生等待隊列，初值為0
semaphore? S_girls; // 女生等待隊列，初值為0
?
普通變量的定義：
int? boys_waiting = 0;? // 正在等待的男生數；
int? girls_waiting = 0; // 正在等待的女生數；
int? using = 0;???? ?? // 當前是否有人在使用浴室;
?
void? boy_wants_to_use_bathroom ( )
{
??? P(S_mutex);
??? if((using == 0) && (girls_waiting == 0))
??????? {
??????????? using? =? 1;
??????????? V(S_mutex);
??????? }
??? else
??????? {
??????????? boys_waiting ++;
??????????? V(S_mutex);
??????????? P(S_boys);
??????? }
}
?
void? boy_leaves_bathroom ( )
{
??? P(S_mutex);
??? if(girls_waiting? >? 0)? // 優先喚醒女生
??????? {
??????????? girls_waiting --;
??????????? V(S_girls);
??????? }
??? else? if(boys_waiting? >? 0)
??????? {
??????????? boys_waiting --;
??????????? V(S_ boys);
??????? }
??????? else???
??????????? using? =? 0;???? // 無人在等待
??????? ??? V(S_mutex);
}
?
void? girl_wants_to_use_bathroom ( )
{
??? P(S_mutex);
??? if(using == 0)
??? {
??????? using? =? 1;
??????? V(S_mutex);
??? }
??? else
??? {
??????? girls_waiting ++;
??????? V(S_mutex);
??????? P(S_girls);
??? }
}
?
void? girl_leaves_bathroom ( )
{
??? P(S_mutex);
??? if(girls_waiting? >? 0)? // 優先喚醒女生
??? {
??????? girls_waiting --;
??????? V(S_girls);
??? }
??? else? if(boys_waiting? >? 0)
??????? {
??????????? boys_waiting --;
??????????? V(S_ boys);
??????? }
??????? else???
??????????? using? =? 0;???? // 無人在等待
??????????? V(S_mutex);
}
?
?
?
?
?
?
?
?
再附上幾個例子：
********************************************************************************************************
?
用PV原語實現進程的互斥
由于用于互斥的信號量sem與所有的并發進程有關，所以稱之為公有信號量。公有信號量的值反映了公有資源的數量。只要把臨界區置于P(sem)和V(sem)之間，即可實現進程間的互斥。就象火車中的每節車廂只有一個衛生間，該車廂的所有旅客共享這個公有資源：衛生間，所以旅客間必須互斥進入衛生間，只要把衛生間放在P(sem)和V(sem)之間，就可以到達互斥的效果。以下例子說明進程的互斥實現。
例1：
??? 生產圍棋的工人不小心把相等數量的黑子和白子混裝載一個箱子里，現要用自動分揀系統把黑子和白子分開，該系統由兩個并發執行的進程組成，功能如下：
??? (1)進程A專門揀黑子，進程B專門揀白子；
??? (2)每個進程每次只揀一個子，當一個進程在揀子時不允許另一個進程去揀子；
?
??? 分析：
??? 第一步：確定進程間的關系。由功能(2)可知進程之間是互斥的關系。
??? 第二步：確定信號量及其值。由于進程A和進程B要互斥進入箱子去揀棋子，箱子是兩個進程的公有資源，所以設置一個信號量s，其值取決于公有資源的數目，由于箱子只有一個，s的初值就設為1。
?
??? 實現：
begin
??? s:semaphore;
??? s:=1;
??? cobegin
??????? process A
??????? begin
??????????? L1: P(s);
??????????? 揀黑子;
??????????? V(s);
??????????? goto L1;
??????? end;
??????? process B
??????? begin
??????????? L2:P(s);
??????????? 揀白子；
??????????? V(s);
??????????? goto L2;
??????? end;
??? coend;
end;
?
判斷進程間是否互斥，關鍵是看進程間是否共享某一公有資源，一個公有資源與一個信號量相對應。確定信號量的值是一個關鍵點，它代表了可用資源實體數。如下實例：
?
?
例2：
??? 某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，廳外的購票者可立即進入，否則需要在外面等待。每個購票者可看成一個進程。
?
??? 分析：第一步：確定進程間的關系。售票廳是各進程共享的公有資源，當售票廳中多于20名購票者時，廳外的購票者需要在外面等待。所以進程間是互斥的關系。第二步：確定信號量及其值。只有一個公有資源：售票廳，所以設置一個信號量s。售票廳最多容納20個進程，即可用資源實體數為20，s的初值就設為20。
?
??? 實現：
?
begin
??? s:semaphore;
??? s:=20;
??? cobegin
??????? process PI(I=1,2,……)
??????? begin P(s);
??????????? 進入售票廳;
??????????? 購票;
??????????? 退出;
??????????? V(s);
??????? end;
??? coend;
end;
?
??? 當購票者進入售票廳前要執行P(s)操作，執行后若s大于或等于零，說明售票廳的人數還未滿可進入。執行后若s小于零，則說明售票廳的人數已滿不能進入。這個實現中同時最多允許20個進程進入售票廳購票，其余進程只能等待。
?
用PV原語實現進程的同步
與進程互斥不同，進程同步時的信號量只與制約進程及被制約進程有關而不是與整組并發進程有關，所以稱該信號量為私有信號量。利用PV原語實現進程同步的方法是：首先判斷進程間的關系為同步的，且為各并發進程設置私有信號量，然后為私有信號量賦初值，最后利用PV原語和私有信號量規定各進程的執行順序。下面我們將例1增添一個條件，使其成為進程間是同步的。
例3：
??? 在例1的基礎之上再添加一個功能：
(3)當一個進程揀了一個棋子（黑子或白子）以后，必讓另一個進程揀一個棋子（黑子或白子）。
?
??? 分析：
??? 第一步：確定進程間的關系。由功能（1）（2）（3）可知，進程間的關系為同步關系。第二步：確定信號量及其值。進程A和B共享箱子這個公有資源，但規定兩個進程必須輪流去取不同色的棋子，因而相互間要互通消息。對于進程A可設置一個私有信號量s1，該私有信號量用于判斷進程A是否能去揀黑子，初值為1。對于進程B同樣設置一個私有信號量s2，該私有信號量用于判斷進程B是否能去揀白子，初值為0。當然你也可以設置s1初值為0，s2初值為1。
?
??? 實現:
?
begin
??? s1,s2:semaphore;
??? s1:=1;s2:=0;
??? cobegin
??????? process A
??????? ??? begin
??????? ??? L1: P(s1);
??????? ??? 揀黑子;
??????? ??? V(s2);
??????? ??? goto L1;
??????? end;???
??????? process B
??????? begin
??????????? L2:P(s2);
??????????? 揀白子;
??????????? V(s1);
??????????? goto L2;
??????? end;
??? coend;
end;
?
另外一個問題就是P原語是不是一定在V原語的前面？回答是否定的。下面看一個例子：
例4：
??? 設在公共汽車上，司機和售票員的活動分別是：司機：啟動車輛，正常行車，到站停車。售票員：上乘客，關車門，售票，開車門，下乘客。用PV操作對其控制。
?
??? 分析：
??? 第一步：確定進程間的關系。司機到站停車后，售票員方可工作。同樣，售票員關車門后，司機才能工作。所以司機與售票員之間是一種同步關系。
??? 第二步：確定信號量及其值。由于司機與售票員之間要互通消息，司機進程設置一個私有信號量run，用于判斷司機能否進行工作，初值為0。售票員進程設置一個私有信號量stop，用于判斷是否停車，售票員是否能夠開車門，初值為0。
??? 實現：
begin
??? stop ,run:semaphore
??? stop:=0;run:=0;
??? cobegin
??????? driver:
??????? begin
??????????? L1: P(run);
??????????? 啟動車輛；
??????????? 正常行車；
??????????? 到站停車；
??????????? V(stop);
??????????? goto L1;
??????? end;
??????? conductor:
??????? begin
??????????? L2:上乘客；
??????????? 關車門；
??????????? V(run);
??????????? 售票；
??????????? P(stop);
??????????? 開車門；
??????????? 下乘客；
??????????? goto L2;
??????? end;
??? coend;
end;
?
用PV操作還可以實現進程同步與互斥的混合問題，典型的如：多個生產者和多個消費者共享容量為n的緩存區。這個例子在很多書中都有介紹，在這里就不說了。
?
?