操作經(jīng)典例題

1、P就是請求資源，V就是釋放資源。 問題1 一個司機與售票員的例子 在公共汽車上，為保證乘客的安全，司機和售票員應(yīng)協(xié)調(diào)工作： 停車后才能開門，關(guān)車門后才能行車。用PV操作來實現(xiàn)他們之間的協(xié)調(diào)。 S1：是否允許司機啟動汽車的變量 S2：是否允許售票員開門的變量 driver()/司機進程 while (1)/不停地循環(huán) P(S1);/請求啟動汽車 啟動汽車; 正常行車； 到站停車； V(S2); /釋放開門變量，相當(dāng)于通知售票員可以開門 busman()/售票員進程 while(1) 關(guān)車門; V(S1)；/釋放開車變量，相當(dāng)于通知司機可以開車 售票 P(S2)；/請求開門 開車門； 上下乘客；

2、注意：busman() driver() 兩個不停循環(huán)的函數(shù)問題2 圖書館有100個座位，每位進入圖書館的讀者要在登記表上登記，退出時要在登記表上注銷。要幾個程序？有多少個進程？（答：一個程序；為每個讀者設(shè)一個進程）（1） 當(dāng)圖書館中沒有座位時，后到的讀者在圖書館為等待（阻塞）（2） 當(dāng)圖書館中沒有座位時，后到的讀者不等待，立即回家。解（1 )設(shè)信號量：S=100; MUTEX=1P(S)P(MUTEX)登記V(MUTEX)閱讀P(MUTEX)注銷V(MUTEX)V(S) 解(2)設(shè)整型變量 COUNT=100; 信號量：MUTEX=1;P(MUTEX);IF (COUNT=0) V(MUTE

3、X); RETURN;COUNT=COUNT-1;登記V(MUTEX);閱讀P(MUTEX);COUNT=COUNT+1;V(MUTEX);RETURN;問題3 有一座東西方向的獨木橋；用P,V操作實現(xiàn)：（1） 每次只允許一個人過橋；（2） 當(dāng)獨木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。（3） 當(dāng)獨木橋上有自東向西的行人時，同方向的行人可以同時過橋，從西向東的方向，只允許一個人單獨過橋。（此問題和讀者與寫者問題相同,東向西的為讀者，西向東的為寫者）。（1）解設(shè)信號量 MUTEX=1P (MUTEX) 過橋V (MUTEX)(2)解設(shè)信號量： MUTEX=1 (東西方互斥)

4、 MD=1 (東向西使用計數(shù)變量互斥) MX=1 (西向東使用計數(shù)變量互斥)設(shè)整型變量： CD=0 (東向西的已上橋人數(shù)) CX=0 (西向東的已上橋人數(shù))從東向西：P (MD)IF (CD=0)P (MUTEX) CD=CD+1V (MD)過橋P (MD)CD=CD-1IF (CD=0)V (MUTEX) V (MD)從西向東：P (MX)IF (CX=0)P (MUTEX) CX=CX+1V (MX)過橋P (MX)CX=CX-1IF (CX=0)V (MUTEX) V (MX)(3) 解：從東向西的，和（2）相同；從西向東的和（1）相同。問題4 有一個俱樂部，有甲乙兩個服務(wù)員，當(dāng)顧客有請

5、求時，甲負責(zé)送煙，乙負責(zé)送火，無顧客請求時，服務(wù)員睡眠。顧客自己不能帶煙和火，當(dāng)顧客要抽煙時，可請求服務(wù)員送煙和火，煙和火還未送到時，顧客必須等待。設(shè)信號量：SY, SH,CY,CH:初值都為0甲服務(wù)員REPEATP(SY)送煙V(CY)UNTIL FALSE乙服務(wù)員REPEATP(SH)送火V(CH)UNTIL FALSE顧客V(SY) /*（請求送煙）*/V(SH) /*（請求送火）*/P(CY) /* (等煙) */P(CH) /* (等火) */抽煙問題5一家四人父、母、兒子、女兒圍桌而坐；桌上有一個水果盤；（1） 當(dāng)水果盤空時，父親可以放香蕉或者母親可以放蘋果，但盤中已有水果時，就不

6、能放，父母等待。當(dāng)盤中有香蕉時，女兒可吃香蕉，否則，女兒等待；當(dāng)盤中有蘋果時，兒子可吃，否則，兒子等待。解 設(shè)信號量：SE=1 (空盤子)；SA0 （放了蘋果的盤子）；SB=0 (放了香蕉的盤子)父親REPEAT剝香蕉P(SE)放香蕉V(SB)UNTIL FALSE母親REPEAT削蘋果P(SE)放蘋果V(SA)UNTIL FALSE兒子P(SA)拿蘋果V(SE)吃蘋果女兒P(SB)拿香蕉V(SE)吃香蕉（2） 把（1）改為：兒子要吃蘋果時，請母親放蘋果，女兒要吃香蕉時，請父親放香蕉，（還是盤子為空時才可以放）。（2）解：再增加兩個信號量：SF=0, SM=0父親REPEATP(SF)剝香蕉P

7、(SE)放香蕉V(SB)UNTIL FALSE母親REPEATP(SM)削蘋果P(SE)放蘋果V(SA)UNTIL FALSE兒子V(SM)P(SA)拿蘋果V(SE)吃蘋果女兒V(SF)P(SB)拿香蕉V(SE)吃香蕉問題6有一個超市，最多可容納N個人進入購物，當(dāng)N個顧客滿員時，后到的顧客在超市外等待；超市中只有一個收銀員?？梢园杨櫩秃褪浙y員看作兩類進程，兩類進程間存在同步關(guān)系。寫出用P;V操作實現(xiàn)的兩類進程的算法（2003年系統(tǒng)設(shè)計員考試的題目）解：設(shè)信號量：S=0，C=0 (顧客與收銀員的同步信號量)，M=N收銀員P(S)收銀V(C)顧客P(M)進入店內(nèi)購物V(S)P(C)V(M)問題7有

8、一個理發(fā)店，店內(nèi)共有20個座位供顧客等待理發(fā)，（進入理發(fā)店的顧客，都在此座位上等待理發(fā)，正在理發(fā)的顧客不占用此座位），當(dāng)20個座位坐滿了，后到的顧客不等待，立即回家。當(dāng)沒有顧客時，理發(fā)師睡眠等待。解：設(shè)信號量：S=0.C=0,MUTEX=1設(shè)整型變量 SM=20理發(fā)師REPEATP(S) -如無顧客，理發(fā)師等待V(C) 叫一個顧客理發(fā)理發(fā)UNTIL FALSE顧客P(MUTEX)IF (SM=0) V(MUTEX)滿座，離開，回家RETURNELSESM=SM-1空座位數(shù)減 1V(MUTEX)V(S)通知理發(fā)師，增加了一個顧客，如理發(fā)師在等待則喚醒他P(C) 等理發(fā)師叫自己理發(fā)P(MUTEX)

9、SM=SM+1被叫到，釋放一個空的座位V(MUTEX)接受理發(fā)如果此題改為：滿座時，顧客等待空座位：則 顧客進程的程序修改如下：把SM設(shè)為信號量 SM=20顧客P(SM) -申請一個座位，無則等待V(S)通知理發(fā)師，增加了一個顧客，如理發(fā)師在等待則喚醒他P(C) 等理發(fā)師叫自己理發(fā)V(SM)接受理發(fā)問題8一個盒子，內(nèi)有黑白兩種棋子（數(shù)量相等），甲每次從盒子中取出一顆黑子，乙每次從盒子中取出一顆白子，一人取了棋子后，必須等另一方取過棋子方可再取，（可假設(shè)甲先取）。解： 設(shè)信號量：SJ=1,SY=0甲REPEATP(SJ)取一顆黑子V(SY)UNTIL 盒子中無黑子乙REPEATP(SY)取一顆白

10、子V(SJ)UNTIL 盒子中無白子（八）按要求完成下面的程序。設(shè)有三個進程，input進程、compute進程和output進程；它們通過共享一個緩沖區(qū)buf的合作關(guān)系如下：（1）input進程每次輸入數(shù)據(jù)后，把數(shù)據(jù)送到buf,供compute進程計算和output進程打?。唬?）comput進程每次從buf取出已輸入的可計算的數(shù)據(jù)進行計算，并當(dāng)output進程把輸入數(shù)據(jù)打印完成后，把計算結(jié)果送入buf供output進程打??；（3）output進程每次按順序把buf中的輸入數(shù)據(jù)和計算結(jié)果在打印機上輸出。解：設(shè)信號量：sa=1,sb=sc=sd=0, 請把能正確實現(xiàn)這三個進程同步關(guān)系的P、V

11、操作的語句填入下面的程序。procedure inputbeginlocal datarepeat get(data); /*輸入數(shù)據(jù)到data*/ p(sa); buf=data; (1) V ( sc ) v(sb);until falseend;procedure computebeginlocol datarepeat (2) P ( sb ) data=buf; 計算data并把結(jié)果保存在data; (3) P ( sd ) buf=data; v(sc);until falseend;procedure outputbeginlocal datarepeat P(sc) 打印 bu

12、f; (4) V ( sd ) p(sc) 打印 buf; v(sa);until falseend;5.今有三個進程R、M、P，它們共享一個緩沖區(qū)。R負責(zé)從輸入設(shè)備讀信息，每次讀出一個記錄并把它存放在緩沖區(qū)中：M在緩沖區(qū)加工讀入的記錄；P把加工后的記錄打印輸出。輸入的記錄經(jīng)加工輸出后，緩沖區(qū)中又可存放下一個記錄。請用P、V操作為同步機構(gòu)寫出他們并發(fā)執(zhí)行時能正確工作的程序。答：三個進程共用一個緩沖區(qū)，他們必須同步工作，可定義三個信號量：S1：表示是否可把讀人的記錄放到緩沖區(qū)，初始值為1.S2：表示是否可對緩沖區(qū)中的記錄加工，初始值為0.S3：表示記錄是否加工好，可以輸出，初始值也為0.三個進程

13、可如下設(shè)計：BeginS1，S2，S3：semaphore；S1：l；S2：S3：0；cobegin process R beginL1：讀記錄；P（S1）；記錄存入緩沖區(qū)；V（S2）；goto L1；end；process MbeginL2：P（S2）；加工記錄；V（S3）；goto L2；end；process PbeginL3：P（S3）；輸出加工后的記錄；V（S1）；goto L3；end；coend；end.6.現(xiàn)有4個進程R1，R2，W1，W2，它們共享可以存放一個數(shù)的緩沖器B.進程R1每次把從鍵盤上投入的一個數(shù)存放到緩沖器B中，供進程W1打印輸出；進程R2每次從磁盤上讀一個數(shù)放到

14、緩沖器B中，供進程W2打印輸出。當(dāng)一個進程把數(shù)據(jù)存放到緩沖器后，在該數(shù)還沒有被打印輸出之前不準(zhǔn)任何進程再向緩沖器中存數(shù)。在緩沖器中還沒有存入一個新的數(shù)之前不允許任何進程加快從緩沖區(qū)中取出打印是怎樣才能使這四個進程在并發(fā)執(zhí)行是協(xié)調(diào)的工作？答：這四個進程實際上是兩個生產(chǎn)者 R1，R2和兩個消費者 W1，W2.各自生成不同的產(chǎn)品中各自的消費對象去消費，他們共享一個的緩沖器。由于緩沖器只能存放一個數(shù)，所以，R1和R2在存放數(shù)時必須互斥。而R1和W1、R2和W2之間存在同步。為了協(xié)調(diào)它們的工作可定義三個信號量：S：表示能否把數(shù)存人緩沖器B，初始值為1.S1：表示R1是否已向緩沖器存入從鍵盤上讀入的一個數(shù)，初始值為0.S2：表示R2是否已向緩沖器存入從磁盤上讀入的一個數(shù)，初始值為0.BeginS，S1，S2：semaphore；S：1；S1：S2：0；Cobeginprocess R1xl ：integerbeginL1：從鍵盤讀一個數(shù)；x1：=讀入的數(shù)；P（S）；P（S）；B：xlV（S1）；g