計(jì)算機(jī)操作系統(tǒng)PV操作例題

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

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

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

4、斥 )? MD=1? ( 東向西使用計(jì)數(shù)變量互斥 ) ? MX=1? ( 西向東使用計(jì)數(shù)變量互斥 )設(shè)整型變量：CD=0? ( 東向西的已上橋人數(shù))? CX=0? (西向東的已上橋人數(shù))從東向西：P (MD) IF (CD=0)P (MUTEX)? CD=CD+1V (MD)過橋P (MD) CD=CD-1 IF (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）相同。

5、問題4 有一個(gè)俱樂部，有甲乙兩個(gè)服務(wù)員，當(dāng)顧客有請(qǐng)求時(shí)，甲負(fù)責(zé)送煙，乙負(fù)責(zé)送火，無顧客請(qǐng)求時(shí)，服務(wù)員睡眠。顧客自己不能帶煙和火，當(dāng)顧客要抽煙時(shí)，可請(qǐng)求服務(wù)員送煙和火，煙和火還未送到時(shí)，顧客必須等待。設(shè)信號(hào)量： 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 一家四人父、母、兒子、女兒圍桌而坐；桌上有一個(gè)水果盤；（ 1） ? 當(dāng)水果盤空時(shí)，父親可以放香蕉或者母親可以放蘋果，但盤中已有水果時(shí)，就不能放，父母等待。

6、當(dāng)盤中有香蕉時(shí)，女兒可吃香蕉，否則，女兒等待；當(dāng)盤中有蘋果時(shí)，兒子可吃，否則，兒子等待。解 設(shè)信號(hào)量： SE=1 ( 空盤子 )； SA 0 （放了蘋果的盤子）；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）改為：兒子要吃蘋果時(shí)，請(qǐng)母親放蘋果，女兒要吃香蕉時(shí)，請(qǐng)父親放香蕉，（還是盤子為空時(shí)才可以放）。（2）解：再增加兩個(gè)信號(hào)量：SF=0, SM=0父親REPEATP(SF)剝香蕉P(S

7、E)放香蕉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 有一個(gè)超市，最多可容納N 個(gè)人進(jìn)入購物，當(dāng)N 個(gè)顧客滿員時(shí)，后到的顧客在超市外等待；超市中只有一個(gè)收銀員。可以把顧客和收銀員看作兩類進(jìn)程， 兩類進(jìn)程間存在同步關(guān)系。出用 P;V 操作實(shí)現(xiàn)的兩類進(jìn)程的算法（ 2003 年系統(tǒng)設(shè)計(jì)員考試的題目）寫解：設(shè)信號(hào)量： S=0 ， C=0 ( 顧客與收銀員的同步信號(hào)量 )， M=N 收銀員P(S)收銀V(C)顧客P(M)進(jìn)入店內(nèi)購物V(S

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

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

10、(SY)UNTIL盒子中無黑子乙REPEATP(SY)取一顆白子V(SJ)UNTIL盒子中無白子（八）按要求完成下面的程序。設(shè)有三個(gè)進(jìn)程，input進(jìn)程、compute進(jìn)程和output進(jìn)程；它們通過共享一個(gè)緩沖區(qū)buf的合作關(guān)系如下：（1） input 進(jìn)程每次輸入數(shù)據(jù)后，把數(shù)據(jù)送到buf, 供 compute 進(jìn)程計(jì)算和（2）comput 進(jìn)程每次從buf 取出已輸入的可計(jì)算的數(shù)據(jù)進(jìn)行計(jì)算，并當(dāng)打印完成后，把計(jì)算結(jié)果送入buf 供 output 進(jìn)程打??；outputoutput進(jìn)程打?。贿M(jìn)程把輸入數(shù)據(jù)（ 3） output 進(jìn)程每次按順序把 buf 中的輸入數(shù)據(jù)和計(jì)算結(jié)果在打印機(jī)上輸出。

11、解：設(shè)信號(hào)量： sa=1,sb=sc=sd=0, 請(qǐng)把能正確實(shí)現(xiàn)這三個(gè)進(jìn)程同步關(guān)系的P、V操作的語句填入下面的程序。procedure inputbeginlocal datarepeat? get(data);? p(sa);? buf=data;? (1)? V ( sc )? ? v(sb);until falseend;procedure computebeginlocol datarepeat? (2)? P ( sb )? data=buf;? 計(jì)算 data 并把結(jié)果保存在data;? (3)? P ( sd )? ? buf=data; ? v(sc); until false

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

13、的記錄放到緩沖區(qū)，初始值為1.S2：表示是否可對(duì)緩沖區(qū)中的記錄加工，初始值為0.S3：表示記錄是否加工好，可以輸出，初始值也為0.三個(gè)進(jìn)程可如下設(shè)計(jì)：BeginS1， S2， S3： semaphore；S1： l； S2： S3： 0；cobeginprocess RbeginL1 ：讀記錄；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；en

14、d.6.現(xiàn)有 4 個(gè)進(jìn)程 R1 ，R2， W1 ， W2 ，它們共享可以存放一個(gè)數(shù)的緩沖器B. 進(jìn)程 R1每次把從鍵盤上投入的一個(gè)數(shù)存放到緩沖器B 中，供進(jìn)程W1 打印輸出； 進(jìn)程 R2 每次從磁盤上讀一個(gè)數(shù)放到緩沖器B 中，供進(jìn)程W2打印輸出。當(dāng)一個(gè)進(jìn)程把數(shù)據(jù)存放到緩沖器后，在該數(shù)還沒有被打印輸出之前不準(zhǔn)任何進(jìn)程再向緩沖器中存數(shù)。在緩沖器中還沒有存入一個(gè)新的數(shù)之前不允許任何進(jìn)程加快從緩沖區(qū)中取出打印是怎樣才能使這四個(gè)進(jìn)程在并發(fā)執(zhí)行是協(xié)調(diào)的工作？答：這四個(gè)進(jìn)程實(shí)際上是兩個(gè)生產(chǎn)者R1 ，R2 和兩個(gè)消費(fèi)者W1 ，W2. 各自生成不同的產(chǎn)品中各自的消費(fèi)對(duì)象去消費(fèi)，他們共享一個(gè)的緩沖器。由于緩沖器只

15、能存放一個(gè)數(shù)，所以，R1和R2在存放數(shù)時(shí)必須互斥。而R1和 W1 、R2 和 W2 之間存在同步。為了協(xié)調(diào)它們的工作可定義三個(gè)信號(hào)量：S：表示能否把數(shù)存人緩沖器B ，初始值為 1.S1：表示R1 是否已向緩沖器存入從鍵盤上讀入的一個(gè)數(shù)，初始值為0.S2：表示R2 是否已向緩沖器存入從磁盤上讀入的一個(gè)數(shù)，初始值為0.BeginS， S1， S2： semaphore；S： 1； S1： S2： 0；Cobeginprocess R1xl： integerbeginL1 ：從鍵盤讀一個(gè)數(shù)；x1： = 讀入的數(shù)；P（ S）；P（ S）；B ： xlV （ S1）；goto L1 ；end；process R2x2：