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

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

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

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

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

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

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

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

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

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

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

11、統(tǒng)為提高地址變換速度采取了什么措施。答：訪問頁表得到內(nèi)存塊號，由內(nèi)存塊號和頁內(nèi)地址構(gòu)成要訪問的物理地址，訪 問物理地址得到所需的指令或數(shù)據(jù)。為了存取指令或數(shù)據(jù)需訪問兩次內(nèi)存，為此，引入聯(lián)想寄存器(快表)來提高地 址變換速度。III. (9分)有如表 1 所示的進程：5表 1進程就緒時間處理時間P103P226P344P465P5821.畫一個圖來說明它們的執(zhí)行過程，分別按以下算法:a. FCFSb. SPNc. RR （時間片長度為 1 ）2計算各種算法下的平均周轉(zhuǎn)時間。答：FCFS：進程就緒時刻結(jié)束時刻服務(wù)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間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進程就緒時刻結(jié)束時刻服務(wù)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間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進程就緒時刻結(jié)束時刻服務(wù)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間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，假設(shè)磁頭當(dāng)前位于柱面 53。 按 FIFO 順序請求的柱面號如下： 98, 183，37，122，14，124，65，67。為了滿 足磁盤請求隊列中的所有請求，請按以下要求完成圖示和計算。1） 分別按照 FCFS、SSTF 算法，畫出示意圖并計算磁頭移過的柱面數(shù)目。2） 假設(shè)當(dāng)前磁頭正朝柱面 0 移動，畫出示意圖說明 SCAN 算法，并計算磁頭移 過的柱面數(shù)目。3） 假設(shè)磁頭單向移動方向為柱面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分）程序?qū)撁娴囊眯蛄腥缦拢? , 2, 3, 4, 2, 1 , 5, 6, 2, 1 , 2, 3, 7, 6, 3, 2, 1 , 2, 3, 6如果為程序分配 4 個內(nèi)存塊，分別使用以下淘汰算法，計算各自的缺頁次數(shù)：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)是以多道程序設(shè)計為基礎(chǔ)的操作系統(tǒng)”？你認(rèn)為是 否在所有的操作系統(tǒng)中都有必要引入多道程序設(shè)計技術(shù)？為什么？2）在所學(xué)過

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