《《虛擬存儲器》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《虛擬存儲器》PPT課件（53頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、4.6 虛 擬 存 儲 器 的 基 本 概 念4.6.虛 擬 存 儲 器 的 引 入1. 問 題 的 提 出 程 序 大 于 總 內(nèi) 存 多 道 程 序 要 運(yùn) 行 內(nèi) 存 只 能 容 納 部 分 作 業(yè) 要 解 決 上 述 問 題 必 須 改 變 常 規(guī) 存 儲 器 管 理方 式 中 作 業(yè) 一 次 性 裝 入 和 運(yùn) 行 時 的 駐 留 性 。 OS把 程 序 當(dāng) 前 使 用 的 部 分 代 碼 和 數(shù) 據(jù) 保 留在 內(nèi) 存 中 , 而 把 其 它 部 分 存 在 磁 盤 上 , 需 要 時 在內(nèi) 存 和 磁 盤 之 間 動 態(tài) 對 換 , 以 解 決 上 述 問 題 ; 這就 是 虛 擬

2、 存 儲 器 的 基 本 思 想 。 2. 程 序 局 部 性 原 理 在 一 段 時 間 內(nèi) 一 個 程 序 的 執(zhí) 行 往 往 呈 現(xiàn)出 高 度 的 局 部 性 , 順 序 執(zhí) 行 的 多 , 過 程 調(diào) 用 , 循 環(huán) 結(jié) 構(gòu) , 對 數(shù) 組 操 作 等 等 。 表 現(xiàn) 為 : 時 間 局 部 性 ： 一 條 指 令 被 執(zhí) 行 了 ， 則 在 不 久 的 將 來 它可 能 再 被 執(zhí) 行 ?？?間 局 部 性 ： 若 某 一 存 儲 單 元 被 使 用 ， 則 在 一 定 時 間內(nèi) , 與 該 存 儲 單 元 附 近 的 單 元 可 能 被 使 用 。 3. 虛 擬 存 儲 技 術(shù) 以

3、 CPU時 間 和 外 存 空 間 換 取 昂 貴 內(nèi) 存 空間 , 這 是 操 作 系 統(tǒng) 中 的 資 源 轉(zhuǎn) 換 技 術(shù) 。實 現(xiàn) 思 想 : 當(dāng) 進(jìn) 程 運(yùn) 行 時 , 先 將 一 部 分 程 序 裝入 內(nèi) 存 , 另 一 部 分 暫 時 留 在 外 存 , 當(dāng) 要 執(zhí) 行 的指 令 不 在 內(nèi) 存 時 , 由 系 統(tǒng) 自 動 將 它 們 從 外 存 調(diào)換 到 內(nèi) 存 。 即 具 有 請 求 調(diào) 入 和 置 換 功 能 。虛 擬 存 儲 器 定 義 : 具 有 請 求 調(diào) 入 和 置 換 功 能 ,對 內(nèi) 存 容 量 擴(kuò) 充 , 得 到 一 個 邏 輯 容 量 等 于 內(nèi) 存與 外 存

4、容 量 之 和 的 “ 虛 內(nèi) 存 ” 。 頁 號 P 頁 內(nèi) 位 移 量 W31 11 04. 虛 擬 地 址 結(jié) 構(gòu)頁 的 大 小 =？頁 的 多 少 =？虛 存 的 大 小 =？ CPUMMU 內(nèi) 存 磁 盤控 制 器 總 線CPU把 虛 地 址 送 給 MMU MMU把 物 理 地 址 送 給 存 儲 器 4.6.2 虛 擬 存 儲 器 的 實 現(xiàn) 方 式請 求 分 頁 方 式分 段 請 求 方 式硬 件 支 持 ：請 求 分 頁 (段 )的 頁 (段 )表 機(jī) 構(gòu)缺 頁 (段 )中 斷 機(jī) 構(gòu)請 求 分 頁 (段 )的 地 址 變 換 機(jī) 構(gòu) 4.6.3 虛 擬 存 儲 器 的 特

5、征離 散 性 : 是 實 現(xiàn) 虛 擬 存 儲 器 的 基 礎(chǔ)多 次 性 : 多 次 將 部 分 調(diào) 入 內(nèi) 存 , 每 當(dāng) 運(yùn) 行 到 不在 內(nèi) 存 那 部 分 程 序 時 ,再 將 它 調(diào) 入交 換 性 : 暫 時 不 執(zhí) 行 允 許 換 出 , 需 要 時 再 換 入虛 擬 性 : 邏 輯 (虛 )上 擴(kuò) 充 了 內(nèi) 存 物 理 (實 )容 量 虛 擬 性 以 多 次 性 和 交 換 性 為 基 礎(chǔ) ,多 次 性 和交 換 性 又 必 須 建 立 在 離 散 分 配 的 基 礎(chǔ) 之 上 。 4.7 請 求 分 頁 式 存 儲 管 理 在 進(jìn) 程 開 始 運(yùn) 行 之 前 , 不 是 裝 入

6、全 部 頁 面 ,而 是 裝入 一 個 或 零 個 頁 面 , 之 后 根 據(jù) 進(jìn) 程 運(yùn) 行 的 需 要 , 動 態(tài) 裝入 其 它 頁 面 ; 當(dāng) 內(nèi) 存 空 間 已 滿 ,而 又 需 要 裝 入 新 的 頁 面時 , 則 根 據(jù) 某 種 算 法 淘 汰 某 個 頁 面 , 以 便 裝 入 新 頁 面 。4.7.1 硬 件 支 持 及 工 作 過 程1、 頁 表 機(jī) 制狀 態(tài) 位 P： 表 示 該 頁 是 在 內(nèi) 存 還 是 在 外 存訪 問 位 ： 記 錄 該 頁 在 一 段 時 間 內(nèi) 被 訪 問 的 次 數(shù)修 改 位 ： 查 看 此 頁 是 否 在 內(nèi) 存 中 被 修 改 過內(nèi) 存 塊

7、 號 狀 態(tài) 位 訪 問 位 修 改 位 外 存 地 址 頁 號 .44K X40K X36K 532K X28K X24K 320K 416K 012K X 8K 1 4K 2 0K 虛 地 址 空 間物 理 地 址 空 間 虛 頁 頁 框 20K 16K 12K 8K 4K 0K. 24K 2、 缺 頁 中 斷 機(jī) 構(gòu) 在 地 址 映 射 過 程 中 , 在 頁 表 中 發(fā) 現(xiàn) 所 要 訪問 的 頁 不 在 內(nèi) 存 , 則 產(chǎn) 生 缺 頁 中 斷 。 操 作 系 統(tǒng)接 到 此 中 斷 信 號 后 , 就 調(diào) 出 缺 頁 中 斷 處 理 程 序 ,根 據(jù) 頁 表 中 給 出 的 外 存 地

8、址 , 將 該 頁 調(diào) 入 內(nèi) 存 ,使 進(jìn) 程 繼 續(xù) 運(yùn) 行 下 去 。 如 果 內(nèi) 存 中 有 空 閑 塊 , 則 分 配 一 頁 將 新 調(diào)入 頁 裝 入 內(nèi) 存 , 并 修 改 頁 表 中 相 應(yīng) 頁 表 項 目 的駐 留 位 及 相 應(yīng) 的 內(nèi) 存 塊 號 。 若 此 時 內(nèi) 存 中 沒 有空 閑 塊 , 則 要 淘 汰 某 頁 , 若 該 頁 在 內(nèi) 存 期 間 被 修改 過 , 則 要 將 其 寫 回 外 存 。 保 留 CPU現(xiàn) 場從 外 存 找 到 缺 頁內(nèi) 存 滿 ?修 改 過 ?選 擇 一 頁 換 出將 該 頁 寫 回 外 存發(fā) 命 令 從 外 存 讀 缺 頁啟 動 I

9、/O硬 件將 一 頁 從 外 存 換 入 修 改 頁 表 頁 越 界 ? 檢 索 快 表命 中 ?訪 問 頁 表修 改 快 表在 內(nèi) 存 ?修 改 訪 問 位 修 改 位形 成 物 理 地 址 開 始N繼 續(xù) Y中 斷NY越 界中 斷NYN Y 缺 頁中 斷 Y 影 響 缺 頁 次 數(shù) 的 因 素(1) 分 配 給 進(jìn) 程 的 物 理 頁 面 數(shù)(2) 頁 面 本 身 的 大 小(3) 程 序 的 編 制 方 法(4) 頁 面 淘 汰 算 法 4.7.2 頁 面 分 配 與 置 換請 求 調(diào) 頁 中 操 作 系 統(tǒng) 提 供 的 支 持 請 求 調(diào) 頁 時 , 把 所 需 的 頁 從 外 存 調(diào)

10、 入 內(nèi) 存 置 換 時 , 將 內(nèi) 存 的 某 些 頁 調(diào) 至 外 存問 題 ：進(jìn) 程 正 常 運(yùn) 行 所 需 的 最 少 物 理 塊 是 多 少 ？每 個 進(jìn) 程 分 配 的 物 理 塊 數(shù) 是 固 定 的 嗎 ？每 個 進(jìn) 程 分 配 的 物 理 塊 數(shù) 依 據(jù) 是 什 么 ？ 1. 最 小 物 理 塊 數(shù) 的 確 定 最 小 物 理 塊 數(shù) 與 硬 件 結(jié) 構(gòu) 、 指 令 格 式 、 尋址 方 式 有 關(guān) 。 直 接 尋 址 方 式 最 少 塊 數(shù) 為 2 間 接 尋 址 方 式 最 少 塊 數(shù) 為 3 功 能 較 強(qiáng) 的 機(jī) 器 最 少 塊 數(shù) 為 62. 頁 面 分 配 和 置 換

11、 策 略 (固 定 分 配 、 可 變 分 配 ) 1) 固 定 分 配 局 部 置 換 系 統(tǒng) 中 駐 留 的 進(jìn) 程 數(shù) 與 分 配 給 進(jìn) 程 的 頁 數(shù) 是 什 么關(guān) 系 ？ （ 正 比 ？ 反 比 ？ ） 塊 數(shù) 太 多 會 出 現(xiàn) 什 么 問 題 ？ 塊 數(shù) 太 少 會 出 現(xiàn) 什 么 問 題 ？ 2) 可 變 分 配 全 局 置 換 空 閑 物 理 塊 由 誰 管 理 ？ (OS?進(jìn) 程 ？ ） 缺 頁 中 斷 時 從 何 處 獲 得 空 閑 頁 ？ 調(diào) 入 調(diào) 出 什 么 時 候 發(fā) 生 （ 空 閑 頁 用 完 還 是 給 進(jìn) 程分 配 的 頁 用 完 ？ ）3) 可 變 分

12、配 局 部 置 換 為 每 個 進(jìn) 程 所 分 配 的 物 理 塊 數(shù) 相 對 固 定 從 每 個 進(jìn) 程 所 分 配 的 頁 面 中 進(jìn) 行 換 入 換 出 。 從 全 局 的 角 度 動 態(tài) 調(diào) 整 每 個 進(jìn) 程 所 分 配 的 頁 面 3. 分 配 算 法 (固 定 分 配 策 略 ） 平 均 分 配 算 法 駐 留 內(nèi) 存 的 進(jìn) 程 平 均 分 配 , 貌 似 公 平 , 實 際不 公 平 , 長 進(jìn) 程 缺 頁 率 高 按 比 例 分 配 算 法 按 駐 留 內(nèi) 存 的 進(jìn) 程 的 大 小 比 例 分 配 , 較 公 平 考 慮 優(yōu) 先 權(quán) 的 分 配 算 法 整 個 內(nèi) 存 分

13、 為 兩 部 分 , 一 部 分 按 比 例 分 配 , 另 一 部 分 按 優(yōu) 先 權(quán) 分 配 , 照 顧 到 重 要 緊 迫 的進(jìn) 程 盡 快 完 成 4.7.3 頁 面 調(diào) 入 策 略什 么 時 候 調(diào) 入 ？ 從 何 處 調(diào) 入 ？ 怎 么 調(diào) 入 ？1.什 么 時 候 調(diào) 入 預(yù) 調(diào) 入 策 略 : 一 次 調(diào) 入 若 干 相 鄰 頁 (預(yù) 計 即 將 運(yùn) 行的 頁 )比 單 頁 調(diào) 入 效 率 高 , 命 中 率 約 50%。 請 求 調(diào) 頁 策 略 : 缺 頁 時 提 出 請 求 , OS將 所 需 一 頁 調(diào)入 內(nèi) 存 , 易 于 實 現(xiàn) , I/O啟 動 頻 率 高 系 統(tǒng)

14、開 銷 大 。2. 從 何 處 調(diào) 入 頁 面 -外 存 分 為 文 件 區(qū) 和 對 換 區(qū) (I/O快 )系 統(tǒng) 有 足 夠 的 對 換 區(qū) 時 , 運(yùn) 行 前 全 部 從 文 件 區(qū) 調(diào) 入對 換 區(qū) , 運(yùn) 行 中 全 部 從 對 換 區(qū) 調(diào) 入 所 需 頁 。系 統(tǒng) 缺 少 足 夠 的 對 換 區(qū) 時 , 不 會 被 修 改 的 頁 從 文 件區(qū) 調(diào) 入 , 會 被 修 改 的 頁 從 對 換 區(qū) 調(diào) 入 換 出 。UNIX:未 運(yùn) 行 過 的 頁 從 文 件 區(qū) 調(diào) 入 , 換 出 到 對 換 區(qū) 3. 頁 面 調(diào) 入 過 程 當(dāng) 程 序 所 要 訪 問 的 頁 不 在 內(nèi) 存 時

15、, 向 CPU發(fā) 出 缺 頁 中 斷 , 中 斷 處 理 程 序 首 先 保 留 CPU環(huán)境 , 再 通 過 查 找 頁 表 得 到 該 頁 在 外 存 的 物 理 塊號 。 此 時 如 果 內(nèi) 存 未 滿 ,則 將 該 頁 調(diào) 入 內(nèi) 存 并修 改 頁 表 ,若 內(nèi) 存 已 滿 ,則 從 內(nèi) 存 中 選 出 一 頁 準(zhǔn)備 換 出 , 如 果 該 頁 已 被 修 改 則 還 需 將 它 寫 回 外存 , 然 后 再 把 所 缺 頁 調(diào) 入 內(nèi) 存 并 修 改 相 應(yīng) 的 頁表 項 , 置 器 存 儲 位 為 1并 將 此 頁 表 項 寫 入 快 表 。整 個 調(diào) 入 過 程 對 用 戶 是 透

16、 明 的 。 好 的 頁 面 置 換 算 法 應(yīng) 具 有 低 的 頁 面 更 換 頻 率 最 佳 置 換 算 法 先 進(jìn) 先 出 算 法 最 近 最 久 未 使 用 LRU 算 法 CLOCK算 法頁 面 緩 沖 算 法4.7.4 頁 面 置 換 算 法 1. 最 佳 置 換 算 法淘 汰 永 不 使 用 或 最 長 時 間 內(nèi) 不 再 被 訪 問 的 頁 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 7 0 0 0 0 4 0 0 0 1 1 3 3 3 1 1 無 法 實 現(xiàn) , 只 能 用 它 做 評 價 標(biāo) 準(zhǔn) 。2.

17、先 進(jìn) 先 出 置 換 算 法 簡 單 易 行 沒 有 考 慮 訪 問 頻 度 的 差 別 , 不 能 保 證 經(jīng)常 訪 問 的 頁 不 被 淘 汰 。 3. 最 近 最 久 未 使 用 LRU 算 法淘 汰 在 最 近 最 久 未 使 用 的 頁 面 。 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 4 4 4 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 1 1 3 3 2 2 2 2 2 7如 何 確 定 哪 一 頁 是 最 近 最 久 未 使 用 的 頁 ？1） 移 位 寄 存 器 為 每 個 在 內(nèi) 存 的 頁 面

18、配 置 一 個 移 位 寄 存 器 ,當(dāng) 訪 問某 頁 時 將 相 應(yīng) 的 寄 存 器 最 高 位 置 1, 每 隔 一 定 時 間 將 寄存 器 右 移 1位 ,將 寄 存 器 存 的 數(shù) 看 作 一 個 整 數(shù) ,顯 然 最 小值 的 寄 存 器 對 應(yīng) 的 頁 就 是 最 近 最 久 未 使 用 的 頁 。 2） 特 殊 棧 用 特 殊 棧 保 存 當(dāng) 前 在 內(nèi) 存 的 各 頁 面 號 , 棧 的 大 小等 于 分 配 的 物 理 塊 數(shù) , 當(dāng) 前 訪 問 頁 號 始 終 保 持 在 棧 頂 , 棧 底 就 是 最 近 最 久 未 使 用 的 頁 號 。 缺 頁 中 斷 時 若 棧

19、未滿 則 將 新 頁 號 壓 棧 , 若 棧 滿 則 淘 汰 棧 底 元 素 , 所 有 元 素下 移 再 將 新 頁 號 壓 棧 。 如 訪 問 頁 號 的 順 序 為 ： 4， 7， 0， 7， 1， 0， 2， 1， 6分 配 的 物 理 塊 數(shù) 為 4， 則 棧 中 頁 面 號 變 化 情 況 如 下 ： 4 1704 704 074 744 7 0 7 1 0 2 1 60174 2017 1207 6120 4. Linux 的 LRU算 法 最 初 分 配 某 個 頁 時 , 頁 的 壽 命 為 3, 每 次 頁 被 訪 問 , 其 壽 命 增 加 3, 直 到 20為 至 。

20、當(dāng) 內(nèi) 核 的 交 換 進(jìn) 程 運(yùn) 行時 (kswapd周 期 運(yùn) 行 ), 在 內(nèi) 存 的 所 有 頁 面 壽 命 減 1。 如果 某 個 頁 的 壽 命 為 0， 則 該 頁 作 為 交 換 候 選 頁 。 5. 簡 單 的 CLOCK置 換 算 法 每 頁 設(shè) 置 一 訪 問 位 A, 當(dāng) 某 頁 被 訪 問 時 , 其訪 問 位 A被 置 為 1。 將 內(nèi) 存 中 所 有 頁 面 都 通過 鏈 接 指 針 鏈 接 成 一 個 循 環(huán) 隊 列 , 進(jìn) 行 循 環(huán)檢 查 。如 果 頁 的 訪 問 位 A=0, 則 淘 汰 該 頁 ; 若 A=1, 則 重 新 將 A置 為 0,暫 不 換

21、出 而 給 該 頁 第 二 次駐 留 內(nèi) 存 的 機(jī) 會 。 繼 續(xù) 向 后 循 環(huán) 檢 查 , 直 到某 頁 訪 問 位 A=0, 則 淘 汰 之 。 6. 改 進(jìn) 的 CLOCK算 法 頁 面 換 出 時 ,如 果 該 頁 已 被 修 改 , 必 須 將 它 重 新 寫到 磁 盤 上 ; 但 如 果 該 頁 未 被 修 改 , 則 不 必 寫 回 磁 盤 。 改進(jìn) 的 CLOCK算 法 增 加 置 換 代 價 這 一 因 素 , 用 修 改 位 M表 示 , 優(yōu) 先 考 慮 M=0 (未 被 修 改 )的 頁 , 淘 汰 順 序 為 : A=0,M=0 A=0,M=1 A=1,M=0 A=

22、1,M=1其 執(zhí) 行 過 程 分 為 三 步 ：(1) 尋 找 A=0且 M=0, 找 到 則 淘 汰 該 頁 , A和 M都 不 變 。(2) 第 一 步 失 敗 , 則 進(jìn) 行 第 二 輪 掃 描 , 尋 找 A=0且 M=1, 找 到 則 淘 汰 該 頁 。 此 遍 將 所 有 經(jīng) 過 的 頁 面 A置 0；(3) 第 二 步 也 失 敗 , 則 此 時 所 有 頁 的 A=0。 重 復(fù) 第 一 步 , 如 果 仍 失 敗 , 再 重 復(fù) 第 二 步 , 一 定 能 找 到 被 淘 汰 的 頁 。 7. 頁 面 緩 沖 算 法 采 用 前 面 介 紹 過 的 可 變 分 配 局 部 置

23、換 方式 , 內(nèi) 存 中 一 部 分 作 為 頁 面 緩 沖 區(qū) , 將 緩 沖 區(qū)的 物 理 快 鏈 接 為 兩 個 鏈 表 空 閑 鏈 表已 修 改 頁 面 的 鏈 表 頁 面 緩 沖 算 法 頁 面 緩 沖 采 用 FIFO置 換 算 法 。 當(dāng) 需 要 讀 入 一 個 頁 面時 , 利 用 空 閑 鏈 表 的 第 一 個 物 理 快 裝 入 該 頁 。 如 果 被 淘 汰 的 頁 面 未 被 修 改 , 就 將 它 直 接 鏈 接 到 空 閑鏈 表 表 尾 , 否 則 , 則 將 其 鏈 接 到 已 修 改 的 鏈 表 表 尾 。 該頁 面 仍 留 在 內(nèi) 存 中 , 并 未 進(jìn) 行

24、實 際 的 換 出 。 當(dāng) 進(jìn) 程 再 次 訪 問 這 些 頁 面 時 , 只 需 花 費(fèi) 較 小 的 開 銷 ，使 該 頁 面 又 返 回 該 進(jìn) 程 的 駐 留 集 。 當(dāng) 被 修 改 頁 面 達(dá) 到 一 定 數(shù) 量 時 ， 再 將 它 們 一 起 寫 回磁 盤 。 顯 著 地 減 少 了 磁 盤 I/O的 次 數(shù) 。 4.7.5 請 求 分 頁 系 統(tǒng) 的 性 能 分 析1、 工 作 集 模 型 根 據(jù) 程 序 的 局 部 性 原 理 , 進(jìn) 程 在 一 段 時 間內(nèi) 一 般 總 是 集 中 訪 問 某 些 頁 面 , 這 些 頁 面 稱 為活 躍 頁 面 , 如 果 分 配 給 某 進(jìn)

25、 程 的 物 理 頁 面 數(shù) 太少 了 , 使 該 進(jìn) 程 所 需 的 活 躍 頁 面 不 能 全 部 裝 入內(nèi) 存 , 則 進(jìn) 程 在 運(yùn) 行 過 程 中 將 頻 繁 發(fā) 生 中 斷 。 在 某 段 時 間 內(nèi) , 進(jìn) 程 實 際 要 訪 問 的 頁 面 集合 稱 為 工 作 集 , 為 進(jìn) 程 分 配 的 物 理 頁 面 稱 為 工作 集 窗 口 , 顯 然 工 作 集 窗 口 尺 寸 越 大 缺 頁 中 斷次 數(shù) 越 少 ; 但 尺 寸 太 大 內(nèi) 存 利 用 率 就 會 下 降 。 2、 抖 動 在 虛 存 中 , 頁 面 在 內(nèi) 存 與 外 存 之 間 頻 繁 調(diào)度 , 以 至 于

26、調(diào) 度 頁 面 所 需 時 間 比 進(jìn) 程 實 際 運(yùn) 行的 時 間 還 多 , 此 時 系 統(tǒng) 效 率 急 劇 下 降 , 甚 至 導(dǎo)致 系 統(tǒng) 崩 潰 , 這 種 現(xiàn) 象 為 抖 動 。產(chǎn) 生 原 因 ：頁 面 淘 汰 算 法 不 合 理分 配 給 進(jìn) 程 的 工 作 集 窗 口 尺 寸 太 小出 現(xiàn) : CPU利 用 率 下 降 調(diào) 入 新 的 進(jìn) 程 從 其 它 進(jìn) 程 獲 得 物 理 塊 缺 頁 中 斷 次 數(shù) 增加 CPU利 用 率 進(jìn) 一 步 下 降 的 惡 性 循 環(huán) 2、 抖 動 的 預(yù) 防1) 采 取 局 部 置 換 策 略 , 不 允 許 從 其 它 進(jìn) 程 獲得 物 理

27、 塊 , 不 會 使 抖 動 擴(kuò) 大 到 其 它 進(jìn) 程 。2) 在 CPU調(diào) 度 中 引 入 工 作 集 算 法 在 調(diào) 度 程 序 從 外 存 調(diào) 入 新 作 業(yè) 時 , 必 須 檢查 內(nèi) 存 中 每 個 進(jìn) 程 的 工 作 集 窗 口 是 否 足 夠 大 , 是 才 能 調(diào) 入 ; 不 至 于 因 新 作 業(yè) 調(diào) 入 擴(kuò) 大 抖 動3) 調(diào) 整 多 道 度 , 使 產(chǎn) 生 缺 頁 的 平 均 時 間 (L)等于 系 統(tǒng) 處 理 進(jìn) 程 缺 頁 的 平 均 時 間 (S)。 課 后 題 P142 16、 17、 18、 19 4.8 請 求 分 段 存 儲 管 理 方 式 4.8.1 硬

28、件 支 持 及 工 作 過 程1、 段 表 內(nèi) 容 增 加 ： 存 在 位 (在 /不 在 內(nèi) 存 , 是 否 可 共 享 ), 存 取 權(quán) 限位 (只 執(zhí) 行 ,只 讀 , 可 讀 寫 ),訪 問 位 (被 訪 問 的 情 況 ),修改 位 (是 否 修 改 過 , 能 否 移 動 ), 增 補(bǔ) 位 (是 否 做 過 動 態(tài)增 長 ), 外 存 始 址 。2、 越 界 中 斷 處 理 進(jìn) 程 在 執(zhí) 行 過 程 中 , 有 時 需 要 擴(kuò) 大 分 段 , 如 數(shù) 據(jù)段 ; 由 于 要 訪 問 的 地 址 超 出 原 有 的 段 長 , 發(fā) 出 越 界 中斷 ; 操 作 系 統(tǒng) 處 理 中 斷

29、 時 , 首 先 判 斷 該 段 的 擴(kuò) 充 位 ,如 可 擴(kuò) 充 , 則 增 加 段 的 長 度 ; 否 則 按 出 錯 處 理 。 缺 段 中 斷 處 理 過 程 從 外 存 讀 入 段 S修 改 段 表 及 空 閑 鏈喚 醒 請 求 進(jìn) 程進(jìn) 行 緊 湊形 成 合 適 空 區(qū) 阻 塞 請 求 進(jìn) 程 空 閑 和 能 滿 足 ? 有 合 適 空 閑 區(qū) ?返 回虛 段 S不 在 內(nèi) 存淘 汰 實 段形 成 合 適 空 區(qū) N YN Y 3、 缺 段 中 斷 處 理 檢 查 內(nèi) 存 中 是 否 有 足 夠 的 空 閑 空 間 若 有 , 則 裝 入 該 段 , 修 改 有 關(guān) 數(shù) 據(jù) 結(jié) 構(gòu)

30、 , 中 斷 返 回 若 沒 有 , 檢 查 內(nèi) 存 中 空 閑 區(qū) 的 總 和 是 否 滿 足 要 求 ,是 則 應(yīng) 采 用 緊 縮 技 術(shù) , 轉(zhuǎn) a; 否 則 , 淘 汰 一 些 段 , 轉(zhuǎn) 4、 地 址 變 換 請 求 分 段 系 統(tǒng) 的 地 址 變 換 機(jī) 構(gòu) , 是 在 分 段 系 統(tǒng) 的地 址 變 換 機(jī) 構(gòu) 基 礎(chǔ) 上 , 增 加 缺 段 中 斷 的 請 求 和 處 理 等功 能 ,當(dāng) 發(fā) 現(xiàn) 要 訪 問 的 段 不 再 內(nèi) 存 時 , 必 須 將 該 段 調(diào) 入內(nèi) 存 并 修 改 段 表 , 然 后 才 能 用 段 表 進(jìn) 行 地 址 變 換 。 分 段 存 儲 管 理 方

31、式 便 于 實 現(xiàn) 分 段 的 共 享與 保 護(hù) , 只 需 在 每 個 進(jìn) 程 的 段 表 中 用 相 應(yīng) 的表 項 指 向 共 享 段 在 內(nèi) 存 的 起 始 地 址 。 為 了 管理 好 共 享 段 , 系 統(tǒng) 配 置 相 應(yīng) 的 數(shù) 據(jù) 結(jié) 構(gòu) 作 為共 享 段 表 。 共 享 段 表 共 享 段 的 分 配 和 回 收 分 段 保 護(hù)4.8.2 分 段 的 共 享 與 保 護(hù) 1. 共 享 段 表 系 統(tǒng) 為 所 有 共 享 段 配 置 一 張 共 享 段 表 , 每 個 共 享段 在 該 表 中 占 一 個 表 項 , 其 中 記 錄 了 段 號 、 段 長 、 內(nèi)存 始 址 、

32、存 在 位 等 信 息 , 同 時 還 記 錄 了 共 享 進(jìn) 程 計 數(shù)和 共 享 此 分 段 的 每 個 進(jìn) 程 的 情 況 。段 號 段 長 內(nèi) 存 始 址 存 在 位 外 存 始 址共 享 進(jìn) 程 計 數(shù) count狀 態(tài) 進(jìn) 程 名 進(jìn) 程 號 段 號 存 取 控 制共 享 段 表 共 享 段 表 項 2. 共 享 段 的 分 配 和 回 收共 享 段 的 分 配 對 第 一 個 請 求 使 用 該 共 享 段 的 進(jìn) 程 , 系 統(tǒng) 為 該 共 享段 分 配 一 物 理 區(qū) 并 把 共 享 段 調(diào) 入 該 區(qū) , 同 時 把 該 區(qū) 的 始址 填 入 該 進(jìn) 程 的 段 表 中 ,

33、 還 需 在 共 享 段 表 中 增 加 一 表 項 , 填 寫 有 關(guān) 信 息 , 把 count置 為 1。 當(dāng) 又 有 其 它 進(jìn) 程 要 訪 問 該 共 享 段 時 , 只 需 在 訪 問 進(jìn)程 的 段 表 中 增 加 一 表 項 , 填 入 該 共 享 段 的 物 理 地 址 ; 并在 共 享 段 表 的 對 應(yīng) 表 項 中 , 填 寫 調(diào) 用 進(jìn) 程 名 和 存 取 控 制等 , 再 執(zhí) 行 count:= count+1 操 作 。共 享 段 的 回 收 取 消 該 進(jìn) 程 的 段 表 中 共 享 段 所 對 應(yīng) 的 表 項 ,并 執(zhí) 行count:= count-1, 結(jié) 果

34、為 0則 回 收 共 享 段 的 內(nèi) 存 并 取 消 該進(jìn) 程 在 共 享 段 表 中 對 應(yīng) 的 表 項 ; 否 則 僅 取 消 該 進(jìn) 程 在 共享 段 表 中 對 應(yīng) 的 紀(jì) 錄 。 3. 分 級 保 護(hù) 各 分 段 在 邏 輯 上 是 獨(dú) 立 的 , 容 易 實 現(xiàn) 信 息 保 護(hù)越 界 檢 查 在 分 段 系 統(tǒng) 的 地 址 變 換 機(jī) 構(gòu) 中 , 段 表 寄 存 器 和 段 表項 都 有 段 長 度 信 息 , 越 界 時 會 發(fā) 出 越 界 中 斷 。存 取 控 制 檢 查 段 表 項 中 設(shè) 置 了 存 取 控 制 字 段 , 其 訪 問 方 式 有 ： 只 讀 、 只 執(zhí) 行

35、 、 允 許 讀 寫環(huán) 保 護(hù) 機(jī) 構(gòu) 它 是 一 種 優(yōu) 先 權(quán) 保 護(hù) 機(jī) 制 , 規(guī) 定 低 編 號 的 環(huán) 具 有 高優(yōu) 先 權(quán) , OS核 心 處 于 0環(huán) 內(nèi) , OS服 務(wù) 在 中 間 環(huán) , 一 般 的 應(yīng)用 程 序 安 排 在 外 環(huán) 上 。 調(diào) 用 和 訪 問 遵 循 ：程 序 可 訪 問 駐 留 在 相 同 環(huán) 或 較 低 優(yōu) 先 權(quán) 環(huán) 中 的 數(shù) 據(jù)程 序 可 調(diào) 用 駐 留 在 相 同 環(huán) 或 較 高 優(yōu) 先 權(quán) 環(huán) 中 的 服 務(wù) 為 了 程 序 能 正 確 執(zhí) 行 , 程 序 的 各 段 必 須 由 連 接 裝配 程 序 把 它 們 鏈 接 成 一 個 可 運(yùn)

36、行 的 目 標(biāo) 程 序 , 有 兩 種方 法 ：靜 態(tài) 鏈 接 : 在 程 序 運(yùn) 行 前 都 鏈 接 好 并 裝 入 內(nèi) 存 。 問 題 ： 花 費(fèi) 時 間 ， 浪 費(fèi) 空 間動 態(tài) 鏈 接 : 程 序 邊 鏈 接 邊 運(yùn) 行 優(yōu) 點(diǎn) ： 節(jié) 省 時 間 和 空 間 , 可 在 較 小 的 內(nèi) 存 上 運(yùn) 行較 大 的 程 序 , 用 不 到 的 段 不 用 鏈 接 頁 不 用 調(diào) 入 內(nèi) 存 。尤 其 是 對 于 大 型 程 序 優(yōu) 點(diǎn) 更 突 出 。4.8.3 段 的 動 態(tài) 鏈 接 1. 段 的 動 態(tài) 鏈 接 由 于 一 些 熟 知 的 事 實 ：大 型 程 序 一 般 分 為 多

37、個 程 序 段 和 多 個 數(shù) 據(jù) 段進(jìn) 程 的 某 些 程 序 段 在 進(jìn) 程 運(yùn) 行 期 間 可 能 根 本 不 用互 斥 執(zhí) 行 的 程 序 段 沒 有 必 要 同 時 駐 留 內(nèi) 存有 些 程 序 段 執(zhí) 行 一 次 后 不 再 用 到 所 以 , 沒 有 必 要 在 在 程 序 運(yùn) 行 前 都 鏈 接 好 , 程 序 開始 運(yùn) 行 時 , 只 將 主 程 序 段 裝 配 好 并 調(diào) 入 內(nèi) 存 , 其 它 各段 的 裝 配 是 在 運(yùn) 行 過 程 中 逐 步 完 成 的 。 每 當(dāng) 需 要 調(diào)用 一 個 新 段 時 , 再 將 這 個 新 段 裝 配 好 , 并 與 主 程 序 段鏈

38、 接 。 這 就 是 動 態(tài) 鏈 接 。 顯 然 ,頁 式 存 儲 管 理 是 難 以完 成 動 態(tài) 鏈 接 的 ; 應(yīng) 采 用 段 式 存 儲 管 理 。 2. 動 態(tài) 鏈 接 的 實 現(xiàn) 在 間 接 尋 址 中 設(shè) 置 鏈 接 間 接 字 和 鏈 接 中 斷 處 理 機(jī) 在 執(zhí) 行 間 接 指 令 時 , 其 硬 件 能 自 動 對鏈 接 字 中 鏈 接 標(biāo) 志 位 進(jìn) 行 判 斷 。 標(biāo) 志 位 =1 時 ，硬 件 自 動 發(fā) 鏈 接 中 斷 , 并 停 止 執(zhí) 行 該 間 接 指 令 ，轉(zhuǎn) 去 執(zhí) 行 鏈 接 中 斷 處 理 程 序 。 處 理 完 后 再 重 新執(zhí) 行 該 間 接 指

39、 令 。 3.鏈 接 中 斷 處 理 根 據(jù) 鏈 接 間 接 字 找 出 要 訪 問 段 的 符 號 名 和 段 內(nèi) 地 址 分 配 段 號 , 檢 查 該 段 是 否 在 內(nèi) 存 , 若 不 在 , 則 從 外 存 調(diào) 入 , 并 登 記 段 表 , 修 改 內(nèi) 存 分 配 表 修 改 間 接 字 : 修 改 連 接 標(biāo) 志 位 為 0, 修 改 直 接 地 址 重 新 啟 動 被 中 斷 的 指 令 執(zhí) 行 4.10 CPU高 速 緩 沖在 計 算 機(jī) 中 ， 為 了 減 少 CPU的 等 待 時 間 ，必 須 提 高 系 統(tǒng) 主 存 儲 器 的 響 應(yīng) 速 度為 此 使 用 了 高 速

40、緩 存 cache， 用 來 存 儲CPU常 用 的 代 碼 和 數(shù) 據(jù) 信 息 1. 工 作 原 理(1) 基 于 程 序 訪 問 的 局 部 性 分 析 表 明 , 在 較 短 的 時 間 間 隔 內(nèi) , 由 程 序 產(chǎn) 生 的 地 址往 往 集 中 在 存 儲 器 邏 輯 地 址 空 間 的 很 小 范 圍 內(nèi) 。 對 數(shù) 組 的 存 儲 和 訪 問 以 及 工 作 區(qū) 的 選 擇 都 使 存 儲 器地 址 相 對 集 中 。 對 局 部 范 圍 的 存 儲 器 頻 繁 訪 問 , 而 對 此 范 圍 以 外 的地 址 則 訪 問 甚 少 的 現(xiàn) 象 , 就 稱 為 程 序 訪 問 的

41、局 部 性 。(2) 高 速 緩 沖 存 儲 器 : 根 據(jù) 程 序 的 局 部 性 原 理 ,在 主 存 和CPU 通 用 寄 存 器 之 間 設(shè) 置 一 個 高 速 的 容 量 相 對 較 小 的高 速 存 儲 器 ,把 正 在 執(zhí) 行 的 指 令 地 址 附 近 的 一 部 分 指 令或 數(shù) 據(jù) 從 主 存 調(diào) 入 這 個 存 儲 器 ,供 CPU在 一 段 時 間 內(nèi) 使用 。 這 對 提 高 運(yùn) 行 速 度 有 很 大 的 作 用 。 (3)命 中 率 : CPU在 任 一 時 刻 從 高 速 緩 沖 中 直 接 可 靠 獲取 數(shù) 據(jù) 的 幾 率 。 命 中 率 越 高 ,直 接 獲

42、 取 數(shù) 據(jù) 的 可 靠 性 就 越 大 。 高 速 緩 沖 空 間 與 主 存 空 間 在 一 定 范 圍 內(nèi) 保 持 適 當(dāng) 比例 的 映 射 關(guān) 系 , 可 以 使 高 速 緩 沖 的 命 中 率 相 當(dāng) 高 。 一 般 情 況 , 高 速 緩 沖 與 內(nèi) 存 的 空 間 比 為 4:1000 即 128kB 高 速 緩 沖 可 映 射 32MB內(nèi) 存 256kB 高 速 緩 沖 可 映 射 64MB內(nèi) 存 在 這 種 情 況 下 ， 命 中 率 都 在 90 以 上 2.高 速 緩 沖 的 分 級 典 型 的 一 級 （ L1） 緩 存 系 統(tǒng) 的 80 的 內(nèi) 存 申 請 都發(fā) 生

43、在 CPU內(nèi) 部 。 只 有 20 的 內(nèi) 存 申 請 是 與 外 部 內(nèi) 存 打 交 道 。 而 這 20 的 外 部 內(nèi) 存 申 請 中 的 80 又 與 二 級 （ L2）緩 存 打 交 道 。 因 此 ， 只 有 4 的 內(nèi) 存 申 請 定 向 到 主 存 中 。 3.CPU高 速 緩 沖 的 重 要 性 PC系 統(tǒng) 的 發(fā) 展 趨 勢 之 一 : CPU主 頻 越 做 越 高 , 系 統(tǒng)架 構(gòu) 越 做 越 先 進(jìn) , 而 主 存 的 結(jié) 構(gòu) 和 存 取 時 間 改 進(jìn) 較 慢 。因 此 在 PC系 統(tǒng) 中 高 速 緩 存 越 做 越 大 。 高 速 緩 存 已 是 評價 和 選 購

44、PC系 統(tǒng) 的 一 個 重 要 指 標(biāo) 。 新 一 代 的 微 處 理 器 , 已 實 現(xiàn) 設(shè) 計 了 L1高 速 緩 存 , L2 高 速 緩 存 和 在 主 板 上 的 L3高 速 緩 存 。 比 如 :在 Intel Pentium III中 , L1高 速 緩 存 為 32 KB, L2可 從 512 KB到 1 MB。 而 AMD K6-III的 L1為 64KB，L2可 達(dá) 256KB, 外 部 L3 高 速 緩 存 可 達(dá) 1 MB。 1. 存 儲 管 理 目 的 充 分 利 用 內(nèi) 存 、 方 便 用 戶 使 用 、 程 序 可 比 內(nèi) 存 空 間 大 、 執(zhí) 行 時 可 動

45、態(tài) 伸 縮 、 存 儲 保 護(hù) 與 安 全 、 共 享 與 通 信 、 了 解 有 關(guān) 資 源 的 使 用 狀 況 、 實 現(xiàn) 性 能 高 時 空 開 銷 小 。2. 存 儲 管 理 的 內(nèi) 容 內(nèi) 存 空 間 的 管 理 、 分 配 與 回 收 、 存 儲 共 享 、 存 儲 保 護(hù) 與 安 全 、 內(nèi) 存 “ 擴(kuò) 充 ”3. 地 址 映 射 (地 址 重 定 位 , 地 址 變 換 ) 邏 輯 地 址 (相 對 ,虛 地 址 )物 理 地 址 (絕 對 ,實 地 址 ) 由 硬 件 實 現(xiàn) , 分 靜 態(tài) 重 定 位 、 動 態(tài) 重 定 位4. 分 區(qū) 存 儲 管 理固 定 分 區(qū) 、 可

46、 變 分 區(qū) (可 變 分 區(qū) 分 區(qū) 表 、 空 閑 分 區(qū) 鏈 ) 5. 分 區(qū) 分 配 算 法首 先 適 配 算 法 、 最 佳 適 配 算 法 、 最 壞 適 配 算 法 6.可 重 定 位 分 區(qū) 分 配 緊 湊 技 術(shù) 解 決 碎 片 問 題 ,重 定 位 寄 存 器 實 現(xiàn) 動 態(tài) 重 定 位7. 對 換 技 術(shù) 在 多 道 環(huán) 境 下 擴(kuò) 充 內(nèi) 存 的 方 法 , 小 內(nèi) 存 運(yùn) 行 大 程 序 。 對 換 的 單 位 ： 進(jìn) 程 對 換 、 分 段 對 換 、 頁 面 對 換 。8.頁 式 存 儲 管 理 (系 統(tǒng) 需 要 , 解 決 碎 片 ) 離 散 分 配 方 式 、

47、 頁 面 大 小 的 選 擇 建 進(jìn) 程 頁 表 、 空 塊 管 理 總 頁 表 、 內(nèi) 存 的 分 配 與 回 收 地 址 變 換 機(jī) 構(gòu) : 頁 表 寄 存 器 、 頁 表 、 快 表 (聯(lián) 想 寄 存 器 )9. 兩 級 和 多 級 頁 表 反 置 頁 表10. 段 式 存 儲 管 理用 戶 需 要 : 信 息 共 享 ,信 息 保 護(hù) ,動 態(tài) 增 長 ,動 態(tài) 鏈 接用 戶 程 序 劃 分 : 程 序 二 維 地 址 空 間 段 號 維 和 段 內(nèi) 地 址 維地 址 變 換 機(jī) 構(gòu) : 段 表 寄 存 器 、 段 表 、 快 表 (聯(lián) 想 寄 存 器 ) 11. 段 頁 式 存 儲

48、管 理 結(jié) 合 兩 者 之 優(yōu) 點(diǎn) 解 決 系 統(tǒng) 需 要 和 用 戶 需 要 用 戶 地 址 空 間 二 維 、 內(nèi) 存 分 配 方 式 分 頁 地 址 變 換 機(jī) 構(gòu) : 段 表 寄 存 器 、 段 表 、 頁 表 、 快 表12. 程 序 局 部 性 原 理 時 間 局 部 性 :指 令 被 執(zhí) 行 后 不 久 它 可 能 再 被 執(zhí) 行 。 空 間 局 部 性 :存 儲 單 元 使 用 后 不 久 附 近 單 元 可 能 被 使 用13. 虛 擬 存 儲 器 定 義 具 有 請 求 調(diào) 入 和 置 換 功 能 ,對 內(nèi) 存 容 量 擴(kuò) 充 , 得 到 一 個邏 輯 容 量 等 于 內(nèi)

49、存 與 外 存 容 量 之 和 的 “ 虛 內(nèi) 存 ” 。14. 虛 擬 存 儲 器 的 特 征 離 散 性 、 多 次 性 、 交 換 性 、 虛 擬 性 虛 擬 性 以 多 次 性 交 換 性 為 基 礎(chǔ) , 又 都 以 離 散 性 為 基 礎(chǔ) 15.請 求 分 頁 式 存 儲 管 理 頁 式 地 址 變 換 機(jī) 構(gòu) 加 缺 頁 中 斷 機(jī) 構(gòu) 頁 表 、 快 表 中 增 加 項 (狀 態(tài) 位 ,訪 問 位 ,修 改 位 ,外 存 地 址 ) 16. 頁 面 調(diào) 入 策 略 何 時 調(diào) 入 : 預(yù) 調(diào) 入 (命 中 率 )、 缺 頁 時 請 求 調(diào) 頁 從 何 處 調(diào) 入 : 外 存 文

50、件 區(qū) 和 對 換 區(qū) (I/O快 ) UNIX策 略 首 次 從 文 件 區(qū) 調(diào) 入 , 換 出 到 對 換 區(qū)17. 頁 面 調(diào) 入 過 程 缺 頁 則 發(fā) 出 缺 頁 中 斷 , 保 留 環(huán) 境 , 找 到 外 存 塊 號 , 若 內(nèi)存 未 滿 則 調(diào) 入 并 修 改 頁 表 , 若 內(nèi) 存 滿 則 選 一 頁 換 出 (被 修改 需 寫 回 外 存 ), 再 將 缺 頁 調(diào) 入 內(nèi) 存 并 修 改 頁 表 和 快 表 。18. 頁 面 置 換 算 法 OPT、 FIFO、 LRU、 CLOCK、 頁 面 緩 沖 算 法 19. 抖 動產(chǎn) 生 原 因 ： 頁 面 淘 汰 算 法 不 合

51、理 、 工 作 集 窗 口 尺 寸 太 小預(yù) 防 : 采 取 局 部 置 換 策 略 , 引 入 工 作 集 算 法 , 調(diào) 整 多 道 度20. 請 求 分 段 存 儲 管 理 方 式 段 式 地 址 變 換 機(jī) 構(gòu) 加 缺 段 中 斷 機(jī) 構(gòu) 。 段 表 快 表 增 加 存 在 位 , 權(quán) 限 位 ,訪 問 位 ,修 改 位 ,增 補(bǔ) 位 外 存 地 址 分 段 的 共 享 與 保 護(hù) : 段 表 項 指 向 共 享 段 內(nèi) 存 首 址 。 共 享 段 表 、 共 享 段 的 分 配 和 回 收 、 分 段 保 護(hù)21. 段 的 鏈 接 靜 態(tài) 鏈 接 : 在 程 序 運(yùn) 行 前 都 鏈 接 好 并 一 次 裝 入 內(nèi) 存 。 動 態(tài) 鏈 接 : 程 序 邊 鏈 接 , 邊 運(yùn) 行 , 小 內(nèi) 存 可 運(yùn) 行 大 程 序22. CPU高 速 緩 存 (Cache ) 根 據(jù) 程 序 的 局 部 性 原 理 ,在 主 存 和 通 用 寄 存 器 之 間 設(shè)置 容 量 相 對 較 小 的 高 速 存 儲 器 , 把 正 在 執(zhí) 行 的 指 令 上 下文 或 數(shù) 據(jù) 從 主 存 調(diào) 入 這 個 存 儲 器 ,提 高 運(yùn) 行 速 度 。 作 業(yè) P143 22、 23、 26