【正文】 頁號 物理塊號 段表 段號 頁表長度 + 頁表始址 狀態(tài) 越界中斷 ≦ 79 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 基本分段存儲管理方式 分段存儲管理方式的引入 分段系統(tǒng)的基本原理 信息共享 段頁式存儲管理方式 80 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 第四章 存儲器管理 內(nèi)存管理概述 連續(xù)分配存儲管理方式 基本分頁存儲管理方式 基本分段存儲管理方式 虛擬存儲器概念及關鍵技術 請求分頁存儲管理方式 請求分段存儲管理方式 81 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 常規(guī)存儲管理問題與對策 ? 要求將一個作業(yè)全部裝入內(nèi)存方能運行 ? 一些對內(nèi)存空間要求超過內(nèi)存容量的大作業(yè)因不能全部裝入內(nèi)存而無法運行 ? 同時有大量作業(yè)要求運行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，則只能將少數(shù)作業(yè)裝入內(nèi)存首先運行，而將其它大量作業(yè)留在外存上等待 ? 解決方法 ? 增加物理內(nèi)存容量（系統(tǒng)成本和機器條件） ? 從邏輯上擴充內(nèi)存容量 =虛擬存儲技術 82 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 一次性全部裝入及駐留性問題 ? 作業(yè)“一次性”全部裝入內(nèi)存并不必要 ? 許多作業(yè)在每次運行時并非用到其全部程序和數(shù)據(jù) ? 作業(yè)常駐內(nèi)存存在不合理性 ? 因輸入輸出操作尚未完成而處于長期等待狀態(tài)的運行進程或某些一次性運行程序?qū)氋F內(nèi)存資源的占據(jù) ? 問題后果 ? 使一些需要運行的作業(yè)無法裝入運行，從而嚴重降低內(nèi)存利用率和減少系統(tǒng)吞吐量 83 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 局部性原理 ? 程序在執(zhí)行時將呈現(xiàn)局部性規(guī)律，即在一較短時間內(nèi)，程序的執(zhí)行僅限于某個部分；相應地，它所訪問的內(nèi)存空間也僅局限于某個區(qū)域 ? 程序在大多數(shù)情況下的順序執(zhí)行特點 ? 過程調(diào)用深度及執(zhí)行軌跡 ? 程序循環(huán)結構執(zhí)行及數(shù)據(jù)結構操作特點 ? 局部性表現(xiàn)形式 ? 時間局部性（指令執(zhí)行與數(shù)據(jù)結構訪問） ? 空間局部性（存儲單元臨近訪問） 84 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 虛擬存儲器技術要點 ? 作業(yè)部分裝入內(nèi)存即可啟動運行 ? 其余部分暫留磁盤 ? 程序執(zhí)行過程頁段訪問機制 ? 已調(diào)入內(nèi)存則直接訪問 ? 尚未調(diào)入內(nèi)存則缺頁 /段中斷及請求調(diào)入 ? 頁段置換功能 ? 技術效果 ? 大用戶程序在小內(nèi)存空間的運行 ? 多道程序度的提高 85 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 虛擬存儲器的定義 ? 所謂虛擬存儲器，是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)。 86 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁虛擬存儲系統(tǒng) ? 技術構成 ? 分頁 + 請求調(diào)頁 + 頁面置換 ? 硬件支持 ? 請求分頁的頁表機制 ? 缺頁中斷機構 ? 地址變換機構 ? 軟件支持 ? 請求調(diào)頁 ? 頁面置換 87 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分段虛擬存儲系統(tǒng) ? 技術構成 ? 分段 + 請求調(diào)段 + 分段置換 ? 硬件支持 ? 請求分段的段表機制 ? 缺段中斷機構 ? 地址變換機構 ? 軟件支持 ? 請求調(diào)段 ? 分段置換 88 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 虛擬存儲器的特征 ? 離散性 ? 離散分配方式 ? 多次性 ? 作業(yè)被分成多次調(diào)入內(nèi)存和運行 ? 對換性 ? 程序和數(shù)據(jù)在作業(yè)運行過程中的換進 /出 ? 虛擬性 ? 內(nèi)存容量的邏輯擴充 89 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 第四章 存儲器管理 內(nèi)存管理概述 連續(xù)分配存儲管理方式 基本分頁存儲管理方式 基本分段存儲管理方式 虛擬存儲器概念及關鍵技術 請求分頁存儲管理方式 請求分段存儲管理方式 90 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 91 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁表機制 ? 頁表項的擴充 頁號 物理塊號 狀態(tài)位 訪問字段 修改位 外存地址 92 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 缺頁中斷機構 ? 缺頁中斷之中斷特征 ? 保護 CPU現(xiàn)場 ? 分析中斷原因 ? 轉(zhuǎn)入缺頁中斷處理程序 ? 恢復 CPU現(xiàn)場 ? 缺頁中斷之特殊性 ? 在指令執(zhí)行期間產(chǎn)生和處理中斷信號 ? 一條指令執(zhí)行期間，可能產(chǎn)生多次缺頁中斷 6 5 4 1 2 3 頁面 copy A TO B B: A: 93 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 地址變換機構 ? 在分頁系統(tǒng)的地址變換機構的基礎上，增加缺頁中斷產(chǎn)生和處理并頁面置換功能而構成 ? 地址變換過程要領 ? 從頁表找到對應分頁的頁表項獲悉該頁尚未調(diào)入內(nèi)存時，應產(chǎn)生缺頁中斷，請求操作系統(tǒng)從外存把該頁調(diào)入內(nèi)存 ? 關于快表和頁表的檢索及表項修改 94 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁系統(tǒng)地址變換過程 程序請求訪問一頁 CPU檢索快表 找到否？ 訪問頁表 是 否 頁在內(nèi)存？ 否 產(chǎn)生缺頁中斷請求調(diào)頁 是 修改頁表對應頁表項訪問字段和修改位 形成物理地址 地址變換結束 頁號有效？ 是 否 越界 中斷 修改快表 95 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁面中斷處理算法流程 保護 CPU現(xiàn)場 缺頁中斷處理 從外存中找到缺頁 內(nèi)存滿否？ 從內(nèi)存選擇某頁換出 是 否 該頁被修改否？ 是 將該頁寫回外存 否 命令 CPU從外存讀取缺頁 啟動 I/O硬件 將缺頁從外存換入內(nèi)存 修改頁表相應表項 狀態(tài)位及物理塊號 返回 恢復 CPU現(xiàn)場 96 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 97 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 最小物理塊數(shù)的確定 ? 保證進程正常運行所需的最少物理塊數(shù) ? 若系統(tǒng)為某進程分配的物理塊數(shù)少于此值，進程將無法正常運行 ? 不同于使進程有效工作所需的物理塊數(shù) ? 與計算機的硬件結構有關，并取決于指令的格式（操作數(shù)個數(shù)）、功能和尋址方式（直接 /間接） 98 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 物理塊分配與置換策略 ? 固定分配局部置換 ? 為每個進程分配一固定頁數(shù)的內(nèi)存空間，在整個運行期間都不再改變 ? 可變分配全局置換 ? 系統(tǒng)設立一個空閑物理塊隊列 ? 可變分配局部置換 ? 依據(jù)缺頁率酌情增加或減少物理塊 99 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 物理塊分配算法 ? 平均分配算法 ? 將系統(tǒng)可供分配的物理塊平均分配 ? 按比例分配算法 ? BlockOfPk = max{minBlocks, Blocks ? PagesOfPk/?PagesOfPi} ? 考慮優(yōu)先權的分配算法 ? 照顧重要或緊迫的作業(yè)能盡快完成 100 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 101 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 何時調(diào)入頁面 ? 預調(diào)頁策略 ? 將那些預計在不久之后便會被訪問的程序或數(shù)據(jù)所在的頁面，預先調(diào)入內(nèi)存 ? 以預測為基礎，主要用于進程首次調(diào)入 ? 請求調(diào)頁策略 ? 當進程在運行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，應立即提出請求，由系統(tǒng)將其所需頁面調(diào)入內(nèi)存；易于實現(xiàn)但系統(tǒng)開銷大 102 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 何處調(diào)入頁面 ? 對換區(qū)空間充分 ? 進程運行前，便須將與該進程有關的文件，從文件區(qū)拷貝到對換區(qū) ? 對換區(qū)空間不足 ? 文件是否修改分別處理 ? UNIX方式 ? 凡未運行過的頁面都應從文件區(qū)調(diào)入，而對于曾運行過又被換出到對換區(qū)的頁面則從對換區(qū)調(diào)入 103 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁面調(diào)入過程 ? 缺頁中斷發(fā)生 ? 程序所訪問的頁面不在內(nèi)存時產(chǎn)生缺頁中斷并轉(zhuǎn)入缺頁中斷處理程序 ? 根據(jù)頁表外存地址調(diào)入所缺頁面 ? 頁表項外存地址（物理塊號） ? 內(nèi)存不足置換 ? 頁面淘汰算法 ? 是否重寫磁盤 104 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 105 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 106 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 抖動與缺頁率 ? 抖動的定義 ? 如果所用置換算法不當，便可能導致這樣一種情形：剛被換出的頁面很快又被訪問，需重新調(diào)入，為此，又需再選一頁換出；而此剛被換出的頁面，不久也被訪問，故又需將它調(diào)入，如此頻繁地更換頁面，以致一個進程在運行中把大部分的時間耗費在頁面置換的工作上，稱該進程發(fā)生了抖動（或稱之為顛簸） ? 缺頁率 ? 缺頁率 = 缺頁中斷次數(shù) /頁面訪問次數(shù) 107 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 108 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 最佳置換算法 ? 基本思想 ? 選擇永不使用或是在最長時間內(nèi)不再被訪問（即距現(xiàn)在最長時間才會被訪問）的頁面淘汰出內(nèi)存 ? 評價 ? 理想化算法，具有最好性能（對于固定分配頁面方式，本法可保證獲得最低的缺頁率），但實際上卻難于實現(xiàn)，故主要用于算法評價參照 109 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 最佳置換算法舉例說明 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 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 ? 某進程分配獲得三個物理塊 ? 缺頁中斷次數(shù)為 6次，缺頁率 30% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預先裝入 110 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 111 2022年 10月 23日星期日 北京交通大學計算機學院 翟高壽 先進