系統(tǒng)結(jié)構(gòu)第3章

1、3.1 存儲(chǔ)系統(tǒng)原理,3.1.1 存儲(chǔ)系統(tǒng)的定義3.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)3.1.3 存儲(chǔ)系統(tǒng)的頻帶平衡3.1.4 并行訪問(wèn)存儲(chǔ)器 3.1.5 交叉訪問(wèn)存儲(chǔ)器 3.1.6 無(wú)沖突訪問(wèn)存儲(chǔ)器,3.1.1 存儲(chǔ)系統(tǒng)的定義,在一臺(tái)計(jì)算機(jī)中，通常有多種存儲(chǔ)器種類：主存儲(chǔ)器、Cache、通用寄存器、緩沖存儲(chǔ)器、磁盤(pán)存儲(chǔ)器、磁帶存儲(chǔ)器、光盤(pán)存儲(chǔ)器等材料工藝：ECL、TTL、MOS、磁表面、激光，SRAM，DRA

2、M訪問(wèn)方式：隨機(jī)訪問(wèn)、直接譯碼、先進(jìn)先出、 相聯(lián)訪問(wèn)、 塊傳送、文件組,存儲(chǔ)器的主要性能：速度、容量、價(jià)格 速度用存儲(chǔ)器的訪問(wèn)周期、讀出時(shí)間、頻帶寬度等表示。 容量用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。 價(jià)格用單位容量的價(jià)格表示，例如：$C/bit。 組成存儲(chǔ)系統(tǒng)的關(guān)鍵：把速度、容量和價(jià)格不同的多個(gè)物理存儲(chǔ)器組織成一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度最快，存儲(chǔ)容量最大，單位容量的價(jià)格最便宜。,1. 存儲(chǔ)系統(tǒng)

3、的定義 兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來(lái)成為一個(gè)存儲(chǔ)系統(tǒng)。這個(gè)存儲(chǔ)系統(tǒng)對(duì)應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。虛擬存儲(chǔ)器系統(tǒng)：對(duì)應(yīng)用程序員透明Cache存儲(chǔ)系統(tǒng)：對(duì)系統(tǒng)程序員以上均透明,由多個(gè)存儲(chǔ)器構(gòu)成的存儲(chǔ)系統(tǒng),在一般計(jì)算機(jī)系統(tǒng)中

4、，有兩種存儲(chǔ)系統(tǒng)：Cache存儲(chǔ)系統(tǒng)：由Cache和主存儲(chǔ)器構(gòu)成 主要目的：提高存儲(chǔ)器速度,虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器和硬盤(pán)構(gòu)成 主要目的：擴(kuò)大存儲(chǔ)器容量,2.存儲(chǔ)系統(tǒng)的容量要求：提供盡可能大的地址空間能夠隨機(jī)訪問(wèn)方法有兩種：只對(duì)系統(tǒng)中存儲(chǔ)容量最大的那個(gè)存儲(chǔ)器進(jìn)行編址，其他存儲(chǔ)器只在內(nèi)部編址或不編址 Cache存儲(chǔ)系統(tǒng)另外設(shè)計(jì)一個(gè)容量很大的邏輯地址空間，把相關(guān)存儲(chǔ)器都映射這個(gè)地址空間中 虛擬存儲(chǔ)系統(tǒng),3.存儲(chǔ)系

5、統(tǒng)的價(jià)格計(jì)算公式：當(dāng)S2》S1時(shí)，C≈C2 S2與S1不能相差太大,4. 存儲(chǔ)系統(tǒng)的速度表示方法：訪問(wèn)周期、存取周期、存儲(chǔ)周期、存取時(shí)間等命中率定義：在M1存儲(chǔ)器中訪問(wèn)到的概率 其中：N1是對(duì)M1存儲(chǔ)器的訪問(wèn)次數(shù) N2是對(duì)M2存儲(chǔ)器的訪問(wèn)次數(shù)訪問(wèn)周期與命中率的關(guān)系： T＝HT1＋(1－H)T2 當(dāng)命中率H→1時(shí)，T→T1,存儲(chǔ)系統(tǒng)的訪問(wèn)效率：訪問(wèn)效率主要與

6、命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān)例3.1：假設(shè)T2＝５T１，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問(wèn)效率。解：,當(dāng)H＝0.9時(shí)，e1＝1／(0.9＋5(1－0.9))＝0.72,當(dāng)H＝0.99時(shí)，e2＝1／(0.99＋5(1－0.99))＝0.96,提高存儲(chǔ)系統(tǒng)速度的兩條途徑：一是提高命中率H，二是兩個(gè)存儲(chǔ)器的速度不要相差太大其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率例3.2

7、：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2＝105 T１。如果要使訪問(wèn)效率到達(dá)e＝0.9，問(wèn)需要有多高的命中率？,解：,0.9H＋90000(1-H)＝189999.1 H＝89999計(jì)算得： H＝0.999998888877777… ≈0.999999,5. 采用預(yù)取技術(shù)提高命中率 方法：不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單元組成的一個(gè)數(shù)據(jù)塊取出來(lái)送入M1存儲(chǔ)器中。,計(jì)算公式： 其中：

8、H’是采用預(yù)取技術(shù)之后的命中率 H是原來(lái)的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積,例3.3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中，當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率H＝0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T2＝5T1。計(jì)算塊大小為４個(gè)字時(shí)，Cache存儲(chǔ)系統(tǒng)的命中率？并分別計(jì)算訪問(wèn)效率。,解：n＝4×5＝20， 采用預(yù)取技術(shù)之后，命中率提高到：,3.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu),多個(gè)層次的存儲(chǔ)器：　 第

9、1層：Register Files(寄存器堆) 第2層： Buffers(Lookahead)(先行緩沖站)　 第3層： Cache(高速緩沖存儲(chǔ)器) 第4層： Main Memory(主存儲(chǔ)器) 第5層： Online Storage(聯(lián)機(jī)存儲(chǔ)器) 第6層： Off-line Storage(脫機(jī)存儲(chǔ)器)用i表示層數(shù)，則有：工作周期Ti＜Ti+1， 存儲(chǔ)容量：Si＜Si+1，單位價(jià)格：

10、Ci＞Ci+1,各級(jí)存儲(chǔ)器的主要主要性能特性 CPU與主存儲(chǔ)器的速度差距越來(lái)越大 目前相差兩個(gè)數(shù)量級(jí) 今后CPU與主存儲(chǔ)器的速度差距會(huì)更大,3.1.3 存儲(chǔ)系統(tǒng)的頻帶平衡,例3.5：Pentium4的指令執(zhí)行速度為8GIPS，CPU取指令8GW/s，訪問(wèn)數(shù)據(jù)16GW/s，各種輸入輸出設(shè)備訪問(wèn)存儲(chǔ)器1GW/s，三項(xiàng)相加，要求存儲(chǔ)器的頻帶寬度不低于25GW/s。 如果采用PC133內(nèi)存，主存與CPU速度差188倍

11、 如果采用PC266內(nèi)存，主存與CPU速度差94倍解決存儲(chǔ)器頻帶平衡方法 (1)多個(gè)存儲(chǔ)器并行工作（本節(jié)下面介紹） (2)設(shè)置各種緩沖存儲(chǔ)器（第五章介紹） (3)采用存儲(chǔ)系統(tǒng)（本章第二、第三節(jié)介紹）,3.1.4 并行訪問(wèn)存儲(chǔ)器,方法：把m字w位的存儲(chǔ)器改變成為m/n字n×w位的存儲(chǔ)器邏輯實(shí)現(xiàn)：把地址碼分成兩個(gè)部分，一部分作為存儲(chǔ)器的地址另一部分負(fù)責(zé)選擇數(shù)據(jù)主要缺點(diǎn)：訪問(wèn)沖突大 (1)取指令沖突

12、(2)讀操作數(shù)沖突 (3)寫(xiě)數(shù)據(jù)沖突 (4)讀寫(xiě)沖突,并行訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖,1. 高位交叉訪問(wèn)存儲(chǔ)器主要目的：擴(kuò)大存儲(chǔ)器容量實(shí)現(xiàn)方法：用地址碼的高位部分區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算方法: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j＝0，1，2，...，m-1 k：存儲(chǔ)體的體號(hào)，k＝0，1，2，...，n-1 存儲(chǔ)器的地址：A＝m×k＋j 存儲(chǔ)

13、器的體內(nèi)地址：Aj＝A mod m。 存儲(chǔ)器的體號(hào)： Ak＝,3.1.5 交叉訪問(wèn)存儲(chǔ)器,高位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖,例3.6：用4M字×4位的存儲(chǔ)芯片組成16M×32位的主存儲(chǔ)器。共用存儲(chǔ)芯片：用最高2位地址經(jīng)譯碼后產(chǎn)生的信號(hào)，控制各組存儲(chǔ)芯片CS。每組中的32根數(shù)據(jù)線分別對(duì)應(yīng)直接相連，稱為“線或”方式。,2. 低位交叉訪問(wèn)存儲(chǔ)器 主要目的：提高存儲(chǔ)器訪問(wèn)速度 實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)

14、分存儲(chǔ)體號(hào) 參數(shù)計(jì)算: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j＝0，1，2，...，m-1 k：存儲(chǔ)體的體號(hào)，k＝0，1，2，...，n-1 存儲(chǔ)器地址A的計(jì)算公式為：A＝n×j＋k 存儲(chǔ)器的體內(nèi)地址：Aj＝ 存儲(chǔ)器的體號(hào)：Ak＝A mod n,低位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖,地址是編碼方法： 由8個(gè)存儲(chǔ)體構(gòu)成的低位交叉編址方式,n個(gè)存儲(chǔ)體分時(shí)啟動(dòng)

15、 一種采用流水線方式工作的并行存儲(chǔ)器 每存儲(chǔ)體的啟動(dòng)間隔為：t＝ 其中： Tm為每個(gè)存儲(chǔ)體的訪問(wèn)周期, n為存儲(chǔ)體個(gè)數(shù)。,訪問(wèn)沖突 共有n個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)周期只能取到k個(gè)有效字,其余n-k個(gè)存儲(chǔ)體有沖突。假設(shè)p(k)是k的概率密度函數(shù)，即p(1)是k＝1的概率，p(2)是k＝2的概率，…,p(n)是k＝n的概率。k的平均值為：N是每個(gè)存儲(chǔ)周期能夠訪問(wèn)到的平均有效字的個(gè)數(shù)。通常把

16、 N稱為并行存儲(chǔ)器的加速比。,定義轉(zhuǎn)移概率為g，即讀出的是轉(zhuǎn)移指令，且轉(zhuǎn)移成功的概率。這時(shí)有： p(1)＝g p(2)＝(1-p(1))g＝(1-g)g p(3)＝(1-p(1)-p(2))g＝(1-g)2g …… p(k)＝(1-g)k-1g (k＝1,2,…,n－1) …… p(n)＝(1-g)n-1,Ｎ＝g＋(1-g)g＋(1-g)2g＋…＋(1-g)n-2g

17、 ＋(1-g)g＋(1-g)2g＋…＋(1-g)n-2g ＋(1-g)2g＋…＋(1-g)n-2g … ＋(1-g)n-2g ＋n(1-g)n-1以上共n行，前n-2行分別為等比級(jí)數(shù)把n-1行拆分成2項(xiàng),則：Ｎ＝1g＋2

18、(1-g)g＋3(1-g)2g＋… ＋(n-1)(1-g)n-2g＋n(1-g)n-1,Ｎ＝1-(1-g)n-1 ＋(1-g)-(1-g)n-1 ＋(1-g)2-(1-g)n-1 … ＋(1-g)n-2-(1-g)n-1 ＋n(1-g)n-1,Ｎ＝1＋(1-g)＋(1-g)2＋…(1-g)n-2＋(1-g)n-1,3.1.6 無(wú)沖突訪問(wèn)存儲(chǔ)器,1. 一維數(shù)組(向量)的無(wú)沖突

19、訪問(wèn)存儲(chǔ)器 按連續(xù)地址訪問(wèn)，沒(méi)有沖突， 位移量為2的變址訪問(wèn)，速度降低一倍，…,具體方法： 存儲(chǔ)體的個(gè)數(shù)取質(zhì)數(shù)，且n≥向量長(zhǎng)度。 原因：變址位移量必然與存儲(chǔ)體個(gè)數(shù)互質(zhì) 例如：Burroughs公司巨型科學(xué)計(jì)算機(jī)BSP 存儲(chǔ)體個(gè)數(shù)為17 向量長(zhǎng)度≤16我國(guó)研制的銀河巨型向量機(jī) 存儲(chǔ)體的個(gè)數(shù)為37 向量長(zhǎng)度≤32,2. 二維數(shù)組的無(wú)沖突訪問(wèn)存儲(chǔ)器要求：一個(gè)n×n的二維數(shù)組，按行、列、對(duì)角線和反

20、對(duì)角線訪問(wèn)，并且在不同的變址位移量情況下，都能實(shí)現(xiàn)無(wú)沖突訪問(wèn)。順序存儲(chǔ)：按行、對(duì)角線訪問(wèn)沒(méi)有沖突，但按列訪問(wèn)每次沖突,錯(cuò)位存儲(chǔ)： 按行、按列訪問(wèn)無(wú)沖突， 但按對(duì)角線訪問(wèn)有沖突,n×n二維數(shù)組無(wú)沖突訪問(wèn)存儲(chǔ)方案 ( P· Budnik 和 D· J· Kuck提出 ) ： 并行存儲(chǔ)體的個(gè)數(shù)m≥n，并且取質(zhì)數(shù)，同時(shí)還要在行、列方向上錯(cuò)開(kāi)一定的距離存儲(chǔ)數(shù)組元素。 設(shè)同一列相鄰

21、元素在并行存儲(chǔ)器中錯(cuò)開(kāi)d1個(gè)存儲(chǔ)體存放，同一行相鄰元素在并行存儲(chǔ)器中錯(cuò)開(kāi)d2個(gè)存儲(chǔ)體存放。當(dāng)m＝22p＋1（p為任意自然數(shù)）時(shí)，能夠同時(shí)實(shí)現(xiàn)按行、按列、按對(duì)角線和按反對(duì)角線無(wú)沖突訪問(wèn)的充要條件是：d1＝2P，d2＝1。,例如：4×4的二維數(shù)組，取并行存儲(chǔ)體的個(gè)數(shù)m＝5，由關(guān)系式m＝22P＋1，解得到p＝1，計(jì)算得到： d1＝21＝2 d2＝1,,,,n×n數(shù)組中的任意一個(gè)元素aij在無(wú)沖突并行存儲(chǔ)器中

22、的體號(hào)地址和體內(nèi)地址的計(jì)算公式： 體號(hào)地址：(2P i＋j＋k) MOD m 體內(nèi)地址：i 其中：0≤i≤n－1， 0≤j≤n－1， k是數(shù)組的第一個(gè)元素a00所在體號(hào)地址， m是并行存儲(chǔ)體的個(gè)數(shù)，要求m≥n且為質(zhì)數(shù)， p是滿足m＝22P＋1關(guān)系的任意自然數(shù)。 主要缺點(diǎn)：浪費(fèi)存儲(chǔ)單元 對(duì)于n×n數(shù)組,有(m-n) × m個(gè)存儲(chǔ)單

23、元浪費(fèi) 主要優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單 列元素順序存儲(chǔ)，行元素按地址取模順序存儲(chǔ),3. 二維數(shù)組的無(wú)沖突訪問(wèn)存儲(chǔ)器(之二)規(guī)則：對(duì)于任意一個(gè)n×n的數(shù)組，如果能夠找到滿足n＝22P關(guān)系的任意自然數(shù)p，則這個(gè)二維數(shù)組就能夠使用n個(gè)并行存儲(chǔ)體實(shí)現(xiàn)按行、列、對(duì)角線和反對(duì)角線的無(wú)沖突訪問(wèn)。4×4數(shù)組用4個(gè)存儲(chǔ)體的無(wú)訪問(wèn)沖突存儲(chǔ)方案,3.2.1 虛擬存儲(chǔ)器工作原理3.2.2 地址的映象和變換方法3.2.3 加快內(nèi)部地址變換的

24、方法3.2.4 頁(yè)面替換算法及其實(shí)現(xiàn)3.2.5 提高主存命中率的方法,3.2 虛擬存儲(chǔ)器,3.2.1 虛擬存儲(chǔ)器工作原理,也稱為虛擬存儲(chǔ)系統(tǒng)、虛擬存儲(chǔ)體系等其概念由英國(guó)曼徹斯特大學(xué)的Kilbrn等人于1961年提出到70年代廣泛應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)目前，許多微型機(jī)也使用虛擬存儲(chǔ)器把主存儲(chǔ)器、磁盤(pán)存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的頁(yè) 主存儲(chǔ)器的頁(yè)稱為實(shí)頁(yè) 虛擬存儲(chǔ)器中的頁(yè)稱為虛頁(yè),內(nèi)部地址變換： 多用戶虛擬地址

25、Av變換成主存實(shí)地址A 多用戶虛擬地址中的頁(yè)內(nèi)偏移D直接作為主存實(shí)地址中的頁(yè)內(nèi)偏移d， 主存實(shí)頁(yè)號(hào)p與它的頁(yè)內(nèi)偏移d直接拼接起來(lái)就得到主存實(shí)地址A。,3.2.2 地址的映象與變換,三種地址空間：虛擬地址空間 主存儲(chǔ)器地址空間 輔存地址空間地址映象： 把虛擬地址空間映象到主存地址空間地址變換： 在程序運(yùn)行時(shí)，把虛地址變換成主存實(shí)地址三種虛擬存儲(chǔ)器： 頁(yè)式虛擬存

26、儲(chǔ)器 段式虛擬存儲(chǔ)器 段頁(yè)式虛擬存儲(chǔ)器,1. 段式虛擬存儲(chǔ)器地址映象方法：每個(gè)程序段都從0地址開(kāi)始編址，長(zhǎng)度可長(zhǎng)可短，可以在程序執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段的長(zhǎng)度。,地址變換方法：由用戶號(hào)找到基址寄存器，讀出段表起始地址，與虛地址中段號(hào)相加得到段表地址，把段表中的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址。,主要優(yōu)點(diǎn)： (1)程序的模塊化性能好。 (2)便于程

27、序和數(shù)據(jù)的共享。 (3)程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。 (4)便于實(shí)現(xiàn)信息保護(hù)。 主要缺點(diǎn)： (1)地址變換所花費(fèi)的時(shí)間長(zhǎng)，兩次加法 (2)主存儲(chǔ)器的利用率往往比較低。 (3)對(duì)輔存（磁盤(pán)存儲(chǔ)器）的管理比較困難。,2. 頁(yè)式虛擬存儲(chǔ)器 地址映象方法：,地址變換方法：,主要優(yōu)點(diǎn)： (1)主存儲(chǔ)器的利用率比較高 (2)頁(yè)表相對(duì)比較簡(jiǎn)單 (3)地址變換的速度比較快 (4)對(duì)磁盤(pán)的管理比較容易

28、 主要缺點(diǎn)： (1)程序的模塊化性能不好 (2)頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間 例如：虛擬存儲(chǔ)空間4GB，頁(yè)大小1KB，則頁(yè)表的容量為4M字，16MB。,3. 段頁(yè)式虛擬存儲(chǔ)器 用戶按段寫(xiě)程序, 每段分成幾個(gè)固定大小的頁(yè) 地址映象方法：每個(gè)程序段在段表中占一行， 在段表中給出頁(yè)表長(zhǎng)度和頁(yè)表的起始地址， 頁(yè)表中給出每一頁(yè)在主存儲(chǔ)器中的實(shí)頁(yè)號(hào)。,地址變換方法： 先查段表，得到頁(yè)表起始地址和頁(yè)表長(zhǎng)度

29、， 再查頁(yè)表找到要訪問(wèn)的主存實(shí)頁(yè)號(hào)， 把實(shí)頁(yè)號(hào)p與頁(yè)內(nèi)偏移d拼接得到主存實(shí)地址。,4. 外部地址變換 每個(gè)程序有一張外頁(yè)表，每一頁(yè)或每個(gè)程序段，在外頁(yè)表中都有對(duì)應(yīng)的一個(gè)存儲(chǔ)字。,3.2.3 加快內(nèi)部地址變換的方法,造成虛擬存儲(chǔ)器速度降低的主要原因： (1) 要訪問(wèn)主存儲(chǔ)器必須先查段表或頁(yè)表， (2) 可能需要多級(jí)頁(yè)表。頁(yè)表級(jí)數(shù)的計(jì)算公式： 其中： Nv為虛擬存儲(chǔ)空間大小，

30、 Np為頁(yè)面的大小， Nd為一個(gè)頁(yè)表存儲(chǔ)字的大小,例如：虛擬存儲(chǔ)空間大小Nv＝4GB，頁(yè)的大小Np＝1KB，每個(gè)頁(yè)表存儲(chǔ)字占用4個(gè)字節(jié)。計(jì)算得到頁(yè)表的級(jí)數(shù)：通常僅把1級(jí)頁(yè)表和2、3級(jí)頁(yè)表中的一小部分駐留在主存中,1.目錄表 基本思想：用一個(gè)小容量高速存儲(chǔ)器存放頁(yè)表,地址變換過(guò)程： 把多用戶虛地址中U與P拼接，相聯(lián)訪問(wèn)目錄表。讀出主存實(shí)頁(yè)號(hào)p，把p與多用戶虛地址中的D拼接得到主存實(shí)地址。

31、如果相聯(lián)訪問(wèn)失敗，發(fā)出頁(yè)面失效請(qǐng)求。主要優(yōu)點(diǎn)： 與頁(yè)表放在主存中相比，查表速度快。主要缺點(diǎn)： 可擴(kuò)展性比較差, 主存儲(chǔ)器容量大時(shí)，目錄表造價(jià)高，速度低。,2. 快慢表,快表：TLB(Translation Lookaside Buffer)： 小容量(幾～幾十個(gè)字)， 高速硬件實(shí)現(xiàn)， 采用相聯(lián)方式訪問(wèn)。 慢表： 當(dāng)快表中查不到時(shí)，從主存的慢表中查找； 慢表按地址訪問(wèn)；用軟件實(shí)現(xiàn)。

32、 快表與慢表也構(gòu)成一個(gè)兩級(jí)存儲(chǔ)系統(tǒng)。 主要存在問(wèn)題：相聯(lián)訪問(wèn)實(shí)現(xiàn)困難，速度低,3. 散列函數(shù) 目的：把相聯(lián)訪問(wèn)變成按地址訪問(wèn) 散列(Hashing)函數(shù)：Ah＝H(Pv),采用散列變換實(shí)現(xiàn)快表按地址訪問(wèn) 避免散列沖突：采用相等比較器 地址變換：相等比較與訪問(wèn)存儲(chǔ)器同時(shí)進(jìn)行,3.2.4 頁(yè)面替換算法及其實(shí)現(xiàn),1. 頁(yè)面替換發(fā)生時(shí)間： 當(dāng)發(fā)生頁(yè)面失效時(shí)，要從磁盤(pán)中調(diào)入一頁(yè)到主存。如果主存儲(chǔ)器的所有頁(yè)面都已經(jīng)被占

33、用，必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁(yè)面，以便騰出主存空間來(lái)存放新調(diào)入的頁(yè)面。2. 評(píng)價(jià)頁(yè)面替換算法好壞的標(biāo)準(zhǔn)： 一是命中率要高， 二是算法要容易實(shí)現(xiàn)。,3. 頁(yè)面替換算法的使用場(chǎng)合：(1)虛擬存儲(chǔ)器中，主存頁(yè)面的替換，一般用軟件實(shí)現(xiàn)。(2)Cache中的塊替換，一般用硬件實(shí)現(xiàn)。(3)虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)字的替換，用硬件實(shí)現(xiàn)。(4)虛擬存儲(chǔ)器中，用戶基地址寄存器的替換，用硬件實(shí)現(xiàn)。(5)在有些虛擬存

34、儲(chǔ)器中，目錄表的替換。,4. 主要頁(yè)面替換算法(1)隨機(jī)算法（RAND random algorithm） 算法簡(jiǎn)單，容易實(shí)現(xiàn)。 沒(méi)有利用歷史信息，沒(méi)有反映程序的局部性 命中率低。(2)先進(jìn)先出算法 (FIFO first-in first-out algorithm) 容易實(shí)現(xiàn)，利用了歷史信息， 沒(méi)有反映局部性。 最先調(diào)入的頁(yè)面，很可能也是要使用的頁(yè)面,(3)近期最少使用算法(LFU l

35、east frequently used algorithm)：既充分利用了歷史信息，又反映了程序的局部性實(shí)現(xiàn)起來(lái)非常困難。(4)最久沒(méi)有使用算法(LRU least recently used algorithm)：把LFU算法中的“多”與“少”簡(jiǎn)化成“有”與“無(wú)”，實(shí)現(xiàn)比較容易(5)最優(yōu)替換算法（OPT optimal replacement algorithm）：是一種理想算法，僅用作評(píng)價(jià)其它頁(yè)面替換算法好壞的標(biāo)準(zhǔn)。

36、 在虛擬存儲(chǔ)器中，實(shí)際上可能采用的只有FIFO和LRU兩種算法。,例3.9：一個(gè)程序共有5個(gè)頁(yè)面組成，在程序執(zhí)行過(guò)程中，頁(yè)面地址流如下： P1，P2，P1，P5，P4，P1，P3，P4，P2，P4 假設(shè)分配給這個(gè)程序的主存只有3個(gè)頁(yè)面。(1)給出用FIFO、LRU和OPT三種頁(yè)面替換算法對(duì)這3個(gè)主存頁(yè)面的調(diào)度情況表，并統(tǒng)計(jì)頁(yè)面命中次數(shù)。(2)計(jì)算這LRU頁(yè)面替換算法的頁(yè)面命中率。(3)假設(shè)每個(gè)數(shù)據(jù)平均被訪問(wèn)30次，為了

37、使LRU算法的失效率小于10-5，計(jì)算頁(yè)面大小至少應(yīng)該為多少？,解：(1)FIFO、LRU和OPT的頁(yè)面命中次數(shù)分別為2次、4次和5次 (2)LRU頁(yè)面替換算法的頁(yè)面命中率為： Hp＝4/10＝0.4(3) 解得 P > 2000字 頁(yè)面大小應(yīng)該為2K字。,例3.10：一個(gè)循環(huán)程序，依次使用P1，P2，P3， P4頁(yè)面，分配給它的主存頁(yè)面數(shù)只有2個(gè)。在 F

38、IFO和LRU算法中，發(fā)生“顛簸”現(xiàn)象。,5. 堆棧型替換算法 定義：對(duì)任意一個(gè)程序的頁(yè)地址流作兩次主存頁(yè)面數(shù)分配，分別分配 m 個(gè)主存頁(yè)面和 n 個(gè)主存頁(yè)面，并且有 m≤n。如果在任何時(shí)刻 t，主存頁(yè)面數(shù)集合 Bt 都滿足關(guān)系： Bt（m）? Bt（n），則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點(diǎn)是： 隨著分配給程序的主存頁(yè)面數(shù)增加，主存的命中率也提高，至少不下降。,3.2.5 提高主存命中率

39、的方法,影響主存命中率的主要因素：(1)程序在執(zhí)行過(guò)程中的頁(yè)地址流分布情況。(2)所采用的頁(yè)面替換算法。(3)頁(yè)面大小。(4)主存儲(chǔ)器的容量(5)所采用的頁(yè)面調(diào)度算法 以下，對(duì)后三個(gè)因素進(jìn)行分析。1.頁(yè)面大小與命中率的關(guān)系 頁(yè)面大小為某個(gè)值時(shí)，命中率達(dá)到最大。,頁(yè)面大小與命中率關(guān)系的解釋： 假設(shè)At和At+1是相鄰兩次訪問(wèn)主存的邏輯地址， d＝｜At－At+1｜。如果ｄ＜Sp，隨著Sp增大，At 和

40、 At+1在同一頁(yè)面的可能性增加，即Ｈ隨著Sp的增大而提高。如果ｄ＞Sp，At和At+1一定不在同一個(gè)頁(yè)面內(nèi)。隨著Sp增大，主存頁(yè)面數(shù)減少，頁(yè)面替換更加頻繁。Ｈ隨著Sp的增大而降低。,當(dāng)Sp比較小的時(shí)候，前一種情況是主要的，Ｈ隨著Sp的增大而提高。當(dāng)Sp達(dá)到某一個(gè)最大值之后，后一種情況成為主要的，Ｈ隨著Sp的增大而降低。當(dāng)頁(yè)面增大時(shí)，造 成的浪費(fèi)也要增加當(dāng)頁(yè)面減小時(shí)，頁(yè) 表和頁(yè)面表在主存 儲(chǔ)器中所占的比例 將增加,

41、2. 主存容量與命中率的關(guān)系 主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。 在S比較小的時(shí)候，H提高得非常快。隨著S的逐漸增加，H提高的速度逐漸降低。當(dāng)S增加到某一個(gè)值之后，H幾乎不再提高。,3. 頁(yè)面調(diào)度方式與命中率的關(guān)系 請(qǐng)求式：當(dāng)使用到的時(shí)候，再調(diào)入主存 預(yù)取式：在程序重新開(kāi)始運(yùn)行之前，把上次 停止運(yùn)行前一段時(shí)間內(nèi)用到的頁(yè)面先調(diào)入到 主存儲(chǔ)器，然后才開(kāi)始運(yùn)行程序。 預(yù)取式的主要優(yōu)點(diǎn)

42、： 可以避免在程序開(kāi)始運(yùn)行時(shí)，頻繁發(fā)生頁(yè)面 失效的情況。 預(yù)取式的主要缺點(diǎn)： 如果調(diào)入的頁(yè)面用不上，浪費(fèi)了調(diào)入的時(shí)間， 占用了主存的資源。,3.3 高速緩沖存儲(chǔ)器,3.3.1 基本工作原理3.3.2 地址映象與變換方法3.3.3 Cache替換算法及其實(shí)現(xiàn)3.3.4 Cache存儲(chǔ)系統(tǒng)的加速比3.3.5 Cache的一致性問(wèn)題3.3.6 Cache的預(yù)取算法,,3.3.1 基本

43、工作原理,3.3.2 地址映象與變換方法,地址映象： 把主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對(duì)應(yīng)關(guān)系。 地址變換： 當(dāng)程序已經(jīng)裝入到Cache之后，在程序運(yùn)行過(guò)程中，把主存地址變換成Cache地址。在選取地址映象方法要考慮的主要因素： 地址變換的硬件實(shí)現(xiàn)容易、速度要快， 主存空間利用率要高， 發(fā)生塊沖突的概率要小。,1. 全相聯(lián)映象及其變換 映象

44、規(guī)則：主存的任意 一塊可以映象到Cache 中的任意一塊。（映象關(guān)系有Cb×Mb種）,地址變換規(guī)則 用硬件實(shí)現(xiàn)非常復(fù)雜,2. 直接映象及其變換 映象規(guī)則： 主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特定的塊中。 Cache地址的計(jì)算公式： b＝B mod Cb 其中：b為Cache塊號(hào)， B是主存塊號(hào)， Cb

45、是Cache塊數(shù)。 實(shí)際上，Cache地址與主存儲(chǔ)器地址的低位部分完全相同。,直接映象方式的地址映象規(guī)則,直接映象方式的地址變換過(guò)程：用主存地址中的塊號(hào)B去訪問(wèn)區(qū)號(hào)存儲(chǔ)器，把讀出來(lái)的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比較：比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。比較結(jié)果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。,直接映象方式的地址變換規(guī)則,提高Cache速度的一種方法： 把區(qū)號(hào)存儲(chǔ)器

46、與Cache合并成一個(gè)存儲(chǔ)器,2. 直接映象及其變換的優(yōu)缺點(diǎn) ? 主要優(yōu)點(diǎn)： 硬件實(shí)現(xiàn)很簡(jiǎn)單，不需要相聯(lián)訪問(wèn)存儲(chǔ)器 訪問(wèn)速度也比較快，實(shí)際上不需要進(jìn)行地址變換 ? 主要缺點(diǎn)： 塊的沖突率比較高。,3. 組相聯(lián)映象及其變換 映象規(guī)則： 主存和Cache按同樣大小劃分成塊和組。 主存和Cache的組之間采用直接映象方式。 在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象

47、方式。 組相聯(lián)映象方式的優(yōu)點(diǎn)： 塊的沖突概率比較低， 塊的利用率大幅度提高， 塊失效率明顯降低。 組相聯(lián)映象方式的缺點(diǎn)： 實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。,組相聯(lián)映象的地址變換過(guò)程：用主存地址中的組號(hào)G按地址訪問(wèn)塊表存儲(chǔ)器。 把讀出來(lái)的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒(méi)有命中。,組相聯(lián)映象的地址變

48、換,提高Cache訪問(wèn)速度的一種方法： 用多個(gè)相等比較器來(lái)代替相聯(lián)訪問(wèn),4. 位選擇組相聯(lián)映象及其變換地址映象規(guī)則：主存和Cache都按同樣大小分塊，Cache在分塊的基礎(chǔ)上再分組，主存按照Cache的組容量分區(qū)。主存的塊與Cache的組之間采用直接映象方式，主存中的塊與Cache中組內(nèi)部的各個(gè)塊之間采用全相聯(lián)映象方式。與組相聯(lián)映象方式比較： 映象關(guān)系明顯簡(jiǎn)單，實(shí)現(xiàn)起來(lái)容易。 在塊表中存放和參與相聯(lián)比較的

49、只有區(qū)號(hào)E,位選擇組相聯(lián)的地址映象規(guī)則,位選擇組相聯(lián)的地址變換規(guī)則,5. 段相聯(lián)映象及其變換映象規(guī)則： 主存和Cache都按同樣大小分塊和段 段之間采用全相聯(lián)映象方式 段內(nèi)部的塊之間采用直接映象方式地址變換過(guò)程：用主存地址中的段號(hào)與段表中的主存段號(hào)進(jìn)行相聯(lián)比較如果有相等的，用主存地址的段內(nèi)塊號(hào)按地址訪問(wèn)Cache的段號(hào)部分。把讀出的段號(hào)s與主存地址的段內(nèi)塊號(hào)b及塊內(nèi)地址w拼接起來(lái)得到Cache地址；,段相聯(lián)映

50、象地址映象規(guī)則,段相聯(lián)映象地址變換過(guò)程,段相聯(lián)映象方式的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)： 段表比較簡(jiǎn)單，實(shí)現(xiàn)的成本低。 例如：一個(gè)容量為256KB的Cache，分成8個(gè)段，每段2048塊，每塊16B。 在段表存儲(chǔ)器中只需要存8個(gè)主存地址的段號(hào), 而在塊表中要存儲(chǔ)8×2048＝16384個(gè)區(qū)號(hào)， 兩者相差2000多倍。主要缺點(diǎn)： 當(dāng)發(fā)生段失效時(shí)，要把本段內(nèi)已經(jīng)建立起來(lái)的所有映象關(guān)系全部撤消。,3.3.

51、3 Cache替換算法及其實(shí)現(xiàn),使用的場(chǎng)合： 直接映象方式實(shí)際上不需要替換算法 全相聯(lián)映象方式的替換算法最復(fù)雜 主要用于組相聯(lián)、段相聯(lián)等映象方式中要解決的問(wèn)題：記錄每次訪問(wèn)Cache的塊號(hào)在訪問(wèn)過(guò)程中，對(duì)記錄的塊號(hào)進(jìn)行管理根據(jù)記錄和管理結(jié)果，找出替換的塊號(hào)主要特點(diǎn)：全部用硬件實(shí)現(xiàn),1. 輪換法及其實(shí)現(xiàn) 用于組相聯(lián)映象方式中，有兩種實(shí)現(xiàn)方法。方法一：每塊一個(gè)計(jì)數(shù)器在塊表內(nèi)增加一個(gè)替換計(jì)數(shù)器字段，

52、 計(jì)數(shù)器的長(zhǎng)度與Cache地址中的組內(nèi)塊號(hào)字段的長(zhǎng)度相同。替換方法及計(jì)數(shù)器的管理規(guī)則：新裝入或替換的塊，它的計(jì)數(shù)器清0，同組其它塊的計(jì)數(shù)器都加“1”。在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換的塊。,方法二：每組一個(gè)計(jì)數(shù)器替換規(guī)則和計(jì)數(shù)器的管理： 本組有替換時(shí)，計(jì)數(shù)器加“1”， 計(jì)數(shù)器的值就是要被替換出去的塊號(hào)。輪換法的優(yōu)點(diǎn)：實(shí)現(xiàn)比較簡(jiǎn)單，能夠利用歷史上的塊地址流情況輪換法的缺點(diǎn)：沒(méi)有利用程序的局部性特點(diǎn),2.

53、 LRU算法及其實(shí)現(xiàn)為每一塊設(shè)置一個(gè)計(jì)數(shù)器 計(jì)數(shù)器的長(zhǎng)度與塊號(hào)字段的長(zhǎng)度相同計(jì)數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計(jì)數(shù)器清0，同組中其它塊的計(jì)數(shù)器加1。命中塊的計(jì)數(shù)器清0，同組的其它計(jì)數(shù)器中，凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來(lái)值的加1，其余計(jì)數(shù)器不變。需要替換時(shí)，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)值最大的計(jì)數(shù)器，它所對(duì)應(yīng)的塊被替換。,LRU算法的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)： (1)命中率比較高， (2)能夠比較正確地利用程

54、序的局部性特點(diǎn)， (3)充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，命中率單調(diào)上升。主要缺點(diǎn)： 控制邏輯復(fù)雜，因?yàn)樵黾恿伺袛嗪吞幚硎欠衩械那闆r。,3. 堆棧法堆棧法的管理規(guī)則：把本次訪問(wèn)的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)行相聯(lián)比較。如果有相等的，則Cache命中。把本次訪問(wèn)塊號(hào)從棧頂壓入，堆棧內(nèi)各單元中的塊號(hào)依次往下移，直至與本次訪問(wèn)的塊號(hào)相等的那個(gè)單元為止，再往下的單元直止棧

55、底都不變。如果沒(méi)有相等的，則Cache塊失效。本次訪問(wèn)的塊號(hào)從棧頂壓入，堆棧內(nèi)各單元的塊號(hào)依次往下移，直至棧底，棧底單元中的塊號(hào)被移出堆棧，它就是要被替換的塊號(hào)。,例如：每組為4塊，則堆棧有4個(gè)存儲(chǔ)單元， 每個(gè)單元2位。,堆棧法的主要優(yōu)點(diǎn)： 塊失效率比較低，因?yàn)樗捎昧薒RU算法。 硬件實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。堆棧法的主要缺點(diǎn)： 速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。堆棧法與比較對(duì)法所用觸發(fā)器的比例：

56、 其中，Gb是Cache每一組的塊數(shù)。當(dāng)Gb大于8時(shí)，堆棧法所用的器件明顯少于比較對(duì)法。,3.3.4 Cache存儲(chǔ)系統(tǒng)的加速比,1. 加速比與命中率的關(guān)系Cache存儲(chǔ)系統(tǒng)的加速比SP為： 其中：Tm為主存儲(chǔ)器的訪問(wèn)周期， Tc為Cache的訪問(wèn)周期， T為Cache存儲(chǔ)系統(tǒng)的等效訪問(wèn)周期， H為命中率。提高加速比的最好途徑

57、是提高命中率,加速比 SP 能夠接近于期望值是： 加速比SP與命中率H的關(guān)系,2. Cache命中率與容量的關(guān)系 Cache的命中率隨它的容量的增加而提高。 關(guān)系曲線可以近似地表示為：,3. Cache命中率與塊大小的關(guān)系 在組相聯(lián)方式中, 塊大小對(duì)命中率非常敏感 塊很小時(shí)，命中率很低。 隨著塊大小增加命中率也增加, 有一個(gè)極大值 當(dāng)塊非常大時(shí)

58、, 進(jìn)入Cache中的數(shù)據(jù)可能無(wú)用 當(dāng)塊大小等于Cache容量時(shí), 命中率將趨近零4. Cache命中率與組數(shù)的關(guān)系 在組相聯(lián)方式中, 組數(shù)對(duì)命中率的影響很明顯 隨著組數(shù)的增加，Cache的命中率要降低。 當(dāng)組數(shù)不太大時(shí)(小于512), 命中率的降低很少 當(dāng)組數(shù)超過(guò)一定數(shù)量時(shí), 命中率的下降非?？?Cache命中率與塊大小的關(guān)系,3.3.5 Cache的一致性,造成Cache與主存的不一致的原因：

59、 (1) 由于CPU寫(xiě)Cache，沒(méi)有立即寫(xiě)主存 (2) 由于IO處理機(jī)或IO設(shè)備寫(xiě)主存,Cache的更新算法 (1)寫(xiě)直達(dá)法，寫(xiě)通過(guò)法，WT(Write-through) CPU的數(shù)據(jù)寫(xiě)入Cache時(shí)，同時(shí)也寫(xiě)入主存 (2) 寫(xiě)回法，抵觸修改法，WB(Write-Back) CPU的數(shù)據(jù)只寫(xiě)入Cache，不寫(xiě)入主存，僅當(dāng)替換時(shí)，才把修改過(guò)的Cache塊寫(xiě)回主存寫(xiě)回法與寫(xiě)直達(dá)法的優(yōu)缺點(diǎn)比較

60、： (1)可靠性，寫(xiě)直達(dá)法優(yōu)于寫(xiě)回法。寫(xiě)直達(dá)法能夠始終保證Cache是主存的副本。如果Cache發(fā)生錯(cuò)誤，可以從主存得到糾正。,(2)與主存的通信量，寫(xiě)回法少于寫(xiě)直達(dá)法。對(duì)于寫(xiě)回法： 大多數(shù)操作只需要寫(xiě)Cache，不需要寫(xiě)主存； 當(dāng)發(fā)生塊失效時(shí)，可能要寫(xiě)一個(gè)塊到主存； 即使是讀操作，也可能要寫(xiě)一個(gè)塊到主存。對(duì)于寫(xiě)直達(dá)法： 每次寫(xiě)操作，必須寫(xiě)、且只寫(xiě)一個(gè)字到主存。實(shí)際上： 寫(xiě)直達(dá)法的

61、寫(xiě)次數(shù)很多、每次只寫(xiě)一個(gè)字； 寫(xiě)回法是的寫(xiě)次數(shù)很少、每次要寫(xiě)一個(gè)塊。舉例說(shuō)明：,(3)控制的復(fù)雜性, 寫(xiě)直達(dá)法比寫(xiě)回法簡(jiǎn)單。對(duì)于寫(xiě)回法： 要為每塊設(shè)置一個(gè)修改位，而且要對(duì)修改位進(jìn)行管理； 為了保證Cache的正確性，通常要采用比較復(fù)雜的校驗(yàn)方式或校正方式。對(duì)于寫(xiě)直達(dá)法： 不需要設(shè)置修改位； 只需要采用簡(jiǎn)單的奇偶校驗(yàn)即可。由于Cache始終是主存的副本，Cache一旦有錯(cuò)誤可以從主存得到糾正。,(4)

62、硬件實(shí)現(xiàn)的代價(jià), 寫(xiě)回法要比寫(xiě)直達(dá)法好。對(duì)于寫(xiě)直達(dá)法： 為了縮短寫(xiě)Cache流水段的時(shí)間，通常要設(shè)置一個(gè)小容量的高速寄存器堆（后行寫(xiě)數(shù)緩沖站），每個(gè)存儲(chǔ)單元要有數(shù)據(jù)、地址和控制狀態(tài)等3部分組成。 每次寫(xiě)主存時(shí)，首先把寫(xiě)主存的數(shù)據(jù)和地址寫(xiě)到高速寄存器堆中。 每次讀主存時(shí)，要首先判斷所讀數(shù)據(jù)是否在這個(gè)高速寄存器堆中。寫(xiě)回法不需要設(shè)置高速緩沖寄存器堆。,寫(xiě)Cache的兩種方法： (1)不按寫(xiě)分配法： 在

63、寫(xiě)Cache不命中時(shí)，只把所要寫(xiě)的字寫(xiě)入主存。 (2)按寫(xiě)分配法： 在寫(xiě)Cache不命中時(shí)，還把一個(gè)塊從主存讀入Cache。 目前，在寫(xiě)回法中采用按寫(xiě)分配法， 在寫(xiě)直達(dá)法中采用不按寫(xiě)分配法。,解決Cache與主存不一致的主要方法： (1)共享Cache法。能根本解決Cache不一致， 共享Cache可能成為訪問(wèn)的瓶頸，硬件復(fù)雜 (2)作廢法。當(dāng)某一處理機(jī)寫(xiě)局

64、部Cache時(shí)， 同時(shí)作廢其他處理機(jī)的局部Cache。 (3)播寫(xiě)法。把寫(xiě)Cache的內(nèi)容和地址放到公共總線上，各局部Cache隨時(shí)監(jiān)聽(tīng)公共總線 (4)目錄表法。在目錄表中存放Cache一致性的全部信息。 (5)禁止共享信息放在局部Cache中。 Cache對(duì)系統(tǒng)程序員不透明。,3.3.6 Cache的預(yù)取算法,預(yù)取算法有如下幾種： (1)按需取。當(dāng)出現(xiàn)Cache不命中時(shí)，才把需要的一個(gè)塊

65、取到Cache中。 (2)恒預(yù)取。無(wú)論Cache是否命中，都把下一塊取到Cache中。 (3)不命中預(yù)取。當(dāng)出現(xiàn)Cache不命中，把本塊和下一塊都取到Cache中。主要考慮因素： 命中率是否提高，Cache與主存間通信量。 恒預(yù)取能使Cache不命中率降低75～85％ 不命中預(yù)取能使Cache不命中率降低30～40％,3.4 三級(jí)存儲(chǔ)系統(tǒng),虛擬存儲(chǔ)系統(tǒng)和Cache存儲(chǔ)系統(tǒng)可同時(shí)存在存儲(chǔ)系統(tǒng)可以有多種

66、構(gòu)成方法不同的構(gòu)成只是實(shí)現(xiàn)技術(shù)不同,3.4.1 存儲(chǔ)系統(tǒng)的組織方式,兩個(gè)存儲(chǔ)系統(tǒng)的組織方式： 又稱為：物理地址Cache存儲(chǔ)系統(tǒng) 目前的大部分處理機(jī)采用這種兩級(jí)存儲(chǔ)系統(tǒng)一個(gè)存儲(chǔ)系統(tǒng)組織方式： 又稱為：虛擬地址Cache存儲(chǔ)系統(tǒng) 如Intel公司的i860等處理機(jī)采用這種組織方式全Cache系統(tǒng)： 沒(méi)有主存儲(chǔ)器， 由Cache和磁盤(pán)組成存儲(chǔ)系統(tǒng)。,1. 兩個(gè)存儲(chǔ)系統(tǒng)的組織方式

67、2. 一個(gè)存儲(chǔ)系統(tǒng)組織方式3. 全Cache系統(tǒng),3.4.2 虛擬地址Cache,虛擬存儲(chǔ)器采用位選擇組相聯(lián)方式 虛擬存儲(chǔ)器中的一頁(yè)等于主存儲(chǔ)器的一個(gè)區(qū)用虛擬地址中的虛頁(yè)號(hào)訪問(wèn)快表如果快表命中，把塊表中的主存區(qū)號(hào)E與快表中的主存實(shí)頁(yè)號(hào)P進(jìn)行比較。若比較結(jié)果相等，則Cache命中。讀出Cache的塊號(hào)b，并與B、b、W拼接得到Cache地址。若Cache不命中，則用主存實(shí)頁(yè)號(hào)P、及B和W拼接，得到主存實(shí)地址。若快

68、表沒(méi)有命中，通過(guò)軟件查主存中的慢表,3.4.3 全Cache存儲(chǔ)系統(tǒng),建立存儲(chǔ)系統(tǒng)的目的：獲得一個(gè)速度接近Cache，容量等于虛擬地址空間的存儲(chǔ)器。這個(gè)存儲(chǔ)器如何構(gòu)成，具體分成幾級(jí)來(lái)實(shí)現(xiàn)，只是具體的實(shí)現(xiàn)技術(shù)而已。隨著計(jì)算機(jī)硬件和軟件技術(shù)的發(fā)展，存儲(chǔ)系統(tǒng)的實(shí)現(xiàn)技術(shù)也在不斷改變。最直接最簡(jiǎn)單的方法：用一個(gè)速度很高，存儲(chǔ)容量很大的存儲(chǔ)器來(lái)實(shí)現(xiàn)。全Cache(all-Cache)是一種理想的存儲(chǔ)系統(tǒng)。,一種多處理機(jī)系統(tǒng)中的全Cache存