【正文】 高等學校 操作系統(tǒng)課程廬山研討班 北京大學信息學院 陳向群 2020， 07 OS課程習題、小測驗、考試與小論文設計 操作系統(tǒng)課程暑期研討班 第五單元 習題設計與安排 ? 課程形式 主課、習題課、專題課、課堂討論 作業(yè)、小論文、源代碼分析、上機實習 ? 考試：筆試 小考試（ 3次） 期末考試 常見題型 ? 選擇題（單選題、多選題） ? 填空題 ? 判斷題 ? 簡答題（問答題） √ ? 應用題 √ ? 綜合題 √ ? Liunx源代碼題 √ ? Windows實習題 √ ? P、 V操作題 √ 應用題 1 ? 作業(yè)管理 ? 作業(yè)調度算法應用（單道、多道） ? 進程管理 ? 進程調度算法應用 ? 存儲管理 ? 可變分區(qū)存儲管理方案 空閑區(qū)分配與回收、移動技術應用 ? 頁式存儲管理方案（頁表構成、頁面分配回收） ? 虛擬頁式存儲管理方案 頁面置換算法應用（ FIFO、 LRU、 OPT） 應用題 2 ? 文件管理 ? 文件目錄檢索、改善 ? 文件的物理結構 ? 記錄的成組和分解 ? 磁盤空間管理 ? 文件系統(tǒng)可靠性 ? 文件系統(tǒng)性能（磁盤調度 [移臂調度、旋轉調度 ]，信息的優(yōu)化分布） ? 死鎖 ? 銀行家算法應用 ? 死鎖檢測 ? 資源分配圖 單道批處理方式下的作業(yè)調度 1 假設有三個作業(yè)，它們的進入時間及估計運行時間如下： 作業(yè)號 進入時刻 估計運行時間 1 10： 00 60分鐘 2 10： 10 60分鐘 3 10： 25 15分鐘 在單道批處理方式下，采用先來先服務算法和最短作業(yè)優(yōu)先算法進行作業(yè)調度。請給出它們的調度順序，并分別計算出作業(yè)平均周轉時間和帶權平均周轉時間。請對計算結果進行解釋。 平均周轉時間： 平均帶權周轉時間： 作業(yè)號 進入時間 執(zhí)行時間 開始時間 完成時間 周轉時間 帶權周轉時間 1 10： 00 60分鐘 10： 00 11： 00 60分鐘 2 10： 10 60分鐘 11： 00 12： 00 110分鐘 11/6 3 10： 25 15分鐘 12： 00 12： 15 110分鐘 110/15 答案：先來先服務算法 單道批處理方式下的作業(yè)調度 2 調度順序： 1， 3， 2 平均周轉時間： 平均帶權周轉時間： 作業(yè)號 進入時間 執(zhí)行時間 開始時間 完成時間 周轉時間 帶權周轉時間 1 10： 00 60分鐘 10： 00 11： 00 60分鐘 2 10： 10 60分鐘 11： 15 12： 15 125分鐘 25/12 3 10： 25 15分鐘 11： 00 11： 15 50分鐘 10/3 最短作業(yè)優(yōu)先算法 單道批處理方式下的作業(yè)調度 3 兩道批處理方式下的作業(yè)調度 1 有一個兩道的批處理操作系統(tǒng)，作業(yè)調度采用最短作業(yè)優(yōu)先的調度算法，進程調度采用基于優(yōu)先數(shù)的搶占式調度算法，有如下的作業(yè)序列： 作業(yè) 進入時間 估計運行時間 優(yōu)先數(shù) JOB1 10： 00 40分鐘 5 JOB2 10： 20 30分鐘 3 JOB3 10： 30 50分鐘 4 JOB4 10： 50 20分鐘 6 其中，優(yōu)先數(shù)數(shù)值越小優(yōu)先級越高。 （ 1）列出所有作業(yè)進入內存時間及運行結束時間； （ 2）計算作業(yè)平均周轉時間和帶權平均周轉時間。 進入內存 運行時間段 周轉時間 Job1 10:00 10:0010:20 10:5011:10 70 Job2 10:20 10:2010:50 30 Job3 11:10 11:1012:00 90 Job4 10:50 12:0012:20 90 平均周轉時間： (70+30+90+90)/4=70 帶權平均周轉時間： (70/40+30/30+90/50+90/20)/4= 答案： 兩道批處理作業(yè)，作業(yè)調度采用最短作業(yè)優(yōu)先，進程調度采用基于優(yōu)先級的搶占式調度同時允許兩個程序存在于主存中 兩道批處理方式下的作業(yè)調度 2 多道批處理方式下的作業(yè)調度 1 某系統(tǒng)采用不能移動已在內存儲器中作業(yè)的可變分區(qū)方式管理內存儲器，現(xiàn)有供用戶使用的內存空間 100K，系統(tǒng)配有 4臺磁帶機，有一批作業(yè)如下： 作業(yè) 進入時間 估計運行時間 內存需要 磁帶機需要 JOB1 10： 00 25分鐘 15K 2臺 JOB2 10： 20 30分鐘 60K 1臺 JOB3 10： 30 10分鐘 50K 3臺 JOB4 10： 35 20分鐘 10K 2臺 JOB5 10： 40 15分鐘 30K 2臺 該系統(tǒng)采用多道程序設計技術，對磁帶機采用靜態(tài)分配，忽略設備工作時間和系統(tǒng)進行調度所共花的時間，請分別寫出采用“先來先服務調度算法”和“最短作業(yè)優(yōu)先算法”選中作業(yè)執(zhí)行的次序以及作業(yè)平均周轉時間。 若允許移動已在內存中的作業(yè)，則作業(yè)被選中的次序又是怎樣的呢？計算出作業(yè)平均周轉時間。 答案： 先來先服務： （ 25＋ 35＋ 70＋ 40＋ 50） /5=44 最短作業(yè)優(yōu)先： (25+35+70+55+30)/5=43 多道批處理方式下的作業(yè)調度 2 多道系統(tǒng)進程平均周轉時間的計算 有 5個批處理作業(yè) A到 E幾乎同時到達計算中心。它們的估計運行時間分別為 10， 6， 2， 4和 8分鐘。其優(yōu)先數(shù)（由外部設定）分別為 3， 5， 2， 1和 4，其中 5級為最高優(yōu)先級。對于下列每種調度算法，計算其平均進程周轉時間，可忽略進程切換的開銷。 （ 1）優(yōu)先級調度 （ 2）先來先服務（按照次序 10， 6， 2， 4， 8運行） （ 3）最短作業(yè)優(yōu)先 對（ 1）到（ 3）假設任一時刻只有一個作業(yè)運行，直到結束。所有的作業(yè)都是 CPU密集型作業(yè)。 答案： （ 1）（ 6+14+24+26+30） /5=20分鐘 （ 2）（ 10+16+18+22+30） /5= （ 3）（ 2+6+12+20+30） /5=14分鐘 可變分區(qū)存儲管理方案 ? 內存管理 ?空閑塊表 —— 記錄了空閑區(qū)起始地址和長度 ?已分配區(qū)表 ? 內存分配 動態(tài)分配 三種分配算法： 首先適配、最佳適配、最差適配 0K 15K 38K 48K 68K 80K 110K 120K 空閑區(qū)表 已分配區(qū)表 始址 長度 標志 15K 23K 未分配 48K 20K 未分配 80K 30K 未分配 空 空 始址 長度 標志 0K 15K J1 38K 10K J2 68K 12K J3 110K 10K J4 空 空 0K 15K 38K 48K 68K 80K 110K 120K 空閑區(qū)表 已分配區(qū)表 始址 長度 標志 15K 23K 未分配 48K 20K 未分配 98K 12K 未分配 空 空 始址 長度 標志 0K 15K J1 38K 10K J2 68K 12K J3 110K 10K J4 80K 5K J5 85K 13K J6 85K 98K 段式存儲管理方案下，空閑塊分配的計算 1 有一個操作系統(tǒng)采用段式存儲管理方案，用戶區(qū)內存為 512K，分配時截取空閑塊的前半部分 (小地址部分 )。初始時內存全部空閑。系統(tǒng)執(zhí)行如下申請、釋放操作序列。 申請 300K，申請 100K，釋放 300K，申請 150K，申請 50K，申請 90K （ 1）若采用首先適應算法，空閑塊表中有哪些空塊？ 請指出大小，地址； （ 2）若采用最佳適應算法，空閑塊表中有哪些空塊？ 指出大小，地址； （ 3）若隨后又申請 80K，針對上述兩種情況說明結果？其結果說明了什么問題？ 答案： （ 1） 200K300K為空閑塊， 490K512K為空閑塊 （ 2） 240K300K為空閑塊， 4