【正文】 1) t=t+z。 signal(s)。 }（6）共享存儲區(qū)通信是如何實現(xiàn)的？（7）假設(shè)某系統(tǒng)未直接提供信號量機制，但提供了進程通信工具。5．應(yīng)用題（1）有三個并發(fā)進程R、W1和W2，共享兩個各可存放一個數(shù)的緩沖區(qū)BB2。試編寫保證三者正確工作的程序。=1。=1。void R( ){ int a。 if(a%2==1) { wait(B1_Empty)。signal(B1_Full)。put a in B2。 } } } void W1( ) { while(1) { wait(B1_Full)。 signal(B1_Empty)。 print a number from B2。 } } void main( ) { parbegin(R( ), W1( ), W2( ))。它們滿足下列條件：任務(wù)A必須領(lǐng)先于任務(wù)B、C和E；任務(wù)E和D必須領(lǐng)先于任務(wù)F；任務(wù)B和C必須領(lǐng)先與任務(wù)D；而任務(wù)F必須領(lǐng)先于任務(wù)G和H。（3）多個進程共享一個文件，其中只讀文件的稱為讀者，只寫文件的稱為寫者。問：1）說明進程間的制約關(guān)系，應(yīng)設(shè)置哪些信號量？2）用wait、signal操作寫出其同步程序。而無論是否有讀者在讀文件。爸爸可向盤中放蘋果，也可向盤中放桔子；兒子專等吃盤中的桔子；女兒專等吃盤中的蘋果。struct semaphone plate, apple, orange。=0。void father( ){ while(1){ prepare an apple or orange。 put the apple or orange in plate。 //如果放的是蘋果 else signal(orange)。 get an orange from the plate。 } } void daughter( ) { while(1) { wait(apple)。 signal(plate)。P1每次用procuce（）生成一個正整數(shù)并用put（）送入緩沖區(qū)某一空單元中；P2每次用getodd（）從該緩沖區(qū)中取出一個奇數(shù)并用countodd（）統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個偶數(shù)并用counteven（）統(tǒng)計偶數(shù)個數(shù)。要求用偽代碼描述（2009年全國碩士研究生入學考試題）。=0。=1。void P1( ){ int X。 wait(empty)。 put( )。 else signal(full_odd)。} } void P2( ) { wait(full_odd)。 getodd( )。 signal(empty)。 } void P3( ) { wait(full_even)。 geteven( )。 signal(empty)。 } void main( ) { parbegin(P1( ), P2( ), P3( ))?，F(xiàn)在需要從中取出一些小球放入一個袋子中。請用信號量機制實現(xiàn)進程的同步與互斥。int black=0, white=0。=1。get a black ball or white ball from the box。wait(mutex2)。 put the black ball in bag。 put the white ball in bag。 }}void main( ){ parbegin(put( ))。A、 將刪除該作業(yè)并收回其所占資源，同時輸出結(jié)果B、 將該作業(yè)的控制塊從當前作業(yè)隊列中刪除，收回其所占資源，并輸出結(jié)果C、 將收回該作業(yè)所占資源并輸出結(jié)果D、 將輸出結(jié)果并刪除內(nèi)存中的作業(yè)（2）批處理作業(yè)是被成批存入 ，以等待作業(yè)調(diào)度選擇。 A、最高響應(yīng)比優(yōu)先 B、先來先服務(wù) C、短作業(yè)優(yōu)先 D、均衡調(diào)度（4）在批處理系統(tǒng)中，周轉(zhuǎn)時間是 。 A、提交 B、后備 C、運行 D、完成 （6）在作業(yè)調(diào)度中，若采用優(yōu)先級調(diào)度算法，為了盡可能使處理器和外部設(shè)備并行工作，有如下三個作業(yè)：J1以計算為主，J2計算和輸入輸出兼顧，J3以輸入輸出為主，則它們的優(yōu)先級從高到低的排列順序是 。 A、執(zhí)行態(tài) B、阻塞態(tài) C、就緒態(tài) D、等待訪問設(shè)備態(tài)（1）B （2）A （3）A （4）B （5）B2．填空題（1）作業(yè)調(diào)度是從處于 后備 狀態(tài)的隊列中選取適當?shù)淖鳂I(yè)投入運行。 等待時間 是指作業(yè)從進入后備隊列到被調(diào)到程序中的時間間隔。作業(yè)所需運行時間（小時）優(yōu)先數(shù)124259381437 （2）在一個具有分時兼批處理的系統(tǒng)中，總是優(yōu)先調(diào)度 分時作業(yè) 。一般地，按調(diào)度的層次，可將調(diào)度分為3級：高級調(diào)度、中級調(diào)度、低級調(diào)度（2）作業(yè)調(diào)度和進程調(diào)度的主要功能分別是什么？ 作業(yè)調(diào)度：主要任務(wù)是從作業(yè)后備隊列中選擇作業(yè)進入內(nèi)存 進程調(diào)度：決定就緒隊列中哪個進程將獲得處理機并實際執(zhí)行將處理機分配給該進程的操作（3）作業(yè)調(diào)度的性能評價標準有哪些？這些性能評價標準在任何情況下都能反映調(diào)度策略的優(yōu)劣嗎？ 調(diào)度性能評價的標準有：平均周轉(zhuǎn)時間、和平均響應(yīng)時間 響應(yīng)時間：從提交第一個請求到產(chǎn)生第一個響應(yīng)所用的時間 周轉(zhuǎn)時間：從作業(yè)提交到作業(yè)完成的時間間隔其平均值不能完全反映所有的策略有劣（4）為什么說多級反饋隊列調(diào)度算法能較好地滿足各類用戶的需要？ （5）假設(shè)就緒隊列中有10個進程，系統(tǒng)將時間片設(shè)為200ms，CPU進行進程切換要花費10ms，試問系統(tǒng)開銷所占的比率約為多少？（6）在批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中一般常采用哪種調(diào)度算法？批處理系統(tǒng)：FCFS先來先服務(wù)、最短作業(yè)優(yōu)先、最短剩余時間優(yōu)先、響應(yīng)比最高者優(yōu)先分時系統(tǒng)：輪轉(zhuǎn)調(diào)度、優(yōu)先級調(diào)度、多級隊列調(diào)度、彩票調(diào)度實時系統(tǒng)：單比率調(diào)度、限期調(diào)度、最少裕度法（7）若在后備作業(yè)隊列中等待運行的同時有三個作業(yè)3，已知它們各自的運行時間為a、b、c，且滿足關(guān)系abc，試證明采用短作業(yè)優(yōu)先調(diào)度算法能獲得最小的平均周轉(zhuǎn)時間。采用動態(tài)優(yōu)先數(shù)調(diào)度策略，優(yōu)先數(shù)越大優(yōu)先級越低。規(guī)定進程的優(yōu)先數(shù)越小，優(yōu)先級越高。假設(shè)忽略進程的調(diào)度時間。 進程創(chuàng)建時間運行時間（ms）優(yōu)先數(shù)P1033P2265P3441P4652P58241）先來先服務(wù)調(diào)度算法作業(yè)號進入時間運行時間（ms）開始執(zhí)行時間完成時間周轉(zhuǎn)時間P103033P226397P3449139P465131812P582182012平均周轉(zhuǎn)時間T＝（3+7+9+12+12）/ 5=平均帶權(quán)周轉(zhuǎn)時間W=(3/3+7/6+9/4+12/5+12/2) / 5=2)時間片輪轉(zhuǎn)調(diào)度算法當時間片q=1時，列出下表，找出運行序列： 時刻運行進程排隊進程時刻運行進程排隊進程0～1P110～11P5P4 P3 P21～2P111～12P4P3 P2 P52～3P2P112～13P3P2 P5 P43～4P1P213～14P2P5 P4 P34～5P2P314～15P5P4 P3 P25～6P3P215～16P4P3 P26～7P2P4 P316～17P3P2 P47～8P4P3 P217～18P2P48～9P3P2 P5 P418～19P49～10P2P5 P4 P319～20P4作業(yè)號進入時間運行時間完成時間周轉(zhuǎn)時間P10344P2261816P3441713P4652014P582157平均周轉(zhuǎn)時間T＝（4+16+13+14+7）/ 5=平均帶權(quán)周轉(zhuǎn)時間W=(4/3+16/6+13/4+14/5+7/2) / 5=3) 非剝奪式優(yōu)先級調(diào)度算法作業(yè)號進入時間運行時間優(yōu)先數(shù)完成時間周轉(zhuǎn)時間P103333P226597P3441139P46521812P58242012平均周轉(zhuǎn)時間T＝（3+7+9+12+12）/ 5=平均帶權(quán)周轉(zhuǎn)時間W=(3/3+7/6+9/4+12/5+12/2) / 5=2015138430P1P2P3P4P54)剝奪式優(yōu)先級調(diào)度算法作業(yè)號進入時間運行時間優(yōu)先數(shù)完成時間周轉(zhuǎn)時間P103333P22652018P344184P4652137P5824157平均周轉(zhuǎn)時間T＝（3+18+4+7+7）/ 5=平均帶權(quán)周轉(zhuǎn)時間W=(3/3+18/6+4/4+7/5+7/2) / 5=9．有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的剝奪式調(diào)度算法。進程到達時間估計運行時間優(yōu)先數(shù)A10：0040分5B10：2030分3C10：3050分4D10：5020分6（1）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。習題61．單項選擇題（1）以下關(guān)于死鎖的必要條件的敘述中錯誤的是 。A、只要檢測出死鎖（尚未解除），則再申請該類資源的進程一定會卷入死鎖B、只要檢測出死鎖（尚未解除），則使用該類資源的所有進程一定卷入了死鎖C、死鎖檢測方法對系統(tǒng)資源的分配不加限制，只要有剩余資源就可以分配D、死鎖檢測中系統(tǒng)需要反復(fù)檢測各進程資源申請和分配情況（3）以下關(guān)于死鎖問題的說法中正確的是 。A、系統(tǒng)處于不安全狀態(tài)一定會發(fā)生死鎖B、系統(tǒng)處于不安全狀態(tài)可能會發(fā)生死鎖C、系統(tǒng)處于安全狀態(tài)時也可能會發(fā)生死鎖D、不安全狀態(tài)是死鎖狀態(tài)的一個特例 （5）資源的靜態(tài)分配算法在解決死鎖問題中用于 。 A、1 B、2 C、3 D、4（1）A （2）B （3）D （4）B （5）A2．填空題（1）解決死鎖的方法可以有多種，其中死鎖的預(yù)防是通過 破壞死鎖的必要條件之一 來實現(xiàn)的，死鎖的避免是通過 防止系統(tǒng)進入不安全狀態(tài) 來實現(xiàn)的。（3）死鎖檢測要解決兩個問題，一是 判斷系統(tǒng) 是否出現(xiàn)了死鎖，二是當有死鎖發(fā)生時怎樣去 解除死鎖 。（5）系統(tǒng)出現(xiàn)死鎖，不僅與 設(shè)備 分配策略有關(guān)，而且與 進程 執(zhí)行的相對速度有關(guān)。3．簡答題（1）何謂死鎖？給出只涉及一個進程的死鎖例子。列：系統(tǒng)資源不足（2）死鎖預(yù)防和死鎖避免。1 破壞互斥條件。3 破壞請求與保持條件。2 銀行家算法避免死鎖。安全狀態(tài)：系統(tǒng)按順序為每個進程分配所需資源，直到滿足每個進程對資源的最大需求，使每個進程都可以順利完成。證明：當n個進程最多需要的資源之和小于m+n時，該系統(tǒng)無死鎖。【證明】根據(jù)以上分析，有：(a11)+(a21)+…+(ai1)…+(an1)≤m1 即 a1+a2+…+ai…+an≤m+n1 亦即 a1+a2+…+ai…+anm+n 命題得證（2）考慮下列資源分配策略：對資源的申請和釋放可以在任何時候進行。1）這種分配策略會導致死鎖嗎？如果會，請舉一個例子；如果不會，請說明產(chǎn)生死鎖的哪一個必要條件不成立？ 2）這種分配方式會導致某些進程的無限等待嗎？為什么？1）不會，因為資源集中在了最后一個申請該資源而陷入等待的進程，條件成熟時，最后一個進程能夠完成工作，釋放資源給其它進程。2）由于后來進程總要剝奪先到的而處于阻塞狀態(tài)進程的資源，因此，先到的進程可能由于長期得不到資源而處于無限期等待狀態(tài)。最大資源需求量已分配資源數(shù)量R1 R2 R3R1 R2 R3P13 2 21 0 0P26 1 34 1 1P33 1 42 1 1P44 2 20 0 2問題：1）將系統(tǒng)中各類資源總數(shù)和此刻各進程對資源的需求數(shù)目用向量或矩陣表示出來；2）如果此時P1和P2均發(fā)出資源請求向量Request(1,0,1)，為了保證系統(tǒng)的安全性，應(yīng)該如何分配資源給這兩個進程？說明你所采用策略的原因。而把資源分配給P2后，需求矩陣為：而系統(tǒng)可用資源向量為（1，1，1），顯然，存在安全序列 P2，P1，P4，P3，系統(tǒng)仍然處于安全狀態(tài)。習題71．單項選擇題（1