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