試題 科大

1、國防科技大學(xué)研究生院 2001 年碩士生入學(xué)考試操作系統(tǒng)試題考生注意：1．答案必須寫在我校統(tǒng)一配發(fā)的專用答題紙上2．統(tǒng)考生做 一、二、三、四、五； 3．單獨考生做一、二、三、六、七；一． （58 分）回答如下問題1． （6 分）假定有一個支持實時、分時和批處理的操作系統(tǒng)，對該系統(tǒng)應(yīng)如何設(shè)計進(jìn)程調(diào)度策略？2． （5 分）什么叫線程？為什么要引進(jìn)線程？3． （6 分）某計算機(jī)系統(tǒng)設(shè)計成只有一級中斷(該級中有多個中斷)的中斷系統(tǒng)，簡述當(dāng)中斷發(fā)

2、生時，是如何進(jìn)入該中斷處理程序的？4． （5 分）在文件系統(tǒng)中為什么要引進(jìn)“Open”系統(tǒng)調(diào)用？操作系統(tǒng)是如何處理的？5．(5 分)假定存儲器空閑塊有如下結(jié)構(gòu)：請你構(gòu)造一串內(nèi)存請求序列，對該請求序列首次滿足分配算法能滿足，而最佳滿足分配法則不能。6．(6 分)為什么要在設(shè)備管理中引入緩沖技術(shù)？操作系統(tǒng)如何實現(xiàn)緩沖技術(shù)？7．(6 分)用什么辦法可以破壞死鎖的循環(huán)等待條件？為什么？8．(6 分)進(jìn)程的狀態(tài)主要有哪些？當(dāng)發(fā)生狀態(tài)轉(zhuǎn)換時，操作系

3、統(tǒng)完成哪些工作？9．(6 分)在文件系統(tǒng)中，為什么要設(shè)立“當(dāng)前目錄”？操作系統(tǒng)如何實現(xiàn)改變“當(dāng)前目錄”？10．(7 分)舉例說明 P、V 操作為什么要用原語實現(xiàn)？操作系統(tǒng)如何實現(xiàn)這種原語操作？二．(12 分)設(shè)有四個進(jìn)程 P1，P2，P3，P4，它們到達(dá)就緒隊列的時刻，運(yùn)行時間及優(yōu)先級如下表所示：問：(1)若采用可剝奪的優(yōu)先級調(diào)度算法，給出各進(jìn)程的調(diào)度次序以及每個進(jìn)程的等待時間。(2)若采用時間片輪轉(zhuǎn)調(diào)度算法，且時間片為 2 個基本時間

4、單位，試給出各進(jìn)程的調(diào)度次序及平均周圍時間。三．(8 分)假設(shè)系統(tǒng)由相同類型的 m 個資源組成，有 n 個進(jìn)程，每個進(jìn)程至少請求一個資源。證明：當(dāng) n 個進(jìn)程最多需要的資源數(shù)之和小于 m n 時，該系統(tǒng)無死鎖。四．(12 分)在頁式虛存系統(tǒng)中，一程序的頁面走向(訪問串)為 1，2，3，4，1，2，5，1，2，3，4，5 ，設(shè)分配給該程序的駐留集為 m，試分別計算 m=3 和 m=4 時，F(xiàn)IFO 和 LRU 兩種算法的頁故障次數(shù)。結(jié)果說

5、明了什么？五．(10 分)對于下述優(yōu)先圖，用 Parbegin/Parend 語句及操作系統(tǒng)提供的同步/互斥工具，寫出并發(fā)程序。 六．(10 分)假設(shè)有三個并發(fā)進(jìn)程 P，Q，R。其中 P 負(fù)責(zé)從輸入設(shè)備上讀入信息并傳送給Q；Q 將信息加工后傳送給 R；R 則負(fù)責(zé)將信息打印輸出。進(jìn)程 P、Q 共享一個由 m 個緩沖區(qū)組成的緩沖池；進(jìn)程 Q、R 共享另一個由 n 個緩沖區(qū)組成的緩沖池(假設(shè)緩沖區(qū)足夠大，進(jìn)程間每次傳輸信息的單位均小于等于緩沖

6、區(qū)長度)。寫出滿足上述條件的并發(fā)程序。六． （10 分）設(shè)系統(tǒng)中僅有一類數(shù)量為 M 的獨占型資源，系統(tǒng)中 N 個進(jìn)程競爭該類資源，其中各進(jìn)程對該類資源的最大需求量為 W。當(dāng) M、N、W 分別取下列值時，試判斷哪些情況會發(fā)生死鎖？為什么？① M=2，N=2，W=1 ②M=3，N=2，W=2 ③M=3，N=2，W=3 ④M=5，N=3，W=2 ⑤M=6，N=3，W=3國防科技大學(xué)研究生院 1996 年碩士生入學(xué)考試編譯原理和操作系統(tǒng)試題操作

7、系統(tǒng)部分參考答案（非標(biāo)準(zhǔn)答案）一．選擇題（每題 3 分，共 15 分）1． （① ② ④ ⑥）2． （① ③ ④ ⑤）3.（③）4． （① ② ③ ④）5.(① ② ⑦)二、當(dāng)駐留集為 3 時，采用 FIFO 替換算法，頁面故障數(shù)為 9 次；采用 LRU 替換算法時，頁面故障數(shù)為 10 次。當(dāng)駐留集為 4 時，采用 FIFO 替換算法，頁面故障數(shù)為 10 次；采用 LRU 替換算法時，頁面故障數(shù)為 8 次。結(jié)果表明，F(xiàn)IFO 替換算法的

8、故障數(shù)不隨駐留集增大而減少；而 LRU 算法的故障數(shù)隨駐留集增大而減少。三．把記錄文件的目錄分成主文件目錄和由其主管的若干個子目錄，各子目錄的位置由主目錄中的一項指出。應(yīng)用中常設(shè)一個主文件目錄，而為系統(tǒng)中每一個用戶設(shè)立一張主文件目錄 MFD，每個用戶的所有文件均設(shè)立一個用戶文件目錄 UFD，作為 MFD 中的一項。用以描述 UFD 的文件名和物理位置，即 UFD 是用戶全部文件的文件控制塊的全體。在二級文件目錄中，欲共享文件需給出一個文

9、件的全路徑名。由系統(tǒng)從根目錄開始檢索；或者用戶將其當(dāng)前目錄指向另一用戶的子目錄上，以實現(xiàn)共享訪問。四．采用 FCFS 調(diào)度算法的被調(diào)度順序為 1à2à3à4à5平均周轉(zhuǎn)時間為 T ＝（T1 T2 T3 T4 T5）/ 5 = (2 2.95 3.5 2 2) / 5 =2.49 (小時 )采用 SJF 調(diào)度算法的被調(diào)度順序為 1à3à5à4à2平均周轉(zhuǎn)時間為

10、 T=T1 T2 T3 T4 T5）/ 5 = (2 2.5 0.5 1.25 4.45 ) / 5 =2.14（小時）五．定義如下公共信號量：mutex0 ~ mutex3 : 分別用于控制互斥訪問 M0 ~ M 3，初值為 1。full0 ~ full3 : 分別用于控制同步訪問 M0 ~ M3 ,其中 full0 初值為 3，full1 ~ full3 初值為 0，表示信箱中消息條數(shù)。 empty0 ~ empty3 : 分別用于

11、同步控制對 M0 ~ M3 的訪問。Empty0 初值為 0，empty2~ empty3 初值為 2，empty1 初值為 3，分別用于表示信箱中空格子個數(shù)。另用 send ( Mi , message )表示將消息送到（Mi mod 4）號信箱中；而用 receive ( Mi，message )表示接收已存在于( Mi mod 4 )中的消息。則使用信號量實現(xiàn)進(jìn)程 Pi (i = 0 , 1 ,2 ,3 )同步及互斥的流程如下：m