操作系統(tǒng)試卷2013一考答案

1、裝訂線（計算機操作系統(tǒng)試題2013 /2014學(xué)年 第 一學(xué)期）二三四五六七十總分一概念 （每小題 2 分，共 10 分）：1 多道程序設(shè)計技術(shù)多道程序設(shè)計技術(shù)是指允許在內(nèi)存中裝入多道程序，使它們并發(fā)運行，以提高資源利用率和系統(tǒng)吞吐量的程序設(shè)計技術(shù)。2 死鎖多個進程在運行過程中因競爭資源而造成的一種僵局，若無外力推動，它們都將無法再繼續(xù)向前推進，此系統(tǒng)狀態(tài)稱為死鎖。3.聯(lián)想寄存器在分頁管理中，為提高地址變換速度，在地址變換機構(gòu)中，增設(shè)一個具有并行查詢能力的特殊高速緩沖寄存器，稱為聯(lián)想寄存器或稱為“快表”，用以存放當(dāng)前的那些頁表表項。4.設(shè)備獨立性應(yīng)用程序獨立于具體使用的物理設(shè)備。即，在應(yīng)用程序

2、中，使用邏輯設(shè)備名稱來請求使用某類設(shè)備。5.文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是從用戶觀點出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及結(jié)構(gòu)，它獨立于文件的物理特性。二填空 （每空 1 分，共 10 分）1. 操作系統(tǒng)是計算機系統(tǒng)最基本和最重要的系統(tǒng) ，是一組控制和管理計算 硬件和資源，合理地對各類作業(yè)進行調(diào)度，以及方便用戶使用的程序集合。2.進程控制塊PCB 是一個數(shù)據(jù)結(jié)構(gòu)，用來記錄相應(yīng)程序在并發(fā)系統(tǒng)內(nèi)執(zhí)行時的動態(tài)信息, 是系統(tǒng)“感知”進程存在的唯一標(biāo)志。3 利用二進制的一位來表示磁盤中一個盤塊的使用情況，由所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。4.將邏輯地址轉(zhuǎn)換為物理地址的調(diào)整過程

3、是在指令執(zhí)行時進行的稱為 動態(tài)重定位.5.在采用請求分頁管理的系統(tǒng)中，頁面的調(diào)入通常是由 缺頁中斷處理完成的。采用 SPOOLING技術(shù)，可以把文件的物理組織有順序 、獨 占設(shè)備變成共享設(shè)備。和索引。8. 若資源信號量S 的初值為 8，當(dāng)前值為-12，則表示在該信號量的阻塞隊列中有12個等待進程。三簡答題（每小題分，共 30 分）1. 設(shè)計現(xiàn)代操作系統(tǒng)的主要目標(biāo)是什么？方便性（方便用戶）有效性（軟硬件資源管理）(3 分)可擴充性(1 分)開放性(1 分)2.文件的物理結(jié)構(gòu)有哪幾種？為何說鏈?zhǔn)轿募贿m合于隨機存?。看穑喉樞蛭募Y(jié)構(gòu)，文件結(jié)構(gòu)，索引文件結(jié)構(gòu)。（2分）文件的文件物理塊不連續(xù)，每個物理

4、塊中設(shè)置一個指針，指向下一個物理塊的地址，這樣，所有的物理塊被起來，形成物理文件。對鏈?zhǔn)轿募诖嫒r必須拉鏈，即必須從鏈?zhǔn)撞槠?，順著鏈指針找到要存取的物理快，因此，不適合隨機存取。（3分）3.目前常用的磁盤調(diào)度算法有哪幾種？每種算法優(yōu)先考慮的問題是什么？答： 先來先服務(wù)、最短尋道時間優(yōu)先和掃描算法。（2 分）先來先服務(wù)根據(jù)進程請求磁盤的先后順序進行調(diào)度，優(yōu)先考慮公平。（1 分）最短尋道時間優(yōu)先，優(yōu)先考慮每次的尋道時間最短。（1 分）掃描算法優(yōu)先考慮避免進程“饑餓”現(xiàn)象。（1 分）班級學(xué)號裝訂線4 何謂死鎖定理？系統(tǒng)S 狀態(tài)的資源分配圖如下，判斷 S 狀態(tài)是否為死鎖狀態(tài)？答： S 狀態(tài)為死鎖狀態(tài)

5、的充分條件是：當(dāng)且僅當(dāng) S 狀態(tài)的資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。（3 分）S 狀態(tài)可完全簡化，S 狀態(tài)不死鎖（2 分）Dijkstra 1965銀行家算法是解決死鎖問題的一種策略在實施資源分配之前，先計算該次分配后產(chǎn)生的系統(tǒng)狀態(tài)是否安全，既是否存在一種進程序列，使得所有的進程都能順利地執(zhí)行結(jié)束若安全則分配，否則分配（3 分）該算法雖有很好的理論意義，但在實際系統(tǒng)中很難實現(xiàn)，因為算法所假設(shè)的條件，如進程預(yù)知申請資源的最大數(shù)目，系統(tǒng)中進程數(shù)目固定等，在實際系統(tǒng)中并不成立所以，由不成立的前提導(dǎo)出的結(jié)果很難說是正確的（2 分）6 實現(xiàn)虛擬器的主要技術(shù)是什么？虛擬器的容量由什么決定

6、？答：部分裝入及對換。（3 分）虛擬器空間就是 CPU 邏輯地址給出的空間，實際上，是內(nèi)存和外存容量之和。5 Dijkstra 1965銀行家算法的主要思想是什么？它能夠用來解決實際中的死塊 2333344445鎖問題嗎？為什么？塊 322223333答:塊 41111222四綜合題（每小題 10 分，共 50 分）1 （10 分）在請求分頁管理系統(tǒng)中，采用 FIFO 頁面置換算法時，作業(yè)頁面為：4，3，2，1，4，3，5，4，3，2，1，5， 若分給該作業(yè)的物理塊數(shù)為 3問題：.計算過程中所發(fā)生的缺頁中斷次數(shù)及缺頁率。(3 分)過程中所發(fā)生的缺頁中.如果分配給作業(yè)的物理塊數(shù)為 4 塊, 計算

7、斷次數(shù)及缺頁率。(3 分).比較所得結(jié)果并給予解釋。(4 分)答：.頁面塊 1塊 2塊 3缺頁4，3，2，1，4，3，5，4，3，2，1，55522314441133缺 缺 缺 缺 缺 缺 缺缺 缺(3 分).分 3 塊缺頁 9 次，缺頁率 9/12*100%=75%頁面4，3，2，1，4，3，5，4，3，2，1，5塊缺頁缺 缺 缺 缺缺 缺 缺 缺 缺 缺分 4 塊缺頁 10 次，缺頁率 10/12*100%=83.3%(3 分).分 4 塊本應(yīng)比分 3 塊降低缺頁率。但采用 FIFO 算法,多分一塊時出現(xiàn)了剛被淘汰出去的頁面過后 馬上又要 它,因而又要將其調(diào)入，調(diào)入又再次淘汰,再 再調(diào)入，

8、反而比分得 3 塊時還多一次缺頁中斷。上述表明，F(xiàn)IFO 算法有一種異?，F(xiàn)象，當(dāng)分配給作業(yè)的 塊增加時，缺頁次數(shù)并沒有減少，反而增加了。其根本原因是算法沒有考慮頁面走可能性之間沒向的動態(tài)特性。既先進入內(nèi)存的頁面與該頁面今后被有必然聯(lián)系。(4 分)2 （10 分）系統(tǒng)中有 5 個進程共享 4 類資源 A,B,C,D。在銀行家算法中，若出現(xiàn)下述資源分配情況：班級學(xué)號P1P2Fig: S 狀態(tài)的資源分配圖ProcessAllocationNeedAvailable問：。該狀態(tài)是否安全？（5 分）若進程 P2 提出請求 Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？（5 分）答：。存在安

9、全序列P0,P3,P4,P1,P2(或P0,P3,P1,P2,P4,P0,P3,P1,P4,P2),該狀態(tài)安全。（5 分）預(yù)分配 P2 Allocation2,5,7,6,Need1,1,3,4系統(tǒng)Available0,4,0,0此時系統(tǒng)可用資源不能滿足任何進程的資源要求，故不存在安全序列，因此系統(tǒng)不能將資源分配給它。（5 分）3 設(shè)有一個發(fā)送者進程和一個接收者進程，其流程圖如下圖所示，S 是用于實現(xiàn)進程同步的信號量，表示接收者進程可接收消息的數(shù)目；Mutex 是用于實現(xiàn)進程互斥的信號量。試問流程圖中的 A,B,C,D 框中應(yīng)填寫什么？假定消息鏈長度沒有限制，S和Mutex 的初植應(yīng)為多少？A

10、BCDABCDABCDC: wait(s)(2 分)P0003200121622D: wait(Mutex)(2 分)P110001750P213542356S初值為 0(1 分)P303320652Mutex初值為 1(1 分)P400140656發(fā)送者進程接收者進程答:A: wait(Mutex)(2 分)B: signal(Mutex)(2 分)4 （10 分）四個作業(yè) J1, J2, J3, J4 , 它們的到達時間和計算時間如下：作 業(yè)到達時刻/時計算時間/小時開始時刻/時結(jié)束時刻/時周轉(zhuǎn)時間/小時J18.01J28.50.25J39.00.1J49.50.4若這四個作業(yè)在一臺處理器

11、上按單道方式運行，采用響應(yīng)比高者優(yōu)先調(diào)度算法，試寫出各作業(yè)的執(zhí)行順序、給出作業(yè)的周轉(zhuǎn)時間及平均周轉(zhuǎn)時間。注:表中時間是十進制表示.如8.5 是 8 點半,不是 8 點 50 分答:作 業(yè)到達時刻/時計算時間/小時開始時刻/時結(jié)束時刻/時周轉(zhuǎn)時間/小時J18.01.08.09.01.0J28.50.259.09.250.75J39.00.19.259.350.35J49.50.49.59.90.49.00 時刻 J1 運行完畢.J2 響應(yīng)比=1+(9.0-8.5)/0.25=3J3 響應(yīng)比=1+(9.0-9.0)/0.1=1J4 未到J2 響應(yīng)比高,調(diào)度J2 運行(3 分)9.25 時刻系統(tǒng)中只

12、有 J3,調(diào)度 J3 運行 (2 分)9.35 時刻cpu 空閑95 時刻 J4 到達，此時系統(tǒng)中只有作業(yè)J4,調(diào)度其運行.(1 分)調(diào)度順序為: J1J2J3J4(2 分)平均周轉(zhuǎn)時間=(1.0+0.75+0.35+0.4)/4=0.625 小時 (2 分)班級學(xué)號申請緩沖區(qū)將消息寫入緩沖區(qū)A將緩沖區(qū)掛在消息鏈尾BSignal(S )CD從消息鏈?zhǔn)兹∫粋€緩沖區(qū)Signal(Mutex)從緩沖區(qū)中取出信息緩沖區(qū)裝訂線5 (10 分) 某操作系統(tǒng)的內(nèi)存管理系統(tǒng)是請求分頁管理系統(tǒng)，邏輯地址長度為16 位，頁面大小為 1K，采用固定分配局部置換策略。若某進程的邏輯地址空間為6 頁，操作系統(tǒng)為該進程分

13、配的物理塊（頁框）為 4，在某時刻該進程的頁表如下表所示：頁號塊號自上次以來未被的時間狀態(tài)位062811399614050注：狀態(tài)位為 1 表示該頁在內(nèi)存，為 0 表示不在內(nèi)存當(dāng)該進程繼續(xù)執(zhí)行，CPU 給出要內(nèi)存的邏輯地址為 17C9H 時。請計算并回答下列問題：. 該邏輯地址對應(yīng)的頁號及頁內(nèi)偏移量分別是多少？（3 分）. 若采用最近最久未使用（LRU）頁面置換算法，請給出地址變換過程。（5 分）. 該邏輯地址對應(yīng)的物理地址是多少？（2 分）答:. 頁面大小為 1K,所以邏輯地址低 10 位為頁內(nèi)地址,既偏移量.16 位邏輯地址的高六位為頁號.邏輯地址 17C9H 按 2 進制展開，為：0001 0111 1100 1001； 高六位為 5，故：頁號為 5，頁內(nèi)偏移量為：