【文章內(nèi)容簡介】 … p(mutex)。語句 v(mutex)。 …11. 由 V 操 作喚醒的進程是否一定能夠直接進入運行狀態(tài) ? 舉例說明之。 答：否。一般來說，喚醒是將進程狀態(tài)由等待狀態(tài)變成就緒狀態(tài)，而就緒進程何時獲得處理機則是由系統(tǒng)的處理機調度策略確定的。如果采用搶占式優(yōu)先級調度算法，并且被喚醒的進程是當前系統(tǒng)中優(yōu)先級最高的進程，那么該進程將被調度執(zhí)行，該進程的狀態(tài)變成運行態(tài)。如果該進程不是系統(tǒng)中優(yōu)先級最高的進程或系統(tǒng)采用其它調度算法，那么該進程不會被調度執(zhí)行，其狀態(tài)將維持在就緒態(tài)。12. 設S1和S2為兩個信號燈變量, 下列八組P、V操作哪些可以同時進行? 哪些不能同時進行? 為什么?(1) P(S1), P(S2) (2) P(S1), V(S2)(3) V(S1), P(S2) (4) V(S1), V(S2) (5) P(S1), P(S1) (6) P(S2), V(S2)(7) V(S1), P(S1) (8) V(S2), V(S2)答： (1),(2),(3),(4)可以同時進行；（5），（6），（7），（8）不可以同時進行。因為如果將信號燈變量看作共享變量，則P、V操作作為其臨界區(qū)，為了不發(fā)生于時間有關的錯誤，須保證多個進程不能對同一個信號燈變量同時執(zhí)行P、V操作。13. 對于生產(chǎn)者—消費者問題，假設緩沖區(qū)是無界的，試用信號燈與 PV 操作給出解法。 答：由于是無界緩沖區(qū)，所以生產(chǎn)者不會因得不到緩沖區(qū)而被阻塞。 semaphore mutex_in=1。 semaphore mutex_out=1。 semaphore product=0。 int in=0 ， out=0。 生產(chǎn)者： while(1){ 生產(chǎn)一個物品； P(mutex_in)。 buffer[in]=物品； in++。 v(mutex_in)。 V(product)。 } 消費者： while(1){ P(product)。 P(mutex_out)。 物品=buffer[out]。 out++。 V(mutex_out)。 } 14. 設有一個可以裝A、B兩種物品的倉庫, 其容量無限大, 但要求倉庫中A、B兩種物品的數(shù)量滿足下述不等式:M≤A物品數(shù)量－B物品數(shù)量≤N其中M和N為正整數(shù). 試用信號燈和PV操作描述A、：若只放入A，而不放入B，則A產(chǎn)品最多可放入N次便被阻塞；若只放入B，而不放入A，則B產(chǎn)品最多可放入M次便被阻塞；每放入一次A,放入產(chǎn)品B的機會也多一次；同理，每放入一次B, mutex=1，sa=N，sb=M。產(chǎn)品A進程: 產(chǎn)品B進程:while(1){ while(1){p(sa)。 p(sb)。p(mutex)。 p(mutex)。A產(chǎn)品入庫； B產(chǎn)品入庫；V(mutex)。 V(mutex)。V(sb)。 V(sa)。} }15. 試用信號燈與 PV 操作實現(xiàn)司機與售票員之間的同步問題。設公共汽車上有一個司機和一個售票員，其活動如下圖所示。 為了安全起見，顯然要求 : (1)關車門后方能啟動車輛。 (2)到站停車后方能開車門。 亦即“啟動車輛”這一活動應當在“關車門”這一活動之后，“開車門”這一活動應當在“到站停車”這一活動之后。 semaphore s1=0,s2=0。 司機： 售票員： while(1){ while(1){ p(s1)。 關車門。 啟動車輛； v(s1)。 正常行駛； 售 票； 到站停車； p(s2)。 v(s2)。 開車門； } }16. 設有A、B、C三組進程, 它們互斥地使用某一獨占型資源R, 使用前申請, 使用后釋放. 資源分配原則如下: (1) 當只有一組申請進程時, 該組申請進程依次獲得R。 (2) 當有兩組申請進程時, 各組申請進程交替獲得R, 組內(nèi)申請進程交替獲得R。 (3) 當有三組申請進程時, 各組申請進程輪流獲得R, free=1。//設備狀態(tài)標志semaphore mutex=1。semaphore qa=qb=qc=0。 //各組等待隊列int counta=countb=countc=0。//等待隊列長度 A組申請：P(mutex)。if(free==1){free=0。V(mutex)。}else{counta++。V(mutex)。P(qa)。}A組釋放：if(countb0){countb 。V(qb)。}else{if(countc0){countc 。V(qc)。}else{if(counta0){counta V(qa)。}else{ free=1。}}}A組進程活動可以給出B組和C組進程活動。17. 設自行車生產(chǎn)線上有一只箱子，其中有 N 個位置 ( N ≥ 3)，每個位置可存放一個車架或一個車輪。 又設有三個工人，其活動分別為: 工人 1活動： do { 加工一個車架 。 車架放入箱中 。 } while (1) 工人 2活動： do { 加工一個車輪 。 車輪放入箱中 。 } while (1) 工人 3活動： do { 箱中取一車架 。 箱中取二車輪 。 組裝為一臺車 。 } while (1) 試分別用信號燈與 PV 操作、管程、會合實現(xiàn)三個工人的合作，要求解中不含死鎖。 一、用信號燈與 PV 操作實現(xiàn)三個工人的合作 首先不考慮死鎖問題，工人 1與工人工人2與工人3構成生產(chǎn)者與消費者關系，這兩對生產(chǎn)/消費關系通過共同的緩沖區(qū)相聯(lián)系。從資源的角度來看，箱字中的空位置相當于工人1和工人2的資源，而車架和車輪相當于工人3的資源。定義三個信號燈如下： semaphore empty=N。 semaphore wheel=0。 semaphore frame=0。 三位工人的活動分別為： 工人 1活動： do { 加工一個車架 。 P(empty)。 車架放入箱中 。 V(frame)。 } while (1) 工人 2活動： do { 加工一個車輪 。 P(empty)。 車輪放入箱中 。 V(wheel)。 } while (1) 工人 3活動： do { P(frame)。 箱中取一車架 。 V(empty)。 P(wheel)。 P(wheel)。 箱中取二車輪 。 V(empty)。 V(empty)。 組裝為一臺車 。 } while (1) 分析上述解法易見，當工人 1推進速度較快時，箱中空位置可能完全被車架占滿或只留有一個存放車輪的位置，而當此時工人3同時取2個車輪時將無法得到，而工人2又無法將新加工的車輪放入箱中；當工人2推進速度較快時，箱中空位置可能完全被車輪占滿，而當此時工人3同取車架時將無法得到，而工人1又無法將新加工的車架放入箱中 。上述兩種情況都意味著死鎖。 為防止死鎖的發(fā)生，箱中車架的數(shù)量不可超過 N2，車輪的數(shù)量不可超過N1，這些限制可以用兩個信號燈來表達。 semaphore s1=N2。 semaphore s2=N1。 如此，可以給出不含死鎖的完整解法如下： 工人 1活動： do { 加工一個車架 。 P(s1)。 P(empty)。 車架放入箱中 。 V(frame)。 } while (1) 工人 2活動： do { 加工一個車輪 。 P(s2)。 P(empty)。 車輪放入箱中 。 V(wheel)。 } while (1) 工人 3活動： do { P(frame)。 箱中取一車架 。 V(empty)。 V(s1)。 P(wheel)。 P(wheel)。 箱中取二車輪 。 V(empty)。 V(empty)。 V(s2)。 V(s2)。 組裝為一臺車 。 } while (1) 詳細描述還應考慮對箱子單元的描述以及訪問互斥問題。建議車架放在箱子的一端，車輪放在箱子的另一端，車架與車輪都采用后進先出的管理方式。Semaphore s1=N2，s2=N1，mutex=1。int in1=0，in2=N1。int buf[N]。工人 1活動： do { 加工一個車架 。 P(s1)。 P(empty)。P(mutex)。Buf[in1]=車架；in1=in1+1。 V(mutex)。 V(frame)。 } while (1) 工人 2活動： do { 加工一個車輪 。 P(s2)。 P(empty)。 P(mutex)。Buf[in2]=車輪；in2=in21。 V(mutex)。V(wheel)。 } while (1) 工人 3活動： do { P(frame)。 P(mutex)。Temp1=Buf[in11]；in1=in11。 V(mutex)。 V(empty)。 V(s1)。 P(wheel)。 P(wheel)。 P(mutex)。Temp2=Buf[in2+1]。in2=in2+1。Temp3=Buf[in2+1]。In2=in2+1。V(mutex)。V(empty)。 V(empty)。 V(s2)。 V(s2)。 組裝為一臺車 。 } while (1) 18. 一座小橋(最多只能承重兩個人)橫跨南北兩岸，任意時刻同一方向只允許一人過橋，南側橋段和北側橋段較窄只能通過一人，橋中央一處寬敞，允許兩個人通過或歇息．試用信號燈和PV操作寫出南、北兩岸過橋的同步算法．semaphore load=2。semaphore north=1。semaphore south=1。 tosouth(){P(load)。P(north)。過北段橋。到橋中間。V(north)。P(south)。過南段橋。到達南岸V(south)。V(load)。}tonorth(){P(load)。P(south)。過南段橋。到橋中間V(south)。P(north)。過北段橋。到達北岸V(north)。V(load)。} 19. 某寺廟，有小和尚、老和尚若干．廟內(nèi)有一水缸，由小和尚提水入缸，供老和尚飲用．水缸可容納 30 桶水，每次入水、取水僅為1桶，不可同時進行。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。設水桶個數(shù)為5個，試用信號燈和 PV 操作給出老和尚和小和尚的活動。 semaphore empty=30。 // 表示缸中目前還能裝多少桶水，初始時能裝 30 桶水 semaphore full=0。 // 表示缸中有多少桶水，初始時缸中沒有水 semaphore buckets=5。 // 表示有多少只空桶可用，初始時有 5 只桶可用 semaphore mutex_well=1。 // 用于實現(xiàn)對井的互斥操作 semaphore mutex_bigjar=1。 // 用于實現(xiàn)對缸的互斥操作 semaphore mutex_bucket=1。 //用于實現(xiàn)對桶的互斥操作 young_monk() { while(1){ P(empty)。 P(buckets)。P(mutex_bucket)。 取一個桶； V(mutex_bucket)。 go to the well。 P(mutex_well)。 get water。 V(mutex_well)。 go to the temple。 P(mutex_bigjar)。 pure the water into the big jar。 V(mutex_bigjar)。 V(buckets)。 V(full)。 } } old_monk() { while(){ P(full)。 P(buckets)。 P(mutex_bucket)。 get a bucket。 V(mutex_bucket)。 P(mutex_bigjar)。 get water。 V(mutex_bigjar)。 V(buckets)。 V(empty)。 } } 20. 設系統(tǒng)中有5臺類型相同的打印機，依次編號為1～5。 又設系統(tǒng)中有n個使用打印機的進程，使用前申請，使用后釋放。 每個進程有一個進程標識，用于區(qū)別不同的進程。 每個進程還有一個優(yōu)先數(shù)，不同進程的優(yōu)先數(shù)各異。當有多個進程同時申請時，按照進程優(yōu)先數(shù)由高到低的次序實施分配。 試用信號燈和PV操作實現(xiàn)對于打印機資源的管理，即要求編寫如下函數(shù)和過程:(1) 函數(shù) require(pid，pri): 申請一臺打印機。參數(shù)pid為進程標識，其值為1到n的整數(shù)。 pri為進程優(yōu)先數(shù)，其值為正整數(shù)。 函數(shù)返回值為所申請到打印機的編號，其值為1到5的整數(shù)。(2) 過程 return(prnt): 釋放一臺打印機。參數(shù)prnt為所釋放打印機的編號，其值為1到5的整數(shù)。解：define N 5Int flag[N+1]。//flag[0]表示可用打印機數(shù),//flag表示第i號打印機的狀態(tài)（1=i=N），0表示占用，1表示空閑PCB *queue=NULL。//進程阻塞隊列semaphore mutex_flag=1。//用于對flag數(shù)組的互斥操作semaphore mutex_queue=1。//用于對阻塞隊列的互斥操作 int require(int pid,int priority){P(mutex_flag)。if(flag[0]0){flag[0]。for(int i=1。iN+1。i++)if(fl