【正文】 31 11 31 40 11 21 31 50 10 ?缺點(diǎn)： 對(duì)新鮮數(shù)據(jù)保護(hù)不夠 (2)LRU 最近最少用算法 (Least recently used ) 該算法將一段時(shí)間內(nèi)最長(zhǎng)時(shí)間沒有被使用的行調(diào)出。故 每行設(shè)置一個(gè)計(jì)時(shí)器，新調(diào)入的和命中行計(jì)數(shù)值為 0 ，同 時(shí)其他各行的計(jì)數(shù)器值加 1 ，當(dāng)需要發(fā)生頁(yè)面調(diào)度時(shí)，比 較各行計(jì)數(shù)器的值，將最大者調(diào)出。 1 1 2 3 2 3 4 5 ?LRU舉例 10 11 20 12 21 30 13 20 31 14 21 30 15 22 31 40 50 23 32 41 10 ?如果出現(xiàn)了下列情況 (LRU) 11 20 10 21 30 12 11 10 22 31 13 40 23 32 50 41 10 33 51 42 11 20 52 43 12 21 53 30 1 2 3 4 5 1 2 3 ?上述現(xiàn)象稱為抖動(dòng)，出現(xiàn)的原因是用戶的程序足局性不好 在這種情況下， Cache的作用得不到發(fā)揮。 ?要充分發(fā)揮計(jì)算機(jī)硬件的高速特性，要求用戶的程序滿 足一定的要求！ 以便實(shí)現(xiàn)硬件與軟件的完美結(jié)合！ 7) 比較三種映射方法中的 LRU ?全相聯(lián) 每次改變和被比較的是 Cache所有行的計(jì)數(shù)值 ?直接相聯(lián) 不用 LRU,只要有沖突就直接替換原 Cache行中 的頁(yè)面，因?yàn)槭嵌鄬?duì)一的關(guān)系 ?組相聯(lián) 頁(yè)面調(diào)入時(shí) ,只是相關(guān)組內(nèi)的計(jì)數(shù)器的計(jì)數(shù)值會(huì) 發(fā)生變化 ,且比較時(shí)也是比較相關(guān)組內(nèi)所有 Cache行的計(jì)數(shù) 器的值 . a)幾個(gè)相關(guān)的概念 ? Cache臟位或修改位 (Dirty bit) 表示 Cache中的數(shù)據(jù)是否被修改過，當(dāng) Cache中某塊數(shù)據(jù)被 CPU修改 (寫 )時(shí)將該位置 1，一般用于 Cache的 寫回策略 ,即表示 Cache中的數(shù)據(jù)被更新，而主存中的數(shù)據(jù)未被更新。 ? Cache有效位 (Valid bit) 用來(lái)表示是否有不經(jīng)過 Cache的主存數(shù)據(jù)更新 (如 DMA操作 ),當(dāng)有這種主存數(shù)據(jù)更新時(shí) ,有效位修改成 0,表示主存的數(shù)據(jù)被更新 ,而Cache中的數(shù)據(jù)無(wú)效 . 8) CACHE的一致性問題 b)Cache的結(jié)構(gòu) Tag Data Valid(1) Dirty(1) ?問題的提出： 正常情況下 , Cache是主存的副本，但經(jīng)過一段時(shí)間后，可 能會(huì)出現(xiàn)兩者內(nèi)容不一致的情況，導(dǎo)致這種不一致的情況有： CPU將 Cache某單元的內(nèi)容修改 成了 X’，而主存相關(guān)單元的內(nèi)容 還是 X，當(dāng)外設(shè)讀取 X對(duì)應(yīng)單元的 數(shù)值時(shí)，就會(huì)發(fā)生不一致錯(cuò)誤。 c)Cache的一致性 主存 cache CPU X’ X I/O (1)情況 1 ?解決問題的方法 (a)寫直達(dá)法 (WT Write through)： CPU在執(zhí)行寫操作時(shí)，必須把數(shù)據(jù)同時(shí)寫入 Cache和主存。 (b)寫回法 (WB Write Back): CPU寫 Cache命中時(shí)，數(shù)據(jù)只寫向 Cache，不寫主存，同時(shí)修改 Cache中數(shù)據(jù)的臟位或修改位，供其它讀內(nèi)存的設(shè)備參考。 主存 cache CPU X X‘ I/O 外設(shè)將主存某單元的內(nèi)容修改 成了 X’，而主存該單元的內(nèi)容 在修改前被讀入到 Cache，還是保存原來(lái)的 X，當(dāng)ＣＰＵ再次讀取該值時(shí)，就會(huì)發(fā)生不一致錯(cuò)誤。 (2)情況 2 ?解決問題的方法 當(dāng)外設(shè)修改主存單元內(nèi)容時(shí)，將Ｃ ache對(duì)應(yīng)位置的有效標(biāo)致位置無(wú)效即可． 主存 cache CPU1 X X’ 或 X (3)情況 3 CPU2 X’ …….. 習(xí)題課 直接 組相聯(lián) 例 1 采用組相聯(lián)映射方式的 Cache中，主存由 B0~ B7共 8塊組成，Cache有 2組，每組 2塊，每塊的大小為 8B，采用 LFU替換算法，在程序執(zhí)行過程中，依次訪問主存地址的塊流為 B B B B BB B0、 B B B B3。 Cache和主存地址格式，并標(biāo)出各部分的長(zhǎng)度 2 畫出主存與 Cache之間各塊的映象對(duì)應(yīng)關(guān)系 3 采用 LFU算法畫出塊的替換過程并計(jì)算 Cache的塊命中率 解：主存的容量為： 8*8=64B Cache的容量為： 2*2*8 = 32B 由組相聯(lián)的映射方法： 主存分組，組內(nèi)分塊，塊內(nèi)分字， Cache分組，組內(nèi)分行，行內(nèi)分字。 1) 主存和 Cache的地址格式及其每部分的長(zhǎng)度如下： 主存組號(hào) 組內(nèi)塊號(hào) 塊內(nèi)字號(hào) 2 1 3 主存地址格式 Cache組號(hào) 組內(nèi)行號(hào) 塊內(nèi)字號(hào) 1 1 3 Cache地址格式 2)Cache與主存之間的對(duì)應(yīng)關(guān)系如下圖所示 主存塊號(hào)及二進(jìn)制值 0 1 2 3 4 5 6 7 00 0 00 1 01 0 01 1 10 0 10 1 11 0 11 1 Cache 組號(hào) 1 0 30 B3 60 B6 10 B1 ? 50 1 70 0 61 60 20 1 40 00 40 0 B7 B5 B4 B0 B6 B6 B4 B2 C0 C1 3)利用 FLU算法進(jìn)行替換算法的映射全過程 命中率 = 1/11 例 。 以下程序 A和 B中，哪一個(gè)對(duì)數(shù)組 A[2048][2048]引用的空間局部性更好？時(shí)間局部性呢？變量 sum的空間局部性和時(shí)間局部性如何？對(duì)于指令來(lái)說， for循環(huán)體的空間局部性和時(shí)間局部性如何？ 程序段 A的時(shí)間局部性和空間局部性分析 (1)數(shù)組 A： 訪問順序?yàn)?A[0][0], A[0][1] ,……, A[0][2047]。 與存放順序一致，故 空間局部性好 ！ 但每個(gè) A[i][j]只被訪問一次，故 時(shí)間局部性差 ！ (2)變量 sum：?jiǎn)蝹€(gè)變量不考慮空間局部性； 每次循環(huán)都要訪問 sum，所以其時(shí)間局部性較好！ (3)for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！ 循環(huán)體被連續(xù)重復(fù)執(zhí)行 2048x2048次，所以時(shí)間局部性好！ 程序段 B的時(shí)間局部性和空間局部性分析 (1)變量 sum：（同程序 A ） (2)for循環(huán)體：（同程序 A） (3)數(shù)組 A：訪問順序?yàn)?A[0][0] ~A[2047][0]。 與存放順序不一致，每次跳過 2048個(gè)單元，若主存與 Cache之間交換信息的塊單位小于 2KB，則沒有空間局部性！ （每個(gè)數(shù)組變量只被訪問一次，沒有時(shí)間局部性， 同程序 A） 例 3 假定主存和 Cache之間采用直接映射方式，塊大小為 16B。Cache的數(shù)據(jù)區(qū)容量為 64KB，主存地址為 32位，按字節(jié)編址，數(shù)據(jù)字長(zhǎng) 32位。要求：說明主存地址如何劃分，訪存過程的硬件實(shí)現(xiàn) ,并計(jì)算 Cache有多少行？容量多大？ (1)計(jì)算機(jī)字長(zhǎng) 32位，每塊大小為 16B，按字節(jié)編址。 ?則一塊包含 4個(gè)字，故需要 2位表示選擇一塊內(nèi)的哪個(gè)字，而一個(gè)字 32位又包含 4個(gè)字節(jié)，故用 2位表示一個(gè) 32位字中的哪個(gè)字節(jié)。 (也可直接理解成需要 4位來(lái)表示選擇哪個(gè)字節(jié) ) ? Cache 分成的行數(shù)為： 64KB/16B = 4096塊， 則用于選擇 Cache行的索引字段位數(shù)為 12位 ?則標(biāo)記字段的位數(shù)為（表示主存的不同分區(qū)） 32 12 （ 2+2) = 16位 硬件訪問過程如下圖所示 (2)計(jì)算 Cache的容量 4096 ? （ 1+16 +128） = 580Kbits 例 4 設(shè)某機(jī)內(nèi)存容量為 16MB,Cache的容量 16KB,每塊 8個(gè)字 ,每個(gè)字32位 .設(shè)計(jì)一個(gè)四路組相聯(lián)映象 (即 Cache內(nèi)每組包含 4個(gè)字塊 )的Cache組織方式 (方式 1), 要求 : 1)畫出主存地址字段中各字段的位數(shù) 2)設(shè) Cache的初態(tài)為空 ,CPU依次從主存第 0,1,2,….99 號(hào)地址單元讀出100個(gè)字 (主存一次讀出一個(gè)字 ),并重復(fù)此次序讀 8次 ,問命中率為多少 ? 3)若 Cache的速度是主存速度的 6倍 ,問有 Cache和無(wú) Cache相比 ,存儲(chǔ)系統(tǒng)的速度提高了多少倍 解 :1) 每塊 8*32位 = 32B 塊內(nèi)地址 5位 Cache行數(shù) : 16KB/32B = 512行 Cache的組數(shù)為 : 512/4 =128組 則主存每組中包含的塊數(shù)為 128塊，組內(nèi)塊地址為 : 7位 主存組地址為 :24 57 =12位 主存組地址 組內(nèi)塊地址 塊內(nèi)字地址 12 7 5 2) 先畫出 Cache的基本結(jié)構(gòu) ………………….. 0組 一個(gè)字塊，包含 8個(gè)字，每個(gè)字 32位 0~7 8~15 16~23 24~31 32~39 40~47 48~55 56~63 64~71 72~79 80~87 88~95 96~103 0~7 32~39 64~71 96~103 8~15 40~47 72~79 16~23 48~55 80~87 24~31 56~63 88~95 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 ………. Z0 Z1 Z2 Z3 Zn K0 K1 K2 K3 K4 (0 組 ) ……………………. K13 按組相聯(lián)映射方式1的映射關(guān)系 0~7 8~15 16~23 24~31 32~39 40~47 48~55 56~63 64~71 72~79 80~87 88~95 96~103 0~7 8~15 16~23 24~31 32~39 40~47 48~55 56~63 64~71 72~79 80~87 88~95 96~103 104~111 112~119 120~127 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 ………. Z0 Z1 Z2 Z3 ?主存 100個(gè)單元只需分13塊 (4組 )就可調(diào)度完成 ,而 Cache有 128組 ,因此 ,訪問主存前 100號(hào)單元不會(huì)發(fā)生頁(yè)面調(diào)度 Zn K0 K1 K2 K3 K4 ……………………. K13 ?初始狀態(tài)為空 ,每塊第一個(gè)字不命中 ,后面 7個(gè)均命中 ?100號(hào)單元對(duì)應(yīng) 13塊 ,第一輪訪問 13次不命中 ,后七輪訪問均命中 ?命中率為 : (100*813)/(8*100) =% 按組相聯(lián)映射方式2的映射關(guān)系 3)由題意 ,設(shè)主存存取周期為 6t,Cache的存取周期為 t 則沒有 Cache的訪問時(shí)間為 : Tnc = 800*6t = 4800t 則有 Cache的訪問時(shí)間為 : Tc = 13*6t +(80013)*t = 865t 則采用 Cache后的訪問速度是沒有 Cache訪問速度的 ( 4800t/865t) 提高的倍數(shù)為 1 = 補(bǔ)充作業(yè) : 某計(jì)算機(jī)采用直接映象 Cache, 已知主存的容量為 4MB, Cache的容量為 4096B,字塊長(zhǎng)度為 8個(gè)字 (每字 32位 ). 1)畫出反映主存與 Cache映象關(guān)系的主存地址各字段