計算機(jī)系統(tǒng)結(jié)構(gòu)—第三章(存儲系統(tǒng))課件

1、存儲系統(tǒng)存儲系統(tǒng)原理虛擬存儲系統(tǒng)Cache存儲系統(tǒng)三級存儲系統(tǒng)存儲系統(tǒng)原理本章內(nèi)容引入存儲系統(tǒng)的基本概念存儲器的層次結(jié)構(gòu)存儲器的頻帶平衡存儲器的作用本章內(nèi)容存儲系統(tǒng)原理 現(xiàn)代計算機(jī)系統(tǒng)都以存儲器為中心（不同于以運(yùn)算器為中心的馮諾依曼計算機(jī)），存儲器是各種信息存儲和交換的中心。3 之 1主存儲器取 指 令取 操 作 數(shù)寫 結(jié) 果I/O 數(shù) 據(jù)存儲器的性能指標(biāo) 存儲容量 SM=Wlm。其中：W為存儲體的字長，l為每個存儲體的字?jǐn)?shù)，m為并行工作的存儲體個數(shù)。 存儲速度 可以用訪問時間TA、存儲周期TM和頻寬（帶寬）BM來描述。 存儲價格 可以用總價格C或每位價格c表示。本章內(nèi)容存儲系統(tǒng)原理3 之 2

2、存儲器的設(shè)計 設(shè)計目的 基本要求是：高速度、大容量、低價格。 存在問題 單靠一種工藝的單一存儲器無法同時滿足容量、速度和價格三方面的要求。 解決方法 使用多種不同工藝的存儲器組成存儲系統(tǒng)，使所有的信息以各種方式分布于不同的存儲器上。本章內(nèi)容存儲系統(tǒng)原理3 之 3存儲系統(tǒng)的基本概念本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的定義常用存儲系統(tǒng)存儲系統(tǒng)的性能指標(biāo)存儲系統(tǒng)的設(shè)計存儲系統(tǒng)的定義本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念 兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件或軟硬件相結(jié)合的方法連接起來成為一個系統(tǒng)。這個系統(tǒng)對應(yīng)用程序員透明，并且，從應(yīng)用程序員看它是一個“存儲器”，這個“存儲器”的速度接

3、近于速度最快的那個存儲器，存儲容量接近于容量最大的那個存儲器，單位容量的價格接近于最便宜的那個存儲器。3 之 1圖示存儲系統(tǒng)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念M1(T1, S1, C1)M2(T2, S2, C2)Mn(Tn, Sn, Cn)Tmin(T1, T2, , Tn), 用存儲周期表示Smax(S1, S2, , Sn), 用MB或GB表示Cmin(C1, C2, , Cn), 用每位的價格表示從外部看3 之 2教師和學(xué)生本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念3 之 3有這么好的事？當(dāng)然有！訪存局部性原理是存儲系統(tǒng)設(shè)計的基礎(chǔ)。常用存儲系統(tǒng)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念虛擬

4、存儲系統(tǒng)Cache存儲系統(tǒng)虛擬存儲系統(tǒng)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念常用存儲系統(tǒng) 原理 由主存儲器和磁盤存儲器構(gòu)成 。 目的 增加存儲器的存儲容量。 特點 采用硬件和軟件相結(jié)合的方法來調(diào)度，因此對應(yīng)用程序員是透明的，對系統(tǒng)程序員是不透明的。主存儲器磁盤存儲器 這個存儲系統(tǒng)從應(yīng)用程序員看：速度接近主存的速度，容量是虛擬地址空間，每位價格接近磁盤存儲器的價格。Cache存儲系統(tǒng)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念常用存儲系統(tǒng) 原理 由Cache和主存儲器構(gòu)成。 目的 提高存儲器的速度。 特點 全部用硬件來調(diào)度，不僅對應(yīng)用程序員還是系統(tǒng)程序員都是透明的。Cache主存儲器 這個存儲系統(tǒng)從系

5、統(tǒng)/應(yīng)用程序員看：速度接近Cache的速度，容量是主存的容量，每位價格接近主存的價格。存儲系統(tǒng)的性能指標(biāo)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲容量存儲價格存儲速度M1(S1,C1,T1)M2(S2,C2,T2)M(S,C,T) 為了分析方便，采用由兩個存儲器M1和M2組成的存儲系統(tǒng)M。存儲容量本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo) 存儲容量接近于M2（即：SS2）。對存儲系統(tǒng)進(jìn)行編址的方法有：可以選擇對M2進(jìn)行編址，M1可以不編址或在系統(tǒng)內(nèi)部編址 例如：Cache存儲系統(tǒng)。為存儲系統(tǒng)另外設(shè)計一個抽象的地址空間，在系統(tǒng)內(nèi)部對M1、M2分別編址并將地址映象到這個抽象的地址空間

6、中 例如：虛擬存儲系統(tǒng)。存儲價格本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo) 整個存儲系統(tǒng)的單位容量平均價格為： 當(dāng)S2S1時，cc2，但S1與S2不能相差太大，否則存儲系統(tǒng)要達(dá)到比較高的性能，調(diào)度起來很困難。存儲速度本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo)命中率H 在M1存儲器中訪問到的概率。存儲系統(tǒng)的訪問時間TN1: M1的訪問次數(shù)N2: M2的訪問次數(shù)6 之 1存儲系統(tǒng)的訪問效率本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo) 提高存儲系統(tǒng)速度的兩條途徑：提高命中率H（見例1）兩個存儲器的速度不要相差太大（見例3）6 之 2例1：不同命中率本章內(nèi)容存儲

7、系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo)問：假設(shè)T2=5T1，在命中率H為0.9和0.99兩種情況下，分別計算存儲系統(tǒng)的訪問效率。答：當(dāng)H=0.9時： 當(dāng)H=0.99時：6 之 3采用預(yù)取技術(shù)提高命中率本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo) 思想 不命中時，把M2存儲器中相鄰幾個單元組成的一個數(shù)據(jù)塊都取出來送入M1存儲器中。 命中率 （見例2）其中：H是采用預(yù)取技術(shù)后的命中率； H是原來的命中率； n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積。6 之 4例2：預(yù)取技術(shù)本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo)問：在一個虛擬存儲系統(tǒng)中，T2105 T1，原來的命中率

8、只有0.8，如果訪問磁盤存儲器的數(shù)據(jù)塊大小為4K字，并要求訪問效率不低于0.9，計算數(shù)據(jù)在主存儲器中的重復(fù)利用率至少為多少？答：假設(shè)數(shù)據(jù)在主存儲器中的重復(fù)利用率為m，根據(jù)前面的給出關(guān)系： 解之得：m=446 之 5例3：兩個存儲器的速度相差太大本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念存儲系統(tǒng)的性能指標(biāo)問：在虛擬存儲系統(tǒng)中，兩級存儲器的速度相差特別懸殊T2=105T1。如果要使訪問效率e=0.9，問需要有多高的命中率？答： 解之得： H=0.999998888877777.0.9999996 之 6存儲系統(tǒng)的設(shè)計本章內(nèi)容存儲系統(tǒng)原理存儲系統(tǒng)的基本概念設(shè)計原則相鄰級的容量差、速度差較大；(減少C)存

9、儲層次具有較高的命中率；(減少T)存儲層次的輔助軟、硬件開銷較小。涉及問題映象規(guī)則：塊從低層調(diào)入高層時放在何位置；查找算法：如何在本層次中查找需訪問的塊；替換算法：發(fā)生失效時，替換哪個塊；寫 策 略：進(jìn)行寫訪問時，應(yīng)進(jìn)行那些操作。存儲器的層次結(jié)構(gòu)本章內(nèi)容存儲系統(tǒng)原理訪問速度越來越快通用寄存器堆指令和數(shù)據(jù)緩沖Cache (SRAM)主存儲器（DRAM）聯(lián)機(jī)外部存儲器（磁盤等）脫機(jī)外部存儲器（磁帶、光盤等）每位的價格越來越便宜存儲容量越來越大CPU內(nèi)部存儲器的頻帶平衡本章內(nèi)容存儲系統(tǒng)原理 問題 計算機(jī)中各級存儲器頻帶應(yīng)該達(dá)到平衡，即：存儲器的速度應(yīng)能跟得上系統(tǒng)的需要。 方法多個存儲器并行，采用并行

10、/交叉訪問等方法提高存儲器的訪問速度（并行存儲器）；設(shè)置各種緩沖存儲器；采用存儲體系，特別是Cache存儲體系。2 之 1并行存儲器本章內(nèi)容存儲系統(tǒng)原理并行訪問存儲器交叉訪問存儲器2 之 2并行訪問存儲器 思想 增加存儲器的字長，例如：把m字w位的存儲器（單體單字存儲器）改變成為m/n字nw位的存儲器（單體多字存儲器），見后圖。 特點優(yōu)點：實現(xiàn)簡單、容易。缺點：訪問的沖突大（取指令沖突、讀操作數(shù)沖突、寫數(shù)據(jù)沖突和讀寫沖突）。本章內(nèi)容存儲系統(tǒng)原理并行存儲器2 之 1圖示并行訪問存儲器本章內(nèi)容存儲系統(tǒng)原理并行存儲器數(shù)據(jù)寄存器MDR存儲體(m字w位)地址寄存器MAR多路選擇器MDR存儲體(m/n字n

11、w位)MAR一般存儲器并行訪問存儲器2 之 2交叉訪問存儲器本章內(nèi)容存儲系統(tǒng)原理并行存儲器地址碼高位交叉地址碼低位交叉地址碼高位交叉訪問存儲器本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器MDR存儲體0MAR0.00.00.0F.FMDR存儲體1MAR0.10.00.1F.FMDR存儲體n-1MARF.F0.0F.FF.F譯碼器 高位 地址寄存器（低位） MDR 數(shù)據(jù)寄存器 MAR 地址寄存器 3 之 1地 址 存儲器某單元的地址為：A = mk + jm：為每個存儲體的容量（地址碼的低log2m位作為存儲體的體內(nèi)地址，而且每個存儲體都相同）。 k：為存儲體的編號，k=0,1,2,n-1（其中n

12、為組成存儲器的存儲體個數(shù)的總和，地址碼的高log2n位作為一個譯碼器的輸入） j：為各個存儲體的體內(nèi)地址，k=0,1,2,m-1 如果已知地址A，則： 存儲器的體內(nèi)地址Aj的計算公式為：Aj = A mod m 存儲器的體號Ak的計算公式為：Ak = A/m本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器3 之 2目 的本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器 目的 擴(kuò)大存儲器容量。 例子 目前，大部分計算機(jī)系統(tǒng)中所采用的模塊化主存儲器通常都是采用高位交叉編址方法實現(xiàn)。 應(yīng)用在單任務(wù)系統(tǒng)中：可用于擴(kuò)大存儲器容量，且擴(kuò)充性好。在多任務(wù)或多用戶系統(tǒng)中：可以通過把不同的任務(wù)分配給不同的存儲體完成來提

13、高存儲器的訪問速度。3 之 3地址碼低位交叉訪問存儲器本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器MDR存儲體0MAR0.00.0F.F0.0MDR存儲體1MAR0.00.1F.F0.1MDR存儲體n-1MAR0.0F.FF.FF.F譯碼器 地址寄存器（高位） （低位） MDR 數(shù)據(jù)寄存器 MAR 地址寄存器 4 之 1地 址 存儲器某單元的地址為：A = nj + km：為每個存儲體的容量（地址碼的高log2m位作為存儲體的體內(nèi)地址，而且每個存儲體都相同）。 k：為存儲體的編號，k=0,1,2,n-1（其中n為組成存儲器的存儲體個數(shù)的總和，地址碼的低log2n位作為一個譯碼器的輸入） j：為

14、各個存儲體的體內(nèi)地址，k=0,1,2,m-1 如果已知地址A，則： 存儲器的體內(nèi)地址Aj的計算公式為：Aj = A/n 存儲器的體號Ak的計算公式為：Ak = A mod n本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器4 之 2目 的本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器 目的 提高存儲器訪問速度。 實現(xiàn) 為此在一個存儲周期內(nèi)，n個存儲體必須同時或分時啟動，實際上是一種采用流水線方式工作的并行存儲器。4 之 3#0t存儲周期Tm#1#2#n-1啟動間隔t = Tm/n問 題本章內(nèi)容存儲系統(tǒng)原理并行存儲器交叉訪問存儲器4 之 4 問題 主存儲器的速度不是隨存儲體的個數(shù)的增加而線性增加。例如

15、：在有的大型計算機(jī)中采用32個存儲體低位交叉來構(gòu)成主存儲器，但是主存儲器的速度只比單個存儲體高10倍左右。 原因 存在訪問沖突，產(chǎn)生沖突的根源主要有二：程序中有轉(zhuǎn)移指令和數(shù)據(jù)的隨機(jī)性。 解決 設(shè)計一種無訪問沖突的存儲器。虛擬存儲系統(tǒng)本章內(nèi)容 虛擬存儲系統(tǒng)也稱虛擬存儲器、虛擬存儲體系，1961年英國曼徹斯特大學(xué)Kilbrn等人提出，70年代廣泛地應(yīng)用于大中型計算機(jī)系統(tǒng)中，目前許多微型機(jī)也開始使用虛擬存儲器。虛擬存儲系統(tǒng)本章內(nèi)容虛擬存儲系統(tǒng)本章內(nèi)容虛擬存儲系統(tǒng)的工作原理地址的映象和變換方法加快內(nèi)部地址變換速度的方法頁面替換算法提高主存命中率的方法頁式虛擬存儲器工作原理磁盤存儲器地址 訪磁盤存儲器

16、命中外部地址變換未命中訪磁帶等虛頁號磁盤實地址外部地址變換 U+PUPD Av多用戶虛地址 主存頁面失效 U+P未命中內(nèi)部地址變換選頁 命中虛頁號主存實頁號主存頁面表0頁 主存未滿 主存滿1頁X訪問主存pd A頁面用替換算法戶2P-10頁主存頁號0頁1頁調(diào)入頁I/O處理機(jī)調(diào)入頁1頁Y被替換頁（I/O通道）替換頁用戶2p-1主存儲器 磁盤存儲器命中？命中？基本概念本章內(nèi)容虛擬存儲系統(tǒng) 三個地址空間 虛擬地址空間、主存地址空間和輔存地址空間。 三個地址 虛擬地址、主存地址和輔存地址。 地址映象 把虛擬地址空間映象到主存地址空間。 地址變換 在程序運(yùn)行時，把虛地址變換成主存地址（內(nèi)部地址變換）或輔存

17、地址（外部地址變換）。外部地址變換本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法裝入磁盤實地址用戶號頁內(nèi)偏移1虛頁號外部地址變換（軟件實現(xiàn)）磁盤號柱面號磁頭號塊號多用戶虛地址外頁表主要內(nèi)容本章內(nèi)容虛擬存儲系統(tǒng) 根據(jù)所采用的地址映象和變換方法（內(nèi)部地址變換）不同，有三種不同類型的虛擬存儲器： 段式虛擬存儲器 頁式虛擬存儲器 段頁式虛擬存儲器段式虛擬存儲器的地址映象本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法 0段1k1段2段3段0500020002000段號段長起址01k8k150016k22009k320030k08k9k16k30k程序空間主存儲器主程序段表3 之 1段大小可變段式虛擬存儲器的地址變換

18、本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法 0段表長度段表基址5As段名起始地址裝入位段長訪問方式用戶號U段號S段內(nèi)偏移D多用戶虛地址主存實地址432101n-1As段表基址寄存器一個用戶（一道作業(yè)）的段表3 之 2段式虛擬存儲器的特點優(yōu)點程序的模塊化性能好便于程序和數(shù)據(jù)的共享程序的動態(tài)鏈接和調(diào)度比較容易便于實現(xiàn)信息保護(hù)缺點地址變換所花費(fèi)的時間比較長，做兩次加法運(yùn)算主存儲器的利用率往往比較低對輔存（磁盤存儲器）的管理比較困難本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法 3 之 3頁式虛擬存儲器的地址映象本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法3 之 10頁1頁2頁3頁頁號主存頁號0123用戶程序主存

19、儲器頁表虛頁號實頁號虛實頁號對照表頁大小固定頁式虛擬存儲器的地址變換本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法 3 之 2Pa裝入位修改位主存頁號標(biāo)志用戶號U虛頁號P頁內(nèi)偏移D頁內(nèi)偏移d1 pPa頁表基址寄存器頁表實頁號p01342頁式虛擬存儲器的特點優(yōu)點主存儲器的利用率比較高；頁表相對比較簡單；地址變換的速度比較快；對磁盤的管理比較容易。缺點程序的模塊化性能不好；頁表很長，需要占用很大的存儲空間。本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法3 之 3段頁式虛擬存儲器的地址映象本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法3 之 10段(12K)段表用戶程序0段頁表主存儲器1段(10K)2段(5K)頁表長

20、度332頁表地址每頁4KB4K4K4K1段頁表2段頁表段頁式虛擬存儲器的地址變換本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法3 之 2用戶號U段號S頁內(nèi)偏移頁內(nèi)偏移Ap實頁號p虛頁號PAsAs裝入修改實頁號標(biāo)志0/11p頁表地址頁表長標(biāo)志修改裝入Ap0/11多用戶頁表多用戶段表段表基址寄存器段頁式虛擬存儲器的特點 段頁式虛擬存儲器一方面具有段式虛擬存儲器的主要優(yōu)點，另一方面具有頁式虛擬存儲器的主要優(yōu)點。本章內(nèi)容虛擬存儲系統(tǒng)地址的映象和變換方法 3 之 3加快內(nèi)部地址變換速度的方法本章內(nèi)容虛擬存儲系統(tǒng)引入目錄表快慢表散列函數(shù)舉例引 入本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 在段/頁式虛擬存儲

21、器中，要訪問主存必須先查段/頁表，在段頁式虛擬存儲器中，既要查段表也要查頁表。如果段、頁表都在主存中，則包括訪問主存本身這一次在內(nèi)，虛擬存儲器的訪問速度將要降低2至3倍。 因此要想使虛擬存儲器的速度接近主存的速度，必須加快查表的速度。下面以頁式虛擬存儲器為例進(jìn)行介紹目錄表的基本思想本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 壓縮頁表的存儲容量（因為虛存頁面數(shù)遠(yuǎn)大于主存頁面數(shù)），用一個小容量高速存儲器存放頁表，從而加快頁表的查表速度。3 之 1目錄表的實現(xiàn) 頁表壓縮 頁表中只保留已裝入主存的那些頁。 高速存儲器 采用按內(nèi)容訪問的相聯(lián)存儲器。本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法實頁號

22、其它標(biāo)志用戶號U頁內(nèi)偏移Dp虛頁號P多用戶虛地址目錄表（按內(nèi)容訪問的相聯(lián)存儲器）頁內(nèi)偏移d實頁號p多用戶虛頁號U, P修改0/1主存實地址相聯(lián)訪問3 之 2目錄表的特點本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 優(yōu)點 與頁表放在主存中相比，查表速度快。 缺點 可擴(kuò)展性比較差，且主存儲器容量增加時，目錄表的造價高，速度降低。3 之 3快慢表的基本思想本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 根據(jù)局部性原理，將頁表分為快表和慢表。快表TLB(Translation Lookaside Buffer)由小容量（幾幾十個字）、高速硬件實現(xiàn)，采用相聯(lián)方式訪問，存放最近用到的頁表信息。當(dāng)快表中查

23、不到時，再從存放在主存儲器中的慢表中查找?？毂砼c慢表也構(gòu)成了一個兩級存儲系統(tǒng)。2 之 1快慢表的實現(xiàn)本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法實頁號用戶號U頁內(nèi)偏移Dp虛頁號P多用戶虛地址頁內(nèi)偏移d實頁號p多用戶虛頁號U, P主存實地址實頁號p裝入1慢表（按地址訪問）快表（按內(nèi)容訪問）2 之 2散列函數(shù)的基本思想本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 將快表的按內(nèi)容相聯(lián)訪問變成按地址訪問，從而可以加大快表容量。為提高快表的查找速率采用散列查找法，散列（Hash）函數(shù)為：快表地址H(多用戶虛頁號)，為避免散列沖突采用相等比較器。2 之 1散列函數(shù)的實現(xiàn)本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址

24、變換速度的方法實頁號用戶號U頁內(nèi)偏移Dp虛頁號P多用戶虛地址按地址訪問的快表頁內(nèi)偏移d實頁號p多用戶虛頁號Pv主存實地址散列變換（硬件實現(xiàn)）相等比較多用戶虛頁號Pv查慢表快表地址Ah快表命中2 之 2舉例：IBM 370/168本章內(nèi)容虛擬存儲系統(tǒng)加快內(nèi)部地址變換速度的方法 IBM 370/168計算機(jī)的虛擬存儲器快表結(jié)構(gòu)及地址變換過程見后圖。虛擬地址長48位，頁面大小為4KB，每個用戶最多占用4K個頁面，最多允許16M個用戶，但同時上機(jī)的用戶數(shù)一般不超過6個。 采用了兩項新的措施： 采用兩個相等比較器 用相聯(lián)寄存器組把24位用戶號U壓縮成3位2 之 12 之 2頁面替換算法本章內(nèi)容虛擬存儲系

25、統(tǒng)概述頁面替換算法隨機(jī)算法（RAND 算法）先進(jìn)先出算法（FIFO算法）近期最少使用算法 （LFU算法）最久沒有使用算法 （LRU算法）最優(yōu)替換算法（OPT算法）堆棧型算法概 述本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 為什么需要頁面替換？ 當(dāng)發(fā)生頁面失效時，要從磁盤中調(diào)入一頁到主存。如果主存所有頁面都已經(jīng)被占用，此時必須從主存儲器中淘汰掉一個不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。 評價頁面替換算法好壞的標(biāo)準(zhǔn) 一是命中率要高，二是算法要容易實現(xiàn)。隨機(jī)算法（RAND 算法）本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 算法 利用軟件或硬件的隨機(jī)數(shù)發(fā)生器來確定主存中要被替換的頁面。 特點 算法簡單，容易

26、實現(xiàn)；但沒有利用歷史信息，沒有反映程序的局部性，命中率低。先進(jìn)先出算法（FIFO算法）本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 算法 選擇最先調(diào)入主存的頁面作為要被替換的頁面。 特點 比較容易實現(xiàn)，利用了歷史信息，但沒有反映程序的局部性。近期最少使用算法 （LFU算法）本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 算法 選擇近期最少訪問的頁面作為要被替換的頁面。 特點 既充分利用了歷史信息，又反映了程序的局部性，但實現(xiàn)起來非常困難。最久沒有使用算法 （LRU算法）本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 算法 選擇近期最久沒有被訪問過的頁面作為要被替換的頁面。 特點 既充分利用了歷史信息，又反映了程序的局部性，而且實現(xiàn)起

27、來比較容易。最優(yōu)替換算法（OPT算法）本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 算法 選擇將來最久不被訪問的頁面作為要被替換的頁面。 特點 OPT算法是一種理想化的算法，可用來作為評價其它頁面替換算法好壞的標(biāo)準(zhǔn)。3 之 1例 子本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法3 之 2 一個程序共有5個頁面組成，程序執(zhí)行過程中的頁地址流如下：P1, P2, P1, P5, P4, P1, P3, P4, P2, P4 假設(shè)分配給這個程序的主存儲器共有3個頁面。給出FIFO、LRU、OPT 三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。在虛擬存儲器中，實際上有可能采用只有FIFO和LRU兩種算法。三種

28、頁面替換算法對同一個頁地址流的調(diào)度過程時間12345678910實際命中次數(shù)頁地址流P1P2P1P5P4P1P3P4P2P4FIFO算法1111 *444 *4 *222次2222 *1111 *4555 *3333*調(diào)入調(diào)入命中調(diào)入替換替換替換命中替換替換LRU算法11111 *111 *224次222 *444 *44455 5 *333 *3 *調(diào)入調(diào)入命中調(diào)入替換命中替換命中替換命中OPT算法111111 *3 *3 *335次2222 *222225 *444444調(diào)入調(diào)入命中調(diào)入替換命中替換命中命中命中3 之 3堆棧型算法本章內(nèi)容虛擬存儲系統(tǒng)頁面替換算法 定義 對任意一個程序的頁地

29、址流作兩次主存頁面數(shù)分配，分別分配m個主存頁面和n個主存頁面，并且有mn。如果在任何時刻t，主存頁面數(shù)集合Bt都滿足關(guān)系：Bt(m) Bt(n)，則這類算法稱為堆棧型替換算法。 基本思想 隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。 例子 LFU、LRU和OPT算法是堆棧型替換算法，而FIFO算法不是。2 之 1FIFO 替換算法是非堆棧型算法2 之 2提高主存命中率的方法本章內(nèi)容虛擬存儲系統(tǒng) 影響主存命中率的主要因素：程序執(zhí)行過程中的頁地址流分布情況所采用的頁面替換算法頁面大小主存容量所采用的頁面調(diào)度算法頁面大小的選擇本章內(nèi)容虛擬存儲系統(tǒng)提高主存命中率的方法 頁面大小的選

30、擇一般要通過對典型程序的模擬實驗來確定，早期一般為1KB，目前大多為4KB、8KB、16KB。頁面大小 SP命中率 H1S2S頁面大小 SP命中率 H1S2S主存容量主存容量本章內(nèi)容虛擬存儲系統(tǒng)提高主存命中率的方法 主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。命中率 H主存容量S1.0頁面調(diào)度算法本章內(nèi)容虛擬存儲系統(tǒng)提高主存命中率的方法 全取式 該用和能調(diào)入的全部調(diào)入。 請求式 當(dāng)使用到的時候，再調(diào)入主存。 預(yù)取式 在程序重新開始運(yùn)行之前，把上次停止運(yùn)行前一段時間內(nèi)用到的頁面先調(diào)入到主存儲器，然后才開始運(yùn)行程序。但如果調(diào)入的頁面用不上，則浪費(fèi)了調(diào)入的時間，占用了主存資源。Cach

31、e存儲系統(tǒng)本章內(nèi)容存儲系統(tǒng)兩級存儲器速度比Cache虛擬存儲器要達(dá)到的目標(biāo)提高速度擴(kuò)大容量實現(xiàn)方法全部硬件軟件為主硬件為輔310倍105倍頁(塊)大小116字1KB16KB等效存儲容量主存儲器虛擬存儲器透明性對系統(tǒng)和應(yīng)用程序員僅對應(yīng)用程序員不命中時處理方式等待主存儲器任務(wù)切換Cache存儲系統(tǒng)與虛擬存儲系統(tǒng)比較Cache存儲系統(tǒng)本章內(nèi)容基本工作原理地址映象與變換方法Cache替換算法Cache的一致性問題Cache性能基本工作原理本章內(nèi)容 Cache存儲系統(tǒng)塊號B塊內(nèi)地址W主存/Cache地址變換塊號b塊內(nèi)地址wCacheCache替換策略儲器主存替換塊裝入塊已滿未滿未命中命中數(shù)據(jù)送CPU（一

32、個字）主存地址（來自CPU）地址映象與變換方法本章內(nèi)容 Cache存儲系統(tǒng)基本概念全相聯(lián)映象及其變換直接映象及其變換組相聯(lián)映象及其變換基本概念本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法 地址映象 把存放在主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對應(yīng)關(guān)系。 地址變換 當(dāng)程序已經(jīng)裝入到Cache之后，在實際運(yùn)行過程中，把主存地址變換成Cache地址。 選擇原則 地址變換的硬件要容易實現(xiàn)；地址變換的速度要快；Cache空間利用率要高；發(fā)生塊沖突的概率要小。全相聯(lián)映象本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法 主存中的任意一塊都可以映象到Cache中的任

33、意一塊。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，映象關(guān)系共有：CbMb種。3 之 1塊0Cache塊1塊Cb-1塊0塊1塊i塊Mb-1主存儲器全相聯(lián)地址變換本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法3 之 2有效位塊號B塊內(nèi)地址W1主存地址目錄表（由相聯(lián)存儲器組成，共Cb個字）主存塊號BB塊號b塊內(nèi)地址wCache塊號b b相聯(lián)比較命中Cache地址特 點優(yōu)點：Cache的塊沖突概率最低；Cache的空間利用率最高。缺點：代價相對較大（相聯(lián)存儲器）；速度相對較低（相聯(lián)比較）。本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法3 之 3直接映象本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法

34、 主存中一塊只能映象到Cache的一個特定的塊中。通常映射方法為：（Cache塊號）=（主存塊號） MOD （Cache中的塊數(shù)）。4 之 1塊0Cache塊1塊Cb-1塊0塊Cb-1主存儲器塊Cb塊2Cb-1塊Mb-Cb塊Mb-1區(qū)0區(qū)1區(qū)Me-1直接地址變換本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法4 之 2有效位區(qū)號E塊內(nèi)地址W1主存地址區(qū)號存儲器（共Cb個字）區(qū)號E (按地址訪問)E 塊號b塊內(nèi)地址w命中Cache地址塊號B相等比較塊失效比較相等且有效位為1，訪問Cache快速直接地址變換本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法4 之 3有效位區(qū)號E塊內(nèi)地址w1按地址訪問的C

35、ache（區(qū)號存儲器+Cache）區(qū)號E塊號b塊內(nèi)地址w相等塊號B相等比較訪主存數(shù)據(jù)0D0數(shù)據(jù)1D1數(shù)據(jù)w-1Dw-11/w送CPU主存地址Cache地址特 點缺點：Cache的塊沖突概率很高Cache的空間利用率很低優(yōu)點：代價相對較低（硬件實現(xiàn)簡單，無需相聯(lián)存儲器）速度相對較快本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法4 之 4組相聯(lián)映象本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法3 之 1 組相聯(lián)映射是目前Cache中用得較多的一種方法，它是介于全相聯(lián)映象和直接映象之間的一種折中方案。它將主存和Cache按同樣大小劃分成塊，還按同樣大小劃分成組，從主存的組到Cache的組之間采用直接

36、映象方法，組內(nèi)的塊采用全相聯(lián)映象方法。 （后圖）相聯(lián)映射和直接映射是組相聯(lián)映射的兩個極端。如果一個組內(nèi)有n塊，則稱為n-路組相聯(lián)。Gb：每組的塊數(shù)Cg：Cache的組數(shù)Me：主存的區(qū)數(shù)Cb：Cache的塊數(shù)Mb：主存的塊數(shù)3 之 2組相聯(lián)地址變換本章內(nèi)容 Cache存儲系統(tǒng)地址映象與變換方法3 之 3（Cache）組內(nèi)塊號b區(qū)號E塊內(nèi)地址W主存地址塊表存儲器 （組內(nèi)相聯(lián)訪問，組間按地址訪問）（主存）區(qū)號E ,組內(nèi)塊號B相聯(lián)比較 (Gb個塊)塊內(nèi)地址w相等Cache地址組內(nèi)塊號B相聯(lián)比較不等組號G組內(nèi)塊號b組號gCache替換算法本章內(nèi)容 Cache存儲系統(tǒng)基本概念輪換法及其實現(xiàn)LRU算法及其實

37、現(xiàn)比較對法堆棧法基本概念本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 為什么需要Cache替換算法？ 當(dāng)發(fā)生塊失效，且可以裝入新調(diào)入塊的幾個Cache塊都已經(jīng)被裝滿時，此時需要Cache替換算法。直接映象方式實際上不需要替換算法，而全相聯(lián)映象方式的替換算法最復(fù)雜。 Cache替換算法和虛擬存儲器替換算法 前者全部用硬件實現(xiàn)，后者主要用軟件實現(xiàn)。輪換法及其實現(xiàn)本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 輪換法本質(zhì)上是一種FIFO算法，通常用于組相聯(lián)映象和地址變換方式中，常見的有兩種實現(xiàn)方法： 每塊一個計數(shù)器 每組一個計數(shù)器每塊一個計數(shù)器本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法輪換法及

38、其實現(xiàn) 在塊表中為Cache的每塊都設(shè)置一個替換計數(shù)器，長度與“組內(nèi)塊號”字段相同。工作方法：裝入或替換時，被裝入或替換的塊計數(shù)器置0，同組其他塊計數(shù)器加1；命中時，塊計數(shù)器不變；需替換時，同組中計數(shù)器值最大的塊被替換。2 之 1舉 例本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法輪換法及其實現(xiàn)Solar-16/65機(jī)：Cache采用組相聯(lián)，每組4塊。2 之 2序列初始值裝入塊00裝入塊01裝入塊10裝入塊11替換塊00塊00000001101100塊01000100011011塊10000110000110塊11000110110001每組一個計數(shù)器本章內(nèi)容 Cache存儲系統(tǒng)Cache替換

39、算法輪換法及其實現(xiàn) 每組設(shè)置一個替換計數(shù)器，長度與“組內(nèi)塊號”字段相同。工作方法：本組有替換時，計數(shù)器加1，計數(shù)器的值就是要被替換出去的塊號。LRU算法及其實現(xiàn)本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 在塊表中為Cache的每塊都設(shè)置一個替換計數(shù)器，長度與“組內(nèi)塊號”字段相同。工作方法：裝入或替換時，被裝入或替換的塊計數(shù)器置0，同組其他塊計數(shù)器加1；命中時，命中塊計數(shù)器置0，同組中比他置0前的值小的計數(shù)器加1，其他不變；需替換時，同組中計數(shù)器值最大（一般為全1）的塊被替換。2 之 1舉 例本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法2 之 2IBM 370/165機(jī)：Cache采用組相

40、聯(lián)，每組4塊。塊地址流主存塊1主存塊2主存塊3主存塊4主存塊5主存塊4塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器Cache塊0100101110111500501Cacheache塊20110300301310310Cache塊3011011400401400動作裝入裝入裝入裝入替換命中比較對法本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 比較對法本質(zhì)上是一種LRU算法，采用硬聯(lián)邏輯實現(xiàn)。 一個兩態(tài)的器件（觸發(fā)器）能夠記錄兩個塊之間的先后順序，多個塊之間的先后順序可以用多個兩態(tài)器件的組合來實現(xiàn)，從而可以在多個塊中找出最久沒有被訪問過的

41、那個塊。4 之 1舉 例 設(shè)計 以組中有三個塊（A、B和C）為例：三塊之間的組合共有C32=3種（AB、AC、BC），可以采用3個兩態(tài)的觸發(fā)器來表示，用TAB=1表示B塊比A塊更久沒有被訪問，其他類似。則三塊最久沒有被訪問過的表達(dá)式為：本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法4 之 2舉 例 硬件本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法01TABRS01TACRS01TBCRS訪問A訪問B訪問C與門與門與門ALRUBLRUCLRU4 之 3舉 例 成本本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 假設(shè)每組的塊數(shù)為Gb，則需要與門的個數(shù)為Gb個，每個與門的輸入端個數(shù)為Gb 1個，需

42、要觸發(fā)器的個數(shù)為： 當(dāng)每組的塊數(shù)較多時，所要的觸發(fā)器個數(shù)和與門輸入端個數(shù)很多，硬件實現(xiàn)的成本很高，此時可以采用分級的方法來實現(xiàn)。4 之 4堆棧法本章內(nèi)容 Cache存儲系統(tǒng)Cache替換算法 堆棧法本質(zhì)上是一種LRU算法，用棧頂?shù)綏５椎南群蟠涡騺碛涗汣ache同一組內(nèi)的各個塊被訪問的先后次序，棧頂是最近被訪問過的塊，棧底是最久沒有被訪問過的塊。棧頂棧底最近訪問過最久沒被訪問過被訪問過的塊號（經(jīng)相聯(lián)比較找到）都下推一行Cache的一致性問題本章內(nèi)容 Cache存儲系統(tǒng) 問題 在單處理機(jī)中會出現(xiàn)Cache與主存內(nèi)容不一致問題。CPUXI/OXCache主存儲器CPUXI/OXCache主存儲器(a

43、) CPU寫Cache(b) I/O寫主存Cache與主存不一致的兩種情況Cache的一致性問題本章內(nèi)容 Cache存儲系統(tǒng) 解決 選擇合適的Cache寫策略。 寫命中時的策略 寫缺失時的策略寫命中時的策略本章內(nèi)容 Cache存儲系統(tǒng)Cache的一致性問題 寫直達(dá)法（寫通過法： Write-Through） CPU在執(zhí)行寫操作時，把數(shù)據(jù)同時寫入Cache和主存。 寫回法 （抵觸修改法： Write-Back ） CPU數(shù)據(jù)只寫入Cache，不寫入主存，僅當(dāng)替換時，才把修改過的Cache塊寫回到主存。2 之 1特點比較可靠性 寫直達(dá)法要優(yōu)于寫回法。與主存的通信量 一般情況下，寫回法少于寫直達(dá)法。

44、控制的復(fù)雜性 寫直達(dá)法比寫回法簡單。硬件實現(xiàn)的代價 寫回法要比寫直達(dá)法好。本章內(nèi)容 Cache存儲系統(tǒng)Cache的一致性問題2 之 2寫缺失時的策略本章內(nèi)容 Cache存儲系統(tǒng)Cache的一致性問題 不按寫分配法 在寫Cache不命中時，只把所要寫的字寫入主存，而包括所寫字在內(nèi)的一個塊不從主存讀入Cache。 按寫分配法 在寫Cache不命中時，除了將所要寫的字寫入主存，還要將包括所寫字在內(nèi)的一個塊從主存讀入Cache。3 之 1例 子本章內(nèi)容 Cache存儲系統(tǒng)Cache的一致性問題3 之 2問：有一個全相聯(lián)映象的Cache，采用寫回法，剛開始時Cache為空，有下面5個存儲器操作：Writ

45、e Mem100， Write Mem100， Read Mem200， Write Mem200， Write Mem100；分別求在不按寫分配法和按寫分配法情況下命中次數(shù)、缺失次數(shù)是多少？答：如采用不按寫分配法：命中次數(shù)為1、缺失次數(shù)為4；如采用按寫分配法：命中次數(shù)為3、缺失次數(shù)為2。提 示目前，在寫回法中一般采用按寫分配法，在寫直達(dá)法中一般采用不按寫分配法。本章內(nèi)容 Cache存儲系統(tǒng)Cache的一致性問題3 之 3Cache性能評價提高Cache性能Cache性能本章內(nèi)容 Cache存儲系統(tǒng)Cache性能評價本章內(nèi)容 Cache存儲系統(tǒng)Cache性能CPU執(zhí)行時間平均存儲器訪問時間（A

46、MAT）CPU執(zhí)行時間本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價其中：3 之 1例 子本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價問：假定有一臺計算機(jī)，當(dāng)所有存儲器訪問操作都能在Cache中命中時，CPI為1.0；數(shù)據(jù)訪問只有l(wèi)oad和store指令，這些指令占全部指令的50%；缺失代價為25個時鐘周期，缺失率為2%。問當(dāng)所有指令都在Cache中命中時，計算機(jī)性能能提高多少？答：Cache始終命中時的計算機(jī)性能為：3 之 2例 子（續(xù)）本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價實際Cache的計算機(jī)性能為：兩者的性能比為：結(jié)論：不發(fā)生Cach

47、e缺失時計算機(jī)性能是原來的1.75倍3 之 3平均存儲器訪問時間（AMAT）本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價3 之 1例 子本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價問：一個由8KB的I-Cache和8KB的D-Cache所構(gòu)成的分立Cache（哈佛結(jié)構(gòu)）與一個16KB的統(tǒng)一Cache哪一個具有更低的缺失率？假設(shè)命中所需的開銷為1個時鐘周期，不命中的開銷為50個時鐘周期，統(tǒng)一Cache的load或store命中需花費(fèi)1個時鐘周期的額外開銷。75%的存儲器存取是指令訪問。Cache大小I-Cache缺失率D-Cache缺失率統(tǒng)一Cache缺失率4KB

48、1.78%15.94%7.24%8KB1.10%10.19%4.57%16KB0.64%6.47%2.87%32KB0.39%4.82%1.99%3 之 2答：分立Cache的整體缺失率為： 由表中可知，16KB的統(tǒng)一Cache的缺失率為2.87%。因此，統(tǒng)一Cache結(jié)構(gòu)具有較低的缺失率。 盡管分立Cache具有較高的缺失率，但其AMAT與統(tǒng)一Cache的AMAT是基本相同的，可見哈佛結(jié)構(gòu)有優(yōu)勢。大多數(shù)現(xiàn)代處理器都采用分立Cache技術(shù)。例 子（續(xù)）本章內(nèi)容 Cache存儲系統(tǒng)Cache性能Cache性能評價3 之 3提高Cache性能本章內(nèi)容 Cache存儲系統(tǒng)Cache性能 可見主要途徑

49、有： 降低缺失代價 降低缺失率 通過并行性降低缺失代價/缺失率 降低Cache命中時間 降低缺失代價本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能多級Cache請求字處理技術(shù)給出讀缺失對寫的優(yōu)先級合并寫緩沖區(qū)犧牲者Cache多級Cache本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價基本思想性能分析設(shè)計考慮基本思想本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價多級Cache 通過在原始Cache和存儲器之間增加另一級Cache，第一級Cache可以小到足以跟上飛快的CPU，而第二級Cache能夠大到足以捕捉到對主存進(jìn)行的大多數(shù)訪

50、問，因而可以減少有效缺失代價。性能分析本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價多級Cache 局部缺失率 本級Cache的缺失數(shù)除以對本級Cache的存儲器訪問總數(shù)。例如：第一級Cache的局部缺失率為缺失率L1，第二級Cache的局部缺失率為缺失率L2 全局缺失率 本級Cache的缺失數(shù)除以CPU產(chǎn)生的存儲器訪問總數(shù)。例如：第一級Cache的全局缺失率為缺失率L1，第二級Cache的全局缺失率為缺失率L1缺失率L2。設(shè)計考慮本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價多級Cache 第二級Cache的容量？ 采用大容量設(shè)計。因為第一

51、級Cache中的所有信息都可能會出現(xiàn)在第二級Cache中，所以第二級Cache應(yīng)該比第一級Cache大得多。如果第二級Cache只是稍微大一點，則局部缺失率會很高。 第二級Cache采用組相聯(lián)映射還是直接映射？ 采用組相聯(lián)映射比采用直接映射性能要好。2 之 1設(shè)計考慮本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價多級Cache2 之 2是否第一級Cache中所有數(shù)據(jù)都包含在第二級Cache中？多級包含 L1中的數(shù)據(jù)通常都出現(xiàn)在L2中。這是通常做法，因為它便于實現(xiàn)I/O和Cache之間內(nèi)容一致性的檢測。多級排除 L1中的數(shù)據(jù)從不會出現(xiàn)在L2中。當(dāng)L2 Cache容量略大

52、于L1 Cache時可以采用此法，不浪費(fèi)L2 Cache的空間。請求字處理技術(shù) 思想 因為CPU在同一時刻只需要塊中的一個字（請求字），所以本技術(shù)不必等到全部塊裝入就可以將所需字送出，然后重新啟動CPU。 方法 請求字優(yōu)先 首先向存儲器請求缺失的字，一旦它到了就將它發(fā)送到CPU中；讓CPU繼續(xù)執(zhí)行，同時裝入塊中的其他字。本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價 盡早重啟動 按正常次序獲取字，只要被請求的字一到達(dá)就將它發(fā)送到CPU中，讓CPU繼續(xù)執(zhí)行。2 之 1局限性 本技術(shù)的收益取決于塊的大?。▔K越大，收益越大）和對塊中未裝入部分的訪問可能性。本章內(nèi)容 Cach

53、e存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價2 之 2給出讀缺失對寫的優(yōu)先級本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價 問題 對于一個寫直達(dá)的Cache，需要設(shè)置容量適中的寫緩沖區(qū)（見后圖）。然而寫緩沖區(qū)使得存儲器訪問變的復(fù)雜，因為其中可能包含讀缺失時所需要的更新數(shù)據(jù)。SW R3,512(R0) ;M512R3 (Cache Index 0)LW R1,1024(R0) ;R1 M1024 (Cache Index 0)LW R2,512(R0) ;R2 M512 (Cache Index 0)R2R3？！3 之 1給出讀缺失對寫的優(yōu)先級本章內(nèi)容 Cac

54、he存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價writebufferCPUin out DRAM (or lower mem)3 之 2給出讀缺失對寫的優(yōu)先級本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價 解決 最簡單的解決方法：讀缺失等待，直到寫緩沖區(qū)為空為止；但該方法會增加讀缺失代價。另一種解決方法：在讀缺失時查看寫緩沖區(qū)中的內(nèi)容，如果沒有沖突而且存儲器系統(tǒng)可以訪問，就可繼續(xù)處理讀缺失；即：使讀缺失優(yōu)先于寫缺失。3 之 3在寫回法的Cache中，在替換塊時也要使用一個簡單的寫緩沖，同樣處理。合并寫緩沖區(qū)本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cac

55、he性能降低缺失代價 思想 在寫緩沖區(qū)中，將多個連續(xù)的數(shù)據(jù)組合起來，提高寫緩沖區(qū)的空間利用率，減少因?qū)懢彌_區(qū)滿而等待的時間。64bit64bit64bit64bit犧牲者Cache本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價 思想 在Cache和它的替換路徑之間增加一個小的、全相聯(lián)的Cache（犧牲者Cache），這個犧牲者Cache中只包含Cache中因為缺失而被替換出的塊（犧牲者），然后在缺失發(fā)生時，在要訪問下層存儲器之前，先檢查犧牲者Cache，看其中是否包含有期望的數(shù)據(jù)，如果有，則犧牲塊與Cache塊互換（見后圖） 。 性能 依賴于特定的程序，一個包含4個存

56、儲字的犧牲者Cache能減少20%90%的沖突缺失。2 之 1犧牲者Cache本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失代價2 之 2降低缺失率本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能導(dǎo)致缺失的原因降低缺失率的技術(shù)增加Cache塊大小增加Cache容量增加相聯(lián)度路預(yù)測和偽相聯(lián)Cache編譯優(yōu)化導(dǎo)致缺失的原因本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率 強(qiáng)制（Compulsory）缺失 對一個塊的第一次訪問一定不在Cache中，所以該塊必須被調(diào)入到Cache中（這也稱為：冷啟動缺失、首次訪問缺失等）。 容量（Capacity

57、）缺失 如果Cache容納不了一個程序持續(xù)執(zhí)行所需要的所有塊，當(dāng)某些塊被替換后，若又重新被訪問就會發(fā)生缺失。 沖突（Conflict）缺失 如果采用組相聯(lián)/直接相聯(lián)，若太多的塊映射到同一組（塊）中，則會出現(xiàn)該組中某塊被別的塊替換后又被重新訪問，這就發(fā)生沖突缺失。4 之 13Cs總?cè)笔?2B blocks； LRU；SPEC92；DECstation 5000；本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率4 之 2Miss Rate per Type0.020.040.060.080.10.120.14Cache Size (KB) 01248163264128Com

58、pulsory Capacity 4-way2-way1-way8-wayConflict2:1Cache經(jīng)驗規(guī)律 一個容量為N的直接映射Cache同容量為N/2的2-路組相聯(lián)Cache有著大致相同的總?cè)笔省?本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率4 之 3Conflict3Cs缺失率分布（相對值）本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率4 之 4Conflict增加Cache塊大小五種不同容量Cache的缺失率與塊大小的關(guān)系本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率0.49%1.15%3.29%9.5

59、1%22.01%2560.49%1.02%2.77%7.78%16.64%1280.51%1.06%2.64%7.00%13.76%640.70%1.35%2.87%7.24%13.34%321.09%2.04%3.94%8.57%15.05%16256641641Cache size (KB)Block size (B)5 之 1圖 示本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率1K4K16K64K256KCache SizeBlock Size (bytes) Miss Rate 0%5%10%15%20%25%1632641282565 之 2分 析 增加塊大小

60、會先降低后增加缺失率 增加塊大小會降低強(qiáng)制缺失率，這是利用了空間局部性原理。但因為它減少了Cache中的塊數(shù)，加重了沖突缺失，如果Cache容量較小時，甚至?xí)腥萘咳笔А?增加塊大小會增加缺失代價本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率塊大小應(yīng)為多大AMAT最?。? 之 3AMAT與塊大小本章內(nèi)容 Cache存儲系統(tǒng)Cache性能提高Cache性能降低缺失率 假設(shè)命中時間為1個時鐘周期，缺失時系統(tǒng)開銷為80個時鐘周期，以后每2個時鐘周期傳送16B，缺失率參見前表。結(jié)果顯示：32/64B是目前Cache所通用的塊大小。5 之 4塊大小的選擇本章內(nèi)容 Cache存儲系