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

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

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

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

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

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

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

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

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

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

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

11、統(tǒng)為提高地址變換速度采取了什么措施。答：訪問(wèn)頁(yè)表得到內(nèi)存塊號(hào)，由內(nèi)存塊號(hào)和頁(yè)內(nèi)地址構(gòu)成要訪問(wèn)的物理地址，訪 問(wèn)物理地址得到所需的指令或數(shù)據(jù)。為了存取指令或數(shù)據(jù)需訪問(wèn)兩次內(nèi)存，為此，引入聯(lián)想寄存器(快表)來(lái)提高地 址變換速度。III. (9分)有如表 1 所示的進(jìn)程：5表 1進(jìn)程就緒時(shí)間處理時(shí)間P103P226P344P465P5821.畫(huà)一個(gè)圖來(lái)說(shuō)明它們的執(zhí)行過(guò)程，分別按以下算法:a. FCFSb. SPNc. RR （時(shí)間片長(zhǎng)度為 1 ）2計(jì)算各種算法下的平均周轉(zhuǎn)時(shí)間。答：FCFS：進(jìn)程就緒時(shí)刻結(jié)束時(shí)刻服務(wù)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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進(jìn)程就緒時(shí)刻結(jié)束時(shí)刻服務(wù)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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進(jìn)程就緒時(shí)刻結(jié)束時(shí)刻服務(wù)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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分）一個(gè)磁盤(pán)有200 個(gè)柱面，編號(hào)從 0 至 U 199，假設(shè)磁頭當(dāng)前位于柱面 53。 按 FIFO 順序請(qǐng)求的柱面號(hào)如下： 98, 183，37，122，14，124，65，67。為了滿 足磁盤(pán)請(qǐng)求隊(duì)列中的所有請(qǐng)求，請(qǐng)按以下要求完成圖示和計(jì)算。1） 分別按照 FCFS、SSTF 算法，畫(huà)出示意圖并計(jì)算磁頭移過(guò)的柱面數(shù)目。2） 假設(shè)當(dāng)前磁頭正朝柱面 0 移動(dòng)，畫(huà)出示意圖說(shuō)明 SCAN 算法，并計(jì)算磁頭移 過(guò)的柱面數(shù)目。3） 假設(shè)磁頭單向移動(dòng)方向?yàn)橹? 到柱面 199，畫(huà)出示意圖說(shuō)明 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ū)?yè)面的引用序列如下：1 , 2, 3, 4, 2, 1 , 5, 6, 2, 1 , 2, 3, 7, 6, 3, 2, 1 , 2, 3, 6如果為程序分配 4 個(gè)內(nèi)存塊，分別使用以下淘汰算法，計(jì)算各自的缺頁(yè)次數(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 次頁(yè)面 123421 156212

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

18、的課程中，你感到哪些課程能促進(jìn)對(duì)操作系統(tǒng)的學(xué)習(xí)？操作系統(tǒng)能 否幫助理解其他課程的內(nèi)容？VII. （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)程間每次傳輸信息的單位均小于等于緩沖區(qū)長(zhǎng) 度）。利用信號(hào)量機(jī)制寫(xiě)出滿足上述條件的并發(fā)程序?！痉治觥勘纠饕疾椴僮飨到y(tǒng)中信號(hào)量的應(yīng)用。3 個(gè)進(jìn)程 P、Q 和 R 之間的關(guān)系如圖 3.13 所示:頁(yè)面1引用2342 21562 2序列1234215621234215612342151134211 1237632123612376321236212376321236622376332255612276661缺頁(yè) + + + +11P彳 I. II. I. I I QI. I. I. I I R進(jìn)程 P P 和 Q Q 之間存在著同步關(guān)系，進(jìn)程 Q Q 和 R R 之間也存在著同步關(guān)系；