2008年秋季操作系統(tǒng)答案及評分標(biāo)準(zhǔn)a.doc

操作系統(tǒng)（A卷）答案及評分標(biāo)準(zhǔn)一、術(shù)語解釋（共20 分 每題2分）進(jìn)程；進(jìn)程是程序在一個數(shù)據(jù)集合上運行的過程， 它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位;(2分)中斷；CPU暫停當(dāng)前程序的執(zhí)行，轉(zhuǎn)去處理計算機內(nèi)部或外部發(fā)生的突發(fā)事件，完成突發(fā)事件處理后回到原來程序執(zhí)行的過程；(2分)重定位；從程序的邏輯地址映射到物理地址的過程；(2分)頁面抖動；剛調(diào)進(jìn)內(nèi)存的頁面不久又被調(diào)出，而調(diào)出后不久又被調(diào)入，CPU大量的時間花費的頁面調(diào)入調(diào)出的現(xiàn)象；(2分)文件的物理組織；文件在存儲設(shè)備上的組織結(jié)構(gòu)；(2分)分時；將CPU的運行時間劃分成若干個時間段（稱為時間片），循環(huán)輪流分配給各個程序（用戶）使用; (2分)死鎖；在一個進(jìn)程集合中的每個進(jìn)程， 都在等待僅由該集合中的另一進(jìn)程才能引發(fā)的事件， 而無限期地僵持下去的局面; (2分)吞吐量；單位時間內(nèi)完成的作業(yè)數(shù); (2分)進(jìn)程同步；一個進(jìn)程執(zhí)行到某一點后要等到另一進(jìn)程執(zhí)行到某點才能繼續(xù)往下執(zhí)行的一種進(jìn)程間關(guān)系；(2分)虛擬存儲器；只進(jìn)程分配部分所需內(nèi)存，剩下內(nèi)存需求等到進(jìn)程真正需要訪問這些存儲器時才被調(diào)入，但在用戶看來卻分配到了所有所需內(nèi)存，這種內(nèi)存管理方式成為虛擬存取器。(2分)二、簡答題（共30分 每題5分）1. 處理機的工作狀態(tài)主要有哪兩種？ 為什么要設(shè)置這兩種狀態(tài)？處理器有用戶態(tài)和和心態(tài)等2中工作狀態(tài)， 設(shè)置2種工作狀態(tài)的原因是為了對操作系統(tǒng)內(nèi)核進(jìn)行保護(hù)。2. 什么時候會發(fā)生缺頁？ 說明缺頁出現(xiàn)時操作系統(tǒng)所做的事情。當(dāng)CPU要訪問的頁面不在內(nèi)存中時，就發(fā)生缺頁中斷；發(fā)生缺頁中斷時，CPU轉(zhuǎn)缺頁中斷處理程序執(zhí)行，將待訪問頁面從外存調(diào)入內(nèi)存，返回被中斷程序，重新啟動引起缺頁的指令。3. 死鎖產(chǎn)生的4個必要條件是什么？死鎖產(chǎn)生的4個必要條件是：互斥條件、保持和等待條件、循環(huán)等待條件、不可搶占條件。4. 高級調(diào)度與低級調(diào)度的主要功能是什么? 兩者是什么關(guān)系?高級調(diào)度是作業(yè)調(diào)度，為作業(yè)分配資源，將作業(yè)調(diào)入內(nèi)存，并為之創(chuàng)建進(jìn)程；低級調(diào)度為進(jìn)程調(diào)度，為進(jìn)程分配處理器；作業(yè)調(diào)度為進(jìn)程調(diào)度做準(zhǔn)備。5. 什么是操作系統(tǒng)？操作系統(tǒng)的主要功能是什么？操作系統(tǒng)是一種系統(tǒng)軟件，是若干程序模塊所的集合，它負(fù)責(zé)管理和控制計算機系統(tǒng)的硬件、軟件資源的分配、調(diào)度和管理，使系統(tǒng)高效、安全地運行；為用戶提供簡單、直觀、靈活的用戶接口和使用環(huán)境；操作系統(tǒng)的主要功能是實現(xiàn)對計算機系統(tǒng)軟硬件資源的管理。6. 為什么要引進(jìn)高級通信機構(gòu)? 請列舉常見進(jìn)程間通信機制的實例。引進(jìn)高級通信機構(gòu)的目的是為了在進(jìn)程間實現(xiàn)大量數(shù)據(jù)的交換；進(jìn)程間通信機制的實例有：管道、消息通信、共享內(nèi)存等。三、理解題（共20分 每題5分）1. 列出5項設(shè)備管理的功能。設(shè)備分配；設(shè)備回收；設(shè)備啟動;I/O操作;中斷處理;緩沖區(qū)管理；2. 列出5種進(jìn)程調(diào)度時機。進(jìn)程正常結(jié)束；進(jìn)程出錯終止；運行時間片用完；等待I/O操作；優(yōu)先級更高度進(jìn)程就緒；3.考慮以下頁表：頁號物理塊號021328假定頁面大小是每頁1024字節(jié)，有效地址的格式為(頁號,頁內(nèi)偏移量)，請計算有效地址 (1,500)、(2,3000)、(3,100)的物理地址。答；有效地址 (1,500)的物理地址為：10243+500=3572; (3分)有效地址 (2,3000)不合法；(1分)有效地址(3,100)的頁號超出頁表范圍，出現(xiàn)地址越界；(1分)4.下列程序設(shè)計技術(shù)和結(jié)構(gòu)對于請求分頁環(huán)境來說， 哪些是“好的”？ 哪些是“不好的”？（1）數(shù)組；（2）雙向鏈表；（3）跳轉(zhuǎn)；(4)循環(huán)；（5）二叉樹4. （1）數(shù)組好；（2）雙向鏈表不好；（3）跳轉(zhuǎn)不好；(4)循環(huán)好；（5）二叉樹不好；(評分標(biāo)準(zhǔn)：每項1分，最多5分)四、綜合題（共30分）1. (10分)設(shè)有一臺計算機， 有兩條IO通道， 分別接一臺卡片輸入機和一臺打印機。 卡片機把一疊卡片逐一輸入到緩沖區(qū)B1中， 加工處理后再搬到緩沖區(qū)B2中， 并在打印機上印出， 問： (1) 系統(tǒng)要設(shè)幾個進(jìn)程來完成這個任務(wù)? 各自的工作是什么?(2) 這些進(jìn)程間有什么樣的相互制約關(guān)系?(3) 用P、 V操作寫出這些進(jìn)程的同步算法。答：(1) 可用3個進(jìn)程完成：Pa：從卡片機讀信息，并逐一輸入到緩沖區(qū)B1中（1分)Pb：從緩沖區(qū)B1讀信息， 加工處理后再搬到緩沖區(qū)B2中（1分)P3：從緩沖區(qū)B2讀信息， 并在打印機上印出 (1分)(2) 這些進(jìn)程間為同步關(guān)系 (2分)(3) 同步算法：初值：empty1=empty2=1; full1=full2=0; (2分)Empty1和Empty2的初值為1，F(xiàn)ull1和Full2的初值為0Pa：(1分)While(1) 從卡片機讀數(shù)據(jù)；P(Empty1);將數(shù)據(jù)寫入緩沖區(qū)B1；V(Full1);Pb：(1分)While (1) P(Full1);從緩沖區(qū)B1讀數(shù)據(jù)；V(Empty1)加工數(shù)據(jù)P(Empty2);將加工后的數(shù)據(jù)寫緩沖區(qū)B2；V(Full2);Pc：(1分)While(1) P(Full2);從緩沖區(qū)2讀數(shù)據(jù)；V(Empty2);打印信息；2. (7分)考慮下面存儲訪問序列， 該程序有460字： 10， 11， 104， 170， 73， 309， 185， 245， 246， 434， 458， 364設(shè)頁面大小是100字，請給出訪問順序。又設(shè)該程序基本可用內(nèi)存是200字，請寫出采用LRU頁面置換算法是頁面替換順序，計算缺頁率。答：頁面走向為：0，1，0，3，1，2，4，3 (1分)采用LRU算法的頁面替換順序為：頁面走向01031243內(nèi)存頁000332231111144是否命中XXXXXX頁面替換順序0312 （2分）頁面替換順序為：0，3，1，2 (2分)缺頁率為：68= 75% (2分)3.(3分) 一個操作系統(tǒng)支持分頁虛存，所用處理機的周期時間是1s，頁面大小是1000字，分頁設(shè)備是磁鼓，它每分鐘轉(zhuǎn)3000圈，傳輸速率是每秒1000000字。 由系統(tǒng)測得下述統(tǒng)計結(jié)果：（1） 所執(zhí)行的全部指令中有0.1%存取的頁面不是當(dāng)前的頁面。（2） 存取另外頁面的指令，它們所存取的頁面有80%已在內(nèi)存。（3） 當(dāng)請求一個新頁面時，所置換頁面有50%在此期間修改過。設(shè)系統(tǒng)中只運行這一個程序，當(dāng)磁鼓進(jìn)行傳送時，處理機空轉(zhuǎn)等待。在上述條件下計算這個系統(tǒng)的有效指令時間（執(zhí)行一條指令所需的平均時間）答：1個頁面從外存?zhèn)鞯絻?nèi)存的時間：100010-610-3 s 1 ms存取當(dāng)前頁面中內(nèi)存單元的時間：1 us 99.9%10-6 s (1分)存取不在當(dāng)前頁面中內(nèi)存單元（但單元已在內(nèi)存）的時間：1 us 0.1% 80% 10-9 s存取不在當(dāng)前頁面中內(nèi)存單元（但單元不在內(nèi)存，被置換頁面不需寫回）的時間：1 ms 0.1% 20%50% =10-7 s存取不在當(dāng)前頁面中內(nèi)存單元（但單元不在內(nèi)存，被置換頁面需寫回）的時間：2 ms 0.1% 20%50% =210-7 s (1分)有效存取時間為: 10-6 s + 10-9 s +10-7 s + 210-7 s 1.3 us (1分)4.(10分)假定在單CPU條件下有下列要執(zhí)行的作業(yè):作業(yè)運行時間優(yōu)先級1103211323414552作業(yè)到來的時間是按作業(yè)編號順序進(jìn)行的(即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位)。（1）用一個執(zhí)行時間圖描述采用時間片輪轉(zhuǎn)算法RR（時間片=1）時執(zhí)行這些作業(yè)的情況；（2）并計算各個作業(yè)的周轉(zhuǎn)時間是多少和平均周轉(zhuǎn)時間。答： (1) RR算法執(zhí)行時間圖：(4分)2018516 14 1210 8 6 40 24321（2）各作業(yè)周轉(zhuǎn)時間：(4分)作業(yè)12345平均周轉(zhuǎn)時間周轉(zhuǎn)時間19151107.2（3）平均周轉(zhuǎn)時間 (2分) (19+1+5+1+10) 5=7.23操作系統(tǒng)（B卷）答案及評分標(biāo)準(zhǔn)一、術(shù)語解釋（共20 分 每題2分）并發(fā)；兩個或更多個程序同時在系統(tǒng)中存在并且運行， 即一個程序段執(zhí)行尚未結(jié)束，另一個程序段已經(jīng)開始執(zhí)行實時；能夠及時響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對事件的處理;死鎖預(yù)防；破壞死鎖的四個必要條件之一，使死鎖不可能發(fā)生；存儲器碎片；經(jīng)過多次內(nèi)存分配與回收后產(chǎn)生的一些尺寸太小得不到利用存儲器塊；多道程序設(shè)計；同時在內(nèi)存中讓多個程序并發(fā)執(zhí)行；線程；一種輕量級進(jìn)程，位于進(jìn)程內(nèi)部，是處理器調(diào)度的基本單位；快表；用于保存最近需要使用的頁表項的高速存儲器；程序地址；程序中使用的存儲器地址；系統(tǒng)調(diào)用；應(yīng)用程序調(diào)用操作系統(tǒng)服務(wù)的唯一方式，采用中斷機制實現(xiàn)；文件邏輯組織；用戶看到的文件結(jié)構(gòu)；二、簡答題1. 操作系統(tǒng)主要有哪幾種基本類型？ 分時系統(tǒng)和實時系統(tǒng)各有何特點？答：操作系統(tǒng)有3種基本類型：批處理系統(tǒng)，分式系統(tǒng)，實時系統(tǒng)；在分式系統(tǒng)中，每個用戶有一個操作終端，將運行時間分成很多時間片，分給各個用戶使用，但用戶看來，每個都感覺在獨占計算機；實時系統(tǒng)可對外部發(fā)生的時間在規(guī)定的時間內(nèi)作出相應(yīng)2. 什么是重定位？ 它分為哪幾類？ 它們之間的差別是什么？答： 重定位是程序地址變換為物理地址的過程；它分為靜態(tài)重定位和動態(tài)重定位2種；靜態(tài)重定位在程序加載到內(nèi)存時通過把程序地址修改成物理地址完成重定位；動靜態(tài)重定位在程序執(zhí)行中、內(nèi)存訪問前有硬件執(zhí)行重定位。3. 文件管理的主要功能是什么？答：文件管理的主要功能：文件存儲空間管理，文件目錄管理，文件操作，文件保護(hù)，文件按名存取。4. 處理機調(diào)度一般可分為哪三級? 其中哪一級調(diào)度必不可少? 為什么?答：處理機調(diào)度一般可分為作業(yè)調(diào)度、交換調(diào)度和進(jìn)程調(diào)度三級；其中進(jìn)程調(diào)度必不可少；因為只有進(jìn)程調(diào)度才能將處理器分配給進(jìn)程使用。5. 在操作系統(tǒng)中為什么要引入進(jìn)程概念? 它與程序的差別和關(guān)系是怎樣的?答：在操作系統(tǒng)中引入進(jìn)程概念是為了更好地描述程序執(zhí)行過程中動態(tài)特性,這些特性是“程序”這個概念無法描述清楚的；它與程序的差別和關(guān)系是：進(jìn)程是程序的執(zhí)行過程，程序是進(jìn)程的靜態(tài)形式。6. 什么是原語？操作系統(tǒng)為何要引入原語的概念。答：原語是執(zhí)行過程中不可被打斷的一段代碼（3分），操作系統(tǒng)引入原語的原因是為了保護(hù)一些系統(tǒng)狀態(tài)、數(shù)據(jù)結(jié)構(gòu)的一致性和完整性(2分)。三、理解題（共20分 每題5分）1. 列出文件控制塊中任意5項內(nèi)容。答： 文件名、文件大小、文件數(shù)據(jù)塊指針、文件創(chuàng)建時間、文件訪問權(quán)限、文件所屬用戶等2. 列出5項進(jìn)程控制塊的內(nèi)容。答：進(jìn)程號、進(jìn)程名、進(jìn)程狀態(tài)、父進(jìn)程指針、堆棧地址等3. 考慮如下段表寫出下述邏輯地址的物理地址。（1） 0， 430；（2） 1， 10；（3） 1， 11；（4） 2， 500；（5） 3， 400；答：(1) 219+430=649(2) 2300+10=2310(3) 2300+11=2311(4) 500100， 發(fā)生地址越界(5) 132740017274. 下列程序設(shè)計技術(shù)和結(jié)構(gòu)對于請求分頁環(huán)境來說， 哪些是“好的”？ 哪些是“不好的”？（1）堆棧；（2） 散列符號表；（3） 順序查找；（4） 二分查找；（5） 純碼；答：（1）好；（2） 不好；（3） 好；（4） 不好；（5） 好四、綜合題（共30分）1. (10分)設(shè)系統(tǒng)中只有一臺打印機， 有三個用戶的程序在執(zhí)行過程中都要使用打印機輸出計算結(jié)果。 設(shè)每個用戶程序?qū)?yīng)一個進(jìn)程。 問： 這三個進(jìn)程間有什么樣的制約關(guān)系？ 試用P、 V操作寫出這些進(jìn)程使用打印機的算法。答： (1)三個進(jìn)程間的關(guān)系是互斥關(guān)系。(2分)(2) 進(jìn)程間同步算法如下：設(shè)置一個互斥信號量mutex來協(xié)調(diào)各進(jìn)程對打印機的使用，初值為1。(2分)用戶進(jìn)程1：(2分)P(mutex);打印計算結(jié)果1；V(mutex);用戶進(jìn)程2：(2分)P(mutex);打印計算結(jié)果2；V(mutex);用戶進(jìn)程3：(2分)P(mutex);打印計算結(jié)果3；V(mutex);2.（7分）假定分頁存儲系統(tǒng)中有快表， 多數(shù)活動頁表項都可收在其中。 如果頁表還是放在內(nèi)存中， 內(nèi)存訪問時間是1s， 若快表的命中率是85%， 則有效存取時間是多少？ 若命中率降為50%， 那么有效存取時間為多少？答：（1） 有效存取時間為：(1-0.85)1 us + 1 us = 1.15 us (4分)（2） (1-0.5) 1 1 1.5 us (3分)姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線3.(3分)假定文件A采用串連文件結(jié)構(gòu)，其文件結(jié)構(gòu)表示如下圖所示，試計算該文件第3個數(shù)據(jù)塊的內(nèi)容保存在哪個物理快中。(注意：