試題 科大

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

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

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

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

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

6、區(qū)長(zhǎng)度)。寫出滿足上述條件的并發(fā)程序。六． （10 分）設(shè)系統(tǒng)中僅有一類數(shù)量為 M 的獨(dú)占型資源，系統(tǒng)中 N 個(gè)進(jìn)程競(jìng)爭(zhēng)該類資源，其中各進(jìn)程對(duì)該類資源的最大需求量為 W。當(dāng) M、N、W 分別取下列值時(shí)，試判斷哪些情況會(huì)發(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國(guó)防科技大學(xué)研究生院 1996 年碩士生入學(xué)考試編譯原理和操作系統(tǒng)試題操作

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

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

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

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

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