【正文】 1S2=0。B2S1=2。B2S2=0。 (2’) Cobegin (`6’=2’*3) P0 P1 P2 begin begin begin P(B0S2) P(B1S2) P(B2S2) 從B0取一個(gè)數(shù)據(jù) 從B1取一個(gè)數(shù)據(jù) 從B2取一個(gè)數(shù)據(jù) V(B0S2) V(B1S1) V(B2S1) 加工 加工 加工 P(B1S1) P(B2S1) P(B0S1) 將加工結(jié)果送B1 將加工結(jié)果送B2 將加工結(jié)果送B0 V(B1S2) V(B2S2) V(B0S2) end end end coend這道題也可以增加互斥信號(hào)量，以便P0與P1之間互斥使用B0緩沖區(qū)，P1與P2之間互斥使用B1緩沖區(qū)，P2與P0之間互斥使用B0緩沖區(qū)。這里主要描述它們之間的同步關(guān)系。若考慮互斥共享緩沖區(qū)，請(qǐng)自己加上。2設(shè)用三個(gè)隊(duì)列管理緩沖區(qū)池的使用情況，分別為空白緩沖隊(duì)列em，輸入緩沖隊(duì)列in，以及輸出緩沖隊(duì)列out。過程add_buf(type,numb)和take_buf(type,numb)分別用來把緩沖區(qū)numb插入type隊(duì)列和從type隊(duì)列中取出緩沖區(qū)numb。試描述進(jìn)程從任一緩沖隊(duì)列中得到一個(gè)緩沖區(qū)的過程get_buf(type,numb)和釋放一個(gè)緩沖區(qū)numb進(jìn)入緩沖隊(duì)列的過程put_buf(type,numb)。答：假定用信號(hào)量s代表任一隊(duì)列的可用緩沖區(qū)個(gè)數(shù)。假定三個(gè)隊(duì)列的初值分別為n1,n2,n3。對(duì)任一隊(duì)列的操作必須互斥。因此再引入一個(gè)互斥使用任一隊(duì)列的信號(hào)量mutex，其初值為1。這里type代表隊(duì)列的類型，它的取值為輸入、輸出和空白。(4’)當(dāng)有進(jìn)程希望從任一隊(duì)列取一個(gè)緩沖區(qū)時(shí)，過程get_buf(type,numb)的動(dòng)作如下： get_buf(type,numb) (`3’) begin p(s) p(mutex) numb=take_buf(type,numb) v(mutex) end當(dāng)有進(jìn)程希望向任一隊(duì)列送一個(gè)緩沖區(qū)時(shí)，過程put_buf(type,numb)的動(dòng)作如下： put_buf(type,numb) (`3’) begin p(mutex) add_buf(type,numb) v(mutex) v(s)end. 3設(shè)有一個(gè)售票廳，可容納100人購票。如果廳內(nèi)不足100人則允許進(jìn)入，進(jìn)入后購票，購票后退出。如果廳內(nèi)已有100人，則在廳外等候。試問：1） 購票者之間是同步還是互斥？用P、V操作表達(dá)購票者的工作過程。解：1）購票者之間是互斥關(guān)系。(2’)2） 一個(gè)售票廳可容納100人購票，說明最多允許100個(gè)購票者共享售票廳；可引入一個(gè)信號(hào)量empty，其初值為100。由于購票者必須互斥地進(jìn)行購票，故應(yīng)再設(shè)一個(gè)mutex，其初值為1。(4’)用P、V操作表達(dá)購票者的工作過程如下：(`4’)empty,mutex:semaphore。empty:=100。 mutex:=1。begin p(empty) p(mutex) 進(jìn)入廳內(nèi)購票,購票后退出 v(empty) v(mutex)end. 4某招待所有100個(gè)床位，住宿者入住要先登記（在登記表上填寫姓名和床位號(hào)）．離去時(shí)要注銷登記（在登記表上刪去姓名和床位號(hào)）．請(qǐng)給出住宿登記及注銷過程的算法描述．答：某招待所有100個(gè)床位，為了正確管理，引入一個(gè)信號(hào)量empty代表空床位數(shù)，初值為100；住宿者入住要先登記（在登記表上填寫姓名和床位號(hào)），顯然，登記表是一個(gè)臨界資源，必須互斥訪問，引入一個(gè)mutex，其初值為1。(4’)住宿登記及注銷過程的算法描述如下： 住宿登記：(`3’) begin p(empty) //檢查有無床位 p(mutex) //申請(qǐng)登記 找出一個(gè)空床位將名字登入表中 v(mutex) end 注銷過程：(`3’) begin p(mutex) //申請(qǐng)退房 找出自己的登記項(xiàng)，并刪除該項(xiàng)的登記 v(mutex) v(empty)end. 5有一個(gè)閱覽室，共有100個(gè)座位。為了很好地利用它，讀者進(jìn)入時(shí)必須先在登記表上進(jìn)行登記。該表表目設(shè)有座位號(hào)和讀者姓名；離開時(shí)再將其登記項(xiàng)擦除。試問：為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序，應(yīng)設(shè)幾個(gè)進(jìn)程、它們之間的關(guān)系怎樣？并請(qǐng)用P、V操作描述進(jìn)程之間的同步算法。解：為了描述閱覽室，用一個(gè)登記表來記錄其使用情況。表中共有100項(xiàng)。每當(dāng)有讀者進(jìn)入閱覽室時(shí)，為了正確地登記，各讀者應(yīng)互斥使用(1’)。為此設(shè)兩個(gè)信號(hào)量：mutex為互斥信號(hào)量，用來制約各讀者互斥地進(jìn)行登記，其初值為1；empty為同步信號(hào)量，用來制約各讀者能同時(shí)進(jìn)入閱覽室的數(shù)量，其初值為100 (2’)。下面用兩個(gè)過程描述對(duì)表格應(yīng)執(zhí)行的動(dòng)作： 登記過程：(`2’) 擦除過程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登記項(xiàng)擦除 找到一個(gè)登記項(xiàng)登記 V(mutex) V(mutex) V(empty) end end 為了正確地描述讀者的動(dòng)作，可以將讀者看成進(jìn)程。若干讀者希望進(jìn)入閱覽室時(shí)，調(diào)用登記過程，退出閱覽室時(shí)，調(diào)用擦除過程(1’)?？梢姡粋€(gè)程序可對(duì)應(yīng)多個(gè)讀者。可設(shè)的進(jìn)程數(shù)由讀者數(shù)決定，其動(dòng)作如下：(`2’) begin 調(diào)用登記過程 進(jìn)入閱覽室閱讀 準(zhǔn)備退出 調(diào)用擦除過程 end. 6一條河上架設(shè)了由若干個(gè)橋墩組成的一座橋。若一個(gè)橋墩只能站一個(gè)人，過河的人只能沿著橋向前走而不能向后退。過河時(shí)，只要對(duì)岸無人過，就可以過；但不允許河對(duì)岸的兩個(gè)人同時(shí)過，以防止出現(xiàn)死鎖。請(qǐng)給出兩個(gè)方向的人順利過河的同步算法。解：假設(shè)一座橋由N個(gè)橋墩，也即最多允許有N個(gè)人同向過河，用一個(gè)計(jì)數(shù)器R記錄同時(shí)過河的人數(shù)(2’)。用S1信號(hào)量保護(hù)計(jì)數(shù)器，其初值為1，R的初值為0；互斥使用橋的信號(hào)量用S表示，其初值為1。(2’)同步算法描述如下： procedure goriver() begin L:P(S1)。 //為同時(shí)過河,申請(qǐng)對(duì)計(jì)數(shù)器計(jì)數(shù) If RN begin V(S1)。 goto L。 end //同方向過河的人站滿橋墩時(shí),重新申請(qǐng)計(jì)數(shù) R=R+1。 If R==1 P(S)。 //申請(qǐng)過河 V(S1)。 //釋放計(jì)數(shù)器的使用權(quán) (3’) 占有一個(gè)橋墩,并順序過河到對(duì)岸。 P(S1)。 R=R1。 If R==0 V(S)。 //如果已經(jīng)無同向的人過河,釋放占用權(quán) V(S1)。 (3’)end. 7在一個(gè)飛機(jī)訂票系統(tǒng)中，多個(gè)用戶共享一個(gè)數(shù)據(jù)庫。各用戶可以同時(shí)查詢信息，若有一個(gè)用戶要訂票，須更新數(shù)據(jù)庫時(shí)，其余所有用戶都不可以訪問數(shù)據(jù)庫。請(qǐng)用P,V操作設(shè)計(jì)一個(gè)同步算法，實(shí)現(xiàn)用戶查詢與訂票功能。要求：當(dāng)一個(gè)用戶訂票而需要更新數(shù)據(jù)庫時(shí)，不能因不斷有查詢者到來而使其長時(shí)間等待。利用信號(hào)量機(jī)制保證其正常執(zhí)行。解：這是典型的讀者——寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫者優(yōu)先。(2’)變量說明：(`2’)計(jì)數(shù)變量rc——正在運(yùn)行的查詢者進(jìn)程數(shù)目，初值為0.信號(hào)量Sw——控制訂票者進(jìn)程的活動(dòng)，初值為1.Src——互斥使用rc變量，初值為1.S——當(dāng)訂票者到達(dá)時(shí)封鎖后續(xù)的讀進(jìn)程，初值為1.讀者進(jìn)程 P(S)P(Src)rc=rc+1if (rc==1) P(Sw)V(Src)V(S) (2’)查詢庫當(dāng)中的信息P(Src)rc=rc1。if (rc==0) V(Sw)V(Src) (2’) 寫者進(jìn)程 (`2’)P(S)P(Sw)更新數(shù)據(jù)庫內(nèi)容V(Sw)V(S)8某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問題：　　(1)用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量各種取值的含義?！　?2)根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的PV操作填入下述空格中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。　　COBEGIN　PROCESS　PI(I=1，2，……)　　　　　　　 begin　　　　　　　　進(jìn)入售票廳； 購票； 　　　　　　　　　　　退出；　　　　　　　 end　　　COEND(3)若欲購票者最多為n個(gè)人，寫出信號(hào)量可能的變化范圍(最大值和最小值)。答：(1)定義一信號(hào)量S，初始值為20?！?1’)　　意義：(`3’=1’*3)　　S0　S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)　　　S=0　表示售票廳中已有20名顧客(購票者)　　　S0　|S|的值為等待進(jìn)入售票廳的人數(shù)　　(2)上空格為P(S) (2’) ；下空格為V(S)　(2’)　(3)S的最大值為20 (1’ )；S的最小值為20－n　(1’ )9在公共汽車上，司機(jī)和售票員各行其職，司機(jī)負(fù)責(zé)開車和到站停車；售票員負(fù)責(zé)售票和開門關(guān)門，當(dāng)售票員關(guān)好車門后，駕駛員才能開車行使。試用P/V操作實(shí)現(xiàn)司機(jī)與售票員間的同步。解答：semaphore mutex1=0,mutex2=0。 (2’) main(){ cobegin driver() busman()coend} (2’)driver(){ while(true){ p(mutex1) 啟動(dòng)公共汽車 正常開車 到站停車 v(mutex2)}} (3’)busman(){ while(true){ 關(guān)車門 v(mutex1) 售票 p(mutex2) 開車門 上下乘客}} (3’)10并發(fā)問題：設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程p1, p2如下。令信號(hào)s1, s2的初值為0，已知z=2，試問p1, p2并發(fā)運(yùn)行結(jié)束后x=? y=? z=? 進(jìn)程p1 進(jìn)程p2 y := 1 x := 1 y := y+2 x := x+1 v(s1) p(s1) z := y+1 x := x+y p(s2) v(s2) y := z+y z := x+z 解答：（分析過程略 2’）從結(jié)果來看，兩個(gè)進(jìn)程無論誰先誰后，結(jié)果都是一樣的。(2’) x = 5。 y = 12。 z = 9 (6’)11 M8M7M6M5M4M3M2試用信號(hào)量機(jī)制來描述下述前趨圖M1 解答：首先定義信號(hào)量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為0，分別表示相對(duì)應(yīng)的進(jìn)程是否完成：(2’)COBEGIN (`8’=1’*8)Process M1:begin V(S12) V(S13) V(S14) endProcess M2:begin P(S12) V(26) endProcess M3:begin P(S13) V(S36) V(S38) endProcess M4:beginP(S14) V(S47) endProcess M5:begin V(S57) endProcess M6:begin P(S26) P(S36) endProcess M7:begin P(S47) P(S57) P(S78) endProcess M8:begin P(S38) P(S78) end COEND12 M6M4M3M5M2試用