【正文】 控制南段橋的使用，初值為1，用于對南段橋互斥。semaphore north=1。tosouth(){P(load)。過北段橋。V(north)。過南段橋。V(load)。P(south)。到橋中間V(south)。過北段橋。V(load)。有小和尚、老和尚若干．廟內(nèi)有一水缸，由小和尚提水入缸，供老和尚飲用。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。semaphore empty=30。// 表示缸中有多少桶水，初始時缸中沒有水semaphore buckets=5。// 用于實現(xiàn)對井的互斥操作semaphore mutex_bigjar=1。young_monk(){while(1){P(empty)。go to the well。get water。go to the temple。pure the water into the big jar。V(buckets)。}}old_monk(){while(){P(full)。P(mutex_bigjar)。V(mutex_bigjar)。V(buckets)。}} 又設(shè)系統(tǒng)中有n個使用打印機的進程，使用前申請，使用后釋放。 每個進程還有一個優(yōu)先數(shù)，不同進程的優(yōu)先數(shù)各異。 試用信號燈和PV操作實現(xiàn)對于打印機資源的管理，即要求編寫如下函數(shù)和過程:(1) 函數(shù) require(pid，pri): 申請一臺打印機。 pri為進程優(yōu)先數(shù)，其值為正整數(shù)。(2) 過程 return(prnt): 釋放一臺打印機。解：define N 5bool flag[N+1]。//進程阻塞隊列semaphore mutex_flag=1。//用于對阻塞隊列的互斥操作print=require(i,priority)。return(print)。if(flag[0]0){flag[0]。iN+1。break。return i。p(mutex_queue)。}}return(int print){P(mutex_flag)。flag[print]=1。}else{V(mutex_flag)。將print分配給queue隊首進程；queue下移；V(mutex_queue)。解：TYPE single_resource=MONITOR。//資源狀態(tài)q: condition。PROCEDURE require。state:=used。PROCEDURE release。signal(q)。BEGIN state:=free END。22. 雖然管程是互斥進入的，但管程中定義的外部子程序必須是可再入的，試說明原因。解：兩個外部過程：sleep用于進程等待指定時間，tick用于時鐘中斷記數(shù)和喚醒等待進程。Var count: integer。//等待隊列define sleep, tick。BEGINcount:=intervalwait(q)。PROCEDURE tick。IF count=0 THENsignal(q)。BEGIN END。24. 管程與會合這兩種同步機制之間的主要差別何在?答：管程與會合都屬于集中式結(jié)構(gòu)化同步機制，但二者的實現(xiàn)機理完全不同。會合是主動性語言成分，一個任務(wù)調(diào)用另一任務(wù)中的入口時，入口代碼是由被調(diào)用任務(wù)自己占有處理機執(zhí)行的。25. 試用會合給出讀寫問題的解法，要求寫者優(yōu)先．解：定義一個任務(wù)，包含如下四個入口：start_read,finish_read, start_write,finish_write。這里顯然需要accept語句的嵌套。finish_read。finish_write。task body readers_and_writers isread_count,write_count:integer。write_count:=0。end start_reador when read_count0 =accept finish_read doread_count:=read_count1。or when write_count=0 =//也許當(dāng)前有讀者accept start_write dowhile read_count0 do//等待讀者讀完accept finish_read doread_count:=read_count1end finish_readend whilewrite_count:=write_count+1。end finish_writeend select。end readers_and_writers。26. 關(guān)于讀者/寫者問題,有人給出如下改進解法:semaphore r_w_w, mutex, s。 (初值為0)讀者活動：P(s)。count++。V(mutex)。{讀操作}P(mutex)。If (count= =0)V(r_w_w)。P(r_w_w)。V(s)。分析上述改進算法的調(diào)度效果。 (1) 參與死鎖的所有進程都占有資源；(2) 參與死鎖的所有進程中至少有兩個進程占有資源；(3) 死鎖只發(fā)生在無關(guān)進程之間；(4) 死鎖可發(fā)生在任意進程之間。如下圖所示，參與進程pppp4，盡管pp4不占有資源，但也卷入死鎖。 參與死鎖的進程至少有兩個，設(shè)為p1,p2，p1占有資源r1而等待資源r2，p2占有資源r2而等待資源r1。死鎖也可能發(fā)生在相關(guān)進程之間，如p1和p2也可能是相關(guān)進程。即死鎖可發(fā)生在任意進程之間。2． 試證明當(dāng)每個資源類中僅有一個資源實例時，資源分配圖中的環(huán)路是死鎖的充要條件。假定環(huán)路上共有k個進程(k32)，設(shè)這k個進程為p1,p2,…,pk。顯然，這k個資源類中的所有資源實例均被環(huán)路上的進程所占有，環(huán)路外的進程有關(guān)資源的任何釋放動作必不涉及這k類資源，因而無法使環(huán)路上的等待進程解除等待狀態(tài)，因而這k個進程將無限期地等待下去，即發(fā)生死鎖。對于每類系統(tǒng)資源，操作系統(tǒng)需要確定一個分配策略，當(dāng)多個進程同時申請某類資源時，由分配策略確定資源分配給進程的次序。在后一種情況下，即使系統(tǒng)沒有發(fā)生死鎖，某些進程也可能會長時間等待。與饑餓相關(guān)的另外一個概念稱為活鎖(live lock)，在忙式等待條件下發(fā)生的饑餓，稱為活鎖。這也表明通過資源分配圖可以檢測死鎖存在與否，但卻不能檢測是否有進程餓死；(4) 死鎖一定涉及多個進程，而饑餓或被餓死的進程可能只有一個。 答：銀行家算法的保守性是指銀行家算法只給出了進程需要資源的最大量，而所需資源的具體申請和釋放順序仍是未知的，因而銀行家只能往最壞處設(shè)想．考慮資源集合R={A(1),B(1)}，進程集合P={p1,p2}，已知進程p1和進程p2的活動序列分別為：p1：a,b,。顯然p1和p2的資源最大需求量均為A(1)，B(1)。 其后系統(tǒng)接收到的命令有兩種可能，一是p1的請求b，二是p2的請求b。又Request[2]=(0,1)￡Available=(0,1)，故該請求系統(tǒng)當(dāng)前能夠滿足。實際上如果真正實施分配系統(tǒng)并不會進入死鎖狀態(tài)，因為分配后按照p2(),p1(b),p1(),p1(),p2 (b),p2(a),p2(),p2()的次序兩個進程可以執(zhí)行完，這是一個p1和p2交叉執(zhí)行的次序，而不是一個順序執(zhí)行的次序，銀行家算法不能判斷。6． 能否給出避免死鎖的充要性算法? 為什么? 答：目前關(guān)于避免死鎖的算法，如銀行家算法是充分性算法，即確保系統(tǒng)時刻處于安全狀態(tài)，這是在系統(tǒng)已知每個進程所需資源最大量的條件下可以給出的最好結(jié)果。而且由于程序中分支和循環(huán)的存在，事先給出進程有關(guān)資源的命令序列一般是不可能的。7． 設(shè)有一個Ｔ型路口，其中A、B、C、D處各可容納一輛車，車行方向如下圖所示，試找出死鎖并用有序分配法消除之。 /\|S:左轉(zhuǎn)(2)S方向兩臺車分別位于B和C；E方向一臺車位于A；W方向一臺車位于D。車輛活動如下：semaphore s1=1,s2=1,s3=1,s4=1。 //按序申請P(s4)。駛?cè)隒。駛出C。E：左轉(zhuǎn)P(s2)。P(s3)；駛?cè)階。V(s3)；駛出D。S：左轉(zhuǎn)P(s1)。P(s2)；駛?cè)隑。V(s2)；駛出A。 證明：假定發(fā)生死鎖，且參與死鎖的進程個數(shù)為n(2￡n￡N)，參與死鎖的n個進程已經(jīng)占有系統(tǒng)中全部M個資源實例，而還沒夠(因它們處于無限期等待狀態(tài))，每個進程至少還需要一個資源實例，因而參與死鎖進程所需要資源總量3M＋n。由此可知，全部進程所需要的資源總量S3(M+n)+(Nn)=M+N。9． 在銀行家算法中，若出現(xiàn)如下資源分配情況： Allocation NeedAvailableABCDABCDABCDP0:003200121623P1:10001750P2:13542356P3:03320652P4:00140656試問：(1)當(dāng)前狀態(tài)是否安全？(2)如果進程P2提出安全請求Request[2]=(1,2,2,2),系統(tǒng)能否將資源分配給它？說明原因．解：（1）當(dāng)前狀態(tài)是安全狀態(tài)。令Work = Available=（1, 6, 2, 3）運行安全性檢測算法，F(xiàn)inish[0]=false并且Need[0]=(0 0 1 2)Work,則Work = Work + Allocation[0]=（1, 6, 2, 3）+（0, 0, 3, 2）=（1, 6, 5, 5）；Finish[0] = true；Finish[3]=false并且Need[3]=（0, 6, 5, 2）Work,則Work = Work + Allocation[3]=（1, 6, 5, 5）+（0, 3, 3, 2）=（1, 9, 8, 7）；Finish[3] = true；Finish[4]=false并且Need[4=（0, 6, 5, 6）Work,則Work = Work + Allocation[4]=（1, 9, 8, 7）+（0, 0, 1, 4 ）=（1, 9, 9, 11）；Finish[4] = true；Finish[1]=false并且Need[1]=（1, 7, 5, 0）Work,則Work = Work + Allocation[4]=（1, 9, 9, 1）+(1, 0, 0, 0 )=(2, 9, 9, 11)；Finish[1] = true；Finish[2]=false并且Need[2]=（2, 3, 5, 6）Work,則Work = Work + Allocation[4]=（2, 9, 9, 11）+（1, 3, 5, 4 ）=（3, 12, 14, 15）；Finish[2] = true；可以找到一個安全進程序列p0,p3，p4，p1,p2，它使Finish[i]=true，對于所有0≤i≤4，因而可以斷言系統(tǒng)當(dāng)前處于安全狀態(tài)．（2）運行銀行家算法，由于Request[2]=（1, 2, 2, 2）￡Need[2]=（2, 3, 5, 6），因而請求合法。假設(shè)將資源分配給p2，則系統(tǒng)狀態(tài)變?yōu)?Allocation NeedAvailableABCDABCDABCDP0:003200120401P1:10001750P2:25 761134P3:03320652P4:00140656運行安全性檢測算法，Work=Available=（0, 4, 0, 1），F(xiàn)inish[i]=false，此時所有Need[i]￡Work[i]均不成立，結(jié)果Finish[i]均為false，不存在安全進程序列，系統(tǒng)處于不安全狀態(tài)。10． 某系統(tǒng)采用死鎖檢測手段發(fā)現(xiàn)死鎖，設(shè)系統(tǒng)中資源類集合為{A，B，C}，資源類A中共有8個實例，資源類B中共有6個實例，資源類C中共有5個實例．又設(shè)系統(tǒng)中進程集合為{p1,p2,p3,p4,p5,p6}，某時刻系統(tǒng)狀態(tài)如下： Allocation RequestAvailable ABCAB CA B Cp1: 10 000 02 2 1p2: 3 2 10 0 0p3: 0 1220 2p4: 00000 0p5: 21003 1p6: 00100 011． 在上述狀態(tài)下系統(tǒng)依次接受如下請求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；Request[4]=(0,0,2)。在由(1)所確定的狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，說明此時已發(fā)生死鎖，并找出參與死鎖的進程。②如果系統(tǒng)接受請求后，將一個A分配給進程p1，則系統(tǒng)狀態(tài)變?yōu)椋篈llocation RequestAvailable ABCAB CA B Cp1: 20 00 0 012 1p2: 3 2 12 1 0p3: 0 1220 2p4: 00000 2p5: 21003 1p6: 00100 0在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列p4,p1,p2,p3,p5,p6，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當(dāng)前沒有進入死鎖狀態(tài)。答：（1）界地址存儲管理方式，進程空間的首地址從0開始編址；（2）頁式存儲管理，進程空間的首地址從0開始編址；（3）段式存儲管理，進程空間各段的首地址從0開始編址；（4）段頁式存儲管理，進程空間各段的起始地址從0開始編址。2．對于如下存儲管理方式來說，進程地址空間各是幾維的？ 此種方法適用于內(nèi)存頁面的分配，但對于外存頁面的分配因分配和去配均需執(zhí)行一次I/O傳輸，速度較慢。160