操作系統(tǒng)原理期末試卷(參考答案及評分標準)

命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊封線密

2012~2013學年第一學期開課學院：軟件學院課程號：09000925考試日期：2012-12-16考試時間：120分鐘單項選擇題〔10分每題1分〕1、頁表中的臟數(shù)據(jù)位(DirtyBit)可以〔B〕〔A〕用來判斷該頁是否在物理內存中〔B〕用來減少PageFault中磁盤數(shù)據(jù)交換的開銷〔C〕用來實現(xiàn)LRU算法〔D〕用來完成LRU的堆棧實現(xiàn)2、關于系統(tǒng)調用〔systemcall〕，以下哪一個是正確的？〔C〕〔A〕系統(tǒng)調用與庫函數(shù)調用是完全一樣的。〔B〕應用程序可以替換系統(tǒng)調用。〔C〕系統(tǒng)調用是應用程序請求操作系統(tǒng)效勞的唯一入口?！睤〕所有的操作系統(tǒng)都具有相同的系統(tǒng)調用。3、對于微核(micro-kernel)操作系統(tǒng)以下哪種說法是正確的〔D〕〔A〕微核操作系統(tǒng)不易于擴展〔B〕微核操作系統(tǒng)中用戶空間與內核空間的通信開銷較低〔C〕微核操作系統(tǒng)移植性較差〔D〕微核操作系統(tǒng)將局部內核模塊移動到了用戶空間4、外部碎片說法正確的選項是〔C〕〔A〕相對于內部碎片問題，外部碎片在操作系統(tǒng)內核之外〔B〕是由不連續(xù)分配方案導致的空間浪費問題〔C〕相對于內部碎片問題，外部碎片在進程之外〔D〕內部碎片可以合并而外部碎片不行5、用戶編寫的程序中所使用的地址是〔A〕〔A〕邏輯地址〔B〕線性地址〔C〕物理地址〔D〕頁表地址16、關于臨界區(qū)〔Criticalsection〕，以下哪個說法是正確的？〔B〕〔A〕臨界區(qū)中允許多個進程同時運行?！睟〕臨界區(qū)是一段訪問共享資源的代碼?！睠〕臨界區(qū)是一塊需要保護的數(shù)據(jù)?！睤〕如果沒有對臨界區(qū)進行保護，程序每一次運行一定都會得到錯誤的結果。7、以下對操作系統(tǒng)的描述哪個是正確的〔C〕〔A〕計算機系統(tǒng)由運算器、控制器、存儲器、輸入、輸出以及操作系統(tǒng)組成〔B〕操作系統(tǒng)需要提供人機界面，因此操作系統(tǒng)介于用戶和應用程序之間〔C〕進程在操作系統(tǒng)中運行時會不斷的在內核態(tài)于用戶態(tài)之間切換〔D〕操作系統(tǒng)的設計與計算環(huán)境不相關8、同一進程內的線程間可共享〔B〕〔A〕?！瞫tack〕〔B〕文件〔C〕CPU存放器〔D〕局部變量9、假設一個系統(tǒng)的邏輯地址空間為8個頁面，其中每一個頁面占1024字節(jié)，物理內存為32個頁幀〔frame〕，該系的邏輯地址和物理地址各需要多少位？〔A〕〔A〕13，15。〔B〕15，17。〔C〕15，13?！睤〕17，13。10、關于虛擬內存，哪一個是正確的？〔D〕〔A〕虛擬內存只能通過請求式調頁〔demandpaging〕實現(xiàn)?！睟〕虛擬內存是一個純軟件的系統(tǒng)，不需要硬件的支持也能實現(xiàn)?！睠〕如果一臺32位的計算機擁有4GB的物理內存，那么它永遠都不會發(fā)生“顛簸〔thrashing〕”?！睤〕在虛擬內存中，有效內存訪問時間近似正比于缺頁異常發(fā)生的概率。多項選擇題〔30分每題3分〕1、進程同步的經典問題包括〔ACE〕〔A〕讀者寫者問題〔B〕拜占庭問題〔C〕哲學家進餐問題〔D〕皮特森問題〔E〕有限緩沖區(qū)問題2、操作系統(tǒng)效勞有〔ABCDE〕〔A〕人機界面〔B〕I/O操作命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊封線密〔D〕進程間通信〔E〕資源分配3、進程調度可分為〔CDE〕〔A〕I/O調度〔B〕資源調度〔C〕長期調度〔D〕短期調度〔E〕中期調度4、以下文件系統(tǒng)的分配方式具有隨機訪問能力的是〔AC〕〔A〕連續(xù)分配〔B〕單向鏈表分配〔C〕單級索引分配〔D〕雙向鏈表分配〔E〕循環(huán)鏈表分配5、同步問題的解決方法有〔AD〕(〔A〕)信號量〔semaphore〕(〔B〕〕銀行家算法(〔C〕)LRU算法(〔D〕)管程〔monitor〕(E)API6、下面哪一個說法是正確的？〔ACD〕〔A〕策略和機制別離是操作系統(tǒng)設計應該遵循的重要原那么。〔B〕如果資源分配圖中包含一個環(huán)，一定發(fā)生了死鎖?！睠〕如果系統(tǒng)采用兩級頁表結構，那么每一個進程必須有獨立的頁表?！睤〕為了獲得最好的地址轉換性能，頁面大小一般都設為2的冪次方。7、以下哪幾個數(shù)據(jù)結構或算法的局部性不好？〔ABD〕〔A〕哈希表〔Hashtable〕?！睟〕指針?！睠〕順序查找〔sequentialsearch〕?！睤〕二分查找〔binarysearch〕。〔E〕?！瞫tack〕8、屬于搶占式〔preemptive〕的進程調度算法是〔BDE〕〔A〕先來先效勞〔FCFS〕。〔B〕輪轉〔Round-Robin，RR〕?！睠〕優(yōu)先級調度。〔D〕多級反應隊列調度〔Multilevelfeedbackqueue〕?！睧〕最短作業(yè)優(yōu)先〔Shortestjobfirst,SJF〕9、常見的頁表結構有〔ADE〕(A)層次〔hierarchy〕(B)堆棧(C)鏈表(D)哈?！瞙ashedtable〕(DE)反向〔inverted〕10、以下屬于文件根本操作的是〔ABCDE〕〔A〕截斷truncate〔B〕讀取read命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊封線密〔D〕創(chuàng)立create〔E〕刪除delete簡答題〔24分〕〔4分〕請解釋PCB的含義并列舉至少三項PCB的內容?！?分〕畫出進程的狀態(tài)變遷圖，并給出狀態(tài)變遷的原因?！?分〕請簡述I/O操作的根本模式和其思想?！?分〕請解釋什么是PageFault，并用畫圖或簡述的方式描述PageFault的處理過程。〔46分〕請簡述死鎖的必要條件,并用資源分配圖列舉一個發(fā)生死鎖的例子。算法題〔36分〕1、(8分)請寫出讀者寫者〔reader-writer〕問題的算法偽代碼。2、(10分)系統(tǒng)中有已經到達的5個進程,請用FCFS，SJF和RR〔時間片為10〕畫出調度過程的甘特圖并計算三種算法的平均等待時間。ProcessBurstTimeP110P229P33P47P5123、(18分，軟件工程專業(yè)題目)假設有一個32位系統(tǒng)的頁面大小為1K字節(jié)，采用FIFO頁面置換算法，當前進程分配4個物理幀，代碼用了1個物理幀并常駐內存?，F(xiàn)有兩個進程分別運行如下的代碼：inttemp=0;inta[][]=newint[128][128inttemp=0;inta[][]=newint[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++)switch(imod4){case0:break;case1:temp+=a[i][j];break;case2:a[i][j]=i+j;break;case3:break;}inttemp=0;inta[][]=newint[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++) switch(jmod4){case0:break;case1:temp+=a[j][i];break;case2:a[j][i]=i+j;break;case3:break;}命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊封線密請計算A和B各自產生了多少次Pagefault？〔4分〕如果這三個物理幀的首地址分別是：79A65400H79C65400H79E65400H請計算兩種算法里當i=6，j=10時a中對應元素的物理地址？〔6分〕假設采用二級頁表無TLB，1個內存訪問周期為1μs，PageFault的時間開銷各項分別為：pagefaultoverhead=10μs；swappageout=300μs；swappagein=30μs；restartoverhead=10μs；兩種算法對數(shù)組總訪問時間分別為多少？〔8分〕34、〔數(shù)字媒體專業(yè)〕(12分，數(shù)字媒體專業(yè)題目)給定進程分配到的頁幀數(shù)為3，頁請求序列為 0,1,4,2,0,2,6,5,1,2,3,2,1,2,6,2,1,3,6,2,分別給出FIFO、LRU和最優(yōu)三種算法的頁面調度的過程并計算缺頁異常數(shù)。5、〔6分，數(shù)字媒體專業(yè)題目〕一個文件系統(tǒng)的FCB〔FileControlBlock〕能存儲13個磁盤塊地址，其中開始前面的10個地址指向文件的前10個磁盤塊，第11個地址指向一個一級索引塊〔singleindirectblock〕，第12個地址指向一個二級索引塊〔doubleindirectblock〕；第13個地址指向一個三級索引塊〔tripleindirectblock〕。假設一個磁盤塊有1024字節(jié)，每一個磁盤塊可以存儲256個磁盤塊地址。請計算該文件系統(tǒng)能存儲的最大的文件是多少字節(jié)？〔只列出表達式即可〕命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日命題人：劉寄組題人：洪明堅審題人：張毅命題時間：2012年11月28日教務處制學院專業(yè)、班年級學號姓名公平競爭、老實守信、嚴肅考紀、拒絕作弊封線密答題紙單項選擇題1、〔、〔B〕2、〔C〕3、〔D〕4、〔C〕5、〔A〕6、〔B〕7、〔C〕8、〔B〕9、〔A〕10、〔D〕多項選擇題1、〔ACE〕2、〔ABCDE〕3、〔CDE〕4、〔AC〕5、〔AD〕6、〔ACD〕7、〔ABD〕8、〔BDE〕9、〔ADE〕10、〔ABCDE〕第一章4分1.7(1分)2.7(3分)第二章4分1.3(1分)2.2(3分)第三章8分1.2(1分)2.3(3分)3.1〔4分〕第四章4分1.8(1分)2.6(3分)第五章10分4.2(10分)第六章14分2.1(3分)2.5(3分)4.1(8分)第七章6分3.4(6分)第八章16分1.4(1分)1.5(1分)1.6(1分)1.9(1分)1.10(1分)2.9(3分)4.3(8分)第九章22分1.1(1分)2.8(3分)3.3(8分)4.3(10分)第十、十一章6分2.10(3分)2.4(3分)第十三章6分3.2(6分)如果你在緒論時講過I/O的Pooling、Interrupt和DMA，建議該題保存簡答題如果你在緒論時講過I/O的Pooling、Interrupt和DMA，建議該題保存1答：PCB是Processcontrolblock進程控制塊的縮寫〔1分〕，PCB中的內容有：進程狀態(tài)〔ProcessState〕、程序計數(shù)器〔ProgramCounter〕、CPU存放器〔CPURegister〕、CPU調度信息〔CPUSchedulingInformation〕、內存管理信息〔Memory-managementInformation〕、資源調度信息〔AccountingInformation〕、I/O狀態(tài)信息〔I/OStatusInformation〕〔任意答對3個即給3分〕2答：必須畫出5個狀態(tài)，否那么為零分；狀態(tài)之間轉移方向畫錯一個扣一分，扣完為止；轉移條件少寫一個扣一分，扣完為止；3答：用圖或者文字畫出或寫出上述6步即得分，少寫不得分，順序錯誤扣一半4答：互斥〔Mutualexclusion〕、擁有并等待〔Holdandwait〕、不可剝奪性〔Nopreemption〕、循環(huán)等待〔Circularwait〕〔4分每個一分〕畫圖〔2分，只要是死鎖即可不要求和參考答案一樣〕算法題1答：信號量WRT=1；信號量MUTEX=1；共享變量ReadCount=0〔3分〕〔變量和信號量的名字可自己定義〕作者Writer〔1分〕Wait(WRT)；CriticalSectionSignal(WRT)；讀者Reader〔4分〕Wait(MUTEX)；ReadCount++;If(ReadCount==1)Wait(WRT)；Signal(MUTEX)；CriticalSectionWait(MUTEX)；ReadCount--;If(ReadCount==0)Signal(WRT)；Signal(MUTEX)；2答：FCFS、SJF、RR的甘特圖如下：畫圖FCFS〔1分〕SJF〔1分〕RR〔1分〕FCFS平均等待時間：(0+10+39+42+49)/5=28〔2分〕SJF平均等待時間(0+3+10+20+32)/5=13〔2分〕RR平均等待時間(0+10+20+23+30+20+10+2)/5=23〔3分〕寫對算式計算錯誤扣一半3答：3.1算法A產生PageFault共64次〔2分〕；算法B共產生PageFault共64*128=8192次?！?分〕3.2算法A中a[6,10]按照FIFO算法應該放入首地址為79A65400H的物理幀中〔如果結果不正確描述出該點1分〕，偏移量為10*4=40=28H〔如果結果不正確描述出該點1分〕，故物理地址為79A65428H〔3分〕；