3．在某超市里有一個(gè)收銀員，且同時(shí)最多允許有n個(gè)顧客購物，我們可以將顧客和收銀員看成是兩類不同的進(jìn)程，且工作流程如下圖所示。為了利用PV操作正確地協(xié)調(diào)這兩類進(jìn)程之間的工作，設(shè)置了三個(gè)信號量S1、S2和Sn，且初值分別為0、0和n。這樣圖中的a應(yīng)填寫__(1)__，圖中的b1、b2應(yīng)分別填寫__(2)__，圖中的c1、c2應(yīng)分別填寫__(3)__。
500){this.resized=true;this.style.width=500;}" resized="true">
(1) A. P(S1) B．P(S2) C．P(Sn) D．P(Sn)、P(S1)
(2) A．P(Sn)、V(S2) B．P(Sn)、V(S1) C．P(S2)、V(S1) D.V(S1)、P(S2)
(3) A．P(S1)、V(S2) B．P(Sn)、V(S1) C．P(S2)、V(S1) D． V(S1)、 P(S2)
答案：（1）C （2）D （3）A
解析：這是一道考查PV操作的題，所以首先得弄清楚那些地方需要互斥、那些地方需要同步。題目中給出了兩類進(jìn)程：顧客進(jìn)程與收銀元進(jìn)程，由于超市是顧客進(jìn)程之間的公有資源，而且超市里限制最多允許有n個(gè)顧客購物，所以要設(shè)置一個(gè)公有信號量Sn，初值是n，顧客進(jìn)程在進(jìn)入超市時(shí)要執(zhí)行P(Sn)，離開超市時(shí)要執(zhí)行V(Sn)操作。顧客購物后要到收銀員處付款，因此顧客進(jìn)程與收銀員進(jìn)程之間是同步的關(guān)系，一次只允許一個(gè)顧客進(jìn)程付款，整個(gè)超市只有一個(gè)收銀員進(jìn)程收費(fèi)，所以需要為顧客進(jìn)程設(shè)置一個(gè)私有信號量S2，為收銀員進(jìn)程設(shè)置一個(gè)私有信號量S1，由于開始時(shí)沒有顧客去付款，收銀員也沒有收費(fèi)，所以S1和S2的初值為0。當(dāng)有顧客買完東西去付款時(shí)執(zhí)行V(S1)，通知收銀員進(jìn)程有顧客付款，此時(shí)收銀員進(jìn)程執(zhí)行P(S1)操作后就可進(jìn)入收費(fèi)，收費(fèi)完成后收銀元進(jìn)程執(zhí)行V(S2)，以通知顧客收費(fèi)完畢，此時(shí)顧客執(zhí)行P(S2)就可離開收銀臺，在離開超市時(shí)需執(zhí)行V(Sn)，釋放資源。
復(fù)習(xí)提示：PV操作在操作系統(tǒng)中處于很重要得地位，要想合適的運(yùn)用PV操作，必須很好的理解進(jìn)程之間的互斥與同步，即那些進(jìn)程之間是互斥的，那些進(jìn)程之間是同步的。
2005年上半年程序員試題
●某系統(tǒng)中有一個(gè)緩沖區(qū)，進(jìn)程P1不斷地生產(chǎn)產(chǎn)品送入緩沖區(qū)，進(jìn)程P2不斷地從緩沖區(qū)取產(chǎn)品消費(fèi)。假設(shè)該緩沖區(qū)只能容納一個(gè)產(chǎn)品。進(jìn)程P1與P2的同步模型如下圖所示：
(這個(gè)圖就是教程中常見的那個(gè)圖)
P1 P2
__| __|
| 生產(chǎn)一個(gè)產(chǎn)品 | P(S2)
| P(S1) | 從緩沖區(qū)取一個(gè)產(chǎn)品
| 產(chǎn)品送緩沖區(qū) | V(S1)
| V(S2) | 消費(fèi)
|__| |__|
為此，應(yīng)設(shè)信號量S1的初值為__(18)__，信號量S2的初值為__(19)__。
(18) A．-2 B．-1 C．0 D．1
(19) A．-2 B．-1 C．0 D．1
答案：(18)D (19)C
分析：
資源S是這個(gè)資源初始狀態(tài)擁有的數(shù)目，也就是沒有任何操作，剛開始的時(shí)候資源的可用數(shù)。
簡單的例子，一個(gè)盤子可以放8個(gè)蘋果，一次只能一個(gè)人拿一個(gè)蘋果或者放一個(gè)蘋果，則設(shè)置兩個(gè)資源S1、S2分別表示盤子中蘋果的數(shù)量和取放蘋果的許可，則S1初始值為8，S2為1。
以下一定要記住：
P操作
S = S-1
S<0 阻塞
V操作
S= S+1
S 〈=0 喚醒
S1、S2分別是P1、P2對緩沖區(qū)操作的開關(guān)，S1=1表示初始狀態(tài)P1進(jìn)程可以對緩沖區(qū)進(jìn)行操作，而對于S2=0正好阻止了P2進(jìn)程對緩沖區(qū)的操作！在剛開始的時(shí)候緩沖區(qū)為空，其允許P1在其中放入產(chǎn)品，但不能讓P2取出產(chǎn)品，所以才產(chǎn)生這樣的結(jié)果
P一次什么什么就減一個(gè)。如果你P的玩意是0.那P下面的東西就不開工了。
V 一次什么就加一次
這個(gè)同步有s1 s2.
s1肯定是為1的。緩沖區(qū)可以放幾個(gè)東西就應(yīng)該是幾.
你P了p1 一次以后。 代表向緩沖區(qū)里放了東西。s1 = 0了。表示緩沖區(qū)不能放東西了。進(jìn)程時(shí)并行了。假設(shè)這句執(zhí)行完了后跳到第二個(gè)程序中去。是p(s2) 剛肯定不行。所以s2一定要為初始要為0. 要等待第一個(gè)放進(jìn)緩沖區(qū)的事做完后V(s2)把s2標(biāo)志位搞醒
●某倉庫有兩名發(fā)貨員，一名審核員。當(dāng)顧客提貨時(shí)，只要發(fā)貨員空閑,允許顧客進(jìn)入倉庫提貨，顧客離開時(shí)，審核員檢驗(yàn)顧客提貨是否正確。其工作流程如下圖所示。為了利用PV操作正確地協(xié)調(diào)他們之間的工作，設(shè)置了兩個(gè)信號量S1和S2，且S1的初值為2，S2的初值為1。圖中的a應(yīng)填寫____(25)___；圖中的b、c和d應(yīng)分別填寫____(26)____。
500){this.resized=true;this.style.width=500;}">
供選擇的答案：
(25)A.P(S1) B.P(S2) C.V(S1) D.V(S2)
(26)A.P(S2)、V（S2）和V（S1） B.P（S1）、V（S1）和V（S2）
C.V（S1）、P(S2)和V(S2) D.V（S2）、P（S1）和V（S1）
分析：
顧客來了,要看看是否有發(fā)貨員.即發(fā)貨員資源是否存在.
所以用P(S1) 若S1>0表示,存在(無論多少)
若S1<=0表示,不存在,進(jìn)程阻塞.
提完貨.這說明,肯定用發(fā)貨員了.肯定還有人等著提貨.這時(shí),應(yīng)該釋放發(fā)貨員.
所以用V(S1)
然后,要審貨.
可能有人正在審呢,所以用P(S2)意思和上面相同.
審?fù)曦?要釋放,可能有人正等著審呢.所以用V(S2)釋放審貨員.
完畢.
PV原語實(shí)現(xiàn)進(jìn)程間互斥與同步
PV原語的含義
P操作和V操作是不可中斷的程序段，稱為原語。PV原語及信號量的概念都是由荷蘭科學(xué)家E.W.Dijkstra提出的。信號量sem是一整數(shù)，sem大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。
P原語操作的動(dòng)作是：
（1）sem減1；
（2）若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；
（3）若sem減1后小于零，則該進(jìn)程被阻塞后進(jìn)入與該信號相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。
V原語操作的動(dòng)作是：
（1）sem加1；
（2）若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行；
（3）若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。
PV操作對于每一個(gè)進(jìn)程來說，都只能進(jìn)行一次，而且必須成對使用。在PV原語執(zhí)行期間不允許有中斷的發(fā)生。
用PV原語實(shí)現(xiàn)進(jìn)程的互斥
由于用于互斥的信號量sem與所有的并發(fā)進(jìn)程有關(guān)，所以稱之為公有信號量。公有信號量的值反映了公有資源的數(shù)量。只要把臨界區(qū)置于P(sem)和V(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。就象火車中的每節(jié)車廂只有一個(gè)衛(wèi)生間，該車廂的所有旅客共享這個(gè)公有資源：衛(wèi)生間，所以旅客間必須互斥進(jìn)入衛(wèi)生間，只要把衛(wèi)生間放在P(sem)和V(sem)之間，就可以到達(dá)互斥的效果。以下例子說明進(jìn)程的互斥實(shí)現(xiàn)。
例1
生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個(gè)箱子里，現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，功能如下：
（1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；
（2）每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子；
分析：
第一步：確定進(jìn)程間的關(guān)系。由功能（2）可知進(jìn)程之間是互斥的關(guān)系。
第二步：確定信號量及其值。由于進(jìn)程A和進(jìn)程B要互斥進(jìn)入箱子去揀棋子，箱子是兩個(gè)進(jìn)程的公有資源，所以設(shè)置一個(gè)信號量s，其值取決于公有資源的數(shù)目，由于箱子只有一個(gè)，s的初值就設(shè)為1。
實(shí)現(xiàn)：
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;
判斷進(jìn)程間是否互斥，關(guān)鍵是看進(jìn)程間是否共享某一公有資源，一個(gè)公有資源與一個(gè)信號量相對應(yīng)。確定信號量的值是一個(gè)關(guān)鍵點(diǎn)，它代表了可用資源實(shí)體數(shù)。如下實(shí)例：
例2
某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，廳外的購票者可立即進(jìn)入，否則需要在外面等待。每個(gè)購票者可看成一個(gè)進(jìn)程。
分析：第一步：確定進(jìn)程間的關(guān)系。售票廳是各進(jìn)程共享的公有資源，當(dāng)售票廳中多于20名購票者時(shí)，廳外的購票者需要在外面等待。所以進(jìn)程間是互斥的關(guān)系。第二步：確定信號量及其值。只有一個(gè)公有資源：售票廳，所以設(shè)置一個(gè)信號量s。售票廳最多容納20個(gè)進(jìn)程，即可用資源實(shí)體數(shù)為20，s的初值就設(shè)為20。
實(shí)現(xiàn)：
begin
s:semaphore;
s:=20;
cobegin
process PI(I=1,2,……)
begin P(s);
進(jìn)入售票廳；
購票；
退出；
V(s);
end;
coend
當(dāng)購票者進(jìn)入售票廳前要執(zhí)行P(s)操作，執(zhí)行后若s大于或等于零，說明售票廳的人數(shù)還未滿可進(jìn)入。執(zhí)行后若s小于零，則說明售票廳的人數(shù)已滿不能進(jìn)入。這個(gè)實(shí)現(xiàn)中同時(shí)最多允許20個(gè)進(jìn)程進(jìn)入售票廳購票，其余進(jìn)程只能等待。
用PV原語實(shí)現(xiàn)進(jìn)程的同步
與進(jìn)程互斥不同，進(jìn)程同步時(shí)的信號量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)，所以稱該信號量為私有信號量。利用PV原語實(shí)現(xiàn)進(jìn)程同步的方法是：首先判斷進(jìn)程間的關(guān)系為同步的，且為各并發(fā)進(jìn)程設(shè)置私有信號量，然后為私有信號量賦初值，最后利用PV原語和私有信號量規(guī)定各進(jìn)程的執(zhí)行順序。下面我們將例1增添一個(gè)條件，使其成為進(jìn)程間是同步的。
例3
在例1的基礎(chǔ)之上再添加一個(gè)功能：
（3）當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子（黑子或白子）以后，必讓另一個(gè)進(jìn)程揀一個(gè)棋子（黑子或白子）。
分析：
第一步：確定進(jìn)程間的關(guān)系。由功能（1）（2）（3）可知，進(jìn)程間的關(guān)系為同步關(guān)系。第二步：確定信號量及其值。進(jìn)程A和B共享箱子這個(gè)公有資源，但規(guī)定兩個(gè)進(jìn)程必須輪流去取不同色的棋子，因而相互間要互通消息。對于進(jìn)程A可設(shè)置一個(gè)私有信號量s1，該私有信號量用于判斷進(jìn)程A是否能去揀黑子，初值為1。對于進(jìn)程B同樣設(shè)置一個(gè)私有信號量s2，該私有信號量用于判斷進(jìn)程B是否能去揀白子，初值為0。當(dāng)然你也可以設(shè)置s1初值為0，s2初值為1。
實(shí)現(xiàn):
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;
另外一個(gè)問題就是P原語是不是一定在V原語的前面？回答是否定的。下面看一個(gè)例子。
例4
設(shè)在公共汽車上，司機(jī)和售票員的活動(dòng)分別是：司機(jī)：啟動(dòng)車輛，正常行車，到站停車。售票員：上乘客，關(guān)車門，售票，開車門，下乘客。用PV操作對其控制。
分析：
第一步：確定進(jìn)程間的關(guān)系。司機(jī)到站停車后，售票員方可工作。同樣，售票員關(guān)車門后，司機(jī)才能工作。所以司機(jī)與售票員之間是一種同步關(guān)系。
第二步：確定信號量及其值。由于司機(jī)與售票員之間要互通消息，司機(jī)進(jìn)程設(shè)置一個(gè)私有信號量run，用于判斷司機(jī)能否進(jìn)行工作，初值為0。售票員進(jìn)程設(shè)置一個(gè)私有信號量stop，用于判斷是否停車，售票員是否能夠開車門，初值為0。
實(shí)現(xiàn)：
begin stop ,run:semaphore
stop:=0;run:=0;
cobegin
driver: begin
L1: P(run);
啟動(dòng)車輛；
正常行車；
到站停車；
V(stop);
goto L1;
end;
conductor:begin
L2:上乘客；
關(guān)車門；
V(run);
售票；
P(stop);
開車門；
下乘客；
goto L2;
end;
coend;
end;
用PV操作還可以實(shí)現(xiàn)進(jìn)程同步與互斥的混合問題，典型的如：多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者共享容量為n的緩存區(qū)。這個(gè)例子在很多書中都有介紹，在這里就不說了。