《計算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案

《《計算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案》由會員分享，可在線閱讀，更多相關(guān)《《計算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案（94頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 1 第 7章 存 儲 層 次 （ P188）Memory Hirarchy 長 期 存 在 的 問 題 ： 在 合 理 的 總 價 格 限 制 下 ， 單 一 型 主 存 器 件 的 速度 跟 不 上 CPU的 發(fā) 展 ， 容 量 不 能 滿 足 軟 件 尺 寸 擴(kuò) 大 。 本 章 學(xué) 習(xí) 提 高 主 存 系 統(tǒng) 性 能 /價 格 比 的 幾 種 結(jié) 構(gòu) 化 方 法 ， 重 點 是“ Cache-主 存 層 次 ” ， 焦 點 問 題 是 如 何 使 流 水 線 每 拍 完 成 一 次 訪 存 。 本 章 基 本 公 式 ：(1)平 均 時 間

2、T = P 1 T1 + P2 T2其 中 P1 + P2 = 100%， 并 且 T1 和T2 都 可 以 再 用 該 式 迭 代 展 開 ， 復(fù) 雜時 ， 可 用 概 率 樹 來 表 示 （ 全 概 率 公 式 ） ；(2)實 際 時 間 T = 理 想 時 間 + P3 每 次 額 外 開 銷 時 間其 中 P3 是 不 利 事 件 發(fā) 生 概 率 。 1 P1 P2 P11 P12 P21 P22 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 2 7.1 存 儲 層 次 原 理 及 性 能 指 標(biāo) （ P188） 7.1.1 基 本 原 理 “ 存 儲 層 次 ” 的 定 義 ： （

3、 參 見 P189第 3段 ） 由 2種 或 多 種 存 儲 部 件 構(gòu) 成 的 復(fù) 合 存 儲 系 統(tǒng) ， 通過 內(nèi) 部 管 理 機(jī) 構(gòu) 的 自 動 更 換 機(jī) 制 ， 能 夠 不 斷 將 大 容量 低 速 存 儲 部 件 中 的 活 躍 內(nèi) 容 復(fù) 制 到 小 容 量 高 速 存儲 部 件 中 （ 后 者 作 為 前 者 的 局 部 副 本 ） 。 它 既 能 滿 足 CPU的 快 速 存 取 需 要 ， 又 有 很 大 的 存儲 容 量 ， 平 均 單 位 價 格 也 很 低 ， 等 效 于 同 時 滿 足 3方 面 要 求 的 理 想 單 一 存 儲 部 件 。 依 據(jù) ： 程 序 訪

4、 問 的 局 部 化 原 理 （ 時 間 局 部 化 ， 空 間 局 部 化 ） 。 模 型 ： 如 右 圖 所 示 ， 存 儲 層 次 由 n層 組 成 ， 滿 足 3個 不 等 式 ： TAici+1， Si頁 數(shù) 8b 頁 數(shù) =2p 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 43 Cache 主 存 層 次 虛 實 變 換 實 現(xiàn) （ 直 接 相 聯(lián) ）快 命 中 方 案 ： 直 接 相 聯(lián) ， 目 錄 表 法 （ P196， 圖 7.9） P 位 S 位 虛 地 址 虛 塊 號 偏 移 標(biāo) 識 段 索 引 段 （ p 位 ） p 位 實 地 址 實 存 目 錄 表 1 塊 =2

5、S 標(biāo) 識 實 塊 號 標(biāo) 志 位 裝 入 ？ 比 較 命 中 ？ 行 數(shù) =2P 行 數(shù) =塊 數(shù) 8b 塊 數(shù) =2p 舉 例 ： 為 了 方 便 用 10進(jìn) 制 討 論 。 設(shè) 虛 塊 號 =000 999， 實 塊 號 =0 9， 于 是 有 索 引 =0 9， 而 標(biāo) 識=00 99。索 引 =0的 實 塊 里 裝 的 虛 塊 標(biāo) 識 可 以 是 00， 01， ， 99， 對 應(yīng) 的 虛 塊 號 就 是 000， 010， 020，030， ， 990。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 44 Cache主 存 層 次 虛 實 變 換 實 現(xiàn) （ 組 相 聯(lián) ）低 失

6、 效 方 案 ： 位 選 擇 組 相 聯(lián) （ 2路 ） ， 目 錄 表 法 （ P196， 圖 7.9） P位 S位 虛 地 址 虛 塊 號 偏 移 標(biāo) 識 段 索 引 段 （ p-1位 ） p位 2 實 地 址 取 2行 選 擇 實 存 目 錄 表 1塊 =2 S 標(biāo) 識 0 實 塊 號 0 標(biāo) 志 位 裝 入 ？ 標(biāo) 識 1 實 塊 號 1 標(biāo) 志 位 裝 入 ？ 0比 較 命 中 0？ 1比 較 命 中 1？ 行 數(shù) =2P 行 數(shù) =塊 數(shù) 8b 塊 數(shù) =2p 直 接 相 聯(lián) ： 位 選 擇 組 相 聯(lián) （ 時 鐘 延 長 10%） ： AF IF ID EX ME WB AF IF

7、 ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 45 7.3.5 偽 相 聯(lián) （ P209） 優(yōu) 點 缺 點直 接 映 象組 相 聯(lián) 命 中 時 間 小 命 中 時 間 大不 命 中 率 高不 命 中 率 低 “ 偽 相 聯(lián) ” 又 稱 “ 列 相 聯(lián) ” ， 按 原 理 還 可 稱 為 “ 伴 生 Cache” 。(1) 比 較 直 接 相 聯(lián) 、 組 相 聯(lián) 的 優(yōu) 缺 點 從 例 7.4我 們 將 看 到 ， 直 接 相

8、 聯(lián) 的 命 中 時 間 較 短 ， 而 多 路 組 相 聯(lián) 的 失 效 率較 低 ， 所 以 它 們 的 平 均 訪 問 時 間 依 兩 個 因 素 的 作 用 大 小 而 互 有 輸 贏 。 有 沒有 什 么 方 法 取 二 者 之 長 呢 ？(2) 偽 相 聯(lián) 的 優(yōu) 點 偽 相 聯(lián) 就 是 直 接 相 聯(lián) 、 組 相 聯(lián) 的 一 種 組 合 方 案 。 優(yōu) 點 是 命 中 時 間 短 、 不命 中 率 還 低 ， 所 以 它 的 平 均 訪 問 時 間 往 往 比 直 接 相 聯(lián) 、 組 相 聯(lián) 都 短 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 46 (3) 基 本 思 想

9、及 工 作 原 理 在 邏 輯 上 把 直 接 相 聯(lián) Cache的 空 間 分 為 上 、 下 兩 個 區(qū) 。 對 于 任 何 一 次 訪問 ， 偽 相 聯(lián) Cache先 按 直 接 相 聯(lián) Cache的 方 式 去 處 理 。 若 命 中 ， 則 其 訪 問 過程 與 直 接 相 聯(lián) Cache的 情 況 一 樣 。 若 不 命 中 ， 則 再 到 另 一 區(qū) 相 應(yīng) 的 位 置 去查 找 。 若 找 到 ， 則 發(fā) 生 了 偽 命 中 。 再 找 不 到 就 只 好 訪 問 下 一 級 存 儲 器 。 顯 然 偽 相 聯(lián) 的 “ 候 選 位 置 ” =2，與 2路 組 相 聯(lián) 相 同 。

10、 每 次 訪 問 時 間 有 3種 可 能 ： 正 常 命 中 （ 快 速 命 中 ） 偽 命 中 （ 慢 速 命 中 ） 不 命 中7.3.5 偽 相 聯(lián) （ 續(xù) 1） 索 引 至 CPU 取 出 數(shù) 據(jù) 送 往 CPU 偽 相 聯(lián) 組 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 47 (4) 快 速 命 中 與 慢 速 命 中 要 保 證 絕 大 多 數(shù) 命 中 都 是 快 速 命 中 ， 就 是 命 中 率 要 高 。 一 種 簡 單 的 辦 法是 在 出 現(xiàn) 偽 命 中 時 ， 交 換 上 下 兩 個 區(qū) 的 內(nèi) 容 ， 因 為 當(dāng) 前 在 下 區(qū) 的 塊 很 可 能是 “ 常 用

11、 塊 ” 。 偽 命 中 情 況 下 需 要 增 加 2個 額 外 的 時 鐘 周 期 （ 其 中 1個 周 期是 多 找 1次 花 去 的 ， 1個 周 期 是 交 換 操 作 所 需 ） 。(5) 偽 相 聯(lián) 的 缺 點 ： 它 的 多 種 命 中 時 間 使 得 CPU流 水 線 上 各 指 令 之 間 的 時 間 對 齊 變 得 困 難 ，所 以 往 往 應(yīng) 用 在 離 CPU比 較 遠(yuǎn) 的 Cache上 ， 比 如 L2-Cache。7.3.5 偽 相 聯(lián) （ 續(xù) 2） 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 48 7.3.5 偽 相 聯(lián) （ 續(xù) 3）折 中 方 案 ： 偽

12、相 聯(lián) （ 2路 ） ， 目 錄 表 法 （ P209） P位 S位 虛 地 址 虛 塊 號 偏 移 標(biāo) 識 段 索 引 段 （ p-1位 ） p位 最 高 位 實 地 址 先 補(bǔ) 0 常 通 方 向 實 存 目 錄 表 1塊 =2 S 標(biāo) 識 0 實 塊 號 0 標(biāo) 志 位 裝 入 ？ 先 比 較 正 常 命 中 ？ 后 比 較 偽 命 中 ？ 標(biāo) 識 1 實 塊 號 1 標(biāo) 志 位 裝 入 ？ 行 數(shù) =2P 行 數(shù) =塊 數(shù) 8b 塊 數(shù) =2p 正 常 命 中 ： 偽 命 中 （ 增 加 2 拍 ） ： AF IF ID EX ME WB AF IF ID EX ME WB AF IF

13、 ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 49 例 7.3.5（ 補(bǔ) 充 ， 2版 P198例 5.6） 一 個 偽 相 聯(lián) Cache， 當(dāng) 在 按 直 接 映 象 找 到 的 位 置 處 沒 有 發(fā) 現(xiàn) 匹 配 、 而 在另 一 個 位 置 才 找 到 數(shù) 據(jù) （ 偽 命 中 ） 時 需 要 增 加 2個 額 外 的 周 期 。 其 它 已 知條 件 如 下 表 所 示 。(1) 推 導(dǎo) 偽 相 聯(lián) 平 均 訪 存 時 間 公 式 ；(2) 當(dāng) Cac

14、he容 量 分 別 為 2KB和 128KB時 ， 直 接 映 象 、 兩 路 組 相 聯(lián) 和 偽 相 聯(lián)這 三 種 組 織 結(jié) 構(gòu) 中 ， 哪 一 種 的 平 均 訪 存 時 間 最 短 ？7.3.5 偽 相 聯(lián) （ 續(xù) 4） 命 中 周 期 數(shù) 不 命 中 率 2KB 不 命 中 率 128KB 不 命 中 開 銷 1路 Cache 1.0 9.8% 1.0% 50 2路 Cache 1.1 7.6% 0.7% 50 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 50 解 ：(1) 首 先 按 通 用 形 式 寫 出 偽 相 聯(lián) 的 平 均 訪 存 時 間 公 式 ：平 均 訪 存 時

15、間 偽 相 聯(lián) 平 均 命 中 時 間 偽 相 聯(lián) 不 命 中 率 偽 相 聯(lián) 不 命 中 開 銷 偽 相 聯(lián) 然 后 根 據(jù) 偽 相 聯(lián) 原 理 ， 可 以 寫 出 其 中 的 ： 平 均 命 中 時 間 偽 相 聯(lián) 命 中 時 間 1路 偽 命 中 率 偽 相 聯(lián) 2周 期 由 于 偽 相 聯(lián) 不 命 中 時 ， 就 是 2個 候 選 位 置 都 不 命 中 ， 所 以 ： 不 命 中 率 偽 相 聯(lián) 不 命 中 率 2路 又 由 于 偽 相 聯(lián) 的 2個 候 選 位 置 命 中 率 之 和 等 于 2路 組 相 聯(lián) ， 所 以 ： 偽 命 中 率 偽 相 聯(lián) 命 中 率 2路 命 中 率

16、 1路 (1 不 命 中 率 2路 ) (1 不 命 中 率 1路 ) 不 命 中 率 1路 不 命 中 率 2路 7.3.5 偽 相 聯(lián) （ 續(xù) 5） 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 51 將 后 3式 依 次 向 前 代 入 ， 得 到 所 需 公 式 ： 平 均 訪 存 時 間 偽 相 聯(lián) 命 中 時 間 1路 (不 命 中 率 1路 不 命 中 率 2路 ) 2周 期 不 命 中 率 2路 不 命 中 開 銷 1路(2) 當(dāng) Cache容 量 為 2KB時 ：平 均 訪 存 時 間 1路 1.0 0.098 50 5.90平 均 訪 存 時 間 2路 1.1 0.076

17、 50 4.90平 均 訪 存 時 間 偽 相 聯(lián) ， 2KB 1.0 (0.098 0.076) 2 (0.076 50) 4.844當(dāng) Cache容 量 為 128KB時 ：平 均 訪 存 時 間 1路 1.0 0.010 50 1.50平 均 訪 存 時 間 2路 1.1 0.007 50 1.45平 均 訪 存 時 間 偽 相 聯(lián) ， 128KB 1.0 (0.010 0.007) 2 (0.007 50) 1.356可 見 ， 對 于 這 兩 種 Cache容 量 ， 偽 相 聯(lián) Cache都 是 速 度 最 快 的 。 7.3.5 偽 相 聯(lián) （ 續(xù) 6） 2014.2.17 計

18、算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 52 結(jié) 論 ： 從 不 命 中 率 看 ， F2路 = F偽 相 聯(lián) F1路 ， 偽 相 聯(lián) 因 不 命 中 帶 來 的 平 均 延 時 與 2路 一 樣 短 （ 1路 較 長 ） ； 從 命 中 時 間 看 ， 偽 相 聯(lián) 在 正 常 命 中 時 與 1路 一 樣 短 （ 2路 較 長 ） ， 偽 命 中時 要 增 加 2拍 ， 后 者 概 率 = H2路 H1路 。 這 種 情 況 下 1路 要 增 加 50拍 。 代 入 2KB、 128KB容 量 的 數(shù) 據(jù) ， 算 出 平 均 訪 存 時 間 TA都 是 偽 相 聯(lián) 最 短 。缺 點 ： 多 種 命 中 時

19、間 習(xí) 題 ： 7.11 7.3.5 偽 相 聯(lián) （ 續(xù) 7） 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 53各 次 作 業(yè) 應(yīng) 交 的 內(nèi) 容 作 業(yè) 9（ 第 10次 課 ）7.11 2 月 19 日 1.10(改 )， 1.7， 1.11(2 解 法 ) 4 月 9 日 7.14(難 題 )， 7.12(難 題 ) 2 月 26 日 2.14(補(bǔ) 充 )， 實 驗 1， 3.8， 3.10 4 月 16 日 8.12(補(bǔ) )， 8.11(改 ) (難 題 ) 3 月 5 日 3.11(改 )， 實 驗 2， 5.11， 5.8， 5.9 4 月 23 日 9.9(改 )， 9.13

20、 3 月 12 日 6.8(改 )， 6.7， 7.9 4 月 30 日 10.6， 10.9(難 題 ) 4 月 2 日 7.11， 7.10 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 54 衡 量 訪 存 時 間 是 否 合 適 的 主 要 標(biāo) 準(zhǔn) 是 處 理 機(jī) 速 度 ， 具 體 說 是 處 理 機(jī) 分配 來 讀 /寫 存 儲 器 的 時 間 長 短 。 處 理 機(jī) 速 度 越 高 要 求 訪 存 時 間 越 短 。 衡 量 處 理 機(jī) 速 度 的 常 用 標(biāo) 準(zhǔn) 是 CPI， 因 為 它 與 程 序 執(zhí) 行 時 間 成 正 比 。 對 順 序 執(zhí) 行 的 處 理 機(jī) ， CPI

21、定 義 為 每 條 指 令 執(zhí) 行 所 需 的 平 均 周 期 數(shù) 。對 流 水 執(zhí) 行 的 處 理 機(jī) ， CPI定 義 為 相 鄰 兩 條 指 令 啟 動 時 間 相 差 的 平 均 周 期數(shù) 。 我 們 現(xiàn) 在 只 關(guān) 心 流 水 處 理 機(jī) 。 下 圖 說 明 訪 存 等 待 （ 不 命 中 ） 會 延 長 瞬 時 CPI。7.2.7 訪 存 時 間 對 CPU性 能 的 影 響 1（ P203）CYCLECPIICCPU 實 際時 間 IF ID EX Mem WBstallIF ID EX Mem WBIF ID EX Mem WBIF ID EX Mem WBIF ID EX M

22、em WBCPI=1 CPI=2 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 55 所 以 在 計 算 平 均 CPI時 ， 應(yīng) 該 加 上 存 儲 器 平 均 “ 不 命 中 開 銷 ” 。 本 章 僅 考 慮 存 儲 器 等 待 在 平 均 CPI計 算 中 的 作 用 ， 暫 時 不 考 慮 流 水 線因 相 關(guān) 、 沖 突 導(dǎo) 致 的 延 遲 ， 所 以 上 式 簡 化 寫 為 又 被 稱 為 以 下 是 計 算 二 者 關(guān) 系 的 幾 組 常 用 公 式 。7.2.7 訪 存 時 間 對 CPU性 能 的 影 響 2 存 儲 器 平 均 不 命 中 開 銷延 遲流 水 線 自 身

23、 產(chǎn) 生 的 平 均每 條 指 令 平 均 延 遲理 想理 想平 均 CPICPICPI 銷每 條 指 令 平 均 不 命 中 開理 想平 均 CPICPI 平 均CPI 實 際CPI 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 56 (1) 第 i級 的 不 命 中 率 ：特 殊 地 ， F1又 可 以 記 為 F， 因 為 M1被 訪 問 次 數(shù) 就 是 CPU的 總 訪 存 次 數(shù) 。(2) 存 儲 系 統(tǒng) 的 平 均 訪 問 時 間 （ 從 CPU看 ） ：其 中 H1 Hn是 來 自 互 斥 事 件 的 完 備 群 ， 它 們 滿 足 關(guān) 系 式 ：注 意 該 公 式 忽 略 了

24、 各 級 之 間 的 傳 送 時 間 。(3) 第 i級 的 平 均 訪 問 時 間 ： 其 中 Ti是 第 i級 的 命 中 時 間 ， TMi是 第 i級 的 失 效 開 銷 時 間 。 7.2.7 訪 存 時 間 對 CPU性 能 的 影 響 3次 數(shù)訪 問 次 數(shù)不 命 中 i iii MMHF 1 ni iiA HTT 1 11 ni iHMiiiiA TFTT 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 57 (4) 程 序 執(zhí) 行 時 間 （ 即 “ CPU時 間 ” ） ：a.b.c.d. (7.3)e. (7.1)f. (7.2)g. 7.2.7 訪 存 時 間 對 CP

25、U性 能 的 影 響 4CYCLECPIICTe 實 際 CYCLEFCPIICTe 平 均 不 命 中 開 銷每 條 指 令 平 均 訪 存 次 數(shù) 平 均理 想 CYCLECPIICTe 數(shù)每 條 指 令 平 均 等 待 周 期理 想 CYCLECPUT e 等 待 存 儲 器 周 期 數(shù)實 際 執(zhí) 行 周 期 數(shù) CYCLECPIICTe 平 均 不 命 中 開 銷數(shù)每 條 指 令 平 均 不 命 中 次理 想 平 均 不 命 中 開 銷 周 期 數(shù)訪 存 次 數(shù)等 待 存 儲 器 周 期 數(shù) 平 均 F 寫 不 命 中 開 銷 周 期 數(shù)“ 寫 ” 次 數(shù)讀 不 命 中 開 銷 周 期

26、 數(shù)“ 讀 ” 次 數(shù)等 待 存 儲 器 周 期 數(shù) 寫讀 FF 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 58 例 7.1（ P204） 假 設(shè) Cache不 命 中 開 銷 為 50個 時 鐘 周 期 ， 當(dāng) 不 考 慮 存 儲 器 停 頓 時 ， 所 有指 令 的 執(zhí) 行 時 間 都 是 2.0個 時 鐘 周 期 ， 訪 問 Cache不 命 中 率 為 2%， 平 均 每 條指 令 訪 存 1.33次 。 比 較 有 Cache與 無 Cache情 況 下 的 CPU時 間 。解 ：已 知 TA1=2.0， 即 理 想 CPI = 2.0， TA2=50， F=2%， 平 均 每

27、 條 指 令 訪 存 1.33次CPU時 間 有 cache IC （ CPIexecution 每 條 指 令 的 平 均 訪 存 次 數(shù) 不 命 中 率 不 命 中 開 銷 ） 時 鐘 周 期 時 間 IC （ 2.0 1.33 2 % 50） 時 鐘 周 期 時 間 IC 3.33 時 鐘 周 期 時 間從 此 式 知 ， 實 際 CPI 2.0 1.33 2 % 50 3.33， 是 理 想 情 況 下 的 3.33/2.0 1.67(倍 )， 換 言 之 ， CPU時 間 是 理 想 情 況 下 的 1.67倍 。 若 不 采 用 Cache， 則 每 次 訪 存 增 加 50個 時

28、 鐘 周 期 ， 每 條 指 令 的 周 期 數(shù) 為 ：CPI無 cache 2.0 1.33 50 68.5， 是 理 想 情 況 下 的 68.5/2.0 34.25倍 ！ 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 59 例 7.2（ P204） 考 慮 兩 種 不 同 組 織 結(jié) 構(gòu) 的 Cache： 直 接 映 象 Cache和 兩 路 組 相 聯(lián) Cache， (1)理 想 Cache（ 命 中 率 為 100%） 情 況 下 的 CPI為 2.0， 時 鐘 周 期 為 2ns， 平 均每 條 指 令 訪 存 1.3次 ； (2)兩 種 Cache容 量 均 為 64KB， 塊

29、 大 小 都 是 32B； (3)在 組 相 聯(lián) Cache中 ， 由 于 多 路 選 擇 器 的 存 在 而 使 CPU的 時 鐘 周 期 增加 到 原 來 的 1.10倍 。 這 是 因 為 對 Cache的 訪 問 總 是 處 于 關(guān) 鍵 路 徑 上 ， 對 CPU的 時 鐘 周 期 有 直 接 的 影 響 ； (4)這 兩 種 結(jié) 構(gòu) Cache的 不 命 中 開 銷 都 是 70ns（ 在 實 際 應(yīng) 用 中 ， 應(yīng) 取 整為 整 數(shù) 個 時 鐘 周 期 ） ； (5)命 中 時 間 為 1個 時 鐘 周 期 ， 64KB直 接 映 象 Cache的 不 命 中 率 為 1.4%，相

30、 同 容 量 的 兩 路 組 相 聯(lián) Cache的 不 命 中 率 為 1.0%。 分 別 比 較 它 們 的 平 均 訪 存 時 間 、 CPU時 間 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 60 例 7.2（ 續(xù) 1）解 ：摘 要 ： 理 想 CPI=2， 不 命 中 開 銷 =70ns， 每 條 指 令 訪 存 1.3次 ， F直 接 =1.4%， F組 =1.0%， Cycle直 接 =2ns， Cycle組 =2.2ns。 比 較 直 接 映 象 Cache（ 即 1路 ） 與 2路 組 相 聯(lián) Cache的 平 均 訪 存 時 間 、 CPU時 間 。(1) 平 均 訪

31、 存 時 間 為 ： 平 均 訪 存 時 間 命 中 時 間 不 命 中 率 不 命 中 開 銷 因 此 ， 兩 種 結(jié) 構(gòu) 的 平 均 訪 存 時 間 分 別 是 ： 平 均 訪 存 時 間 1路 2.0 （ 0.014 70） 2.98ns 平 均 訪 存 時 間 2路 2.0 1.10 （ 0.010 70） 2.90ns 兩 路 組 相 聯(lián) Cache的 平 均 訪 存 時 間 短 一 些 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 61 例 7.2（ 續(xù) 2）(2) CPU時 間 IC （ CPIexecution 每 條 指 令 的 平 均 訪 存 次 數(shù) 不 命 中 率

32、不 命 中 開 銷 ） 時 鐘 周 期 時 間 IC （ CPIexecution 時 鐘 周 期 時 間 每 條 指 令 的 平 均 訪 存 次 數(shù) 不 命 中 率 不 命 中 開 銷 時 鐘 周 期 時 間 ）代 入 參 數(shù) 得 ：CPU時 間 1路 IC (2.0 2 (1.3 0.014 70) 5.27 ICCPU時 間 2路 IC (2.0 2 1.10 (1.3 0.010 70) 5.31 IC直 接 映 象 Cache的 CPU時 間 短 一 些 。 5.31 ICCPU時 間 1路 1.015.27 ICCPU時 間 2路 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 6

33、2 欲 設(shè) 計 一 個 L2-Cache， 已 知 它 的 不 命 中 開 銷 L2 50個 時 鐘 周 期 ， 問 下列 兩 種 映 像 方 式 對 不 命 中 開 銷 有 何 影 響 。 (1) L2-Cache采 用 直 接 相 聯(lián) ， 局 部 不 命 中 率 L2 25%， 命 中 時 間 L2 10個 時 鐘 周 期 ； (2) L2-Cache采 用 兩 路 組 相 聯(lián) ， 局 部 不 命 中 率 L2 20% ， 命 中 時 間 L2 10.1個 時 鐘 周 期 。解 ： （ 此 例 與 P204的 例 7.2參 數(shù) 相 似 ， 注 意 區(qū) 別 ） 題 目 已 經(jīng) 給 出 了 L

34、2-Cache恒 定 的 “ 不 命 中 開 銷 L2” ， 那 么 它 的 不 同 映像 方 式 影 響 的 只 能 是 L1-Cache的 不 命 中 開 銷 ， 根 據(jù) 多 級 存 儲 層 次 原 理 ，TM1 M2的 平 均 訪 問 時 間 。 所 以 本 題 實 質(zhì) 上 是 問 哪 種 映 像 方 式 下 L2-Cache的 平 均 訪 問 時 間 較 小 。 另 外 ， 在 不 使 用 L3-Cache情 況 下 ， “ 不 命 中 開 銷 L2 50個 時 鐘 周 期 ”意 思 是 “ 主 存 平 均 訪 問 時 間 50個 時 鐘 周 期 ” 。 例 7.4（ P216） 20

35、14.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 63 (1) L2-Cache采 用 直 接 相 聯(lián) 平 均 訪 問 時 間 10.0 25% 50 22.5 個 時 鐘 周 期(2) L2-Cache采 用 兩 路 組 相 聯(lián) 平 均 訪 問 時 間 10.1 20% 50 20.1 個 時 鐘 周 期(3) 兩 路 組 相 聯(lián) 的 命 中 時 間 之 所 以 比 直 接 相 聯(lián) 增 加 0.1個 時 鐘 周 期 ， 是 因 為虛 實 變 換 按 組 查 表 后 要 進(jìn) 行 多 路 選 擇 （ P199圖 7.12和 P198第 8段 ） ， 需 要額 外 增 加 時 間 。 具 體 實 現(xiàn) 方

36、 案 可 以 把 時 鐘 周 期 調(diào) 慢 為 1.01倍 （ 這 將 使 所 有動 作 都 減 慢 1%， 甚 至 主 存 訪 問 ） ， 或 者 僅 在 命 中 時 增 加 1個 時 鐘 周 期 。 按 增 加 1個 時 鐘 周 期 的 方 案 ， L2-Cache的 命 中 時 間 為 11， 有 ： 平 均 訪 問 時 間 11 20% 50 21.0 個 時 鐘 周 期 (2)(3)情 況 下 L2-Cache的 平 均 訪 問 時 間 都 比 直 接 相 聯(lián) 小 ， 所 以 L2-Cache采 用 兩 路 組 相 聯(lián) 性 能 更 好 。注 ： 教 材 中 該 例 中 說 “ 幸 運(yùn)

37、的 話 ， 取 整 為 10個 周 期 ” ， 就 是 說 多 路 選 擇 動作 時 間 有 可 能 “ 擠 ” 進(jìn) 原 有 的 10周 期 中 ， 習(xí) 題 中 通 常 不 這 樣 給 條 件 。 習(xí) 題 7.10 例 7.4（ 續(xù) ） 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 64各 次 作 業(yè) 應(yīng) 交 的 內(nèi) 容 作 業(yè) 10（ 第 11次 課 ）7.10 2 月 19 日 1.10(改 )， 1.7， 1.11(2 解 法 ) 4 月 9 日 7.14(難 題 )， 7.12(難 題 ) 2 月 26 日 2.14(補(bǔ) 充 )， 實 驗 1， 3.8， 3.10 4 月 16 日

38、8.12(補(bǔ) )， 8.11(改 ) (難 題 ) 3 月 5 日 3.11(改 )， 實 驗 2， 5.11， 5.8， 5.9 4 月 23 日 9.9(改 )， 9.13 3 月 12 日 6.8(改 )， 6.7， 7.9 4 月 30 日 10.6， 10.9(難 題 ) 4 月 2 日 7.11， 7.10 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 65 Windows 2000 使 用 基 于 分 頁 機(jī) 制 的 虛 擬 內(nèi) 存 。 每 個 進(jìn) 程 有 4GB的 虛 擬 地址 空 間 。 程 序 中 使 用 的 都 是 4GB地 址 空 間 中 的 虛 擬 地 址 。 而

39、訪 問 物 理 內(nèi) 存， 需 要 使 用 物 理 地 址 。 物 理 內(nèi) 存 以 字 節(jié) （ 8位 ） 為 單 位 編 址 。 物 理 內(nèi) 存 分 頁 ， 一 個 物 理 頁 的 大 小 為 4K字 節(jié) ， 第 0個 物 理 頁 從 物 理 地 址 0 x00000000 處 開 始 。 由 于 頁 的 大 小 為 4KB， 就 是 0 x1000字 節(jié) ， 所 以 第 1頁從 物 理 地 址 0 x00001000處 開 始 。 第 2頁 從 物 理 地 址 0 x00002000處 開 始 。 可以 看 到 由 于 頁 的 大 小 是 4KB， 所 以 只 需 要 32bit的 地 址 中

40、 高 20bit來 尋 址 物 理頁 。 使 用 了 分 頁 機(jī) 制 之 后 ， 4G的 地 址 空 間 被 分 成 了 固 定 大 小 的 頁 ， 每 一 頁 或者 被 映 射 到 物 理 內(nèi) 存 ， 或 者 被 映 射 到 硬 盤 上 的 交 換 文 件 中 ， 或 者 沒 有 映 射任 何 東 西 。 對 于 一 般 程 序 來 說 ， 4G的 地 址 空 間 ， 只 有 一 小 部 分 映 射 了 物 理內(nèi) 存 ， 大 片 大 片 的 部 分 是 沒 有 映 射 任 何 東 西 。 物 理 內(nèi) 存 也 被 分 頁 ， 來 映 射地 址 空 間 。 對 于 32bit的 Win2k， 頁

41、 的 大 小 是 4K字 節(jié) 。 CPU用 來 把 虛 擬 地 址 轉(zhuǎn) 換 成 物 理 地 址 的 信 息 存 放 在 叫 做 頁 目 錄 和 頁 表 的 結(jié) 構(gòu) 里 。 Windows 2000虛 擬 存 儲 器 1 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 66 頁 表 一 個 頁 表 的 大 小 為 4K字 節(jié) ， 放 在 一 個 物 理 頁 中 。 由 1024個 4字 節(jié) 的 頁 表 項 組 成 。 頁 表 項 的 大 小 為 4個 字 節(jié) (32bit)， 所 以 一 個 頁 表 中 有1024個 頁 表 項 。 頁 表 中 的 每 一 項 的 內(nèi) 容 （ 每 項 4個 字

42、節(jié) ,32bit） 高 20bit用 來放 一 個 物 理 頁 的 物 理 地 址 ， 低 12bit放 著 一 些 標(biāo) 志 。 頁 目 錄 一 個 頁 目 錄 大 小 為 4K字 節(jié) ， 放 在 一 個 物 理 頁 中 。 由 1024個4字 節(jié) 的 頁 目 錄 項 組 成 。 頁 目 錄 項 的 大 小 為 4個 字 節(jié) (32bit)， 所 以 一 個 頁 目錄 中 有 1024個 頁 目 錄 項 。 頁 目 錄 中 的 每 一 項 的 內(nèi) 容 （ 每 項 4個 字 節(jié) ） 高20bit用 來 放 一 個 頁 表 （ 頁 表 放 在 一 個 物 理 頁 中 ） 的 物 理 地 址 ， 低

43、 12bit放 著一 些 標(biāo) 志 。 對 于 x86系 統(tǒng) ， 頁 目 錄 的 物 理 地 址 放 在 CPU的 CR3寄 存 器 中 。 如 果 CPU寄 存 器 中 的 分 頁 標(biāo) 志 位 被 設(shè) 置 ， 那 么 執(zhí) 行 內(nèi) 存 操 作 的 機(jī) 器 指 令時 ， CPU會 自 動 根 據(jù) 頁 目 錄 和 頁 表 中 的 信 息 ， 把 虛 擬 地 址 轉(zhuǎn) 換 成 物 理 地 址， 完 成 該 指 令 。 比 如 mov eax,004227b8h ， 這 是 把 地 址 004227b8h處 的 值賦 給 寄 存 器 的 匯 編 代 碼 ， 004227b8這 個 地 址 就 是 虛 擬

44、址 。 CPU在 執(zhí) 行 這 行 代 碼 時 ， 發(fā) 現(xiàn) 寄 存 器 中 的 分 頁 標(biāo) 志 位 已 經(jīng) 被 設(shè) 定 ， 就 自 動 完 成 虛 擬 地 址 到 Windows 2000虛 擬 存 儲 器 2 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 67 物 理 地 址 的 轉(zhuǎn) 換 ， 使 用 物 理 地 址 取 出 值 ， 完 成 指 令 。 對 于 Intel CPU 來 說， 分 頁 標(biāo) 志 位 是 寄 存 器 CR0的 第 31位 ， 為 1表 示 使 用 分 頁 ， 為 0表 示 不 使 用分 頁 。 對 于 初 始 化 之 后 的 Win2k 我 們 觀 察 CR0 ， 發(fā)

45、 現(xiàn) 第 31位 為 1。 表 明Win2k是 使 用 分 頁 的 。 CPU把 虛 擬 地 址 轉(zhuǎn) 換 成 物 理 地 址 ： 一 個 虛 擬 地 址 ， 大 小 4個 字 節(jié) (32bit)， 包 含 著 找 到 物 理 地 址 的 信 息 ， 分 為3個 部 分 ： 第 22位 到 第 31位 這 10位 （ 最 高 10位 ） 是 頁 目 錄 中 的 索 引 ， 第 12位 到 第 21位 這 10位 是 頁 表 中 的 索 引 ， 第 0位 到 第 11位 這 12位 （ 低 12位 ） 是 頁內(nèi) 偏 移 。 對 于 一 個 要 轉(zhuǎn) 換 成 物 理 地 址 的 虛 擬 地 址 ， C

46、PU首 先 根 據(jù) CR3中 的值 ， 找 到 頁 目 錄 所 在 的 物 理 頁 。 然 后 根 據(jù) 虛 擬 地 址 的 第 22位 到 第 31位 這 10位 （ 最 高 的 10bit)的 值 作 為 索 引 ， 找 到 相 應(yīng) 的 頁 目 錄 項 (PDE,page directory entry),頁 目 錄 項 中 有 這 個 虛 擬 地 址 所 對 應(yīng) 頁 表 的 物 理 地 址 。 有 了 頁 表 的 物理 地 址 ， 根 據(jù) 虛 擬 地 址 的 第 12位 到 第 21位 這 10位 的 值 作 為 索 引 ， 找 到 該 頁表 中 相 應(yīng) 的 頁 表 項 (PTE,page

47、 table entry),頁 表 項 中 就 有 這 個 虛 擬 地 址 所 對 應(yīng) 物 理 頁 的 物 理 地 址 。 最 后 用 虛 擬 地 址 的 最 低 12位 ， 也 就 是 頁 內(nèi) Windows 2000虛 擬 存 儲 器 3 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 68 偏 移 ， 加 上 這 個 物 理 頁 的 物 理 地 址 ， 就 得 到 了 該 虛 擬 地 址 所 對 應(yīng) 的 物 理 地址 。 一 個 頁 目 錄 有 1024項 ， 虛 擬 地 址 最 高 的 10bit剛 好 可 以 索 引 1024項 （ 2的10次 方 等 于 1024） 。 一 個 頁

48、 表 也 有 1024項 ， 虛 擬 地 址 中 間 部 分 的 10bit， 剛好 索 引 1024項 。 虛 擬 地 址 最 低 的 12bit（ 2的 12次 方 等 于 4096） ， 作 為 頁 內(nèi)偏 移 ， 剛 好 可 以 索 引 4KB， 也 就 是 一 個 物 理 頁 中 的 每 個 字 節(jié) 。 一 個 虛 擬 地 址 轉(zhuǎn) 換 成 物 理 地 址 的 計 算 過 程 就 是 ， 處 理 器 通 過 CR3找 到 當(dāng)前 頁 目 錄 所 在 物 理 頁 ， 取 虛 擬 地 址 的 高 10bit,然 后 把 這 10bit右 移 2bit（ 因 為每 個 頁 目 錄 項 4個 字

49、節(jié) 長 ， 右 移 2bit相 當(dāng) 于 乘 4） 得 到 在 該 頁 中 的 地 址 ， 取出 該 地 址 處 PDE（ 4個 字 節(jié) ） ， 就 找 到 了 該 虛 擬 地 址 對 應(yīng) 頁 表 所 在 物 理 頁， 取 虛 擬 地 址 第 12位 到 第 21位 這 10位 ， 然 后 把 這 10bit右 移 2bit（ 因 為 每 個頁 表 項 4個 字 節(jié) 長 ， 右 移 2bit相 當(dāng) 于 乘 4） 得 到 在 該 頁 中 的 地 址 ， 取 出 該 地址 處 的 PTE（ 4個 字 節(jié) ） ， 就 找 到 了 該 虛 擬 地 址 對 應(yīng) 物 理 頁 的 地 址 ， 最 后加 上 1

50、2bit的 頁 內(nèi) 偏 移 得 到 了 物 理 地 址 。Windows 2000虛 擬 存 儲 器 4 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 69 32bit的 一 個 指 針 ， 可 以 尋 址 范 圍 0 x00000000-0 xFFFFFFFF， 4GB大 小 。也 就 是 說 一 個 32bit的 指 針 可 以 尋 址 整 個 4GB地 址 空 間 的 每 一 個 字 節(jié) 。 一 個頁 表 項 負(fù) 責(zé) 4K的 地 址 空 間 和 物 理 內(nèi) 存 的 映 射 ， 一 個 頁 表 1024項 ， 也 就 是 負(fù)責(zé) 1024*4k=4M的 地 址 空 間 的 映 射 。 一

51、個 頁 目 錄 項 ， 對 應(yīng) 一 個 頁 表 。 一 個頁 目 錄 有 1024項 ， 也 就 對 應(yīng) 著 1024個 頁 表 ， 每 個 頁 表 負(fù) 責(zé) 4M地 址 空 間 的 映射 。 1024個 頁 表 負(fù) 責(zé) 1024*4M=4G的 地 址 空 間 映 射 。 一 個 進(jìn) 程 有 一 個 頁 目錄 。 所 以 以 頁 為 單 位 ， 頁 目 錄 和 頁 表 可 以 保 證 4G的 地 址 空 間 中 的 每 頁 和 物理 內(nèi) 存 的 映 射 。 每 個 進(jìn) 程 都 有 自 己 的 4G地 址 空 間 ， 從 0 x00000000-0 xFFFFFFFF。 通 過每 個 進(jìn) 程 自

52、己 的 一 套 頁 目 錄 和 頁 表 來 實 現(xiàn) 。 由 于 每 個 進(jìn) 程 有 自 己 的 頁 目 錄和 頁 表 ， 所 以 每 個 進(jìn) 程 的 地 址 空 間 映 射 的 物 理 內(nèi) 存 是 不 一 樣 的 。 兩 個 進(jìn) 程的 同 一 個 虛 擬 地 址 處 （ 如 果 都 有 物 理 內(nèi) 存 映 射 ） 的 值 一 般 是 不 同 的 ， 因 為他 們 往 往 對 應(yīng) 不 同 的 物 理 頁 。 4G地 址 空 間 中 低 2G， 0 x00000000-0 x7FFFFFFF是 用 戶 地 址 空 間 ， 4G地 址 空 間 中 高 2G， 0 x80000000-0 xFFFFF

53、FFF 是 系 統(tǒng) 地 址 空 間 。 訪 問 系 統(tǒng) 地址 空 間 需 要 程 序 有 ring0的 權(quán) 限 。 Windows 2000虛 擬 存 儲 器 5 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 70 Windows 2000虛 實 變 換 示 意 圖 指 令 b31=1表 示 分 頁 IR 操 作 碼 操 作 數(shù) （ 直 接 尋 址 ） 實 存 空 間 （ 最 多 4GB） 虛 地 址 CR1寄 存 器 10b 10b 12b （ 虛 頁 號 ） 4 4 實 地 址 1頁 =212B CR3寄 存 器 （ 4KB） 頁 目 錄 首 址 頁 表 0 （ 取 高 20位 ） 實

54、頁 號 標(biāo) 志 位 頁 目 錄 20b 12b 頁 表 首 址 高 20位 標(biāo) 志 位 20b 12b 頁 表 1023 實 頁 號 標(biāo) 志 位 注 ： 頁 目 錄 、 頁 表 大 小 都 是 4KB 20b 12b 8b 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 71 7.2.5 替 換 算 法 (P198) 上 面 所 講 的 地 址 映 象 方 式 是 在 虛 頁 調(diào) 入 時 的 “ 選 址 ” 規(guī) 則 ， 而 地 址 變換 方 法 則 是 命 中 時 獲 得 實 地 址 的 手 段 。 不 命 中 時 需 要 增 加 的 操 作 就 是 首 先 調(diào) 出 一 頁 ， 調(diào) 出 之 后

55、 再 調(diào) 入 稱 為 “ 替 換 ” 。 替 換 算 法 要 解 決 的 是 選 擇 調(diào) 出 對 象 的 問 題 。 替 換 算 法 的 目 的 是 在 發(fā) 生 實 頁 爭 用 （ 即 根 據(jù) 地 址 映 象 方 式 ， 將 要 調(diào) 入的 虛 頁 被 允 許 進(jìn) 入 的 所 有 實 頁 均 被 其 它 虛 頁 占 用 ） 時 ， 選 擇 將 來 不 太 可能 使 用 或 者 使 用 最 晚 的 虛 頁 作 為 調(diào) 出 對 象 ， 以 騰 出 一 個 實 頁 來 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 72 幾 種 常 用 的 替 換 算 法(1)隨 機(jī) 算 法 RAND 在 比 較

56、 范 圍 內(nèi) 任 取 一 頁 作 為 淘 汰 頁 ；(2)先 進(jìn) 先 出 算 法 FIFO 在 比 較 范 圍 內(nèi) 選 取 調(diào) 入 最 早 的 一 頁 作 為 淘 汰 頁 ；(3)最 不 經(jīng) 常 使 用 算 法 LFU 在 比 較 范 圍 內(nèi) 選 取 最 近 一 個 單 位 時 間 內(nèi) 使 用次 數(shù) 最 少 的 一 頁 作 為 淘 汰 頁 ；(4)最 不 接 近 使 用 算 法 LRU 在 比 較 范 圍 內(nèi) 選 取 最 后 一 次 使 用 離 現(xiàn) 在 最 久的 一 頁 作 為 淘 汰 頁 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 73 從 LFU到 LRU的 近 似邏 輯 推 理

57、： 近 期 最 少 使 用 LFU 最 近 一 個 單 位 時 間 內(nèi) 使 用 次 數(shù) 最 少 相 鄰兩 次 使 用 的 平 均 間 隔 時 間 最 大 上 次 使 用 時 間 離 現(xiàn) 在 最 久 最 久 沒 有 使 用LRU 偶 然 偏 差 ： 使 用 稀 疏 的 頁 面 有 可 能 恰 巧 剛 剛 用 過 ， 離 現(xiàn) 在 更 近 。統(tǒng) 計 性 能 ： “ 現(xiàn) 在 ” 離 “ 上 次 ” 使 用 時 間 的 平 均 距 離 ， 應(yīng) 為 相 鄰 兩 次 使 用 時間 距 離 的 1/2， 所 以 大 多 數(shù) 情 況 下 LRU與 LFU的 判 斷 結(jié) 論 應(yīng) 該 是 一 致 的 。頁 面 A

58、訪 問使 用 頻 繁 ， 相 鄰 使 用 間 隔 小上 次 使 用 時 間 離 現(xiàn) 在 近 時 間 t頁 面 B 訪 問使 用 稀 疏 ， 相 鄰 使 用 間 隔 大上 次 使 用 時 間 離 現(xiàn) 在 遠(yuǎn) 時 間 t現(xiàn) 在 （ 要 淘 汰 一 頁 ） 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 74 算 法 模 擬 ： 實 存 狀 況 圖 (清 華 教 材 圖 3.32)以 下 是 FIFO、 LRU算 法 比 較 ， 其 中 *號 表 示 被 選 中 的 淘 汰 頁 已 訪 問 次 數(shù) t 0 1 2 3 4 5 6 7 8 9 10 被 訪 問 虛 頁 號 無 1 2 1 5 4 1

59、3 4 2 4 命 中 總 次 數(shù) 0 空 1 1 1 1* 4 4 4* 4* 2 2 1 空 空 2 2 2 2* 1 1 1 1* 4 實 存 空 間 使 用情 況 （ 實 頁 號 為 0、 1、 2） 2 空 空 空 空 5 5 5* 3 3 3 3* 操 作 名 稱 初 態(tài) (空 ) 調(diào) 入 調(diào) 入 命 中 調(diào) 入 替 換 替 換 替 換 命 中 替 換 替 換 FIFO 2次 被 訪 問 實 頁 號 0 1 0 2 0 1 2 0 0 1 0 空 1 1 1 1 1* 1 1 1* 2 2 1 空 空 2 2 2* 4 4 4* 4 4 4 實 存 空 間 使 用情 況 （ 實 頁

60、 號為 0、 1、 2） 2 空 空 空 空 5 5 5* 3 3 3* 3* 操 作 名 稱 初 態(tài) (空 ) 調(diào) 入 調(diào) 入 命 中 調(diào) 入 替 換 命 中 替 換 命 中 替 換 命 中 LRU 4次 被 訪 問 實 頁 號 0 1 0 2 1 0 2 1 0 1 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 75 課 堂 練 習(xí) 7.3（ 鄭 緯 民 題 3-19中 3、 4、 6、 8小 問 ， 稍 改 ） 假 設(shè) 在 一 個 采 用 位 選 擇 組 相 聯(lián) 映 象 方 式 的 Cache中 ， 主 存 由 B0 B7共 8塊組 成 ， Cache有 2組 ， 每 組 2塊 ， 每

61、 塊 的 大 小 為 16個 字 節(jié) ， 采 用 LRU塊 替 換 算 法。 程 序 執(zhí) 行 過 程 中 依 次 訪 問 這 個 Caehe的 塊 地 址 流 如 下 ： B6， B2， B4， B1，B4， B6， B3， B0， B4， B5， B7， B3(3)畫 出 主 存 與 Cache之 間 各 個 塊 的 映 象 對 應(yīng) 關(guān) 系 。(4)Cache塊 號 記 為 C0、 C1、 C2和 C3， 列 出 程 序 執(zhí) 行 過 程 中 Cache地 址 流 。(6)計 算 Cache的 塊 命 中 率 。(8)如 果 上 述 地 址 流 中 的 每 個 塊 號 實 際 代 表 對 該

62、塊 的 連 續(xù) 16次 訪 問 ， 計 算 在這 種 情 況 下 的 Cache命 中 率 （ 也 稱 為 存 儲 單 元 命 中 率 ） 。 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 76 7.2.6 Cache的 寫 策 略 （ P202）寫 策 略 ：(1)寫 直 達(dá) 法 （ write through） ： 每 次 都 對 上 、 下 級 存 儲 器 同 時 寫 ；(2)寫 回 法 （ write back） ： 只 寫 入 上 級 存 儲 器 鏡 象 數(shù) 據(jù) ， 等 到 鏡 象 數(shù) 據(jù) 調(diào)出 時 再 寫 回 下 級 存 儲 器 ， 這 樣 CPU的 寫 等 待 時 間 短 ，

63、寫 回 的 次 數(shù) 也 少 。對 上 級 存 儲 器 寫 失 效 時 的 策 略 ：(1)按 寫 分 配 法 （ write allocate） ： 先 調(diào) 入 塊 ， 在 上 級 存 儲 器 寫 。 又 稱 寫時 取 法 （ fetch on write） ， 多 配 合 寫 回 法 。(2)不 按 寫 分 配 法 （ no-write allocate） ： 直 接 寫 入 下 級 存 儲 器 ， 又 稱 繞寫 法 （ write around， CPU繞 過 上 級 存 儲 器 ） ， 多 配 合 寫 直 達(dá) 法 。 習(xí) 題 ： 7.14 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu)

64、77 7.2.4 Cache的 工 作 過 程 （ P197）概 況 ： 塊 大 小 32B， 塊 數(shù) 256， 直 接 映 象 ， 寫 直 達(dá) ， 采 用 不 按 寫 分 配 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 78 Cache“讀 ” 訪 問 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 79 Cache“ 寫 ” 訪 問 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 80 (1)分 離 式 Cache在 命 中 情 況 下 ， IF與 MEM操 作 都 不 需 要 停 頓 。分 離 式 Cache與 混 合 式 （ 統(tǒng) 一 式 ） Cache（ 補(bǔ) 充 2版 P185）分

65、 離 式 Cache結(jié) 構(gòu) 示 意 圖IF ID WBMEMEX指 令 Cache 數(shù) 據(jù) Cache下 一 級 存 儲 器 IF ID EX ME WB IF ID EX ME WB IF ID EX ME WB IF ID EX ME WB IF ID EX ME WB 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 81 (2)混 合 式 （ 統(tǒng) 一 式 ） Cache在 命 中 情 況 下 ， 每 次 有 效 MEM操 作 都 會 迫 使 后 面 一 條 指 令 的 IF停 頓 （ 結(jié)構(gòu) 沖 突 ） 。分 離 式 Cache與 混 合 式 Cache（ 續(xù) 1）混 合 式 Cache結(jié)

66、 構(gòu) 示 意 圖IF ID WBMEMEX混 合 Cache下 一 級 存 儲 器 IF ID EX ME WB LD/STORE 指 令 IF ID EX ME WB IF ID EX ME WB 其 它 類 指 令 S IF ID EX ME WB IF ID EX ME WB 2014.2.17 計 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 82 下 表 是 兩 種 Cache結(jié) 構(gòu) 的 不 命 中 率 實 測 數(shù) 據(jù) （ DECstation5000處 理 機(jī)， SPEC92測 試 程 序 ， 直 接 映 像 ， 塊 大 小 32B）注 意 ： 比 較 平 均 不 命 中 率 應(yīng) 該 在 總 容 量 相 同 的 條 件 下 進(jìn) 行 ， 比 如 32KB混合 Cache與 16KB指 令 Cache+16KB數(shù) 據(jù) Cache相 比 。 對 分 離 Cache還 有 ：分 離 式 Cache與 混 合 式 Cache（ 續(xù) 2）容 量 指 令 Cache 數(shù) 據(jù) Cache 混 合 Cache 1 KB 3.06% 24.61% 13.34% 2 KB 2.26% 20.57% 9.78% 4 K