(完整word版)河海大學2005-2006學年第一學期操作系統(tǒng)期末試卷

1、12005-2006學年第一學期操作系統(tǒng)期末試卷（計算機科學與技術專業(yè) 2003 級）班級_ 學號_ 姓名_ 成績_I.填空.（30分，每空1分）1. 在系統(tǒng)中，沒有程序運行時，CPU 做什么？ _忙等_ （從中選擇一個答案： 暫停、忙等、等待中斷、休眠）。2. 引入多道程序技術帶來的主要好處是 提高了 CPU 利用率_ ;但如果多道程序數目太多，則會造成一種稱為 _抖動_ 現(xiàn)象的問題。3. 導致進程狀態(tài)從運行-就緒轉換的原因是_ 超時，進程的時間片到期_。4. 進程調度算法（FCFS, SPN, SRT, RR, FB）中對各種類型的進程（如 CPU 密集型或I/O 密集型進程）都能平等對待

2、的是 RR 時間片輪轉和_FB 多級 反饋隊列。5.（用十進制表示）考慮以下段表:段號段基址段長033012418762112111993498302請給出以下邏輯地址對應的物理地址，如果地址變換產生了缺段，請指明:a. 0, 99429330+99b. 2, 78189111+78c. 1, 265缺段211V2656. 在一個物理空間為 232字節(jié)的純分頁系統(tǒng)中，如果虛擬地址空間大小為212頁,頁的大小為 512 字節(jié)，那么：a. 一個虛擬地址有多少位？21b. 個頁框有多少字節(jié)？512c. 在一個物理地址中用多少位來指明對應的頁框？23d. 頁表的長度為多少（即頁表中表項數目為多少）？2

3、12 （4096）7. 目前常用的文件目錄結構是樹型（多級） 目錄結構。28.適合磁盤的外存分配模式是：連續(xù)、鏈接、索引。9.進程遷移是指一將一個進程的狀態(tài)，從一臺機器轉移到另一臺機器上，從而使 該進程能在目標機上執(zhí)行.10. 分布式系統(tǒng)中的關鍵機制是 進程間通信。中間件提供了標準的編程接口和協(xié)議，掩藏了不同網絡協(xié)議和操作系統(tǒng)之間的復雜細節(jié)和差異，其實現(xiàn)基于消息傳遞和遠程過程調用兩種機制。11. 操作系統(tǒng)安全里說的身份鑒別機制的作用是_識別請求存取的用戶，并判斷它的合法性。12. 根據美國國防部的劃分，計算機系統(tǒng)的安全從低到高分為哪4 等？ D，C，B, A （按從低到高的順序）。13. 正誤

4、判斷題：a.在 SPOOLing 系統(tǒng)中，對用戶進程的設備申請，系統(tǒng)將物理字符設備按 時間片方式分配給用戶進程使用。X。b.SPOOLing 系統(tǒng)是虛擬存儲技術的體現(xiàn)X 。14. 判斷題：系統(tǒng)調用與用戶程序之間的調用不同之處是處理機狀態(tài)的改變。15. 虛擬設備是指通過某種虛擬計數，將一臺物理設備變成若干臺邏輯設備。邏輯設備實際上并不存在，只是給用戶的一種感覺。在操作系統(tǒng)中引入虛擬設備的原因是_為了克服獨占設備所具有的速度較慢、資源利用率較低的缺點，以提高 設備利用率。16. 已知某文件采用串聯(lián)結構，它由 10 個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊大小相等，都為 1024 字節(jié)，并依次存放

5、在 10, 61, 32, 75, 87, 98, 46, 37, 33, 11 號磁盤塊上。若要存取文件的第7654 邏輯字節(jié)處的信息，要訪問的磁盤塊塊號為_ 377654/1024=7 _。17.在采用分頁式存儲管理的系統(tǒng)中，某作業(yè)對應的頁表如下:頁號塊號0314293245已知頁大小為 4096 字節(jié)，則邏輯地址 8862 對應的物理地址為37534 - （十進制表示）19.對于硬盤上存放的信息， 物3理上讀寫的最小單位是一個物理塊_ 。（選擇以下一個填空：二進位、字節(jié)、物理塊、邏輯記錄）20. _ 理中斷 _ 是操作系統(tǒng)必須提供的功能。（選擇以下一個填空:GUI；為進程提供系統(tǒng)調用命令

6、；處理中斷；編譯源程序）21. 操作系統(tǒng)具備處理同時性活動的能力，其最重要的硬件支持是_中斷系統(tǒng)II.簡答（共 32 分，每題 4 分）.1假設系統(tǒng)由相同類型的 m 個資源組成，有 n 個進程，每個進程至少請求一個 資源。證明：當 n 個進程最多需要的資源數之和小于 m+n 時，該系統(tǒng)無死鎖。 證：假設第 i 個進程的最大資源需求量為 Ri，（ 1 = i = n ）；則對于最差的情況而言， 每個進程都必須得到其所需的全部資源才能完成運行。在每個進程都得到了部分資源，即對任一第i 個進程而言，已經擁有Ri-1個資源，還差一個資源即可滿足其最大要求。此時，如果系統(tǒng)中還余一資源，即 如有E（ Ri

7、-1） + 1 = m則系統(tǒng)不會產生死鎖刀 Ri - n + 1 = m刀 Ri = m + n - 1 刀 Ri m + n因此，當 n 個進程最多需要的資源數之和小于m+n 時，該系統(tǒng)無死鎖。2.使用分段及分頁地址轉換的一個問題是要使用I/O。假設用戶希望將某些數據由輸入設備讀入內存，為了保證數據傳輸過程中的有效性，通常將要放入數據處 的實際內存地址提供給I/O 設備，由于將實際地址傳送給I/O,因此，在非?？焖俚臄祿鬏斶^程中不再需要進行費時的地址轉換。這一方法所帶來的安全問題是什么？答：正在等待 I/O 完成的進程，可能滿足置換算法的要求，其對應I/O 的進程頁面被換出。從而導致輸入的

8、數據不在所需進程空間內，且對于換入進程而言，I/O破壞了新?lián)Q入進程空間里的數據。3.二級目錄和多級目錄的好處是什么？ 答：檢索速度快、允許文件重名、便于共享。4.為什么打印機的輸出文件在打印前通常都假脫機輸出到磁盤上？答：提高 CPU 和打印機的并行工作程序；加快進程打印輸出速度，縮短進程周 轉時間，提高系統(tǒng)的吞吐量。45.死鎖的產生有 4 個必要條件：互斥條件、請求與保持條件(逐步請求條件)、不剝奪條件、環(huán)路等待條件。死鎖的預防就是破壞這 4 個必要條件中的一個或幾個， 來達到防止產生死鎖的目的。請簡要說明死鎖預防的各種策略及其優(yōu)劣。答：(1)破壞“互斥條件”。由于資源特性所限，一般情況下這

9、個條件是無法摒棄的，但對于某些互斥共享的設備，如打印機，則可以通過Spooling 技術來摒棄互斥條件。(2)破壞“請求與保持條件”。可以采用資源靜態(tài)分配法，即對資源采用一 次性分配策略，但會導致資源利用率的下降。(3)破壞“不剝奪條件”?？梢圆捎脛儕Z策略，但涉及到對資源現(xiàn)場的恢復 問題，需付出高昂代價。因此，一般只適用于處理機和存儲器資源，不適宜對其 他資源使用該方法。(4)破壞“環(huán)路等待條件”?？梢圆捎觅Y源順序分配法，但實際情況是：資源編號增加的順序與實際使用資源的順序不一致，從而可能導致提早分配資源而導致資源長期不用的現(xiàn)象，使資源利用率下降。6. 為何段式管理有段內越界，而頁式管理無頁內

10、越界問題？答：頁的劃分是由操作系統(tǒng)完成的，每個地址由系統(tǒng)自動劃分為頁號和頁內地址兩部分，因此無頁內越界問題。而段的劃分是由編譯程序完成的，邏輯地址由段 號和段內偏移量組成，因此，存在段內越界問題。7什么是進程？操作系統(tǒng)通過什么來感知進程的存在？答：進程的概念，一般把它定義為可并發(fā)執(zhí)行的程序在一個數據集合上的運行過 程。操作系統(tǒng)需要通過一定的數據結構來描述進程的情況和控制進程的運行，這個數據結構就是進程控制塊( (PCB，Process Control Block)。PCB 是進程存在的 惟一標志，操作系統(tǒng)通過檢測PCB 的存在來感知進程的存在。8.簡述分頁式存儲管理方案中地址變換過程，并說明系

11、統(tǒng)為提高地址變換速度采取了什么措施。答：訪問頁表得到內存塊號，由內存塊號和頁內地址構成要訪問的物理地址，訪 問物理地址得到所需的指令或數據。為了存取指令或數據需訪問兩次內存，為此，引入聯(lián)想寄存器(快表)來提高地 址變換速度。III. (9分)有如表 1 所示的進程：5表 1進程就緒時間處理時間P103P226P344P465P5821.畫一個圖來說明它們的執(zhí)行過程，分別按以下算法:a. FCFSb. SPNc. RR （時間片長度為 1 ）2計算各種算法下的平均周轉時間。答：FCFS：進程就緒時刻結束時刻服務時間周轉時間帶權周轉時間P10333-0 = 33/3 = 1.0P22969-2 =

12、 77/6 = 1.17P3413413-4 = 99/4 = 2.25P4618518-6 = 1212/5 = 2.4P5820220-8 = 1212/2 = 6.0平均8.62.56SPN：602468101214161820P1cP2tfP3P4I-P5進程就緒時刻結束時刻服務時間周轉時間帶權周轉時間P10333-0 = 33/3 = 1.0P22969-2 = 77/6 = 1.17P3415415-4 = 1111/4 = 2.75P4620520-6 = 1414/5 = 2.80P5811211-8 = 33/2 = 1.5平均7.601.84RR :0 246 810 12

13、14161820i111j:iI1聲i!P1匚 iiII；：!：J1b1rias:P2I1L-ai11H|B1FaI-11Il1|11111S：fiii-aiP35:!:11:iE-I1_fc i h 1 a I t 5_ ! t ; 1P41!B1:16 -iFii11;:ij i:；tiI-S11：I!P5-1；j 3 ti1 ii !- ! :1 i I1；i 1進程就緒時刻結束時刻服務時間周轉時間帶權周轉時間P10434-0 = 44/3 = 1.33P2218618-2 = 1616/6 = 2.67P3417417-4 = 1313/4 =3.25P4620520-6 = 1414

14、/5 = 2.80710.82.71IV. （7分）一個磁盤有200 個柱面，編號從 0 至 U 199，假設磁頭當前位于柱面 53。 按 FIFO 順序請求的柱面號如下： 98, 183，37，122，14，124，65，67。為了滿 足磁盤請求隊列中的所有請求，請按以下要求完成圖示和計算。1） 分別按照 FCFS、SSTF 算法，畫出示意圖并計算磁頭移過的柱面數目。2） 假設當前磁頭正朝柱面 0 移動，畫出示意圖說明 SCAN 算法，并計算磁頭移 過的柱面數目。3） 假設磁頭單向移動方向為柱面0 到柱面 199，畫出示意圖說明 CSCAN 算法。 解：FCFS :(98-53)+(183-

15、98)+(183-37)+(122-37)+(122-14)+(124-14)+(124-65)+(67-65) = 600SSTF :(65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124-122)+(183-124) = 236SCAN :P5815215-8 = 77/2 = 3.50平均143753656798122 124183014375365 6798122 124183(53-37)+(37-14)+(14-0)+(65-0)+(67-65)+(98-67) + (122-98) + (124-122)+(183-124) =

16、 2361838CSCAN :V. （6分）程序對頁面的引用序列如下：1 , 2, 3, 4, 2, 1 , 5, 6, 2, 1 , 2, 3, 7, 6, 3, 2, 1 , 2, 3, 6如果為程序分配 4 個內存塊，分別使用以下淘汰算法，計算各自的缺頁次數：a. FIFO 算法b. LRU 算法c. OPT 算法解：014375365 6798122 124(53-37)+(37-14)+(14-0)+(65-0)+(67-65)+(98-67) + (122-98) + (124-122)+(183-124) = 2361839FIFO : 14 次頁面 123421 156212

17、23763 3212 236 6引用10序列12344456211376621133123334562213776221212223456621337662211123455621137766缺頁+LRU : 10 次OPT: 8 次頁面12342 2156212376321236引用序列12344456666666666666123333333333333333312222222222222222211111111177771111缺頁+VI.（6分）1）如何理解“現(xiàn)代操作系統(tǒng)是以多道程序設計為基礎的操作系統(tǒng)”？你認為是 否在所有的操作系統(tǒng)中都有必要引入多道程序設計技術？為什么？2）在所學過

18、的課程中，你感到哪些課程能促進對操作系統(tǒng)的學習？操作系統(tǒng)能 否幫助理解其他課程的內容？VII. （10分）假設有三個并發(fā)進程 P，Q, R。其中 P 負責從輸入設備上讀入信息 并傳送給 Q；Q 將信息加工后傳送給 R； R 則負責將信息打印輸出。進程P、Q共享一個由 m 個緩沖區(qū)組成的緩沖池；進程 Q、R 共享另一個由 n 個緩沖區(qū)組成的緩沖池（假設緩沖區(qū)足夠大，進程間每次傳輸信息的單位均小于等于緩沖區(qū)長 度）。利用信號量機制寫出滿足上述條件的并發(fā)程序?！痉治觥勘纠饕疾椴僮飨到y(tǒng)中信號量的應用。3 個進程 P、Q 和 R 之間的關系如圖 3.13 所示:頁面1引用2342 21562 2序列1234215621234215612342151134211 1237632123612376321236212376321236622376332255612276661缺頁 + + + +11P彳 I. II. I. I I QI. I. I. I I R進程 P P 和 Q Q 之間存在著同步關系，進程 Q Q 和 R R 之間也存在著同步關系；