【正文】 斷次數(shù)為 12次，缺頁率 60% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預(yù)先裝入 先進(jìn)先出置換算法舉例說明 113 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 114 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 最近最久未使用置換算法 LRU ? 基本思想 ? 以“最近的過去”作為“最近的將來”的近似，選擇最近一段時(shí)間最長時(shí)間未被訪問的頁面淘汰出內(nèi)存 ? 評價(jià) ? 適用于各種類型的程序，性能較好，但需要較多的硬件支持 115 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 ? 某進(jìn)程分配獲得三個(gè)物理塊 ? 缺頁中斷次數(shù)為 9次，缺頁率 45% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預(yù)先裝入 最近最久未使用置換算法舉例說明 116 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 最近最久未使用置換算法硬件支持 — 移位寄存器 B R R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 1 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 117 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 最近最久未使用置換算法硬件支持 — 棧 4 4 7 4 7 0 7 4 0 7 0 4 7 1 7 0 4 1 0 1 7 4 0 1 0 7 4 1 2 1 0 7 4 2 1 2 0 7 4 1 2 1 0 7 4 2 6 2 1 0 7 6 ? 某進(jìn)程分配獲得五個(gè)物理塊 頁面訪問序列 118 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 119 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 簡單 Clock置換算法 (NRU) 塊號 頁號 頁面 訪問位 指針 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1 查尋指針 入口 返回 查尋指針 前移指向下一表目 選擇該頁淘汰 頁面訪問位 =0？ 置頁面 訪問位為 0 是 否 120 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 改進(jìn)型 Clock置換算法 ? 基本思想 ① 從查尋指針當(dāng)前位置起掃描內(nèi)存分頁循環(huán)隊(duì)列，選擇 A=0且 M=0的第一個(gè)頁面淘汰；若未找到，轉(zhuǎn)② ② 開始第二輪掃描，選擇 A=0且 M=1的第一個(gè)頁面淘汰，同時(shí)將經(jīng)過的所有頁面訪問位置 0；若不能找到，轉(zhuǎn)① ? 評價(jià) ? 與簡單 Clock算法相比，可減少磁盤的 I/O操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描，故實(shí)現(xiàn)算法自身的開銷增大 121 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 122 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 最少使用置換算法 LFU ? 基本思想 ? 為內(nèi)存各頁設(shè)置一移位寄存器用于記錄對應(yīng)被訪頻率，并選擇在最近時(shí)期使用次數(shù)最少的頁面淘汰 ? 評價(jià) ? 鑒于僅用移位寄存器有限各位來記錄頁面使用會導(dǎo)致訪問一次與訪問多次的等效性，本算法并不能真實(shí)全面地反映頁面使用情況 123 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 124 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面緩沖算法 PBA ? 基本思想 ? 設(shè)立空閑頁面鏈表和已修改頁面鏈表 ? 采用可變分配和基于先進(jìn)先出的局部置換策略，并規(guī)定被淘汰頁先不做物理移動(dòng)，而是依據(jù)是否修改分別掛到 空閑頁面鏈表 或 已修改頁面鏈表 的末尾 ? 空閑頁面鏈表同時(shí)用于物理塊分配 ? 當(dāng)已修改頁面鏈表達(dá)到一定長度如 64個(gè)頁面時(shí)，一起將所有已修改頁面寫回磁盤，故可顯著減少磁盤 I/O操作次數(shù) 125 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 126 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 127 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第四章 存儲器管理 內(nèi)存管理概述 連續(xù)分配存儲管理方式 基本分頁存儲管理方式 基本分段存儲管理方式 虛擬存儲器概念及關(guān)鍵技術(shù) 請求分頁存儲管理方式 請求分段存儲管理方式 128 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分段存儲管理方式 請求分段中的硬件支持 分段共享 分段保護(hù) 129 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 段表機(jī)制 ? 段表項(xiàng)的擴(kuò)充 段名 段長 分段基址 存取方式 訪問字段 修改位 狀態(tài)位 增補(bǔ)位 外存地址 起始 盤塊號 130 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 地址變換機(jī)構(gòu) ? 在分段系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，增加缺段中斷產(chǎn)生和處理并分段置換功能而構(gòu)成 ? 地址變換過程要領(lǐng) ? 從段表找到對應(yīng)分段的段表項(xiàng)獲悉該段尚未調(diào)入內(nèi)存時(shí)，應(yīng)產(chǎn)生缺段中斷，請求操作系統(tǒng)從外存把該段調(diào)入內(nèi)存 ? 關(guān)于快表和段表的檢索及表項(xiàng)修改 131 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分段系統(tǒng)地址變換 訪問 [S][W] S段表長度 且W分段長度 ？ 修改分段 S對應(yīng)段表項(xiàng)訪問字段和修改位 形成內(nèi)存物理地址 (A) = (分段基址 ) + (W) 返回 是 否 分段越界中斷處理 存取方式合法 ？ 是 否 分段保護(hù)中斷處理 分段 S在內(nèi)存 ？ 是 否 請求缺段中斷處理 132 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 缺段中斷機(jī)構(gòu)及處理過程 虛段 S不在內(nèi)存 保護(hù) CPU現(xiàn)場 內(nèi)存中有合適的空閑區(qū)？ 查找空閑分區(qū) (鏈 )表 從外存讀入虛段 S 修改段表及空閑分區(qū) (鏈 )表 恢復(fù) CPU現(xiàn)場 返回 是 否 內(nèi)存空閑分區(qū)容量能否滿足？ 空閑分區(qū)拼接以形成一個(gè)合適的空閑區(qū)，并修改空閑分區(qū) (鏈 )表 是 否 淘汰若干實(shí)段以形成一個(gè)合適的空閑區(qū)，同時(shí)修改段表及空閑分區(qū) (鏈 )表 133 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分段存儲管理方式 請求分段中的硬件支持 分段共享 分段保護(hù) 134 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 共享段表 ? 共享進(jìn)程計(jì)數(shù) ? 存取控制字段 ? 共享段不同段號 … 共享段 表項(xiàng) i … 段名 段長 分段 基址 狀態(tài)位 外存 地址 進(jìn)程名 進(jìn)程號 段號 存取控制字段 … … … … 共享進(jìn)程計(jì)數(shù) count 分段共享進(jìn)程描述 共享段表 135 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 共享段的分配與回收 ? 共享段的分配 ? 對于第一個(gè)請求使用某共享段的進(jìn)程，由系統(tǒng)為該共享段進(jìn)行內(nèi)存區(qū)的分配和裝入，同時(shí)把共享段信息填入對應(yīng)進(jìn)程段表中，并在共享段表中為之增加一個(gè)表項(xiàng)和填寫相關(guān)內(nèi)容；對于以后其它進(jìn)程提出共享該段要求，則僅需對對應(yīng)的進(jìn)程段表表項(xiàng)及共享段表表項(xiàng)修正即可 ? 共享段的回收 ? 與共享段分配過程恰好相逆 136 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分段存儲管理方式 請求分段中的硬件支持 分段共享 分段保護(hù) 137 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 越界檢查與存取控制檢查 ? 越界檢查 ? 段號及段內(nèi)地址合法性檢查 ? 存取控制檢查 ? 段表中對應(yīng)表項(xiàng)存取控制字段為依據(jù) ? 通常訪問方式包括只讀、只執(zhí)行（既不可讀也不可寫）、讀 /寫三種 ? 共享段的存取控制應(yīng)對不同進(jìn)程賦予不同權(quán)限，既要保證信息安全，又要滿足運(yùn)行需要 138 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 環(huán)保護(hù)機(jī)構(gòu) ? 程序間控制傳輸 ? 一個(gè)程序可調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù) ? 數(shù)據(jù)訪問 ? 一個(gè)程序可訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù) 環(huán) 0 環(huán) 1 調(diào)用 環(huán) 2 返回 調(diào)用 返回 環(huán) 0 環(huán) 1 環(huán) 2 數(shù)據(jù)訪問 數(shù)據(jù)訪問 139 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 請求分段存儲管理方式 請求分段中的硬件支持 分段共享 分段保護(hù) 140 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第四章 存儲器管理 內(nèi)存管理概述 連續(xù)分配存儲管理方式 基本分頁存儲管理方式 基本分段存儲管理方式 虛擬存儲器概念及關(guān)鍵技術(shù) 請求分頁存儲管理方式 請求分段存儲管理方式 141 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 作業(yè)題 ? 談?wù)勀銓λ梨i的概念、產(chǎn)生原因及其必要條件的認(rèn)識與理解。同時(shí)并就死鎖的各種處理策略展開討論。 ? 在課本關(guān)于銀行家算法的例子中，如果 P0發(fā)出的請求量由 Request0 (0,2,0)改為 Request0 (0,1,0)，問系統(tǒng)可否將資源分配給它？ 142 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 《 操作系統(tǒng)實(shí)踐 》 實(shí)驗(yàn) 5 ? 銀行家算法設(shè)計(jì)、實(shí)現(xiàn)及模擬性測試： I. 運(yùn)用銀行家算法和死鎖避免策略實(shí)現(xiàn)系統(tǒng)資源的安全分配；事先約定系統(tǒng)提供的資源類型及數(shù)量明細(xì)；隨機(jī)發(fā)生進(jìn)程創(chuàng)建事件（伴隨最大需求向量）、資源請求事件（伴隨資源申請向量）及撤銷事件。 II. 撰寫實(shí)驗(yàn)報(bào)告，闡述實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)?zāi)繕?biāo)、實(shí)驗(yàn)步驟、技術(shù)難點(diǎn)及解決方案、關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法流程、測試方案與過程及運(yùn)行效果、結(jié)論與體會等。 2022年 10月 23日星期日 同學(xué)們，再見！