【正文】 110110010111001011101010011111111011010011100100區(qū) 01區(qū) 10區(qū) 11區(qū) Cache 主存 目錄表 xxxxxxxx00 01 10 11 86 直接映象 ——地址變換 目錄表 塊失效 相等比較 區(qū)號 Ei 塊號 i 塊內(nèi)地址 塊號 i 塊內(nèi)地址 主存地址 Cache地址 相等 Ei 1 區(qū)號（按地址訪問） 有效位 訪問 Cache 優(yōu)點(diǎn)：簡單；缺點(diǎn)：命中率低。 87 直接映象 ——訪問過程 區(qū)號 塊 號B 塊 內(nèi)地址W 塊 號B 塊內(nèi) 地址W相等比較 1/W主存地址Cach e地址CPU相等主存不相等有效位 區(qū)號 數(shù)據(jù) 1 數(shù)據(jù) 2 數(shù)據(jù) n 1 E D1 D2 Dn 直接映象快速訪問 Cache 88 例： 例 1 假設(shè)在某個(gè)計(jì)算機(jī)系統(tǒng)中 Cache容量為 64K字節(jié)，數(shù)據(jù)塊大小是16個(gè)字節(jié)，主存容量是 4M，地址映象為直接相聯(lián)方式。 （ 1）主存地址多少位？如何分配？ （ 2） Cache地址多少位？如何分配？ （ 3）目錄表的格式和容量？ 主存地址格式： 區(qū)號 區(qū)內(nèi)塊號 塊內(nèi)地址 21 16 15 4 3 0 緩存地址格式： 塊 號 塊內(nèi)地址 15 4 3 0 目錄表的格式： 主存區(qū)號 有效位 6 1 0 解： 容量：應(yīng)與緩存塊數(shù)量相同即 212=4096 89 例： 例 2 若主存具有 16個(gè)數(shù)據(jù)塊， Cache有 4個(gè)數(shù)據(jù)塊（見前圖）。設(shè) CPU訪存的地址順序?yàn)?0000（塊）、 1100、 0000、 0100、 1000、 1100，請分析執(zhí)行過程和 Cache的使用狀況。 90 （二）全相聯(lián)映象 ? 全相聯(lián)映象規(guī)則： 主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊的空間中 。 B：每塊大小 C： Cache容量 M：主存容量 塊 0 塊 1 ： 塊 i ： 塊 M/B1 塊 0 塊 1 ： 塊 C/B1 Cache 主存儲(chǔ)器 91 全相聯(lián)地址變換 塊號 塊內(nèi)地址 主存地址 塊號 塊內(nèi)地址 Cache地址 Bi bi 1 主存塊號 B Cache塊號 b 有效位 優(yōu)點(diǎn)：命中率較高， Cache的存儲(chǔ)空間利用率高； 缺點(diǎn)：線路復(fù)雜，成本高，速度低。 92 例： 例 3 假設(shè)在某個(gè)計(jì)算機(jī)系統(tǒng)中 Cache容量為 32K字節(jié)，數(shù)據(jù)塊大小是 16個(gè)字節(jié)，主存容量是 1M，地址映象為全相聯(lián)方式。 （ 1）主存地址多少位？如何分配？ （ 2） Cache地址多少位？如何分配？ （ 3）目錄表的格式和容量？ 93 直接映象與全相聯(lián)映象 直接映象 按地址一次讀出。結(jié)構(gòu)簡單 ,易實(shí)現(xiàn) 全相聯(lián)映象 按內(nèi)容查找，多次讀出和相聯(lián)比較讀出。結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)難。 直接映象 目錄表容量小， 全相聯(lián)映象 目錄表大。 直接映象 Cache利用率低， 全相聯(lián)映象 Cache利用率高。 當(dāng) Cache容量大時(shí)，目錄表容量和查找表時(shí)間不容忽視。 94 （三）組相聯(lián)映象 ? 映象規(guī)則（ 1） ： 1. 主存與緩存分成大小相同的組 。 2. 主存容量是緩存容量的整數(shù)倍，將主存空間按緩存的大小分成區(qū)，主存中每一區(qū)中的組數(shù)與緩存的組數(shù)相同。 3. 組間直接映象；組內(nèi)全相聯(lián)映象。 95 組相聯(lián)映象 區(qū) 0 區(qū) Me－ 1 組 1 組 0 組 C/B－ 1 塊 0 塊 B－ 1 塊 B 塊 2B－ 1 Cache 塊 0 塊 B－ 1 塊 B 塊 2B－ 1 組 1 組 C/B－ 1 組 0 組 C/B(Me－ 1) 組 C/BMe－ C/B+1 組 C/BMe－ 1 96 組相聯(lián)地址變換 目錄表 相等 不等 Cache地址 區(qū)號 組號 組內(nèi)塊號 塊內(nèi)地址 主存地址 組號 組內(nèi)塊號 塊內(nèi)地址 相聯(lián)比較 區(qū)號 E 組內(nèi)塊號 組內(nèi)塊號 EiBi bi 97 例： 例 4 主存容量為 1MB， 緩存容量為 32KB，每塊為 64個(gè)字節(jié)，緩存共分 128組。 請寫出： （ 1）主存與 Cache的格式； （ 2）相關(guān)存儲(chǔ)器的格式與容量 解： 主存地址： 區(qū)號 組號 塊號 塊內(nèi)地址 19 15 14 8 7 6 5 0 緩存地址： 組號 塊號 塊內(nèi)地址 14 8 7 6 5 0 區(qū)號 Ei 塊號 Bi 緩存塊號 bi 裝入位 9 5 4 3 2 1 0 相關(guān)存儲(chǔ)器的格式： 相關(guān)存儲(chǔ)器的容量，應(yīng)與緩存的塊數(shù)相同，即 : 組數(shù) 組內(nèi)塊數(shù) =128 4=512 98 組相聯(lián) ? 映象規(guī)則（ 2） ： 1. Cache被劃分為若干組，每組由若干塊構(gòu)成 。 2. 主存中的每一塊可以放置到 Cache中唯一的一組內(nèi)任意塊位置。 3. 內(nèi)存塊和 Cache的組直接映象，對應(yīng)組內(nèi)的塊為全相聯(lián)映象。 4. 每個(gè)組內(nèi)有 n個(gè)數(shù)據(jù)塊，稱為 n路組相聯(lián)。 99 000001000011001000011000011101100101110010111010100111111110110110011111010100001101000100組 01組 10組 11組 16塊 8塊 主存 CACHE 2路組相聯(lián) 100 組相聯(lián)映象公式： k= i mod (G) 其中 G為 Cache組數(shù)。 設(shè) G = 2g, k是 i 的 低 k位。 內(nèi)存第 i個(gè)數(shù)據(jù)塊映象到 Cache的第 k組。 101 n（路數(shù)） G（組數(shù)） 直接映象 1 M 全相聯(lián)映象 M 1 組相聯(lián)映象 1 n M 1 G M 不同相聯(lián)度的組數(shù)和路數(shù) 問題： n取值大小對存儲(chǔ)系統(tǒng)的影響？ M: Cache中的塊數(shù) 102 Cache替換算法及其實(shí)現(xiàn) ? 虛擬存儲(chǔ)器 中的 頁面替換算法 主要是用 軟件實(shí)現(xiàn) ，采用 全相聯(lián)映象 方式。 ? Cache中，由于其速度高， 替換算法 必須用 硬件實(shí)現(xiàn) 。且 Cache中一般 不 采用全相聯(lián)映象方式。 ? Cache的三種常用替換算法： ? 隨機(jī)法 (Random， RAND法 ) ? 先進(jìn)先出法 (FirstIn FirstOut， FIFO法 ) ? 最久沒有使用法（ Least Frequently Used， LFU） 103 Cache替換算法（ 1） ? 隨機(jī)法： 隨機(jī)地選擇被替換地塊 需要隨機(jī)發(fā)生器 ? 優(yōu)點(diǎn)： 簡單，容易實(shí)現(xiàn) ? 缺點(diǎn)： 沒有考慮 Cache中數(shù)據(jù)塊使用情況。不能利用程序的局部性。 104 Cache替換算法（ 2） ? 先進(jìn)先出法： 最早進(jìn)入 Cache的數(shù)據(jù)塊被替換。 ? 實(shí)現(xiàn)： 每次訪問塊計(jì)數(shù)器加 1。 ? 優(yōu)點(diǎn)： 簡單，容易實(shí)現(xiàn)。 ? 缺點(diǎn)： 最早進(jìn)入的塊可能經(jīng)常被使用。 105 Cache替換算法（ 3） ? 最久沒有使用法： 很久沒有被訪問的塊被替換 ? 實(shí)現(xiàn)： 每個(gè)數(shù)據(jù)塊設(shè)計(jì)數(shù)器；被訪問塊計(jì)數(shù)器清 0，其他數(shù)據(jù)塊加 1。 ? 優(yōu)點(diǎn)：利用局部性原理 ? 缺點(diǎn)：不易實(shí)現(xiàn) 106 例： 設(shè)有一道程序，有 1至 5共五塊，執(zhí)行時(shí)的塊地址流（即執(zhí)行時(shí)依次用到的程序塊號）為： 2， 3， 2， 1， 5， 2， 4， 5， 3， 2， 5， 2 若分配給該道程序的緩存有 3塊，分別采用 FIFO和 LFU替換算法表示這 3塊的使用和替換過程。 說明： （ 1）隨機(jī)算法：用隨機(jī)數(shù)確定要替換的塊； （ 2） FIFO算法：替換最早裝入主存的塊； （ 3） LFU算法：依據(jù)各塊使用的情況，選擇最近最少使用的塊替換。 107 時(shí)間 t 1 2 3 4 5 6 7 8 9 10 11 12 塊地址流 2 3 2 1 5 2 4 5 3 2 5 2 先進(jìn)先出 FIFO 調(diào)進(jìn) 調(diào)進(jìn) 調(diào)進(jìn) 命中 替換 替換 替換 替換 命中 命中 替換 替換 命中命中命中命中 3次 近期最少使用 LFU 2 2 3 2 3 2* 3 1 3* 1 5 5 1* 2 5* 2 4 2 4 5* 2* 4 3 3 4 2* 3 4* 5 3* 5 2 2 調(diào)進(jìn) 2 3 調(diào)進(jìn) 2 3 命中 2 3* 1 調(diào)進(jìn) 2* 1 5 替換 5 1* 2 命中 2 5* 4 替換 2* 4 5 命中 5 4* 3 替換 3 5* 2 替換 3* 2 5 命中 5 2 3* 命中 命中命中命中命中命中命中 5次 1