【文章內(nèi)容簡(jiǎn)介】 ex)。 put( )。 if(X%2==0) signal(full_even)。 else signal(full_odd)。 signal(mutex)。} } void P2( ) { wait(full_odd)。 wait(mutex)。 getodd( )。 countodd( )=countodd( )+1。 signal(empty)。 signal(mutex)。 } void P3( ) { wait(full_even)。 wait(mutex)。 geteven( )。 counteven( )=counteven( )+1。 signal(empty)。 signal(mutex)。 } void main( ) { parbegin(P1( ), P2( ), P3( ))。 }（6）放小球問(wèn)題：一個(gè)箱子里只有白色和黑色兩種小球，且數(shù)量足夠多。現(xiàn)在需要從中取出一些小球放入一個(gè)袋子中。約定：1）一次只能放入一個(gè)小球；2）白球的數(shù)量至多只能比黑球少N個(gè)，至多只能比黑球多M個(gè)（M，N為正整數(shù)）。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程的同步與互斥。struct semaphone mutex1, mutex2。int black=0, white=0。=1。=1。void put( ){ while(1) { wait(mutex1)。get a black ball or white ball from the box。signal(mutex1)。wait(mutex2)。 if(Black) //如果取到的是黑球 if(blackwhiteN) { black++。 put the black ball in bag。 } else //如果取到的是白球 if(( whiteblackM) { white++。 put the white ball in bag。 } signal(mutex2)。 }}void main( ){ parbegin(put( ))。}習(xí)題51．單項(xiàng)選擇題（1）當(dāng)作業(yè)進(jìn)入完成狀態(tài)時(shí)，操作系統(tǒng) 。A、 將刪除該作業(yè)并收回其所占資源，同時(shí)輸出結(jié)果B、 將該作業(yè)的控制塊從當(dāng)前作業(yè)隊(duì)列中刪除，收回其所占資源，并輸出結(jié)果C、 將收回該作業(yè)所占資源并輸出結(jié)果D、 將輸出結(jié)果并刪除內(nèi)存中的作業(yè)（2）批處理作業(yè)是被成批存入 ，以等待作業(yè)調(diào)度選擇。 A、輸入井 B、輸出井 C、映象區(qū) D、內(nèi)存（3）一種即有利于短作業(yè)又兼顧長(zhǎng)作業(yè)的作業(yè)調(diào)度算法是 。 A、最高響應(yīng)比優(yōu)先 B、先來(lái)先服務(wù) C、短作業(yè)優(yōu)先 D、均衡調(diào)度（4）在批處理系統(tǒng)中，周轉(zhuǎn)時(shí)間是 。 A、作業(yè)運(yùn)行時(shí)間 B、作業(yè)等待時(shí)間和運(yùn)行時(shí)間之和 C、作業(yè)的相對(duì)等待時(shí)間 D、作業(yè)被調(diào)度進(jìn)入內(nèi)存到運(yùn)行完畢的時(shí)間（5）在操作系統(tǒng)中，作業(yè)處于 狀態(tài)時(shí)，已處于進(jìn)程管理之下。 A、提交 B、后備 C、運(yùn)行 D、完成 （6）在作業(yè)調(diào)度中，若采用優(yōu)先級(jí)調(diào)度算法，為了盡可能使處理器和外部設(shè)備并行工作，有如下三個(gè)作業(yè)：J1以計(jì)算為主，J2計(jì)算和輸入輸出兼顧，J3以輸入輸出為主，則它們的優(yōu)先級(jí)從高到低的排列順序是 。 A、J1，J2，J3 B、J2，J3，J1 C、J2，J3，J1 D、J3，J1，J2 （7）一個(gè)作業(yè)被成功調(diào)度后，系統(tǒng)為其創(chuàng)建相應(yīng)的進(jìn)程，該進(jìn)程的初始狀態(tài)是 。 A、執(zhí)行態(tài) B、阻塞態(tài) C、就緒態(tài) D、等待訪問(wèn)設(shè)備態(tài)（1）B （2）A （3）A （4）B （5）B2．填空題（1）作業(yè)調(diào)度是從處于 后備 狀態(tài)的隊(duì)列中選取適當(dāng)?shù)淖鳂I(yè)投入運(yùn)行。從作業(yè)提交給系統(tǒng)到作業(yè)完成的時(shí)間間隔叫做 周轉(zhuǎn)時(shí)間 。 等待時(shí)間 是指作業(yè)從進(jìn)入后備隊(duì)列到被調(diào)到程序中的時(shí)間間隔。假定把下列四個(gè)作業(yè)同時(shí)提交系統(tǒng)并進(jìn)入 后備 隊(duì)列，當(dāng)使用短作業(yè)優(yōu)先調(diào)度算法時(shí)，單道環(huán)境下，四個(gè)作業(yè)的平均等待時(shí)間是 ，平均周轉(zhuǎn)時(shí)間是 ；當(dāng)使用高優(yōu)先數(shù)優(yōu)先的調(diào)度算法時(shí)，作業(yè)的平均等待時(shí)間是 ，平均周轉(zhuǎn)時(shí)間是 。作業(yè)所需運(yùn)行時(shí)間（小時(shí)）優(yōu)先數(shù)124259381437 （2）在一個(gè)具有分時(shí)兼批處理的系統(tǒng)中，總是優(yōu)先調(diào)度 分時(shí)作業(yè) 。 3．簡(jiǎn)答題（1）什么是分層次調(diào)度？在分時(shí)系統(tǒng)中有作業(yè)調(diào)度的概念嗎？如果沒(méi)有，為什么？分層次調(diào)度：為了提高進(jìn)程的利用率，在有些操作系統(tǒng)中把一部分在內(nèi)存中處于就緒狀態(tài)或阻塞狀態(tài)而在短時(shí)期內(nèi)又得不到執(zhí)行的進(jìn)程換出內(nèi)存，以讓其他作業(yè)的進(jìn)程競(jìng)爭(zhēng)處理器。一般地，按調(diào)度的層次，可將調(diào)度分為3級(jí)：高級(jí)調(diào)度、中級(jí)調(diào)度、低級(jí)調(diào)度（2）作業(yè)調(diào)度和進(jìn)程調(diào)度的主要功能分別是什么？ 作業(yè)調(diào)度：主要任務(wù)是從作業(yè)后備隊(duì)列中選擇作業(yè)進(jìn)入內(nèi)存 進(jìn)程調(diào)度：決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)并實(shí)際執(zhí)行將處理機(jī)分配給該進(jìn)程的操作（3）作業(yè)調(diào)度的性能評(píng)價(jià)標(biāo)準(zhǔn)有哪些？這些性能評(píng)價(jià)標(biāo)準(zhǔn)在任何情況下都能反映調(diào)度策略的優(yōu)劣嗎？ 調(diào)度性能評(píng)價(jià)的標(biāo)準(zhǔn)有：平均周轉(zhuǎn)時(shí)間、和平均響應(yīng)時(shí)間 響應(yīng)時(shí)間：從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)所用的時(shí)間 周轉(zhuǎn)時(shí)間：從作業(yè)提交到作業(yè)完成的時(shí)間間隔其平均值不能完全反映所有的策略有劣（4）為什么說(shuō)多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各類用戶的需要？ （5）假設(shè)就緒隊(duì)列中有10個(gè)進(jìn)程，系統(tǒng)將時(shí)間片設(shè)為200ms，CPU進(jìn)行進(jìn)程切換要花費(fèi)10ms，試問(wèn)系統(tǒng)開(kāi)銷所占的比率約為多少？（6）在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中一般常采用哪種調(diào)度算法？批處理系統(tǒng)：FCFS先來(lái)先服務(wù)、最短作業(yè)優(yōu)先、最短剩余時(shí)間優(yōu)先、響應(yīng)比最高者優(yōu)先分時(shí)系統(tǒng)：輪轉(zhuǎn)調(diào)度、優(yōu)先級(jí)調(diào)度、多級(jí)隊(duì)列調(diào)度、彩票調(diào)度實(shí)時(shí)系統(tǒng)：?jiǎn)伪嚷收{(diào)度、限期調(diào)度、最少裕度法（7）若在后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)3，已知它們各自的運(yùn)行時(shí)間為a、b、c，且滿足關(guān)系abc，試證明采用短作業(yè)優(yōu)先調(diào)度算法能獲得最小的平均周轉(zhuǎn)時(shí)間。（8）簡(jiǎn)述UNIX System V中進(jìn)程調(diào)度算法的特點(diǎn)。采用動(dòng)態(tài)優(yōu)先數(shù)調(diào)度策略，優(yōu)先數(shù)越大優(yōu)先級(jí)越低。調(diào)度程序從內(nèi)存就緒隊(duì)列中選取優(yōu)先數(shù)最小的進(jìn)程作為上行進(jìn)程3．應(yīng)用題（1）考慮5個(gè)進(jìn)程PPPPP5，它們的創(chuàng)建時(shí)間、運(yùn)行時(shí)間及優(yōu)先數(shù)如下表所示。規(guī)定進(jìn)程的優(yōu)先數(shù)越小，優(yōu)先級(jí)越高。試描述在采用下述幾種調(diào)度算法時(shí)各個(gè)進(jìn)程運(yùn)行過(guò)程，并計(jì)算采用每種算法時(shí)的進(jìn)程平均周轉(zhuǎn)時(shí)間。假設(shè)忽略進(jìn)程的調(diào)度時(shí)間。1）先來(lái)先服務(wù)調(diào)度算法；2）時(shí)間片輪轉(zhuǎn)調(diào)度算法（時(shí)間片為1ms）；3）非剝奪式優(yōu)先級(jí)調(diào)度算法；4）剝奪式優(yōu)先級(jí)調(diào)度算法。 進(jìn)程創(chuàng)建時(shí)間運(yùn)行時(shí)間（ms）優(yōu)先數(shù)P1033P2265P3441P4652P58241）先來(lái)先服務(wù)調(diào)度算法作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間（ms）開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間P103033P226397P3449139P465131812P582182012平均周轉(zhuǎn)時(shí)間T＝（3+7+9+12+12）/ 5=平均帶權(quán)周轉(zhuǎn)時(shí)間W=(3/3+7/6+9/4+12/5+12/2) / 5=2)時(shí)間片輪轉(zhuǎn)調(diào)度算法當(dāng)時(shí)間片q=1時(shí)，列出下表，找出運(yùn)行序列： 時(shí)刻運(yùn)行進(jìn)程排隊(duì)進(jìn)程時(shí)刻運(yùn)行進(jìn)程排隊(duì)進(jìn)程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è)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間P10344P2261816P3441713P4652014P582157平均周轉(zhuǎn)時(shí)間T＝（4+16+13+14+7）/ 5=平均帶權(quán)周轉(zhuǎn)時(shí)間W=(4/3+16/6+13/4+14/5+7/2) / 5=3) 非剝奪式優(yōu)先級(jí)調(diào)度算法作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間優(yōu)先數(shù)完成時(shí)間周轉(zhuǎn)時(shí)間P103333P226597P3441139P46521812P58242012平均周轉(zhuǎn)時(shí)間T＝（3+7+9+12+12）/ 5=平均帶權(quán)周轉(zhuǎn)時(shí)間W=(3/3+7/6+9/4+12/5+12/2) / 5=2015138430P1P2P3P4P54)剝奪式優(yōu)先級(jí)調(diào)度算法作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間優(yōu)先數(shù)完成時(shí)間周轉(zhuǎn)時(shí)間P103333P22652018P344184P4652137P5824157平均周轉(zhuǎn)時(shí)間T＝（3+18+4+7+7）/ 5=平均帶權(quán)周轉(zhuǎn)時(shí)間W=(3/3+18/6+4/4+7/5+7/2) / 5=9．有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的剝奪式調(diào)度算法。下表所示為作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。進(jìn)程到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù)A10：0040分5B10：2030分3C10：3050分4D10：5020分6（1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。（2）計(jì)算平均周轉(zhuǎn)時(shí)間。習(xí)題61．單項(xiàng)選擇題（1）以下關(guān)于死鎖的必要條件的敘述中錯(cuò)誤的是 。A、只要具備了死鎖的必要條件，就一定發(fā)生死鎖現(xiàn)象B、解決死鎖問(wèn)題可以從死鎖的必要條件出發(fā)C、一旦出現(xiàn)死鎖，處于死鎖狀態(tài)的進(jìn)程一定同時(shí)具備死鎖的必要條件D、死鎖的四個(gè)必要條件之間不是完全獨(dú)立的，但也不是等價(jià)的（2）以下關(guān)于死鎖檢測(cè)的敘述中錯(cuò)誤的是 。A、只要檢測(cè)出死鎖（尚未解除），則再申請(qǐng)?jiān)擃愘Y源的進(jìn)程一定會(huì)卷入死鎖B、只要檢測(cè)出死鎖（尚未解除），則使用該類資源的所有進(jìn)程一定卷入了死鎖C、死鎖檢測(cè)方法對(duì)系統(tǒng)資源的分配不加限制，只要有剩余資源就可以分配D、死鎖檢測(cè)中系統(tǒng)需要反復(fù)檢測(cè)各進(jìn)程資源申請(qǐng)和分配情況（3）以下關(guān)于死鎖問(wèn)題的說(shuō)法中正確的是 。A、死鎖問(wèn)題是無(wú)法解決的，但可以避免B、死鎖的預(yù)防是通過(guò)破壞進(jìn)程進(jìn)入不安全狀態(tài)來(lái)實(shí)現(xiàn)的C、通過(guò)避免死鎖四個(gè)必要條件中的任何一個(gè)就可以實(shí)現(xiàn)死鎖避免D、死鎖的檢測(cè)和解除是配合使用的，當(dāng)系統(tǒng)檢測(cè)到出現(xiàn)死鎖時(shí)，就通過(guò)死鎖解除方法解除死鎖 （4）以下關(guān)于系統(tǒng)的安全狀態(tài)的描述中正確的是 。A、系統(tǒng)處于不安全狀態(tài)一定會(huì)發(fā)生死鎖B、系統(tǒng)處于不安全狀態(tài)可能會(huì)發(fā)生死鎖C、系統(tǒng)處于安全狀態(tài)時(shí)也可能會(huì)發(fā)生死鎖D、不安全狀態(tài)是死鎖狀態(tài)的一個(gè)特例 （5）資源的靜態(tài)分配算法在解決死鎖問(wèn)題中用于 。 A、死鎖預(yù)防 B、死鎖避免 C、死鎖檢測(cè) D、死鎖解除 （6）有3個(gè)進(jìn)程共享7個(gè)同類資源，為使系統(tǒng)不會(huì)發(fā)生死鎖，每個(gè)進(jìn)程最多可以申請(qǐng) 個(gè)資源。 A、1 B、2 C、3 D、4（1）A （2）B （3）D （4）B （5）A2．填空題（1）解決死鎖的方法可以有多種，其中死鎖的預(yù)防是通過(guò) 破壞死鎖的必要條件之一 來(lái)實(shí)現(xiàn)的，死鎖的避免是通過(guò) 防止系統(tǒng)進(jìn)入不安全狀態(tài) 來(lái)實(shí)現(xiàn)的。（2）死鎖的避免，就是通過(guò)保持系統(tǒng)處于 安全狀態(tài) 來(lái)避免死鎖，所以每當(dāng)有進(jìn)程提出資源分配請(qǐng)求時(shí)，系統(tǒng)應(yīng)分析 各進(jìn)程已占資源數(shù)、尚需資源數(shù)和系統(tǒng)中可以分配的剩余資源數(shù)，然后決定是否為當(dāng)前的申請(qǐng)者分配資源。（3）死鎖檢測(cè)要解決兩個(gè)問(wèn)題，一是 判斷系統(tǒng) 是否出現(xiàn)了死鎖，二是當(dāng)有死鎖發(fā)生時(shí)怎樣去 解除死鎖 。（4）為了避免死鎖，可以采用 銀行家 算法進(jìn)行資源安全分配。（5）系統(tǒng)出現(xiàn)死鎖，不僅與 設(shè)備 分配策略有關(guān)，而且與 進(jìn)程 執(zhí)行的相對(duì)速度有關(guān)。（6）當(dāng)檢測(cè)到系統(tǒng)發(fā)生死鎖時(shí)，可采用 解除所有死鎖進(jìn)程 、 逐個(gè)撤銷死鎖進(jìn)程 和 搶占死鎖進(jìn)程的資源供其它進(jìn)程使用 來(lái)解除死鎖。3．簡(jiǎn)答題（1）何謂死鎖？給出只涉及一個(gè)進(jìn)程的死鎖例子。兩個(gè)或兩個(gè)以上的進(jìn)程無(wú)限期地等待永遠(yuǎn)不可能發(fā)生的事件，則稱這些進(jìn)程處于死鎖。列：系統(tǒng)資源不足（2）死鎖預(yù)防和死鎖避免。死