【正文】 31 11 31 40 11 21 31 50 10 ?缺點(diǎn)： 對新鮮數(shù)據(jù)保護(hù)不夠 (2)LRU 最近最少用算法 (Least recently used ) 該算法將一段時間內(nèi)最長時間沒有被使用的行調(diào)出。故 每行設(shè)置一個計(jì)時器，新調(diào)入的和命中行計(jì)數(shù)值為 0 ，同 時其他各行的計(jì)數(shù)器值加 1 ，當(dāng)需要發(fā)生頁面調(diào)度時，比 較各行計(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)象稱為抖動，出現(xiàn)的原因是用戶的程序足局性不好 在這種情況下， Cache的作用得不到發(fā)揮。 ?要充分發(fā)揮計(jì)算機(jī)硬件的高速特性，要求用戶的程序滿 足一定的要求！ 以便實(shí)現(xiàn)硬件與軟件的完美結(jié)合！ 7) 比較三種映射方法中的 LRU ?全相聯(lián) 每次改變和被比較的是 Cache所有行的計(jì)數(shù)值 ?直接相聯(lián) 不用 LRU,只要有沖突就直接替換原 Cache行中 的頁面，因?yàn)槭嵌鄬σ坏年P(guān)系 ?組相聯(lián) 頁面調(diào)入時 ,只是相關(guān)組內(nèi)的計(jì)數(shù)器的計(jì)數(shù)值會 發(fā)生變化 ,且比較時也是比較相關(guān)組內(nèi)所有 Cache行的計(jì)數(shù) 器的值 . a)幾個相關(guān)的概念 ? Cache臟位或修改位 (Dirty bit) 表示 Cache中的數(shù)據(jù)是否被修改過，當(dāng) Cache中某塊數(shù)據(jù)被 CPU修改 (寫 )時將該位置 1，一般用于 Cache的 寫回策略 ,即表示 Cache中的數(shù)據(jù)被更新，而主存中的數(shù)據(jù)未被更新。 ? Cache有效位 (Valid bit) 用來表示是否有不經(jīng)過 Cache的主存數(shù)據(jù)更新 (如 DMA操作 ),當(dāng)有這種主存數(shù)據(jù)更新時 ,有效位修改成 0,表示主存的數(shù)據(jù)被更新 ,而Cache中的數(shù)據(jù)無效 . 8) CACHE的一致性問題 b)Cache的結(jié)構(gòu) Tag Data Valid(1) Dirty(1) ?問題的提出： 正常情況下 , Cache是主存的副本，但經(jīng)過一段時間后，可 能會出現(xiàn)兩者內(nèi)容不一致的情況，導(dǎo)致這種不一致的情況有： CPU將 Cache某單元的內(nèi)容修改 成了 X’，而主存相關(guān)單元的內(nèi)容 還是 X，當(dāng)外設(shè)讀取 X對應(yīng)單元的 數(shù)值時，就會發(fā)生不一致錯誤。 c)Cache的一致性 主存 cache CPU X’ X I/O (1)情況 1 ?解決問題的方法 (a)寫直達(dá)法 (WT Write through)： CPU在執(zhí)行寫操作時，必須把數(shù)據(jù)同時寫入 Cache和主存。 (b)寫回法 (WB Write Back): CPU寫 Cache命中時，數(shù)據(jù)只寫向 Cache，不寫主存，同時修改 Cache中數(shù)據(jù)的臟位或修改位，供其它讀內(nèi)存的設(shè)備參考。 主存 cache CPU X X‘ I/O 外設(shè)將主存某單元的內(nèi)容修改 成了 X’，而主存該單元的內(nèi)容 在修改前被讀入到 Cache，還是保存原來的 X，當(dāng)ＣＰＵ再次讀取該值時，就會發(fā)生不一致錯誤。 (2)情況 2 ?解決問題的方法 當(dāng)外設(shè)修改主存單元內(nèi)容時，將Ｃ ache對應(yīng)位置的有效標(biāo)致位置無效即可． 主存 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)出各部分的長度 2 畫出主存與 Cache之間各塊的映象對應(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的地址格式及其每部分的長度如下： 主存組號 組內(nèi)塊號 塊內(nèi)字號 2 1 3 主存地址格式 Cache組號 組內(nèi)行號 塊內(nèi)字號 1 1 3 Cache地址格式 2)Cache與主存之間的對應(yīng)關(guān)系如下圖所示 主存塊號及二進(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 組號 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中，哪一個對數(shù)組 A[2048][2048]引用的空間局部性更好？時間局部性呢？變量 sum的空間局部性和時間局部性如何？對于指令來說， for循環(huán)體的空間局部性和時間局部性如何？ 程序段 A的時間局部性和空間局部性分析 (1)數(shù)組 A： 訪問順序?yàn)?A[0][0], A[0][1] ,……, A[0][2047]。 與存放順序一致，故 空間局部性好 ！ 但每個 A[i][j]只被訪問一次，故 時間局部性差 ！ (2)變量 sum：單個變量不考慮空間局部性； 每次循環(huán)都要訪問 sum，所以其時間局部性較好！ (3)for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！ 循環(huán)體被連續(xù)重復(fù)執(zhí)行 2048x2048次，所以時間局部性好！ 程序段 B的時間局部性和空間局部性分析 (1)變量 sum：（同程序 A ） (2)for循環(huán)體：（同程序 A） (3)數(shù)組 A：訪問順序?yàn)?A[0][0] ~A[2047][0]。 與存放順序不一致，每次跳過 2048個單元，若主存與 Cache之間交換信息的塊單位小于 2KB，則沒有空間局部性！ （每個數(shù)組變量只被訪問一次，沒有時間局部性， 同程序 A） 例 3 假定主存和 Cache之間采用直接映射方式，塊大小為 16B。Cache的數(shù)據(jù)區(qū)容量為 64KB，主存地址為 32位，按字節(jié)編址，數(shù)據(jù)字長 32位。要求：說明主存地址如何劃分，訪存過程的硬件實(shí)現(xiàn) ,并計(jì)算 Cache有多少行？容量多大？ (1)計(jì)算機(jī)字長 32位，每塊大小為 16B，按字節(jié)編址。 ?則一塊包含 4個字，故需要 2位表示選擇一塊內(nèi)的哪個字，而一個字 32位又包含 4個字節(jié)，故用 2位表示一個 32位字中的哪個字節(jié)。 (也可直接理解成需要 4位來表示選擇哪個字節(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個字 ,每個字32位 .設(shè)計(jì)一個四路組相聯(lián)映象 (即 Cache內(nèi)每組包含 4個字塊 )的Cache組織方式 (方式 1), 要求 : 1)畫出主存地址字段中各字段的位數(shù) 2)設(shè) Cache的初態(tài)為空 ,CPU依次從主存第 0,1,2,….99 號地址單元讀出100個字 (主存一次讀出一個字 ),并重復(fù)此次序讀 8次 ,問命中率為多少 ? 3)若 Cache的速度是主存速度的 6倍 ,問有 Cache和無 Cache相比 ,存儲系統(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組 一個字塊，包含 8個字，每個字 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個單元只需分13塊 (4組 )就可調(diào)度完成 ,而 Cache有 128組 ,因此 ,訪問主存前 100號單元不會發(fā)生頁面調(diào)度 Zn K0 K1 K2 K3 K4 ……………………. K13 ?初始狀態(tài)為空 ,每塊第一個字不命中 ,后面 7個均命中 ?100號單元對應(yīng) 13塊 ,第一輪訪問 13次不命中 ,后七輪訪問均命中 ?命中率為 : (100*813)/(8*100) =% 按組相聯(lián)映射方式2的映射關(guān)系 3)由題意 ,設(shè)主存存取周期為 6t,Cache的存取周期為 t 則沒有 Cache的訪問時間為 : Tnc = 800*6t = 4800t 則有 Cache的訪問時間為 : Tc = 13*6t +(80013)*t = 865t 則采用 Cache后的訪問速度是沒有 Cache訪問速度的 ( 4800t/865t) 提高的倍數(shù)為 1 = 補(bǔ)充作業(yè) : 某計(jì)算機(jī)采用直接映象 Cache, 已知主存的容量為 4MB, Cache的容量為 4096B,字塊長度為 8個字 (每字 32位 ). 1)畫出反映主存與 Cache映象關(guān)系的主存地址各字段