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