【正文】 位置的請示訪問者將優(yōu)先執(zhí)行，當前磁頭在53道上，則總的移動順序為：53—65—67—98—122—124—183—37—14。移動道數(shù)為：12+2+30+23+84+24+2+59=236。若磁頭的當前位置為100磁道，磁頭正向磁道號增加方向移動，現(xiàn)有一磁盤讀寫請求隊列：237201316190、392140。若采用我來先服務、最短尋道時間優(yōu)先和掃描算法，試計算出平均尋道長度各為多少？解：采用先來先服務方法：磁道移動數(shù)目為：77+353+171+73+113+42+129+208+369+25+14+22=1596，平均尋道長度為1596/12=133。采用最短尋道時間優(yōu)先磁盤調度算法，進行調度的情況為：32+58+15+144+21+11+6+4+1+14+372+22=700，平均尋道長度為700/12=。采用掃描算法，進行調度時，從100道開始，磁頭向磁道號增加的方向移動，磁道移動總數(shù)為：32+58+15+171+22+337+21+11+6+4+1+14=692，平均尋道長度為：692/12=。第六章 進程間的制約關系一、選擇題1．在為多道程序所提供的可共享的系統(tǒng)資源不足時，可能出現(xiàn)死鎖。但是，不適當?shù)模ˋ ）也可能產生死鎖。 B2．采用資源剝奪法可解除死鎖，還可以采用（B）方法解除死鎖。 ：互斥、（ B ）、循環(huán)等待和不剝奪。 　，要防止死鎖的發(fā)生，可以破壞這四個必要條件，但破壞（A ）條件是不太實際的。 （ D ）條件。 ?。?C ）的情況下，系統(tǒng)出現(xiàn)死鎖。 （ B ）算法。 ，進程競爭資源（ B ）會產生死鎖。 —定10．在非剝奪調度方式下，運行進程執(zhí)行V原語后，其狀態(tài)（ A ）。 B11．兩個進程爭奪同一個資源（B ）。 （ A ）。 （ C ）。0，進程繼續(xù)執(zhí)行 0，要喚醒一個就緒進程 =0，要喚醒一個等待進程 =0，要喚醒一個就緒進程，當S0，進程將進入信號量的（A）。 （C ）的進程隊列就說明系統(tǒng)有可能發(fā)生死鎖了。 ，當前值為－2，則等待在該信號量上的進程數(shù)為（B ）個。 （C）條件，來達到預防死鎖的目的。B18. 設系統(tǒng)中有N（N2）個進程，則系統(tǒng)中最不可能的是有（B）個進程處于死鎖狀態(tài)。 （2M=N）19．任何兩個并發(fā)進程之間（ D ）。A．一定存在互斥關系 B．一定存在同步關系C．一定彼此獨立無關 D．可能存在同步或互斥關系20．P、V操作是（ A ）。A．兩條低級進程通信原語 B．兩條高級進程通信原語C．兩條系統(tǒng)調用命令 D．兩條特權指令22．進程的并發(fā)是指若干個進程（ A ）。A．共享系統(tǒng)資源　　　　B．在執(zhí)行的時間上是重疊的　　C．順序執(zhí)行　　　　　　D．相互制約23．下列解決死鎖的方法中，屬于死鎖預防策略的是（ B ）。A．銀行家算法　 　　　B．資源有序分配　C．資源分配圖化簡法 D．撤消進程法24．使用mail命令的進程通信屬于（ D ）通信。A．共享存儲器　　B．實時通信　　C．消息緩沖通信 D．非實時通信25．從下面對臨界區(qū)的敘述中選出一條正確的（ D ）。A．臨界區(qū)是指進程中用于實現(xiàn)進程互斥的那段代碼。B．臨界區(qū)是指進程中用于實現(xiàn)進程同步的那段代碼。C．臨界區(qū)是指進程中用于實現(xiàn)進程通信的那段代碼。D．臨界區(qū)是指進程中訪問臨界資源的那段代碼。27．若兩個并發(fā)進程相關臨界區(qū)的互斥信號量mutex現(xiàn)在的取值為0，則正確的描述就該是（ B 　）。A．沒有進程進入臨界區(qū)　　　　　　　　　B．有一個進程進入臨界區(qū)　C．有一個進程進入臨界區(qū)，另一個在等待　　　　D．不定28．信箱通信是進程間的一種（ B ）通信方式。A．直接　　　　B．間接　　　C．低級　　　　　D．信號量二、填空題1．每個進程中訪問（臨界資源 ）的程序段稱為臨界區(qū)，兩個進程同時進入相關的臨界區(qū)會造成錯誤。2．在操作系統(tǒng)中進程間的通信可以分為（ 直接 ）通信與（間接 ）通信兩種。3．產生死鎖的四個必要條件是（互斥 ）、（請求和保持 ）、（不剝奪 ）和循環(huán)等待條件。4．在銀行家法中，當一個進程提出資源請求將會導致系統(tǒng)從（ 安全 ）狀態(tài)進入（ 不安全 ）狀態(tài)時，就暫時拒絕這一請求。5．信號量的物理意義是當信號量大于零時表示（可用的臨界資源的個數(shù) ）。當信號量小于零時，其絕對值為（因為得不到該臨界資源而阻塞的進程個數(shù) ）。（動 ）態(tài)概念，而程序是一個（靜 ）態(tài)概念。7．對待死鎖，一般應考慮死鎖的預防、避免、檢測和解除四個問題。典型的銀行家算法是屬于（死鎖避免 ），破壞環(huán)路等待條件是屬于（ 預防死鎖 ），而剝奪資源是（ 死鎖解除 ）的基本方法。三、名詞解釋1. 臨界區(qū)：每個進程中訪問臨界資源的那段代碼。2. 臨界資源：在一段時間內只允許一個進程訪問的資源。3. 進程同步：相互合作的進程中，某一進程要等待另一進程提供信息才能夠繼續(xù)執(zhí)行，把這樣的進程間的制約關系稱為進程同步。4. 進程互斥：一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行，也就是說，不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)。5. 進程通信：指進程之間的信息交換。6. 管道：是指用于連接一個讀進程和一個寫進程以實現(xiàn)他們之間通信的一個共享文件，又名pipe文件。7. 死鎖：是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。8. 死鎖定理：當且僅當某狀態(tài)的資源分配圖是不可完全簡化的。四、簡答題1. 同步機構應遵循哪些基本準則？為什么？答：（1）空閑讓進：當無進程處于臨界區(qū)時，應允許一個請求進入臨界區(qū)的進程立即進入，以有效地利用臨界資源。（2）忙則等待：當已有進程進入臨界區(qū)時，其他試圖進入臨界區(qū)的進程必須等待，以保證對臨界資源的互斥訪問。（3）有限等待：對要求訪問臨界資源的進程，應保證在有限時間內使其進入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。（4）讓權等待：當進程不能進入自己的臨界區(qū)時，應立即釋放處理機，以免進程陷入“忙等”。2. 產生死鎖的原因和必要條件是什么？答：產生死鎖的原因包括競爭資源和進程間推進順序非法。產生死鎖的必要條件是互斥條件、請求和保持條件、不剝奪條件、環(huán)路等待條件。3. 不安全狀態(tài)是否必然導致系統(tǒng)進入死鎖狀態(tài)？答：不安全狀態(tài)不一定導致系統(tǒng)進入死鎖狀態(tài)。因為，安全性檢查中使用的向量Max是進程執(zhí)行前提供的，而在實際運行過程中，一進程需要的最大資源量可能小于Max，如一進程對應的程序中有一段進行錯誤處理的代碼，其中需要n個A種資源，若該進程在運行過程中沒有碰到相應錯誤而不需調用該段錯誤處理代碼，則它實際上將完全不會請求這n個A種資源。4. 有相同類型的5個資源被4個進程所共享，且每個進程最多需要2個這樣的資源就可以運行完畢。試問該系統(tǒng)是否會由于對這種資源的競爭而產生死鎖。答：該系統(tǒng)不會由于對這種資源的競爭而產生死鎖。因為在最壞情況下，每個進程都需要2個這樣的資源，且每個進程都已申請到了1個資源，那么系統(tǒng)中還剩下1個可用資源。無論系統(tǒng)為了滿足哪個進程的資源申請而將資源分配給該進程，都會因為該進程已獲得了它所需要的全部資源而確保它運行完畢，從而可將它占有的2個資源歸還給系統(tǒng)，這就保證了其余三個進程能順利運行。由于可知，該系統(tǒng)不會由于對這種資源的競爭而產生死鎖。五、綜合題1. 試從物理概念上說明記錄型信號量P和V。答：P意味著進程請求一個單位的資源，（），0時，表示資源已分配完畢，此時該進程進行自我阻塞，放棄CPU，；否則表示請求成功，進程可繼續(xù)執(zhí)行。V表示執(zhí)行的進程釋放一個單位的資源，≤0時，表示在該信號量表中仍有等待該資源的進行被阻塞，此時應調用喚醒原語，；否則不進行其他操作。2. 在生產者——消費者問題中，如果缺少了V(full)或V(empty)，對執(zhí)行結果有何影響？答：如果缺少了V(full)，則full信號量的值總是0，消費者執(zhí)行P(full)時就會阻塞，而且永不會被喚醒，而生產者生產消息裝滿緩沖池后也會阻塞，此后緩沖池一直是滿狀態(tài)。如果缺少了V(empty)，生產者生產了n個消息后就會阻塞，此后empty信號量的值一直為0，而消費者消費完后也會一直阻塞，緩沖池以后一直是空的。3. 在測量控制系統(tǒng)中的數(shù)據(jù)采集任務時，把所采集的數(shù)據(jù)送往一單緩沖區(qū)；計算任務從該單緩沖區(qū)中取出數(shù)據(jù)進行計算。試寫出利用信號量機制實現(xiàn)兩任務共享單緩沖區(qū)的同步算法。答：var empty,full:semaphore:=1,0var buffer:bbeginparbegin gather: beginrepeat ……..gather an item in x。P(empty)。b:=x。V(full)。until false。endpute: beginrepeat……..P(full)。y:=b。V(empty)。pute the item in y。until false。endparendend4. 桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果或桔子，兒子專等吃桔子，女兒專等吃蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取用，請用P、V操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。答：var s,sa,s0:semaphore:=1,0,0begin parbegin father:begin repeat P(s)。 將水果放入盤中；if(放的是桔子) then V(s0)。 else V(sa)。until falseendson: begin repeat P(s0)。從盤中取桔子；V(s)。吃桔子；until falseenddaughter: begin repeatP(sa)。從盤中取蘋果；V(s)。吃蘋果；until falseendparendend ：分別按三種調度算法填寫出下列作業(yè)的完成時間、周轉時間、帶權周轉時間和執(zhí)行序列。進程名ABCDE執(zhí)行序列到達時間01345服務時間21532FCFS完成時間2381113ABCDE周轉時間22578帶權周轉時間1217/34SJF完成時間2381310ABCED周轉時間22595帶權周轉時間12135/2RRq=2完成時間2313129ABCDECDC周轉時間221084帶權周轉時間1228/325. 在銀行家算法中，若出現(xiàn)下述資源分配情況：ProcessAllocationA B C DNeedABCDAvailableABCDP00 0 3 20 0 1 21 7 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 0 3 20 6 5 2P40 0 1 40 6 5 6試問：（1）該狀態(tài)是否安全？（2）若進程P2提出請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？答：（1）對該狀態(tài)進行安全性檢查：資源情況進程WorkA B C DNeed A B C DAllocation A B C DWork+Allocation A B C DFinish P0P3P4P1P21 7 2 21 7 5 41 7 8 61 7 9 102 7 9 100 0 1 20 6 5 20 6 5 61 7 5 02 3 5 60 0 3 20 0 3 20 0 1 41 0 0 01