【正文】 習貫徹 “ 三個代表 ” 重要思想，學習黨的十六屆四中全會精神，自覺用 “ 三個代表 ” 重要思想指導工作，進一步加強黨支部的建 設，在工作中較好的發(fā)揮了政治核心和戰(zhàn)斗堡壘作用，工會黨支部工作總結。 數(shù)據同步問題等， 采用 DMA ， I/O Channel 等機制都可以的。 內存 ，頁面替換 瓶頸 。 文件系統(tǒng) ，查找文件，讀寫文件 。 2) 如果該操作系統(tǒng)主要負責處理 IOBounded 進程，你認為系統(tǒng)性能的瓶頸可能是什么？如何解決？ 進程調度瓶頸。 12 文件系統(tǒng)服務。 2) 為防止某些數(shù)據文件被非法訪問，可以有哪些保護手段？ 保護域，對進程進行約束，讓進程在某保護域中執(zhí)行，由保護域限制進程訪問的數(shù)據； 存取控制表，對文件進行約束，在訪問文件數(shù)據時按存取控制表進行檢測； 權限表 ， 存儲 進程對各文件的操作權限 ； 目錄、文件、磁盤扇區(qū)的加密。請回答以下問題： 1) 從內存管理的角度分析，可以有哪些安全保護手段？ 在 PSW 中加入對內存的控制信息 ，如 上下界保護法，為每一個進程設立上下界寄存器，里面存放著被保護程序和數(shù)據的起始地址和終止地址 ； 在 頁表 中增加對訪問的限制位 ，如 保護鍵法為每一個被保護的存儲塊分配一個單獨的保護鍵 ； 第三種方法結合第一種，當 CPU處于用戶態(tài)時使用第 一種方案的方法。 在物理實現(xiàn)時，選用 i 節(jié)點方式對文件目錄進行管理。 結合操作系統(tǒng)教材上的方法設計，涉及東西較多，實際上就是一個真是的文件系統(tǒng)了。該文件系統(tǒng)主要滿足商用 I/O 操作，因此空間變化比較頻繁，請設計一種合理的文件系統(tǒng)磁盤空間管理方式。 ? 本部分只需選做 2 題，多做題目不加分。 ? 必須寫明所有題目的題號，如果填寫不完全，視為不指定答題順序。 (5 分 ) 第三部分：系統(tǒng)分析題（共 3 題，選做 2 題，共 25 分） ? 請在下面的表格中指定答題順序，在對應的分值下列明題號。 如果在周期性提供時鐘中斷的系統(tǒng)中，可以在每 k個時鐘中斷時做出調度策略。 (1 分 ) 2） 請描述在計算機中何時處理進程調度？如果采用多級隊列調度算法，請嘗試設計一個進程調度程序的軟件框架。(1 分 ) Exit 狀態(tài)指 該進程的全部工作已經完成，但是由于被其他進程引用等原因，數(shù)據結構還沒有刪除。請問從發(fā)送進程提出請求，到接收進程獲得數(shù)據的最小時間間隔是多少？ interrupt Hardware driver User process Device independence I/O請求 I/O響應 System call libraries, daemon process such as spooling Naming, protection, sharing Error handling, registers setting Handle I/O interrupt 9 1ms(系統(tǒng)調用，請求發(fā)出 )+2*1024byte/(1byte/us)(復制到網卡緩存 )+1024byte/(10M*bit/s)( 發(fā)送數(shù)據 )+1024byte/(1bit/s)( 接收數(shù)據 )+1ms(接收完成，中斷 )+2*1024byte/(1byte/us)(復制 ) (3 分 ) 大約 15ms (1 分 ) 9. 進程管理問題（默認分值： 8 分） 設操作系統(tǒng)中的進程狀態(tài)有如下七個： New、 Ready、 Run、 Blocked、Exit、 Suspend Ready、 Suspend Blocked，請回答以下問題： 1） 請分析 New、 Exit 和 Suspend 狀態(tài)的作用 。 OS 將新到達的數(shù)據包復制到內核緩沖區(qū)中，并檢查該數(shù)據包屬于哪個接收進程，然后將數(shù)據復制到接收進程的內存空間中。接收端的網卡以每微 秒 1 位的速率保存它們。然后操作系統(tǒng)將數(shù)據復制到一個內核緩沖區(qū)中，再將數(shù)據復制到網卡的數(shù)據緩沖區(qū)中。注意：必 須說明有哪些系統(tǒng)進程 /服務進程參與，以及各自的作用。 (2 分 ) 8. I/O 設備與 I/O 軟件問題的分析和解決（默認分值： 12 分） 設有一臺 32 位計算機，使用單核 CPU。 (2 分 ) 3）在分頁系統(tǒng)中將 I/O 設備的數(shù)據緩沖區(qū)映射到內存空間后，其對應的頁面是否能夠被替換？為什么 ？ 不行。這 是 Belady異?，F(xiàn)象。該進程創(chuàng)建時沒有加載任何頁面，即該進程啟動時其所有指令和數(shù)據都不在內存中。 (6 分 ) 3） 在你設計的軟件框架中，是否存在死鎖的可 能？如果有的話，你如何處理死鎖問題？ 不會產生死鎖。 } V(LMutex)。 if(iL2RCount == 0) { V(RMutex)。 // 過隧道后的信號燈 恢復 P(LMutex)。 V(Concur)。 SetRLightRed()。 iL2RCount++。 2. 左側 汽車過隧道進程 // 記錄過隧道猴子數(shù)，對右側信號量進行 P 操作 P(Concur)。 int iL2RCount = 0。 semph RMutex = 1。 答案參考猴子過橋問題： 1. 信號量定義 typedef int semph。信號燈位置在隧道口前，傳感器位置得 分 車道 車道 車道 車道 隧道 5 在離隧道口更遠一點的地方，在經過傳感器后如果信號燈立即改變，有充分時間讓司 機停車。 隧道是兩邊車的競爭條件?？刂葡到y(tǒng)使用一 個單核多線程 CPU作為處理器，并在隧道兩端設置信號燈如下：綠燈表示行進，紅燈表示停止。為了避免事故的發(fā)生，需要設計一套傳感和信號系統(tǒng)。 ? 必須寫明所有題目的題號，如果填寫不完全，視為不指定答題順序。 (每個 1 分 ) 4 第二部分：編程計算題（共 4 題，必做，共 45 分） ? 請在下面的表格中指定答題順序，在對應的分值下列明題號。 (3 分 ) 5. 請列出至少 6 種你認為合理的 CPU性能評價參數(shù)。記錄式文件將文件中的記錄按照一定的方式進行排列，從而形成不同的邏輯結構，用戶方便對其進行修改、追加、查找等功能。 )(2 分 ) 4. 文件的邏輯結構分為幾種形式？文件的磁盤布局分為幾種形式？ 文件的邏輯結構主要分兩大類：字符流式的無結構文件和記錄式的有結構文件。 (3 分 ) 采用分頁 (Paging)、分段 (Segment)一類技術，通過對內存面面的調度來實現(xiàn)。操作系統(tǒng)通過某種方案來將當前使用的那部分數(shù)據方法內存中，而將其他部分放在磁盤上。 (2 分 ) 這種方式驅動 I/O 和中斷驅動 I/O 的最主要的區(qū)別在于不再需要CPU的參與。 DMA，即直接存儲器存取， 是指在外設和存儲器之間開辟一個直接得 分 2 的數(shù) 據通道，數(shù)據傳輸由另外的 DMA 控制器 來完成 (2 分 )。(每個 1 分 ) 非剝奪式調度算法： 先來先服務，最短作業(yè)優(yōu)先 等 。 。 剝奪式調度： 操作系統(tǒng)按照進程調度算法控制多個進程分享 CPU，使得 CPU在多個進程之間進行切換，這種機制叫做剝奪式調度。 1 南開大學信息技術科學學院考試卷 20202020 年度第一學期期末 操作系統(tǒng) A 卷（共 16 頁） 專業(yè) ▁▁▁▁ 年級 ▁▁▁ 學號 ▁▁▁▁ 姓名 ▁▁▁▁ 成績 ▁▁▁▁ 考生 注意：請將答案寫在空白的答題紙上，答題時標明題號。 第一部分：簡答題（共 30 分，每題 6 分） 答題要求：請用簡潔 精練 的文字回答以下問題 1. 進程調度的策略分為剝奪式調度和不可剝奪式調度，請簡要解釋兩種策略的含義以及差別，并對每種調度策略列出至少兩種對應的調度算法。 (定義1 分 ) 而非剝奪式調度是指： 進程一旦占用 CPU，就會一直運行到結束，其他進程只能等待該進程釋放 CPU 后才能依次占用 CPU，這種機制叫非剝奪式調度。 (定義 1 分 ) 剝奪式調度算法 ：時間片輪轉 ，優(yōu)先級調度 ，最短剩余時間優(yōu)先 等 。 (每個 1 分 ) 2. 請簡要解釋 DMA 機制的工作方式，并分析 DMA 驅動 I/O 與中斷驅動 I/O 的差別。 DMA 控制器在開始傳輸之前獲取目的地址，由 DMA 控制器控制外設將數(shù)據寫入存儲器 。 (2 分 ) 3. 虛擬存儲管理的內在思想是什么？從技術角度如何實現(xiàn)這種思想？ 虛擬存儲器的思想是：程序 、數(shù)據、堆棧的總大小可能超過可用的物理內存的總大小。虛擬存儲器管理的本質是利用了程序數(shù)據的局部性原理。 (1 分 )(具體解釋略。 (2 分 )字符流式的文件管理簡單，用戶操作較為簡單，常見的如源代碼文件、目標代碼文件等。 (1 分 ) 文件的磁盤布局是指文件存儲在磁盤上的具體實現(xiàn)方式，主要有連續(xù)分配 、鏈表分配、在內存中采用表的鏈表分配（索引文件）、 i 結點等幾種方式。 主頻、 倍頻、外頻、 指令集、 流水線條數(shù) 、前端總線 頻率 、一級數(shù) 3 據 cache、 一級指令 cache、 二級 cache 等。每格只許列出一個題號，否則做無效處理。 ? 如填寫內容無效或者不填寫表格 ，則按照默認的答題順序評分 第一題（ 15分） 第二題（ 12分） 第三題（ 10分） 第四題（ 8 分） 6. 進程同步互斥與死鎖問題的解決（默認分值： 15 分） 有一條南北雙向的國家公路，其中一段路程共享一個單車道的隧道，行駛的汽車到達隧道入口處時，沒有迎面而來的汽車時才能使用隧道。當一輛汽車接近隧道時，傳感器通過 Arrive 函數(shù)向信號控制系統(tǒng)傳遞汽車運行的方向參數(shù)；當一輛汽車離開隧道時，傳感器通過 Depart 函數(shù)向信號控制系統(tǒng)傳遞汽車的運行參數(shù)。 圖 1 是該問題的示意圖： 請回答以下問題： 1） 分析該問題中存在的同步和互斥關系，并確定需要使用幾個傳感器和信號燈，說明使用方式和設置位置。 (1 分 ) 使用兩個傳感器和兩個信號燈，分別在左右進入隧道的路上每條路上設置一個傳感器和一個信號燈。 (2 分 ) 2） 用偽代碼設計該控制系統(tǒng)的軟件框架（描述每個進程的處理過程）。 semph LMutex = 1。 semph Concur = 1。 int iR2LCount = 0。 // 在通過傳感器時開始 P(LMutex)。 if(iL2RCount == 1) { P(RMutex)。 } V(LMutex)。 // 過隧道 Pass_Bridge(L,R)。 6 iL2RCount。 SetRLightGreen()。 3. 右側汽車過隧道進程與左側類似。 (1 分 ) 7. 虛擬存儲管理 —— 缺頁調度問題的分析（默認分值： 12 分） 使用“分頁式”虛擬存儲管理技術，假設一個進程 P 的頁面訪問順序如下： 0 1 2 3 0 1 4 0 1 2 3 4。 1）設分配給該進程的物理頁幀為 3 個，使用 FIFO 頁面置換算法時，請問會發(fā)生多少次缺頁中斷？使用硬件實現(xiàn)的 LRU 算法，會發(fā)生多少次缺頁中斷？ FIFO: 9 次 (2 分 ) 當前頁 0 1 2 3 0 1 4 0 1 2 3 4 物理楨 0 0 0 3 3 3 4 4 4 4 4 4 / 1 1 1 0 0 0 0 0 2 2 2 / / 2 2 2 1 1 1 1 1 3 3 是否中斷 ● ● ● ● ● ● ● ● ● 替換頁 / / / 0 1 2 3 0 1 LRU: 10 次 (2 分 ) 當前頁 0 1 2 3 0 1 4 0 1 2 3 4 物理楨 0 0 0 3 3 3 4 4 4 2 2 2 / 1 1 1 0 0 0 0 0 0 3 3 / / 2 2 2 1 1 1 1 1 1 4 7 是否中斷 ● ●