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