哈工大《操作系統(tǒng)試題》2010CS試卷和答案

試題：操作系統(tǒng)班號：姓名：第5頁（共6頁）哈工大2010年秋季學(xué)期學(xué)號姓名操作系統(tǒng)試題題號一二三四五六總分分數(shù)第1頁（共6頁）卷面50分，加上實驗50分作為最終成績。對于不需要實驗成績的學(xué)生，卷面50分x2后作為最終成績。共六道題，均為必答題。一、回答下列問題：(1)給出輪轉(zhuǎn)調(diào)度算法(Round-Robin，RR)的基本思想；(1分)(2)評價進程調(diào)度算法的常見指標有平均等待時間和系統(tǒng)吞吐量，給出這兩個指標的含義；(2分)(3)選擇上述兩個評價指標中任意一個，解釋RR算法中時間片變大會如何影響它；(1分)(4)相比其他調(diào)度算法而言，你認為輪轉(zhuǎn)調(diào)度算法能達到的特有目標是什么？說明原因；(2分)(5)說明如何設(shè)計操作系統(tǒng)的相關(guān)參數(shù)才能保證RR算法在任何情況下都能達到上述特有目標。(2分)

二、假定某一基于分頁的虛擬存儲系統(tǒng)(請求調(diào)頁)，某時刻測得各相關(guān)部分的利用率：CPU為20%，磁盤交換區(qū)I/O為99.7%，其他設(shè)備I/O為5%。(1)虛擬存儲系統(tǒng)中的交換區(qū)起什么作用？（2分）(2)解釋什么是請求調(diào)頁。（2分）(3)解釋產(chǎn)生這些現(xiàn)象的原因。（2分）(4)更換一個更快的CPU能提高CPU利用率嗎？為什么？（1分）(5)增加磁盤交換分區(qū)的容量能提高CPU利用率嗎？為什么？（1分）(6)請設(shè)計一種與(4)(5)問無關(guān)的提高CPU利用率措施。（1分）

三、中斷及中斷處理對操作系統(tǒng)某些功能的實現(xiàn)具有重要的作用，給出4個這樣的例子（過于相近的例子算作一個）。每個例子2分，共8分。

四、看漫畫回答問題：競爭條件（RaceContitions）是什么？（2分）舉一個簡單例子，說明如何用互斥鎖解決競爭條件。（3分）請分析一下，空循環(huán)（EmptyLoop，就是循環(huán)體里什么都不做，但還要循環(huán)很多次的循環(huán)）能解決競爭條件嗎？（3分）基于第(3)問你的分析，解釋一下此圖的笑點在哪。（1分）

五、保存文件的歷史版本已經(jīng)成為現(xiàn)代文件系統(tǒng)的一項重要功能。但基于inode的ext4文件還沒有此功能。你來設(shè)計它吧！請回答下列問題：簡要描述inode文件系統(tǒng)的基本思想。（2分）inode文件系統(tǒng)的目錄結(jié)構(gòu)中至少要包含哪兩項數(shù)據(jù)？（2分）請設(shè)計有歷史版本保存功能的inode文件系統(tǒng)如何索引每個文件及其歷史版本。設(shè)計中也要包括目錄結(jié)構(gòu)的設(shè)計。（4分）

六、有一只鐵籠子，每次只能放入一只動物。獵手向籠中放入老虎，牧民向籠中放入羊。動物園等待取籠中的老虎，飯店等待取籠中的羊。(1)信號量兩個基本操作是什么？（2分）(2)信號量的操作為什么必須是原子操作？（2分）(3)請用信號量，編寫偽代碼，解決此問題。與信號量無關(guān)的步驟可一筆帶過。（4分）試卷A一、（1）所有進程輪流執(zhí)行一小段時間（2）所有進程在就緒隊列等待的時間均值，系統(tǒng)單位時間內(nèi)運行/完成的進程個數(shù)（3）平均等待時間：與進程情況有關(guān)，只要假定的情況下結(jié)論正確即可。吞吐率：與單位時間的選擇和進程情況有關(guān)，只要假定的情況下結(jié)論正確即可。（4）任何能有合理解釋的目標均可。例如：用戶響應(yīng)時間有界，用戶響應(yīng)時間是一個進程此次執(zhí)行到下一次之前在就緒隊列中的等待的時間，由于輪轉(zhuǎn)調(diào)度使得每個進程最多只能執(zhí)行一個時間片就讓出CPU，所以進程不可能在就緒隊列中無限等待。（5）針對其選擇的目標做出合理說明即可。例如：就緒隊列中的進程個數(shù)有界，分配給每個進程的時間片大小有上界。二、保存暫時不需要的內(nèi)存內(nèi)容，以騰出更多內(nèi)存空間訪問到某頁時才加載該頁CPU效率較低的原因是系統(tǒng)出現(xiàn)了顛簸，磁盤交換區(qū)使用率很高證明很多頁面被換出到了磁盤上，當然分配給進程的頁面就很少了，不足以覆蓋一個進程的局部，從而出現(xiàn)了顛簸，由于忙于磁盤換入換出，CPU利用率低，啟動其他I/O設(shè)備的可能性變小，所以其他I/O設(shè)備利用率低。不能。CPU加快只可能讓工作集更大，顛簸得更厲害不能。不可能產(chǎn)生影響殺死一些進程，或加大內(nèi)存三、（1）時鐘中斷可以減少分配給當前進程的時間片，實現(xiàn)RR調(diào)度。（2）時鐘中斷可以完成頁面的掃描，實現(xiàn)訪問位清0以及頁面換出，從而實現(xiàn)頁面淘汰。（3）缺頁中斷可以完成頁面調(diào)度，實現(xiàn)請求調(diào)頁功能，從而實現(xiàn)虛擬內(nèi)存。（4）INT0x80可以實現(xiàn)系統(tǒng)調(diào)用，從而實現(xiàn)從用戶態(tài)到核心態(tài)的切換。（5）在IO工作完成時的中斷（如磁盤讀寫完成時的中斷）可以喚醒等待在這些IO事件上的進程，從而實現(xiàn)進程的并發(fā)。四、并發(fā)進程同時訪問共享的資源互斥鎖的理解1分；互斥鎖操作的理解1分；例子正確1分；某些情況下能降低競爭條件發(fā)生的概率，但不能徹底解決；用拼概率的方法解決程序問題是愚蠢且可笑的五、把指向各個數(shù)據(jù)塊的指針統(tǒng)一保存到inode中文件名和inode塊號目錄項中除了文件名，還要記錄文件版本。不同版本指向不同inode。當文件被修改時，inode被復(fù)制一份新的，修改新inode中被修改的數(shù)據(jù)塊所對應(yīng)的指針。六、P和V信號量本身也是臨界資源籠子=1老虎=0羊=0獵手(){While(true){P(籠子)放老虎V(老虎)}}動物園()