任命大學答案(共7頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上操作系統(tǒng)2016年07月考試考前練習題一、綜合應用題1. 某寺廟有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚飲用，水缸可容納10桶水，水取自同一口井，水井徑窄，每次只能容一個桶取水，水桶總數(shù)為3個，每次入水取水僅為1桶水，且不可同時進行，試給出有關(guān)從缸取水、入水的算法描述。2. 設A、B兩個具有完成截止期限的周期性實時任務的執(zhí)行輪廓如下表所示，請畫出采用以下調(diào)度算法進行調(diào)度的進程運行圖：（1）固定優(yōu)先級調(diào)度（A優(yōu)先）；（2）固定優(yōu)先級調(diào)度（B優(yōu)先）；（3）最早完成截止時間調(diào)度。進程到達時間執(zhí)行時間結(jié)束截止時間A（1）01020A（2）201040A（3）4

2、01060A（4）601080A（5）8010100*B（1）02550B（2）5025100*3. 為什么要在操作系統(tǒng)中引入進程的概念？引入進程的概念會對系統(tǒng)產(chǎn)生怎樣的影響？4. 設有四個作業(yè)J1、J2、J3、J4，它們的到達時間和計算時間見下表，若這四個作業(yè)在一臺處理器上按單道方式運行，采用最高響應比優(yōu)先調(diào)度算法，試寫出各作業(yè)的執(zhí)行順序、各作業(yè)的周轉(zhuǎn)時間及平均周轉(zhuǎn)時間。5. 有三個進程P1、P2和P3并發(fā)工作，進程P1需要資源S3和S1，進程P2需要資源S2和S1，進程P3需要資源S3和S2，問：（1）若對資源分配不加限制，會發(fā)生什么情況？為什么？（2）為保證進程正常運行，應采用怎樣的分配

3、策略？列出所有可能的方法。6. 在單處理器系統(tǒng)中，如果用戶級線程與內(nèi)核級線程間是一對一的映射，那么，多線程程序比相同功能的單線程程序運行快，為什么？7. 請說明Linux系統(tǒng)中的進程狀態(tài)中的不可中斷（uninterruptible）狀態(tài)的含義和用途。8. 若從存取速度、存儲空間利用、易更新性的角度考慮文件系統(tǒng)的有效性，針對以下各種情形，什么樣的文件組織的有效性最好：（1）數(shù)據(jù)更新不頻繁，按隨機次序頻繁存??；（2）數(shù)據(jù)頻繁更新，比較頻繁地存取整個文件；（3）數(shù)據(jù)頻繁更新，按隨機次序頻繁存取。9. 設一個層次式文件系統(tǒng)以空閑空間鏈表的方式管理空閑磁盤空間，請考慮：（1）假如指向空閑空間的指針丟失，

4、系統(tǒng)能否重構(gòu)空閑空間鏈表？（2）試設計一個方案，確保單個內(nèi)存故障不會導致指針丟失。10. 設某系統(tǒng)中既有就緒進程也有就緒/掛起進程，且至少有一個就緒/掛起進程的優(yōu)先級比所有就緒進程都高，有兩種極端的調(diào)度策略：（1）為減少交換，總是選擇就緒進程運行；（2）總是選擇最高優(yōu)先級的進程運行，哪怕引起不必要的交換。請你給出一種既考慮優(yōu)先級也考慮性能的折中策略。11. 設A、B、C、D、E五個進程的到達時間和服務時間如下表所示，請分別畫出用循環(huán)調(diào)度算法（RR，q=1）、最短剩余時間優(yōu)先算法（SRT）、最高響應比優(yōu)先算法（HRRN）進行調(diào)度的進程運行圖。 附：參考答案1. 某寺廟有小和尚、老和尚若干，有一水

5、缸，由小和尚提水入缸供老和尚飲用，水缸可容納10桶水，水取自同一口井，水井徑窄，每次只能容一個桶取水，水桶總數(shù)為3個，每次入水取水僅為1桶水，且不可同時進行，試給出有關(guān)從缸取水、入水的算法描述。解答:從井中取水并放入水缸是一個連續(xù)的動作可以視為一個進程，從缸中取水為另一個進程。設水井和水缸為臨界資源，引入well、vat；三個水桶無論從井中取水還是放入水缸中都是一次一個，應該給它們一個信號量pail，搶不到水桶的進程只好等待。水缸滿時，不可能再放水，設置empty信號量控制入水量；水缸空時，不可以取水，設置full信號量來控制。本題需要設置5個信號量來控制：semaphore well=1;

6、/用于互斥地訪問水井semaphore vat=1; /用于互斥地訪問水缸semaphore empty=10; /用于表示水缸中剩余空間能容納的水的桶數(shù)semaphore full=0; /表示水缸中的水的桶數(shù)semaphore pail=3; /表示有多少個水桶可以用，初值為3/老和尚while(1)p(full);p(pail);p(vat);從水缸中打一桶水;V(vat);V(empty);喝水;V(pail);/小和尚while(1)p(empty);p(pail);p(well);從井中打一桶水;V(well);p(vat);將水倒入水缸中;V(vat);V(full);V(pai

7、l);2. 設A、B兩個具有完成截止期限的周期性實時任務的執(zhí)行輪廓如下表所示，請畫出采用以下調(diào)度算法進行調(diào)度的進程運行圖：（1）固定優(yōu)先級調(diào)度（A優(yōu)先）；（2）固定優(yōu)先級調(diào)度（B優(yōu)先）；（3）最早完成截止時間調(diào)度。進程到達時間執(zhí)行時間結(jié)束截止時間A（1）01020A（2）201040A（3）401060A（4）601080A（5）8010100*B（1）02550B（2）5025100*解答:3. 為什么要在操作系統(tǒng)中引入進程的概念？引入進程的概念會對系統(tǒng)產(chǎn)生怎樣的影響？解答:在操作系統(tǒng)中引入進程的概念，是為了實現(xiàn)多個程序的并發(fā)執(zhí)行。傳統(tǒng)的程序不能與其他程序并發(fā)執(zhí)行，只有在為其創(chuàng)建進程后才能與

8、其他程序（進程）并發(fā)執(zhí)行。這是因為并發(fā)執(zhí)行的程序（即進程）是"走走停停"地執(zhí)行的，只有在為其創(chuàng)建進程后，在停下時才能將其現(xiàn)場信息保存在它的PCB中，等下次被調(diào)度時再從PCB中恢復CPU現(xiàn)場并繼續(xù)執(zhí)行，而傳統(tǒng)的程序無法滿足上述要求。建立進程所帶來的好處是使多個程序能并發(fā)執(zhí)行，這極大地提高了資源利用率和系統(tǒng)吞吐量。但管理進程也需要付出一定代價，包括PCB以及協(xié)調(diào)各運行機構(gòu)所占用的內(nèi)存空間開銷，以及為進行進程間切換、同步和通信等所付出的時間開銷。4. 設有四個作業(yè)J1、J2、J3、J4，它們的到達時間和計算時間見下表，若這四個作業(yè)在一臺處理器上按單道方式運行，采用最高響應比優(yōu)先調(diào)

9、度算法，試寫出各作業(yè)的執(zhí)行順序、各作業(yè)的周轉(zhuǎn)時間及平均周轉(zhuǎn)時間。解答:5. 有三個進程P1、P2和P3并發(fā)工作，進程P1需要資源S3和S1，進程P2需要資源S2和S1，進程P3需要資源S3和S2，問：（1）若對資源分配不加限制，會發(fā)生什么情況？為什么？（2）為保證進程正常運行，應采用怎樣的分配策略？列出所有可能的方法。解答:1）可能會發(fā)生死鎖。滿足發(fā)生死鎖的四大條件，例：P1占有S1申請S3，P2占有S2申請S1，P3占有S3申請S2。2）可有以下幾種答案：A采用靜態(tài)分配：由于執(zhí)行前已獲得所需的全部資源，故不會出現(xiàn)占有資源又等待別的資源的現(xiàn)象（或不會出現(xiàn)循環(huán)等待的現(xiàn)象）。B采用按序分配：不會出

10、現(xiàn)循環(huán)等待的現(xiàn)象。C采用銀行家算法：因為在分配時，保證了系統(tǒng)處于安全狀態(tài)。6. 在單處理器系統(tǒng)中，如果用戶級線程與內(nèi)核級線程間是一對一的映射，那么，多線程程序比相同功能的單線程程序運行快，為什么？解答:問題的關(guān)鍵在于CPU是否要等待I/O操作。在內(nèi)核級多線程的進程中，當一個內(nèi)核級線程調(diào)用引起阻塞的系統(tǒng)調(diào)用時，其他內(nèi)核級線程可以繼續(xù)運行，在單處理器系統(tǒng)中，單線程進程調(diào)用此類系統(tǒng)調(diào)用時，該進程將被阻塞，但是，內(nèi)核級多線程的進程可以繼續(xù)執(zhí)行。7. 請說明Linux系統(tǒng)中的進程狀態(tài)中的不可中斷（uninterruptible）狀態(tài)的含義和用途。解答:與可中斷狀態(tài)類似，不可中斷狀態(tài)也是一種阻塞狀態(tài)，兩者

11、的區(qū)別是：在不可中斷狀態(tài)，進程直接等待硬件條件的發(fā)生，因而不處理任何信號。不可中斷狀態(tài)用于進程必須不受中斷地等待的場合，或者，預期事件會很快發(fā)生的場合。例如，當一個進程打開一個設備文件而相應的設備驅(qū)動程序開始探測相應的硬件設備時，進程進入不可中斷狀態(tài)，因為在探測完成之前驅(qū)動程序不能被中斷，否則，硬件設備很可能會被置于意想不到的狀態(tài)。8. 若從存取速度、存儲空間利用、易更新性的角度考慮文件系統(tǒng)的有效性，針對以下各種情形，什么樣的文件組織的有效性最好：（1）數(shù)據(jù)更新不頻繁，按隨機次序頻繁存?。唬?）數(shù)據(jù)頻繁更新，比較頻繁地存取整個文件；（3）數(shù)據(jù)頻繁更新，按隨機次序頻繁存取。解答:（1）索引文件（

12、2）索引順序文件（3）散列或索引文件9. 設一個層次式文件系統(tǒng)以空閑空間鏈表的方式管理空閑磁盤空間，請考慮：（1）假如指向空閑空間的指針丟失，系統(tǒng)能否重構(gòu)空閑空間鏈表？（2）試設計一個方案，確保單個內(nèi)存故障不會導致指針丟失。解答:（1）可以重構(gòu)。首先，建立一個位圖（bit map），用于表示磁盤中的每一個盤塊，初值置為全0；然后，從文件系統(tǒng)的根目錄（即"/"目錄）開始對整個文件系統(tǒng)進行遍歷，把每個文件占用的每個盤塊在位圖中對應的位置標記為1；遍歷結(jié)束后，位圖中0對應的塊便是空閑塊，可以為它們重新構(gòu)建鏈表。（2）在磁盤上一處或多處保存空閑空間鏈接指針的副本，指針更新時，同時更新相應副本，這樣，就算內(nèi)存和磁盤塊出現(xiàn)故障，也有辦法借助副本獲得有效的指針值。10. 設某系統(tǒng)中既有就緒進程也有就緒/掛起進程，且至少有一個就緒/掛起進程的優(yōu)先級比所有就緒進程都高，有兩種極端的調(diào)度策略：（1）為減少交換，總是選擇就緒進程運行；（2）總是選擇最高優(yōu)先級的進程運行，哪怕引起不必要的交換。請你給出一種既考慮優(yōu)先級