【正文】 ? 全 Cache系統(tǒng)：沒有主存，只有 Cache和磁盤。 ? 平均訪存時間 =命中時間 L1+失效率 L1*失效開銷 L1 ? 失效開銷 L1 =命中時間 L2+失效率 L2*失效開銷 L2 》》》 ? 平均訪存時間 =命中時間 L1+失效率 L1*（命中時間L2+失效率 L2*失效開銷 L2） 137 多級 Cache 局部失效率 ： (對應(yīng)某級的 Cache) 的訪問次數(shù)該級的失效次數(shù)該級局部失效率C a c h eC a c h e?全局失效率： 發(fā)出的訪存次數(shù)的失效次數(shù)該級全局失效率C PUC a c h e?全局失效率 L2 = 失效率 L1 * 失效率 L2 全局失效率會變小。 22）亂序取策略 先從主存讀取所需數(shù)據(jù)，使 CPU繼續(xù)執(zhí)行。 2。因此在替換時，只有數(shù)據(jù)體有寫回的問題。 3. 直接映象查表和讀取數(shù)據(jù)同時進行。 j 100。 i 5000。 Int val[size] Int key[size] 改為： Struct merge{ Int val Int key }。 ?在緩沖器中被訪問的指令數(shù)據(jù)塊返回時存入 Cache。命中時，直接訪問存取；失效時，先轉(zhuǎn)到檢查 Cache中的另一個位置，若仍不命中，再訪問主存。 注：提高 Cache相聯(lián)度和增加塊大小都會產(chǎn)成副作用。 (3) 但當(dāng) Cache容量小時，增加塊大小，可能提高失效率。 112 Cache的性能分析 1. Ta=Tc*H+(1H)Tm 2. Ta=Tc*H+(1H)(Tc+Tm) =Tc+(1H)Tm 平均訪存時間＝命中時間＋失效率 失效開銷 注： Tm—— 主存訪問時間 Ta—— 平均訪存時間 113 Cache系統(tǒng)的加速比 等效的訪問周期為 T a mccca THTHT )1( ???Cache系統(tǒng)的加速比 Sp )1(1)1(cmccmcccmampHTTHTHTHTTTS???????命中率越高，加速比越大。 2. 某些塊被替換時沒有被修改過。 ? 對 Cache的讀操作，查表命中檢查可以和讀數(shù)同時進行，而寫操作，必須先進行命中檢查， 命中后，方可進行寫操作 。 ? 優(yōu)點：利用局部性原理 ? 缺點：不易實現(xiàn) 106 例： 設(shè)有一道程序，有 1至 5共五塊，執(zhí)行時的塊地址流（即執(zhí)行時依次用到的程序塊號）為： 2， 3， 2， 1， 5， 2， 4， 5， 3， 2， 5， 2 若分配給該道程序的緩存有 3塊，分別采用 FIFO和 LFU替換算法表示這 3塊的使用和替換過程。 ? 實現(xiàn)： 每次訪問塊計數(shù)器加 1。且 Cache中一般 不 采用全相聯(lián)映象方式。 設(shè) G = 2g, k是 i 的 低 k位。 2. 主存中的每一塊可以放置到 Cache中唯一的一組內(nèi)任意塊位置。 2. 主存容量是緩存容量的整數(shù)倍，將主存空間按緩存的大小分成區(qū)，主存中每一區(qū)中的組數(shù)與緩存的組數(shù)相同。 直接映象 目錄表容量小， 全相聯(lián)映象 目錄表大。 92 例： 例 3 假設(shè)在某個計算機系統(tǒng)中 Cache容量為 32K字節(jié)，數(shù)據(jù)塊大小是 16個字節(jié)，主存容量是 1M，地址映象為全相聯(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個數(shù)據(jù)塊， Cache有 4個數(shù)據(jù)塊（見前圖）。 3. 主存中某區(qū)中的一塊存入緩存時只能存入緩存中塊號相同的位置。 Cache存儲體 2. 當(dāng)在 Cache不能發(fā)現(xiàn)所需數(shù)據(jù)，需要到主存中讀取，并轉(zhuǎn)存入 Cache。塊的大小通常以在主存的一個存儲周期能訪問到的數(shù)據(jù)長度為限。 72 虛擬存儲器的性能分析 訪問虛存的等效訪問周期 21 )1( THTHT vvv ???影響命中率的因素有下列幾方面： (一 ) 頁面大小 (二 ) 主存容量 (三 ) 頁面調(diào)度方式 訪問主存的時間 訪問主存的命中率 磁盤存儲器的訪問速度 73 啟示： 當(dāng)為某個程序分配存儲空間時，容量增加到一定時程度，命中率增加很慢。 70 頁面替換算法的實現(xiàn) ? 基本方法： 設(shè)立一個主存頁面分配表，記錄主存頁面使用情況，一條記錄默認對應(yīng)一個主存頁。 ? 區(qū)分是否為堆棧型替換算法的目的在于尋求調(diào)整主存頁分配的方法。 FIFO就不是一種堆棧型算法，而LRU和 OPT一定是堆棧型的算法。 ? 解決方法： 增加程序的使用頁面數(shù)。 ? 最優(yōu)替換算法（ OPT），將來最久不被訪問的頁面，以歷史信息為依據(jù)。 ? 常用頁面替換算法 : （五種算法） ? 隨機算法（ RAND），隨機選擇主存中的頁面。 形式描述： An=H(Pv) 要求此 H采用硬件實現(xiàn)，技術(shù)上可以采用折疊的方法。 ② 當(dāng)在快表中未找到時，在慢表中查找到的實頁號 P不僅送到地址 register中 ,而且同時也送到快表之中。稱這個小容量的頁目錄為快表。 57 提高查表速度 ——方法一：目錄表 ? 一個目錄表項對應(yīng)一個主存頁 采用基于內(nèi)容訪問的相聯(lián)存儲器 (圖 ) ? （同 Cache中的全相聯(lián)映象） 存在的不足： 當(dāng)主存容量增加時，目錄表的容量也將增加，此時查表的速度將減慢，因此不利于提高訪存的速度。即按照圖 Pagetable1頁的大小 (4KB ) 。 ③ 采用指令預(yù)判技術(shù)，對于可能要產(chǎn)生 Page fault 的指令，先將其調(diào)入 RAM，才開始執(zhí)行該條指令。 斷點和現(xiàn)場的確定和處理。 51 外部地址變換 ? 每一個用戶有一張外頁表。需要將虛擬地址轉(zhuǎn)成輔存的物理地址，以便訪問輔存。 50 地址變換 ? 內(nèi)部地址映象：把虛擬地址空間映象到主存物理地址空間。 48 段頁式虛擬存儲器 ——地址變換 段表基地址 段表長度 As 6 頁表地址 頁表長 標(biāo)志 修改位 裝入位 Ap 0/1 1 虛頁號 P 頁內(nèi)偏移 D 段號 S 用戶號 U ＋ 多用戶虛地址 一個用戶段表 各種標(biāo)志 修改位 實頁號 裝入位 0/1 p 1 實頁號 p 頁內(nèi)偏移 D ＋ 一個段的頁表 Ap 主存地址 用戶表 49 段頁式虛擬存儲器 ——分析 注意： 1）段表和頁表一個記錄項對應(yīng)虛存的一個虛段和虛頁。 ? 程序的模塊化性能不好 (頁大小固定，程序段長度變化）。 ? 頁表的管理比較簡單，可以不考慮程序的長短，按固定塊長分配，管理，調(diào)度。 44 （ 2）頁式虛擬存儲器 ? 頁： 將主存空間與虛存空間按固定的大小劃分成塊 ，每塊稱為一頁 。 42 段式虛擬存儲器 ——地址變換 段表基地址 段表長度 As 5 訪問方式 段長 裝入位 起始地址 段號 5 4 3 2 1 段內(nèi)偏移 D 段號 S 用戶號 U 主存實地址 ＋ ＋ 多用戶虛地址 一個用戶的段表 As 用戶表（段表基址寄存器） 43 段式虛擬存儲器 ——分析 ? 優(yōu)點： ? 程序模塊化的性能好，各段在功能上是相互獨立的； ? 便于程序與數(shù)據(jù)的共享； ? 程序的動態(tài)鏈接比較容易； ? 便于實現(xiàn)存儲保護。 多次段調(diào)入，可能造成主存空間碎片。 ? 地址映象： 將虛存空間分段，主存的空間按這種段來分配和管理 。 替換算法 基本使用最久未使用算法 LFU。 實頁號 p 頁內(nèi)偏移 d 主存地址的組成 用戶號 U 頁內(nèi)偏移 D 多用戶虛擬地址的組成 虛頁號 P 35 虛擬存儲器工作工程 磁盤地址 (Head,cyle,sect) 外部地址變換 Uid Pv D 內(nèi)部地址變換 P m D 0頁 1頁 ? ? 1 2 ? p 頁 I/O 處理機 I/O 通道 可用主存頁號 替換算法 主存頁面表 AV(多用戶虛地址 ) 0頁 0頁 1頁 0頁 1 2 n 1 2 ? n 不 命 中 主存 頁面實效 主 存 未 滿 主存滿 rollin rollin out rollin out rollin 虛擬存儲器 選 頁 X 用 戶 Y 用 戶 命中時 主頁空間 36 虛擬存儲器的特點 1）多用戶多進程可以共享主存空間 每個用戶或進程具有獨立存儲空間，多用戶和進程共享較小的存儲空間 2）程序員不必管理存儲器 程序自動覆蓋 3）采用動態(tài)再定位，簡化程序的裝入 37 虛擬存儲器需要解決的四個問題 映象規(guī)則 由于輔存一般是磁盤，當(dāng)不命中時，失效開銷非常大。 ? 目的：解決主存容量不足的問題。 ? 關(guān)于多維數(shù)組的無沖突訪問存儲器：例子見下頁。 28 轉(zhuǎn)移概率與并行存儲器 2468101214160 ggNn)1(1 ???轉(zhuǎn)移概率 gn 轉(zhuǎn)移概率 g和并行存貯存貯體 n 間的關(guān)系 一般地取 n=8時，效果良好。 ? 設(shè) p(1)=g；表示讀出的第一條指令為轉(zhuǎn)移指令的概率。 N為每個存儲周期能讀取的平均有效字數(shù)。 ? 采用低位交叉訪問存貯器能夠大幅度地提高 主存的速度。 ? 主要沖突： ? 取指令沖突（條件轉(zhuǎn)移，轉(zhuǎn)移成功，隨后取出指令無用） ? 讀操作數(shù)沖突（需要的多個操作數(shù)不一定都存放在同一個存儲字中，否則可能需要多次讀出） ? 寫數(shù)據(jù)沖突（必須湊齊 n個數(shù)才一起寫入存儲器，否則影響頻帶寬度） ? 讀寫沖突（要讀出的一個字和要寫入的一個字處在同一個存儲字內(nèi)時，無法在一個存儲周期內(nèi)完成）。 ? 三種方法實現(xiàn)并行存儲器： ? 并行訪問存貯器 ? 交叉訪問存儲器 ? 無訪問沖突存儲器 18 并行訪問存儲器 數(shù)據(jù)寄存器 數(shù)據(jù)總線 地址總線 地址寄存器 體號 W W1 W2 W3 W4 m1 m2 m3 m4 b a 體內(nèi)地址 地址寄存器中 高位部分 作為 模塊地址 ，同時訪問多個存儲模塊。???16 頻帶平衡 ? 頻帶寬度： 單位時間內(nèi)所能訪問的數(shù)據(jù)量。利用了程序的局部性原理。 ? 多級 Cache：通常采用兩級或三級 Cache。用軟件或軟件和硬件結(jié)合的方法實現(xiàn)。若仍不能發(fā)現(xiàn)數(shù)據(jù)，接著訪問 Mi，依次類推，直至 M