【正文】 述如下：var s1，s2：semaphore；s1=0； s2=0。cobegin{ driver ( )。 busman ( )。}coenddriver ( ) begin while(1) { P(s1) 啟動車輛； 正常行車； 到站停車； V(s2)。} endbusman ( ) begin while(1) { 關車門；， V(s1) 售票； P(s2) 開車門； 上下乘客；} end7 在信號量S上作P、V操作時，S的值發(fā)生變化，當S＞0、S=0、S0時，它們的物理意義是什么？答：S的值表示它代表的物理資源的使用狀態(tài)：S0表示還有共享資源可供使用。S=0表示共享資源正被進程使用但沒有進程等待使用資源。S0表示資源已被分配完，還有進程等待使用資源。8 (1)兩個并發(fā)進程并發(fā)執(zhí)行，其中，A、B、C、D、E是原語，試給出可能的并發(fā)執(zhí)行路徑。Process P Process Qbegin begin A； D； B； E； C； end； end；(2) 兩個并發(fā)進程P1和P2并發(fā)執(zhí)行，它們的程序分別如下： P1 P2 repeat repeat k:=k2。 print k。 k:=k+1。 k:=0。 until false。 until false。若令k的初值為5，讓P1先執(zhí)行兩個循環(huán)，然后，P1和P2又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關的錯誤。答：(1) 共有10種交錯執(zhí)行的路徑：A、B、C、D、E；A、B、D、E、C；A、B、D、C、E；A、D、B、E、C；A、D、B、C、E；A、D、E、B、C；D、A、B、E、C；D、A、B、C、E；D、A、E、B、C；D、E、A、B、C。(2) 把語句編號，以便于描述：P1 P2 repeat repeat k:=k2。 ① print k。 ③ k:=k+1。 ② k:=0。 ④ until false。 until false。1) K的初值為5，故P1執(zhí)行兩個循環(huán)后，K=23。2) 語句并發(fā)執(zhí)行有以下情況： ①、②、③、④，這時的打印值為：47 ③、④、①、②，這時的打印值為：23 ①、③、②、④，這時的打印值為：46 ①、③、④、②，這時的打印值為：46 ③、①、②、④，這時的打印值為：23 ③、①、④、②，這時的打印值為：23由于進程P1和P2并發(fā)執(zhí)行，共享了變量K，故產(chǎn)生了‘結果不唯一’。9 另一個經(jīng)典同步問題：吸煙者問題(patil，1971)。三個吸煙者在一個房間內，還有一個香煙供應者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴，供應者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應者隨機地將兩樣東西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應者，供應者再把兩樣東西放在桌子上，喚醒另一個吸煙者。試采用：(1)信號量和P、V操作，(2)管程編寫他們同步工作的程序。答：(1)用信號量和P、V操作。var S,S1,S2,S3。semaphore。 S:=1。S1:=S2:=S3:=0。 flag1,flag2,flag3:Boolean。 flag1:=flag2:=flag3:=true。cobegin{ process 供應者begin repeat P(S)。 取兩樣香煙原料放桌上，由flagi標記。 /*flageflageflage3代表煙草、紙、火柴 if flag2amp。flag3 then V(S1)。 /*供紙和火柴 else if flag1amp。flag3 then V(S2)。 /*供煙草和火柴 else V(S3)。 /*供煙草和紙 untile false。 end process 吸煙者1begin repeat P(S1)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。process 吸煙者2begin repeat P(S2)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。process 吸煙者3begin repeat P(S3)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。}coend.10 系統(tǒng)有同類資源m個，被n個進程共享，問：當m＞n和m≤n時，每個進程最多可以請求多少個這類資源時，使系統(tǒng)一定不會發(fā)生死鎖?答：當m≤n時，每個進程最多請求1個這類資源時，系統(tǒng)一定不會發(fā)生死鎖。當mn時，如果m/n不整除，每個進程最多可以請求”商+1”個這類資源，否則為”商”個資源，使系統(tǒng)一定不會發(fā)生死鎖?11 N個進程共享M個資源，每個進程一次只能申請/釋放一個資源，每個進程最多需要M個資源，所有進程總共的資源需求少于M+N個，證明該系統(tǒng)此時不會產(chǎn)生死鎖。答：設max （i）表示第i個進程的最大資源需求量，need(i)表示第i個進程還需要的資源量，alloc(i)表示第i個進程已分配的資源量。由題中所給條件可知： max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))m+n如果在這個系統(tǒng)中發(fā)生了死鎖，那么一方面m個資源應該全部分配出去， alloc(1)+ ┅+alloc(n)=m另一方面所有進程將陷入無限等待狀態(tài)?？梢酝瞥? need(1)+ ┅+need(n)n上式表示死鎖發(fā)生后，n個進程還需要的資源量之和小于n，這意味著此刻至少存在一個進程i,need(i)=0,即它已獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源，那么它就能執(zhí)行完成并釋放它占有的資源，這與前面的假設矛盾，從而證明在這個系統(tǒng)中不可能發(fā)生死鎖。12 設當前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=(1，1，2)： Claim Allocation進程, R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0P2 6 1 3 5 1 1P3 3 1 4 2 1 1P4 4 2 2 0 0 2(1) 計算各個進程還需要的資源數(shù)CkiAki?(2) 系統(tǒng)是否處于安全狀態(tài)，為什么?(3) P2發(fā)出請求向量request1(1，0，1)，系統(tǒng)能把資源分給它嗎？(4) 若在P2申請資源后，若P1發(fā)出請求向量request0(1，0，1)，系統(tǒng)能把資源分給它嗎？(5) 若在P1申請資源后，若P3發(fā)出請求向量request0(0，0，1)，系統(tǒng)能把資源分給它嗎？答：(1) P1，P2，P3，P4的CkiAki分別為：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)(3) 系統(tǒng)處于安全狀態(tài)，存在安全序：P2，P1，P3，P4(4) 可以分配，存在安全序列：P2，P1，P3，P4。(5) 不可以分配。(6) 不可以分配。13 系統(tǒng)有A、B、C、D共4種資源，在某時刻進程P0、PPP3和P4對資源的占有和需求情況如表，試解答下列問題：ProcessAllocationClaimAvailableA B C DA B C D A B C D P00 0 3 20 0 4 4 1 6 2 2P11 0 0 02 7 5 0 P21 3 5 43 6 10 10P30 3 3 2 0 9 8 4 P40 0 1 40 6 6 10(1) 系統(tǒng)此時處于安全狀態(tài)嗎？(2) 若此時P2發(fā)出request1(2)，系統(tǒng)能分配資源給它嗎？為什么？答：(1)系統(tǒng)處于安全狀態(tài)，存在安全序列：P0，P3，P4，P1，P2。 (2)不能分配，否則系統(tǒng)會處于不安全狀態(tài)。14 把死鎖檢測算法用于下面的數(shù)據(jù)，并請問： Available=(1，0，2，0)110 0011 2310 0Need=1 00 02 11 0301 1010 0111 1Allocation=0 11 00 00 0 (1) 此時系統(tǒng)此時處于安全狀態(tài)嗎？(2) 若第二個進程提出資源請求request2(0，0，1，0)，系統(tǒng)能分配資源給它嗎？(3) 若第五個進程提出資源請求request5(0，0，1，0)，系統(tǒng)能分配資源給它嗎？答：(1)此時可以找出進程安全序列：P4，P1，P5，P2，P3。故系統(tǒng)處于安全狀態(tài)。(2)可以分配，存在安全序列：P4，P1，P5，P2，P3。(3)不可分配，系統(tǒng)進入不安全狀態(tài)。15 某系統(tǒng)有R1設備3臺，R2設備4臺，它們被PPP3和P4進程共享，且已知這4個進程均按以下順序使用設備： →申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1(1) 系統(tǒng)運行中可能產(chǎn)生死鎖嗎？為什么？(2) 若可能的話，請舉出一種情況，并畫出表示該死鎖狀態(tài)的進程—資源圖。答：(1)系統(tǒng)四個進程需要使用的資源數(shù)為R1各2臺，R2各1臺?？梢娰Y源數(shù)不足，同時各進程申請資源在先，有可能產(chǎn)生死鎖發(fā)生的四個條件，故系統(tǒng)可能產(chǎn)生死鎖。(2) 當三個進程執(zhí)行完申請資源R1，開始執(zhí)行申請資源R2時，第四個進程會因沒有資源R1而被阻塞。當三個進程執(zhí)行完申請資源R2后，系統(tǒng)還剩1個R2資源。而這三個進程因執(zhí)行申請第二個資源R1而全部被阻塞，系統(tǒng)進入死鎖。● ● ●●●●●P1P2P3P416 假定某計算機系統(tǒng)有R1和R2兩類可再使用資源（其中R1有兩個單位，R2有一個單位），它們被進程P1，P2所共享，且已知兩個進程均以下列順序使用兩類資源。 →申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1→試求出系統(tǒng)運行過程中可能到達的死鎖點，并畫出死鎖點的資源分配圖（或稱進程－資源圖）。答：當兩個進程都執(zhí)行完第一步(都占用R1) 時，系統(tǒng)進入不安全狀態(tài)。這時無論哪個進程執(zhí)行完第二步，死鎖都會發(fā)生?？赡艿竭_的死鎖點：進程P1占有一個R1和一個R2，而進程P2占有一個R1?；蛘呦喾础＿@時己形成死鎖。進程資源圖為：．P1P1．P1P117 桌上有一只盤子，最多可以容納兩個水果，每次僅能放入或取出一個水果。爸爸向盤子中放蘋果(apple)，媽媽向盤子中放桔子(orange)，兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子中的蘋果。試用：(1)信號量和P、V操作，(2)管程，來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關系。答：(1)用信號量和P、V操作。類似于課文中的答案，擴充如下：1) 同步信號量初值為2；2) 要引進一個互斥信號量mutex，用于對盤子進行互斥；3)盤子中每一項用橘子、蘋果2個枚舉值。varplate ARRAY[0,1] of (apple, orange)。flag0,flag1:boolean。mutex:semaphore。 sp:semaphore。 /* 盤子里可以放幾個水果 */ sg1，sg2:semaphore。 /* 盤子里有桔子，有蘋果?*/ sp := 2。 /* 盤子