操作系統(tǒng)原理期末考試試題B卷(2008)-參考答案

1、第 頁，共10頁第 頁，共10頁南開大學(xué)信息技術(shù)科學(xué)學(xué)院本科生2008-2009年度第一學(xué)期操作系統(tǒng)原理課程期末試卷（B卷）草稿區(qū)請簡述分時操作系統(tǒng)中兩種最主要的進程調(diào)度策略，并對每種策略舉出2種實例。剝奪式調(diào)度：操作系統(tǒng)按照進程調(diào)度算法控制多個進程分享CPU，使得CPU在多個進程之間進行切換,這種機制叫做剝奪式調(diào)度。（定義1分）而非剝奪式調(diào)度是指：進程一旦占用CPU，就會一直運行到結(jié)束，其他進程只能等待該進程釋放CPU后才能依次占用CPU，這種機制叫非剝奪式調(diào)度。（定義1分）剝奪式調(diào)度算法：時間片輪轉(zhuǎn)，優(yōu)先級調(diào)度，最短剩余時間優(yōu)先等。（每個1分）非剝奪式調(diào)度算法：先來先服務(wù)，最短作業(yè)優(yōu)先等。

2、（每個1分）2.請簡要解釋DMA機制的工作方式，并分析DMA驅(qū)動I/O與中斷驅(qū)動I/O的差別？DMA，即直接存儲器存取，是指在外設(shè)和存儲器之間開辟一個直接的數(shù)據(jù)通道，數(shù)據(jù)傳輸由另外的DMA控制器來完成（2分）。DMA控制器在開始傳輸之前獲取目的地址，由DMA控制器控制外設(shè)將數(shù)據(jù)寫入存儲器。（2分）這種方式驅(qū)動I/O和中斷驅(qū)動I/O的最主要的區(qū)別在于不再需要CPU的參與。（2分）文件的邏輯結(jié)構(gòu)分為幾種形式？文件的磁盤布局分為幾種形式？文件的邏輯結(jié)構(gòu)主要分兩大類：字符流式的無結(jié)構(gòu)文件和記錄式的有結(jié)構(gòu)文件。（2分）字符流式的文件管理簡單，用戶操作較為簡單，常見的如源代碼文件、目標(biāo)代碼文件等。記錄式文

3、件將文件中的記錄按照一定的方式進行排列，從而形成不同的邏輯結(jié)構(gòu)，用戶方便對其進行修改、追加、查找等功能。（1分）文件的磁盤布局是指文件存儲在磁盤上的具體實現(xiàn)方式，主要有連續(xù)分配、鏈表分配、在內(nèi)存中采用表的鏈表分配（索引文件）、i結(jié)點等幾種方式。（3分）草稿區(qū)解釋什么是中斷，并對中斷的處理過程做簡要描述。中斷是指計算機在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何非尋常的或者非預(yù)期的急需處理的事件，使得CPU暫時中斷當(dāng)前正在執(zhí)行的的程序轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或者調(diào)度新的進程執(zhí)行的過程。（3分）般中斷處理程序主要由以下幾步完成，判斷中斷響應(yīng)文件、關(guān)中斷、保存中斷現(xiàn)場、分析中

4、斷原因轉(zhuǎn)中斷處理子程序、執(zhí)行中斷處理子程序、恢復(fù)現(xiàn)場、開中斷、返回中斷點。（3分）請列出至少3種你認為CPU中比較重要的跟操作系統(tǒng)有關(guān)的寄存器。CPU中最重要的寄存器有：程序計數(shù)器PC,其中裝有下一周期要被執(zhí)行的指令的地址。（2分）指令寄存器IR，內(nèi)裝有待執(zhí)行的指令。（2分）程序狀態(tài)字PSW,該寄存器中的各個比特位代表著系統(tǒng)中當(dāng)前的各種不同狀態(tài)與信息。例如執(zhí)行模式是否允許中斷等。（2分）二、編程計算題（本題共四小題，共計45分，必做）草稿區(qū)請在下面的表格中指定答題順序，在對應(yīng)的分值下列明題號。每格只許列出一個題號，否則做無效處理。必須寫明所有題目的題號，如果填寫不完全，視為不指定答題順序。如填

5、寫內(nèi)容無效或者不填寫表格，則按照默認的題面分值評分第一題（15分）第二題（12分）第三題（10分）第四題（8分）6.進程同步互斥與死鎖問題的解決（默認分值：15分）有一條南北雙向的國家公路，其中一段路程共享一個單車道的隧道，行駛的汽車到達隧道入口處時，沒有迎面而來的汽車時才能使用隧道。為了避免事故的發(fā)生，需要設(shè)計一套傳感和信號系統(tǒng)。當(dāng)一輛汽車接近隧道時，傳感器通過Arrive函數(shù)向信號控制系統(tǒng)傳遞汽車運行的方向參數(shù)；當(dāng)一輛汽車離開隧道時，傳感器通過Depart函數(shù)向信號控制系統(tǒng)傳遞汽車的運行參數(shù)。控制系統(tǒng)使用一個單核多線程CPU作為處理器，并在隧道兩端設(shè)置信號燈如下：綠燈表示行進，紅燈表示停止

6、。圖1是該問題的示意圖：請回答以下問題：1）分析該問題中存在的同步和互斥關(guān)系，并確定需要使用幾個傳感器和信號燈，說明使用方式和設(shè)置位置隧道是兩邊車的競爭條件。（1分）使用兩個傳感器和兩個信號燈，分別在左右進入隧道的路上每條路上設(shè)置一個傳感器和一個信號燈。信號燈位置在隧道口前，傳感器位置在離隧道口更遠一點的地方，在經(jīng)過傳感器后如果信號燈立即改變，有充分時間讓司機停車。（2分）2）用偽代碼設(shè)計該控制系統(tǒng)的軟件框架（描述每個進程的處理過程）。在你設(shè)計的軟件框架中，是否存在死鎖的可能？如果有的話，你如何處理死鎖問題？1.信號量定義typedefintsemph;semphLMutex=1;semphR

7、Mutex=1;semphConcur=1;intiL2RCount=0;intiR2LCount=0;左側(cè)汽車過隧道進程/記錄過隧道汽車數(shù)，對右側(cè)信號量進行P操作P(Concur);/在通過傳感器時開始P(LMutex);iL2RCount+;if(iL2RCount=1)P(RMutex);SetRLightRed();V(LMutex);V(Concur);/過隧道Pass_Bridge(L,R);/過隧道后的信號燈恢復(fù)P(LMutex);iL2RCount-;if(iL2RCount=0)V(RMutex);SetRLightGreen();V(LMutex);3.右側(cè)汽車過隧道進程與

8、左側(cè)類似。(6分)草稿區(qū)草稿區(qū)第 頁，共10頁第 頁，共10頁第 頁，共10頁7.虛擬存儲管理缺頁調(diào)度問題的分析（默認分值：10分）使用“分頁式”虛擬存儲管理技術(shù)，假設(shè)一個進程P的頁面訪問順序如下：012301401234。該進程創(chuàng)建時沒有加載任何頁面，即該進程啟動時其所有指令和數(shù)據(jù)都不在內(nèi)存中。1）設(shè)分配給該進程的物理頁幀為3個，使用FIFO頁面置換算法時，請問會發(fā)生多少次缺頁中斷？使用硬件實現(xiàn)的LRU算法，會發(fā)生多少次缺頁中斷？FIFO:9次（2分）當(dāng)前頁012301401234物理楨000333444444/11100000222/2221111133是否中斷替換頁/012301LRU:

9、10次（2分）當(dāng)前頁012301401234物理楨000333444222/11100000033/2221111114是否中斷替換頁/01234012）對于以上兩種頁面置換算法，如希望減少缺頁中斷的次數(shù)，是否可以通過增加物理頁幀來解決？為什么？FIFO在這種情況下不能減少缺頁中斷，反而會增加（列表說明）。這是Belady異?，F(xiàn)象。（2分）而LRU和其他如最優(yōu)置換算法這類為棧式算法，增加物理頁幀后必然能提高命中率。（2分）3）在分頁系統(tǒng)中將I/O設(shè)備的數(shù)據(jù)緩沖區(qū)映射到內(nèi)存空間后，其對應(yīng)的頁面是否能夠被替換？為什么？不行。因為I/O設(shè)備的數(shù)據(jù)緩沖區(qū)映射到內(nèi)存空間后，是虛擬的地址空間，并不真的存在

10、于內(nèi)存之中，因此不能進行頁面替換。（2分）8.I/O設(shè)備與I/O軟件問題的分析和解決（默認分值：12分）設(shè)有一臺32位計算機，使用單核CPU。你負責(zé)基于這臺計算機設(shè)計一種新的網(wǎng)卡驅(qū)動程序，網(wǎng)卡的數(shù)據(jù)緩沖區(qū)為1M大小，為了完成這個任務(wù)，你必須分析并解決以下問題：1）I/O軟件問題：用戶進程通過該網(wǎng)卡向局域網(wǎng)中的另一臺計算機發(fā)送數(shù)據(jù)，請遵循I/O軟件的層次和控制流程，描述用戶進程數(shù)據(jù)被保存到網(wǎng)卡緩沖區(qū)中的完整處理過程。注意：必須說明有哪些系統(tǒng)進程/服務(wù)進程參與，以及各自的作用。守護進程（daemonprocess）是用于假脫機（spooling）技術(shù)，使用在如打印機等獨占設(shè)備上；（6分）2）網(wǎng)卡的

11、工作模式如下：用戶發(fā)出一個系統(tǒng)調(diào)用，請求將數(shù)據(jù)發(fā)送到局域網(wǎng)的另一臺計算機上。然后操作系統(tǒng)將數(shù)據(jù)復(fù)制到一個內(nèi)核緩沖區(qū)中，再將數(shù)據(jù)復(fù)制到網(wǎng)卡的數(shù)據(jù)緩沖區(qū)中。當(dāng)所有數(shù)據(jù)都安全存放在網(wǎng)卡的數(shù)據(jù)緩沖區(qū)后，再將它們以每秒10M位的速率發(fā)送。接收端的網(wǎng)卡以每微妙1位的速率保存它們。當(dāng)最后一位被接受后，目標(biāo)計算機的CPU將被中斷。OS將新到達的數(shù)據(jù)包復(fù)制到內(nèi)核緩沖區(qū)中，并檢查該數(shù)據(jù)包屬于哪個接收進程，然后將數(shù)據(jù)復(fù)制到接收進程的內(nèi)存空間中。設(shè)每一個中斷及其相關(guān)的處理過程需花費1毫秒，數(shù)據(jù)包為1024字節(jié)（忽略包頭），并且復(fù)制一個字節(jié)花費1微秒時間。請問從發(fā)送進程提出請求，到接收進程獲得數(shù)據(jù)的最小時間間隔是多少？

12、1ms（系統(tǒng)調(diào)用，請求發(fā)出）+2*1024byte/（lbyte/us）（復(fù)制到網(wǎng)卡緩存）+1024byte/（10M*bit/s）（發(fā)送數(shù)據(jù)）+1024byte/（1bit/s）（接收數(shù)據(jù)）+1ms（接收完成，中斷）+2*1024byte/（1byte/us）（復(fù)制）（3分）草稿區(qū)大約15ms（1分）9.進程管理問題（默認分值：8分）設(shè)操作系統(tǒng)中的進程狀態(tài)有如下七個：New、Ready、Run、Blocked、Exit、SuspendReady、SuspendBlocked、Exit，請回答以下問題：1）請分析New、Exit和Suspend狀態(tài)的作用。New狀態(tài)指該進程的數(shù)據(jù)結(jié)構(gòu)已創(chuàng)建，但

13、內(nèi)存映像還沒有被加載。（1分）Exit狀態(tài)指該進程的全部工作已經(jīng)完成，但是由于被其他進程引用等原因，數(shù)據(jù)結(jié)構(gòu)還沒有刪除。（1分）Suspend狀態(tài)指該進程內(nèi)存映像已經(jīng)被替換出內(nèi)存。（1分）2）請描述在計算機中何時處理進程調(diào)度？如果采用多級隊列調(diào)度算法，請嘗試設(shè)計一個進程調(diào)度程序的軟件框架在創(chuàng)建一個新進程時；在某進程退出時；當(dāng)某進程被阻塞時；在一個I/O中斷發(fā)生時。如果在周期性提供時鐘中斷的系統(tǒng)中，可以在每k個時鐘中斷時做出調(diào)度策略。（2分）進程調(diào)度程序框架設(shè)計要點：使用多級隊列；動態(tài)優(yōu)先級調(diào)度；響應(yīng)時間短；防止饑餓。（5分）三、系統(tǒng)分析題（本題共三小題，共計25分，選做2題，多做題目不得分）請

14、在下面的表格中指定答題順序，在對應(yīng)的分值下列明題號。每格只許列出一個題號，否則做無效處理。必須寫明所有題目的題號，如果填寫不完全，視為不指定答題順序。如填寫內(nèi)容無效或者不填寫表格，則按照默認的題面分值評分第一題（15分）第二題（10分）10.文件系統(tǒng)綜合設(shè)計（默認分值：15分）假定你負責(zé)設(shè)計一個基于32位計算機的文件系統(tǒng)，如果存儲磁盤的容量是60G,磁盤扇區(qū)大小為1M,文件的最大容量為2GB,文件名僅支持8.3格式。該文件系統(tǒng)主要滿足商用I/O操作，因此空間變化比較頻繁，請設(shè)計一種合理的文件系統(tǒng)磁盤空間管理方式。包括目錄、文件的邏輯結(jié)構(gòu)與物理實現(xiàn)。結(jié)合操作系統(tǒng)教材上的方法設(shè)計，涉及東西較多，實

15、際上就是一個真實的文件系統(tǒng)了。由于用于商用I/O操作，需要對文件記錄進行頻繁的修改、增刪、查找等操作，并且可能使用到大的數(shù)據(jù)量，為了有序地管理目錄和文件，使用層次級的目錄結(jié)構(gòu)，對文件則選擇記錄序列的邏輯組織結(jié)構(gòu)。在物理實現(xiàn)時，選用i節(jié)點方式對文件目錄進行管理。磁盤塊分為功能塊以及數(shù)據(jù)塊，其中引導(dǎo)塊，超級塊，位圖塊以及i節(jié)點塊為功能塊，其余的為數(shù)據(jù)塊。超級塊記錄文件系統(tǒng)的信息。位圖塊用來管理磁盤塊的使用情況，位圖塊中的某個塊為“1”表示對應(yīng)的磁盤塊可用。i節(jié)點塊用于記錄文件以及目錄的信息。磁盤的第一個塊是引導(dǎo)塊，保留不用。超級塊是第二個磁盤塊。一個位圖塊有1M*8=8M個二進制位，能表示8M*1

16、M=8T的磁盤容量，所以只需一個位圖塊就能管理所有的磁盤塊。文件系統(tǒng)的目錄和文件不是固定的，所以i結(jié)點塊動態(tài)分配，一個塊能包含的i結(jié)點數(shù)與i結(jié)點的具體大小有關(guān)。一個文件最大是2G，也就是2K個磁盤塊草稿區(qū)草稿區(qū)第 #頁，共10頁第 頁，共10頁如果為每一個文件一次分配這么多塊，會造成資源的浪費，因此可以默認為每個文件分配一個小數(shù)量的磁盤塊，如果不夠，再申請磁盤塊，最多能申請2K個。11.操作系統(tǒng)綜合設(shè)計（默認分值：15分）假設(shè)你需要為某企業(yè)設(shè)計一個分時操作系統(tǒng)，請回答以下問題：1）你認為哪些系統(tǒng)進程最重要？時鐘中斷，設(shè)備驅(qū)動，shell,idle。文件系統(tǒng)服務(wù)。安全認證進程。根該系統(tǒng)具體負責(zé)的

17、主要工作有關(guān)系，記錄日志的進程，數(shù)據(jù)保存和處理系統(tǒng)等。災(zāi)難恢復(fù)進程。2）如果該操作系統(tǒng)主要負責(zé)處理IO-Bounded進程，你認為系統(tǒng)性能的瓶頸可能是什么？如何解決？如果時間片過短，則進程調(diào)度占用時間比例過大。進程調(diào)度瓶頸。如果使用時間片輪轉(zhuǎn)算法，時間片長度會成為瓶頸，如果時間片過長，則無法滿足頻繁調(diào)度的需求文件系統(tǒng)，查找文件，讀寫文件。建立索引。內(nèi)存，頁面替換瓶頸。10速度瓶頸。數(shù)據(jù)同步問題等，采用DMA，I/OChannel等機制都可以的。草稿區(qū)草稿區(qū)第 頁，共10頁第 #頁，共10頁12.系統(tǒng)安全分析(默認分值：10分)操作系統(tǒng)的安全性越來越重要，為了實現(xiàn)對數(shù)據(jù)和信息的安全保護，在操作系統(tǒng)設(shè)計過程中，需要設(shè)計很多方法技術(shù)。請回答以下問題：1)從內(nèi)存管理的角度分析，可以有哪些安全保護手段？基于段的管理：每個段有基地址，有段限長，有特權(quán)級。只有滿足一定特權(quán)級要求的進程才可以訪問該段，并且只能訪問段限長大小之內(nèi)的數(shù)據(jù)。在PSW中加入對內(nèi)存的控制信息，如上下界保護法