現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心3.1存儲(chǔ)系統(tǒng)原理3.2虛擬存

1、現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心 3.1 存儲(chǔ)系統(tǒng)原理 3.2 虛擬存儲(chǔ)器 3.3 高速緩沖存儲(chǔ)器(Cache) 3.4 三級(jí)存儲(chǔ)系統(tǒng)第3章 存儲(chǔ)系統(tǒng)9/11/20221計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 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 并行訪問存儲(chǔ)器 3.1.5 交叉訪問存儲(chǔ)器 3.1.6 無沖突訪問存儲(chǔ)器9/11/20222計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.1.1 存儲(chǔ)系統(tǒng)的定義 在一臺(tái)計(jì)算機(jī)中，通常有多種存儲(chǔ)器種類：主存儲(chǔ)器、Cache、通用寄存器、緩沖存儲(chǔ)器、磁盤存儲(chǔ)器、磁帶存儲(chǔ)器、光盤存儲(chǔ)器等材料工藝：

2、ECL、TTL、MOS、磁表面、激光，SRAM，DRAM訪問方式：隨機(jī)訪問、直接譯碼、先進(jìn)先出、 相聯(lián)訪問、 塊傳送、文件組9/11/20223計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 存儲(chǔ)器的主要性能：速度、容量、價(jià)格 速度用存儲(chǔ)器的訪問周期、讀出時(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à)格最便宜。9/11/20224計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1. 存儲(chǔ)系統(tǒng)的定義 兩個(gè)或兩個(gè)以上

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

4、/11/20227計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器和硬盤構(gòu)成 主要目的：擴(kuò)大存儲(chǔ)器容量9/11/20228計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2.存儲(chǔ)系統(tǒng)的容量要求：提供盡可能大的地址空間能夠隨機(jī)訪問方法有兩種：只對系統(tǒng)中存儲(chǔ)容量最大的那個(gè)存儲(chǔ)器進(jìn)行編址，其他存儲(chǔ)器只在內(nèi)部編址或不編址 Cache存儲(chǔ)系統(tǒng)另外設(shè)計(jì)一個(gè)容量很大的邏輯地址空間，把相關(guān)存儲(chǔ)器都映射這個(gè)地址空間中 虛擬存儲(chǔ)系統(tǒng)9/11/20229計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.存儲(chǔ)系統(tǒng)的價(jià)格計(jì)算公式：當(dāng)S2S1時(shí)，CC2 S2與S1不能相差太大9/11/202210計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)4. 存儲(chǔ)系統(tǒng)

5、的速度表示方法：訪問周期、存取周期、存儲(chǔ)周期、存取時(shí)間等命中率定義：在M1存儲(chǔ)器中訪問到的概率 其中：N1是對M1存儲(chǔ)器的訪問次數(shù) N2是對M2存儲(chǔ)器的訪問次數(shù)訪問周期與命中率的關(guān)系： THT1(1H)T2 當(dāng)命中率H1時(shí)，TT19/11/202211計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)的訪問效率：訪問效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān)例3.1：假設(shè)T2T，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問效率。解：當(dāng)H0.9時(shí)，e11(0.95(10.9)0.72當(dāng)H0.99時(shí)，e21(0.995(10.99)0.969/11/202212計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)

6、系統(tǒng)提高存儲(chǔ)系統(tǒng)速度的兩條途徑：一是提高命中率H，二是兩個(gè)存儲(chǔ)器的速度不要相差太大其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率例3.2：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2105 T。如果要使訪問效率到達(dá)e0.9，問需要有多高的命中率？9/11/202213計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)解：0.9H90000(1-H)189999.1 H89999計(jì)算得： H0.999998888877777 0.9999995. 采用預(yù)取技術(shù)提高命中率 方法：不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單元組成的一個(gè)數(shù)據(jù)塊取出來送入M1存儲(chǔ)器中。9/11/202214計(jì)算機(jī)系

7、統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 計(jì)算公式： 其中：H是采用預(yù)取技術(shù)之后的命中率 H是原來的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積例3.3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中，當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率H0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T25T1。計(jì)算塊大小為個(gè)字時(shí)，Cache存儲(chǔ)系統(tǒng)的命中率？并分別計(jì)算訪問效率。9/11/202215計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)解：n4520， 采用預(yù)取技術(shù)之后，命中率提高到：9/11/202216計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.4：在一個(gè)虛擬存儲(chǔ)系統(tǒng)中，T2105 T，原來的命中率只有0.8，如果訪問磁盤存儲(chǔ)器的數(shù)據(jù)塊大小為4K字，并要求訪

8、問效率不低于0.9，計(jì)算數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為多少？解：假設(shè)數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率為m，根據(jù)前面給出的關(guān)系，有如下方程組：9/11/202217計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)解方程組： 由方程(1)得到：0.9H+90000-90000H=19/11/202218計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 證明方法一： 采用預(yù)取技術(shù)之后， 不命中率(1-H)降低倍：9/11/202219計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 證明方法二： 在原有命中率的計(jì)算公式中，把訪問次數(shù)擴(kuò)大到n倍。由于采用了預(yù)取技術(shù)，命中次數(shù)為：nN1(n-1)N2,不命中次數(shù)仍為N2，因此新的命中率為：9/11/2

9、02220計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)多個(gè)層次的存儲(chǔ)器： 第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ù)，則有：工作周期TiTi+1， 存儲(chǔ)容量：SiSi+1，單位價(jià)格：CiCi+19/11/202221計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)各級(jí)存儲(chǔ)器的主要主要性能特性 CPU與主存儲(chǔ)器的速度差距

10、越來越大 目前相差兩個(gè)數(shù)量級(jí) 今后CPU與主存儲(chǔ)器的速度差距會(huì)更大9/11/202223計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.1.3 存儲(chǔ)系統(tǒng)的頻帶平衡例3.5：Pentium4的指令執(zhí)行速度為8GIPS，CPU取指令8GW/s，訪問數(shù)據(jù)16GW/s，各種輸入輸出設(shè)備訪問存儲(chǔ)器1GW/s，三項(xiàng)相加，要求存儲(chǔ)器的頻帶寬度不低于25GW/s。 如果采用PC133內(nèi)存，主存與CPU速度差188倍 如果采用PC266內(nèi)存，主存與CPU速度差94倍解決存儲(chǔ)器頻帶平衡方法 (1)多個(gè)存儲(chǔ)器并行工作（本節(jié)下面介紹） (2)設(shè)置各種緩沖存儲(chǔ)器（第五章介紹） (3)采用存儲(chǔ)系統(tǒng)（本章第二、第三節(jié)介紹）9/11/2

11、02224計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.1.4 并行訪問存儲(chǔ)器方法：把m字w位的存儲(chǔ)器改變成為m/n字nw位的存儲(chǔ)器邏輯實(shí)現(xiàn)：把地址碼分成兩個(gè)部分，一部分作為存儲(chǔ)器的地址另一部分負(fù)責(zé)選擇數(shù)據(jù)主要缺點(diǎn)：訪問沖突大 (1)取指令沖突 (2)讀操作數(shù)沖突 (3)寫數(shù)據(jù)沖突 (4)讀寫沖突9/11/202225計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 并行訪問存儲(chǔ)器結(jié)構(gòu)框圖9/11/202226計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1. 高位交叉訪問存儲(chǔ)器主要目的：擴(kuò)大存儲(chǔ)器容量實(shí)現(xiàn)方法：用地址碼的高位部分區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算方法: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j0，

12、1，2，.，m-1 k：存儲(chǔ)體的體號(hào)，k0，1，2，.，n-1 存儲(chǔ)器的地址：Amkj 存儲(chǔ)器的體內(nèi)地址：AjA mod m。 存儲(chǔ)器的體號(hào)： Ak 3.1.5 交叉訪問存儲(chǔ)器9/11/202227計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 高位交叉訪問存儲(chǔ)器結(jié)構(gòu)框圖9/11/202228計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.6：用4M字4位的存儲(chǔ)芯片組成16M32位的主存儲(chǔ)器。共用存儲(chǔ)芯片：用最高2位地址經(jīng)譯碼后產(chǎn)生的信號(hào)，控制各組存儲(chǔ)芯片CS。每組中的32根數(shù)據(jù)線分別對應(yīng)直接相連，稱為“線或”方式。9/11/202229計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202230計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存

13、儲(chǔ)系統(tǒng)2. 低位交叉訪問存儲(chǔ)器 主要目的：提高存儲(chǔ)器訪問速度 實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)分存儲(chǔ)體號(hào) 參數(shù)計(jì)算: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j0，1，2，.，m-1 k：存儲(chǔ)體的體號(hào)，k0，1，2，.，n-1 存儲(chǔ)器地址A的計(jì)算公式為：Anjk 存儲(chǔ)器的體內(nèi)地址：Aj 存儲(chǔ)器的體號(hào)：AkA mod n9/11/202231計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 低位交叉訪問存儲(chǔ)器結(jié)構(gòu)框圖9/11/202232計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 地址是編碼方法： 由8個(gè)存儲(chǔ)體構(gòu)成的低位交叉編址方式9/11/202233計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) n個(gè)存

14、儲(chǔ)體分時(shí)啟動(dòng) 一種采用流水線方式工作的并行存儲(chǔ)器 每存儲(chǔ)體的啟動(dòng)間隔為：t 其中： Tm為每個(gè)存儲(chǔ)體的訪問周期, n為存儲(chǔ)體個(gè)數(shù)。9/11/202234計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)訪問沖突 共有n個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)周期只能取到k個(gè)有效字,其余n-k個(gè)存儲(chǔ)體有沖突。假設(shè)p(k)是k的概率密度函數(shù)，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值為：N是每個(gè)存儲(chǔ)周期能夠訪問到的平均有效字的個(gè)數(shù)。通常把 N稱為并行存儲(chǔ)器的加速比。9/11/202235計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)定義轉(zhuǎn)移概率為g，即讀出的是轉(zhuǎn)移指令，且轉(zhuǎn)移成功的概率。這時(shí)有： p(1)g p(

15、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 (k1,2,n1) p(n)(1-g)n-19/11/202236計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) g(1-g)g(1-g)2g(1-g)n-2g (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)則：1g2(1-g)g3(1-g)2g (n-1)(1-g)n-2gn(1-g)n-11-(1-g)n-19/11/202237計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1-(

16、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-g)n-2g1(1-g)(1-g)2(1-g)n-2(1-g)n-19/11/202238計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202239計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202240計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.7：Star-100巨型機(jī)存儲(chǔ)系統(tǒng)采用并行和交叉相結(jié)合的方式工作，有32個(gè)存儲(chǔ)體低位交叉，每次并行讀寫512位，存儲(chǔ)周期為1280ns，處理機(jī)字長32位，計(jì)算它的頻帶寬度Bm和峰值速度T。解：因?yàn)椋簄32，w512，Tm128

17、0ns， Bmn w/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s T2.5ns與Tm相比，峰值速度提高512倍實(shí)際速度的提高要遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字9/11/202241計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 3.1.6 無沖突訪問存儲(chǔ)器1. 一維數(shù)組(向量)的無沖突訪問存儲(chǔ)器 按連續(xù)地址訪問，沒有沖突， 位移量為2的變址訪問，速度降低一倍，9/11/202242計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 具體方法： 存儲(chǔ)體的個(gè)數(shù)取質(zhì)數(shù)，且n向量長度。 原因：變址位移量必然與存儲(chǔ)體個(gè)數(shù)互質(zhì) 例如：Burroughs公司巨型科學(xué)計(jì)算機(jī)BSP 存儲(chǔ)體個(gè)數(shù)為17 向量長度16我國研制的銀

18、河巨型向量機(jī) 存儲(chǔ)體的個(gè)數(shù)為37 向量長度329/11/202243計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. 二維數(shù)組的無沖突訪問存儲(chǔ)器要求：一個(gè)nn的二維數(shù)組，按行、列、對角線和反對角線訪問，并且在不同的變址位移量情況下，都能實(shí)現(xiàn)無沖突訪問。順序存儲(chǔ)：按行、對角線訪問沒有沖突，但按列訪問每次沖突9/11/202244計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 錯(cuò)位存儲(chǔ)： 按行、按列訪問無沖突， 但按對角線訪問有沖突9/11/202245計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)nn二維數(shù)組無沖突訪問存儲(chǔ)方案 ( P Budnik 和 D J Kuck提出 ) ： 并行存儲(chǔ)體的個(gè)數(shù)mn，并且取質(zhì)數(shù)，同時(shí)還要在行、列方

19、向上錯(cuò)開一定的距離存儲(chǔ)數(shù)組元素。 設(shè)同一列相鄰元素在并行存儲(chǔ)器中錯(cuò)開d1個(gè)存儲(chǔ)體存放，同一行相鄰元素在并行存儲(chǔ)器中錯(cuò)開d2個(gè)存儲(chǔ)體存放。當(dāng)m22p1（p為任意自然數(shù)）時(shí)，能夠同時(shí)實(shí)現(xiàn)按行、按列、按對角線和按反對角線無沖突訪問的充要條件是：d12P，d21。9/11/202246計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例如：44的二維數(shù)組，取并行存儲(chǔ)體的個(gè)數(shù)m5，由關(guān)系式m22P1，解得到p1，計(jì)算得到： d1212 d219/11/202247計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) nn數(shù)組中的任意一個(gè)元素aij在無沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址的計(jì)算公式： 體號(hào)地址：(2P ijk) MOD m 體

20、內(nèi)地址：i 其中：0in1， 0jn1， k是數(shù)組的第一個(gè)元素a00所在體號(hào)地址， m是并行存儲(chǔ)體的個(gè)數(shù)，要求mn且為質(zhì)數(shù)， p是滿足m22P1關(guān)系的任意自然數(shù)。 主要缺點(diǎn)：浪費(fèi)存儲(chǔ)單元 對于nn數(shù)組,有(m-n) m個(gè)存儲(chǔ)單元浪費(fèi) 主要優(yōu)點(diǎn)：實(shí)現(xiàn)簡單 列元素順序存儲(chǔ)，行元素按地址取模順序存儲(chǔ)483. 二維數(shù)組的無沖突訪問存儲(chǔ)器(之二)規(guī)則：對于任意一個(gè)nn的數(shù)組，如果能夠找到滿足n22P關(guān)系的任意自然數(shù)p，則這個(gè)二維數(shù)組就能夠使用n個(gè)并行存儲(chǔ)體實(shí)現(xiàn)按行、列、對角線和反對角線的無沖突訪問。44數(shù)組用4個(gè)存儲(chǔ)體的無訪問沖突存儲(chǔ)方案9/11/202249計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)實(shí)現(xiàn)方法：

21、假設(shè)aij是44數(shù)組中的任意一個(gè)元素，下標(biāo)i和j都可以用兩位二進(jìn)制表示。假設(shè)i和j的高位和低位分別為iH、iL、jH和jL，則aij在無沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址如下： 體號(hào)地址：2(iL jH)(iH iL jL) 體內(nèi)地址：j 其中：0i3，0j3主要優(yōu)點(diǎn)：沒有浪費(fèi)的存儲(chǔ)單元，主要缺點(diǎn)：在執(zhí)行并行讀和寫操作時(shí)需要借助比較復(fù)雜的對準(zhǔn)網(wǎng)絡(luò)。9/11/202250計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.2.1 虛擬存儲(chǔ)器工作原理3.2.2 地址的映象和變換方法3.2.3 加快內(nèi)部地址變換的方法3.2.4 頁面替換算法及其實(shí)現(xiàn)3.2.5 提高主存命中率的方法3.2 虛擬存儲(chǔ)器9/11/202

22、251計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.2.1 虛擬存儲(chǔ)器工作原理也稱為虛擬存儲(chǔ)系統(tǒng)、虛擬存儲(chǔ)體系等其概念由英國曼徹斯特大學(xué)的Kilbrn等人于1961年提出到70年代廣泛應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)目前，許多微型機(jī)也使用虛擬存儲(chǔ)器把主存儲(chǔ)器、磁盤存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的頁 主存儲(chǔ)器的頁稱為實(shí)頁 虛擬存儲(chǔ)器中的頁稱為虛頁9/11/202252計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)內(nèi)部地址變換： 多用戶虛擬地址Av變換成主存實(shí)地址A 多用戶虛擬地址中的頁內(nèi)偏移D直接作為主存實(shí)地址中的頁內(nèi)偏移d， 主存實(shí)頁號(hào)p與它的頁內(nèi)偏移d直接拼接起來就得到主存實(shí)地址A。9/11/202253計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

23、第三章 存儲(chǔ)系統(tǒng)3.2.2 地址的映象與變換三種地址空間：虛擬地址空間 主存儲(chǔ)器地址空間 輔存地址空間地址映象： 把虛擬地址空間映象到主存地址空間地址變換： 在程序運(yùn)行時(shí)，把虛地址變換成主存實(shí)地址三種虛擬存儲(chǔ)器：頁式虛擬存儲(chǔ)器 段式虛擬存儲(chǔ)器 段頁式虛擬存儲(chǔ)器9/11/202255計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1. 段式虛擬存儲(chǔ)器地址映象方法：每個(gè)程序段都從0地址開始編址，長度可長可短，可以在程序執(zhí)行過程中動(dòng)態(tài)改變程序段的長度。地址變換方法：由用戶號(hào)找到基址寄存器，讀出段表起始地址，與虛地址中段號(hào)相加得到段表地址，把段表中的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址。 主要優(yōu)點(diǎn)： (1)程序

24、的模塊化性能好。 (2)便于程序和數(shù)據(jù)的共享。 (3)程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。 (4)便于實(shí)現(xiàn)信息保護(hù)。 主要缺點(diǎn)： (1)地址變換所花費(fèi)的時(shí)間長，兩次加法 (2)主存儲(chǔ)器的利用率往往比較低。 (3)對輔存（磁盤存儲(chǔ)器）的管理比較困難。9/11/202258計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. 頁式虛擬存儲(chǔ)器 地址映象方法： 地址變換方法：9/11/202260計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 主要優(yōu)點(diǎn)： (1)主存儲(chǔ)器的利用率比較高 (2)頁表相對比較簡單 (3)地址變換的速度比較快 (4)對磁盤的管理比較容易 主要缺點(diǎn)： (1)程序的模塊化性能不好 (2)頁表很長，需要占用很大的存儲(chǔ)

25、空間 例如：虛擬存儲(chǔ)空間4GB，頁大小1KB，則頁表的容量為4M字，16MB。9/11/202261計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 段頁式虛擬存儲(chǔ)器 用戶按段寫程序, 每段分成幾個(gè)固定大小的頁 地址映象方法：每個(gè)程序段在段表中占一行， 在段表中給出頁表長度和頁表的起始地址， 頁表中給出每一頁在主存儲(chǔ)器中的實(shí)頁號(hào)。 地址變換方法： 先查段表，得到頁表起始地址和頁表長度， 再查頁表找到要訪問的主存實(shí)頁號(hào)， 把實(shí)頁號(hào)p與頁內(nèi)偏移d拼接得到主存實(shí)地址。4. 外部地址變換 每個(gè)程序有一張外頁表，每一頁或每個(gè)程序段，在外頁表中都有對應(yīng)的一個(gè)存儲(chǔ)字。3.2.3 加快內(nèi)部地址變換的方法造成虛擬存儲(chǔ)器速度

26、降低的主要原因： (1) 要訪問主存儲(chǔ)器必須先查段表或頁表， (2) 可能需要多級(jí)頁表。頁表級(jí)數(shù)的計(jì)算公式： 其中： Nv為虛擬存儲(chǔ)空間大小， Np為頁面的大小， Nd為一個(gè)頁表存儲(chǔ)字的大小9/11/202265計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例如：虛擬存儲(chǔ)空間大小Nv4GB，頁的大小Np1KB，每個(gè)頁表存儲(chǔ)字占用4個(gè)字節(jié)。計(jì)算得到頁表的級(jí)數(shù)：通常僅把1級(jí)頁表和2、3級(jí)頁表中的一小部分駐留在主存中9/11/202266計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1.目錄表 基本思想：用一個(gè)小容量高速存儲(chǔ)器存放頁表地址變換過程： 把多用戶虛地址中U與P拼接，相聯(lián)訪問目錄表。讀出主存實(shí)頁號(hào)p，把p與多用戶虛地

27、址中的D拼接得到主存實(shí)地址。如果相聯(lián)訪問失敗，發(fā)出頁面失效請求。主要優(yōu)點(diǎn)： 與頁表放在主存中相比，查表速度快。主要缺點(diǎn)： 可擴(kuò)展性比較差, 主存儲(chǔ)器容量大時(shí)，目錄表造價(jià)高，速度低。9/11/202268計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. 快慢表 快表：TLB(Translation Lookaside Buffer)： 小容量(幾幾十個(gè)字)， 高速硬件實(shí)現(xiàn)， 采用相聯(lián)方式訪問。 慢表： 當(dāng)快表中查不到時(shí)，從主存的慢表中查找； 慢表按地址訪問；用軟件實(shí)現(xiàn)。 快表與慢表也構(gòu)成一個(gè)兩級(jí)存儲(chǔ)系統(tǒng)。 主要存在問題：相聯(lián)訪問實(shí)現(xiàn)困難，速度低9/11/202270計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 散列

28、函數(shù) 目的：把相聯(lián)訪問變成按地址訪問 散列(Hashing)函數(shù)：AhH(Pv) 采用散列變換實(shí)現(xiàn)快表按地址訪問 避免散列沖突：采用相等比較器 地址變換：相等比較與訪問存儲(chǔ)器同時(shí)進(jìn)行4.虛擬存儲(chǔ)器舉例 例3.8：IMB370/168計(jì)算機(jī)的虛擬存儲(chǔ)器中的快表結(jié)構(gòu)及地址變換過程。 虛擬地址長36位，頁面大小為4KB，每個(gè)用戶最多占用4K 個(gè)頁面，最多允許16G個(gè)用戶，但同時(shí)上機(jī)的用戶數(shù)一般不超過6個(gè)。 采用了兩項(xiàng)新的措施： (1)采用兩個(gè)相等比較器，以減少散列沖突。 (2)用一個(gè)相聯(lián)寄存器組，把24位用的多戶號(hào)U壓縮成3位，以縮短快表的長度。9/11/202273計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)

29、3.2.4 頁面替換算法及其實(shí)現(xiàn)1. 頁面替換發(fā)生時(shí)間： 當(dāng)發(fā)生頁面失效時(shí)，要從磁盤中調(diào)入一頁到主存。如果主存儲(chǔ)器的所有頁面都已經(jīng)被占用，必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。2. 評價(jià)頁面替換算法好壞的標(biāo)準(zhǔn)： 一是命中率要高， 二是算法要容易實(shí)現(xiàn)。9/11/202275計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 頁面替換算法的使用場合：(1)虛擬存儲(chǔ)器中，主存頁面的替換，一般用軟件實(shí)現(xiàn)。(2)Cache中的塊替換，一般用硬件實(shí)現(xiàn)。(3)虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)字的替換，用硬件實(shí)現(xiàn)。(4)虛擬存儲(chǔ)器中，用戶基地址寄存器的替換，用硬件實(shí)現(xiàn)。(5)在有些虛擬

30、存儲(chǔ)器中，目錄表的替換。9/11/202276計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)4. 主要頁面替換算法(1)隨機(jī)算法（RAND random algorithm） 算法簡單，容易實(shí)現(xiàn)。 沒有利用歷史信息，沒有反映程序的局部性 命中率低。(2)先進(jìn)先出算法 (FIFO first-in first-out algorithm) 容易實(shí)現(xiàn)，利用了歷史信息， 沒有反映局部性。 最先調(diào)入的頁面，很可能也是要使用的頁面9/11/202277計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)(3)近期最少使用算法(LFU least frequently used algorithm)：既充分利用了歷史信息，又反映了程序的局

31、部性實(shí)現(xiàn)起來非常困難。(4)最久沒有使用算法(LRU least recently used algorithm)：把LFU算法中的“多”與“少”簡化成“有”與“無”，實(shí)現(xiàn)比較容易(5)最優(yōu)替換算法（OPT optimal replacement algorithm）：是一種理想算法，僅用作評價(jià)其它頁面替換算法好壞的標(biāo)準(zhǔn)。 在虛擬存儲(chǔ)器中，實(shí)際上可能采用的只有FIFO和LRU兩種算法。9/11/202278計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.9：一個(gè)程序共有5個(gè)頁面組成，在程序執(zhí)行過程中，頁面地址流如下： P1，P2，P1，P5，P4，P1，P3，P4，P2，P4 假設(shè)分配給這個(gè)程序的主存只

32、有3個(gè)頁面。(1)給出用FIFO、LRU和OPT三種頁面替換算法對這3個(gè)主存頁面的調(diào)度情況表，并統(tǒng)計(jì)頁面命中次數(shù)。(2)計(jì)算這LRU頁面替換算法的頁面命中率。(3)假設(shè)每個(gè)數(shù)據(jù)平均被訪問30次，為了使LRU算法的失效率小于10-5，計(jì)算頁面大小至少應(yīng)該為多少？9/11/202279計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)解：(1)FIFO、LRU和OPT的頁面命中次數(shù)分別為2次、4次和5次 (2)LRU頁面替換算法的頁面命中率為： Hp4/100.4(3) 解得 P 2000字 頁面大小應(yīng)該為2K字。9/11/202280計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202281計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存

33、儲(chǔ)系統(tǒng)例3.10：一個(gè)循環(huán)程序，依次使用P1，P2，P3， P4頁面，分配給它的主存頁面數(shù)只有2個(gè)。在 FIFO和LRU算法中，發(fā)生“顛簸”現(xiàn)象。5. 堆棧型替換算法 定義：對任意一個(gè)程序的頁地址流作兩次主存頁面數(shù)分配，分別分配 m 個(gè)主存頁面和 n 個(gè)主存頁面，并且有 mn。如果在任何時(shí)刻 t，主存頁面數(shù)集合 Bt 都滿足關(guān)系： Bt（m） Bt（n），則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點(diǎn)是： 隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。9/11/202283計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202284計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.2.5

34、提高主存命中率的方法影響主存命中率的主要因素：(1)程序在執(zhí)行過程中的頁地址流分布情況。(2)所采用的頁面替換算法。(3)頁面大小。(4)主存儲(chǔ)器的容量(5)所采用的頁面調(diào)度算法 以下，對后三個(gè)因素進(jìn)行分析。1.頁面大小與命中率的關(guān)系 頁面大小為某個(gè)值時(shí)，命中率達(dá)到最大。9/11/202285計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)頁面大小與命中率關(guān)系的解釋： 假設(shè)At和At+1是相鄰兩次訪問主存的邏輯地址， dAtAt+1。如果Sp，隨著Sp增大，At 和 At+1在同一頁面的可能性增加，即隨著Sp的增大而提高。如果Sp，At和At+1一定不在同一個(gè)頁面內(nèi)。隨著Sp增大，主存頁面數(shù)減少，頁面替換更加

35、頻繁。隨著Sp的增大而降低。9/11/202286計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)當(dāng)Sp比較小的時(shí)候，前一種情況是主要的，隨著Sp的增大而提高。當(dāng)Sp達(dá)到某一個(gè)最大值之后，后一種情況成為主要的，隨著Sp的增大而降低。當(dāng)頁面增大時(shí)，造 成的浪費(fèi)也要增加當(dāng)頁面減小時(shí)，頁 表和頁面表在主存 儲(chǔ)器中所占的比例 將增加9/11/202287計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. 主存容量與命中率的關(guān)系 主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。 在S比較小的時(shí)候，H提高得非?？臁ｋS著S的逐漸增加，H提高的速度逐漸降低。當(dāng)S增加到某一個(gè)值之后，H幾乎不再提高。9/11/202288計(jì)算機(jī)系統(tǒng)

36、結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 頁面調(diào)度方式與命中率的關(guān)系 請求式：當(dāng)使用到的時(shí)候，再調(diào)入主存 預(yù)取式：在程序重新開始運(yùn)行之前，把上次 停止運(yùn)行前一段時(shí)間內(nèi)用到的頁面先調(diào)入到 主存儲(chǔ)器，然后才開始運(yùn)行程序。 預(yù)取式的主要優(yōu)點(diǎn)： 可以避免在程序開始運(yùn)行時(shí)，頻繁發(fā)生頁面 失效的情況。 預(yù)取式的主要缺點(diǎn)： 如果調(diào)入的頁面用不上，浪費(fèi)了調(diào)入的時(shí)間， 占用了主存的資源。9/11/202289計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)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的一致性問題3

37、.3.6 Cache的預(yù)取算法9/11/202290計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)9/11/202291計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.3.1 基本工作原理3.3.2 地址映象與變換方法 地址映象： 把主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對應(yīng)關(guān)系。 地址變換： 當(dāng)程序已經(jīng)裝入到Cache之后，在程序運(yùn)行過程中，把主存地址變換成Cache地址。在選取地址映象方法要考慮的主要因素： 地址變換的硬件實(shí)現(xiàn)容易、速度要快， 主存空間利用率要高， 發(fā)生塊沖突的概率要小。9/11/202293計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1. 全相聯(lián)映象及其變換 映象規(guī)則

38、：主存的任意 一塊可以映象到Cache 中的任意一塊。（映象關(guān)系有CbMb種） 地址變換規(guī)則 用硬件實(shí)現(xiàn)非常復(fù)雜9/11/202295計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. 直接映象及其變換 映象規(guī)則： 主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特定的塊中。 Cache地址的計(jì)算公式： bB mod Cb 其中：b為Cache塊號(hào)， B是主存塊號(hào)， Cb是Cache塊數(shù)。 實(shí)際上，Cache地址與主存儲(chǔ)器地址的低位部分完全相同。9/11/202296計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 直接映象方式的地址映象規(guī)則 直接映象方式的地址變換過程：用主存地址中的塊號(hào)B去訪問區(qū)號(hào)存儲(chǔ)器，把讀出來的區(qū)號(hào)與主存地

39、址中的區(qū)號(hào)E進(jìn)行比較：比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。比較結(jié)果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。9/11/202298計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 直接映象方式的地址變換規(guī)則 9/11/202299計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 提高Cache速度的一種方法： 把區(qū)號(hào)存儲(chǔ)器與Cache合并成一個(gè)存儲(chǔ)器2. 直接映象及其變換的優(yōu)缺點(diǎn) 主要優(yōu)點(diǎn)： 硬件實(shí)現(xiàn)很簡單，不需要相聯(lián)訪問存儲(chǔ)器 訪問速度也比較快，實(shí)際上不需要進(jìn)行地址變換 主要缺點(diǎn)： 塊的沖突率比較高。9/11/2022101計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 組相聯(lián)映象及其

40、變換 映象規(guī)則： 主存和Cache按同樣大小劃分成塊和組。 主存和Cache的組之間采用直接映象方式。 在兩個(gè)對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。 組相聯(lián)映象方式的優(yōu)點(diǎn)： 塊的沖突概率比較低， 塊的利用率大幅度提高， 塊失效率明顯降低。 組相聯(lián)映象方式的缺點(diǎn)： 實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。9/11/2022102計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)組相聯(lián)映象的地址變換過程：用主存地址中的組號(hào)G按地址訪問塊表存儲(chǔ)器。 把讀出來的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒有命中。9/11/2022104計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章

41、 存儲(chǔ)系統(tǒng) 組相聯(lián)映象的地址變換 提高Cache訪問速度的一種方法： 用多個(gè)相等比較器來代替相聯(lián)訪問9/11/2022107計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)4. 位選擇組相聯(lián)映象及其變換地址映象規(guī)則：主存和Cache都按同樣大小分塊，Cache在分塊的基礎(chǔ)上再分組，主存按照Cache的組容量分區(qū)。主存的塊與Cache的組之間采用直接映象方式，主存中的塊與Cache中組內(nèi)部的各個(gè)塊之間采用全相聯(lián)映象方式。與組相聯(lián)映象方式比較： 映象關(guān)系明顯簡單，實(shí)現(xiàn)起來容易。 在塊表中存放和參與相聯(lián)比較的只有區(qū)號(hào)E9/11/2022108計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 位選擇組相聯(lián)的地址映象規(guī)則 位選擇組相聯(lián)

42、的地址變換規(guī)則5. 段相聯(lián)映象及其變換映象規(guī)則： 主存和Cache都按同樣大小分塊和段 段之間采用全相聯(lián)映象方式 段內(nèi)部的塊之間采用直接映象方式地址變換過程：用主存地址中的段號(hào)與段表中的主存段號(hào)進(jìn)行相聯(lián)比較如果有相等的，用主存地址的段內(nèi)塊號(hào)按地址訪問Cache的段號(hào)部分。把讀出的段號(hào)s與主存地址的段內(nèi)塊號(hào)b及塊內(nèi)地址w拼接起來得到Cache地址；9/11/2022111計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 段相聯(lián)映象地址映象規(guī)則段相聯(lián)映象地址變換過程段相聯(lián)映象方式的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)： 段表比較簡單，實(shí)現(xiàn)的成本低。 例如：一個(gè)容量為256KB的Cache，分成8個(gè)段，每段2048塊，每塊16B。 在段

43、表存儲(chǔ)器中只需要存8個(gè)主存地址的段號(hào), 而在塊表中要存儲(chǔ)8204816384個(gè)區(qū)號(hào)， 兩者相差2000多倍。主要缺點(diǎn)： 當(dāng)發(fā)生段失效時(shí)，要把本段內(nèi)已經(jīng)建立起來的所有映象關(guān)系全部撤消。9/11/2022114計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.3.3 Cache替換算法及其實(shí)現(xiàn)使用的場合： 直接映象方式實(shí)際上不需要替換算法 全相聯(lián)映象方式的替換算法最復(fù)雜 主要用于組相聯(lián)、段相聯(lián)等映象方式中要解決的問題：記錄每次訪問Cache的塊號(hào)在訪問過程中，對記錄的塊號(hào)進(jìn)行管理根據(jù)記錄和管理結(jié)果，找出替換的塊號(hào)主要特點(diǎn)：全部用硬件實(shí)現(xiàn)9/11/2022115計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)1. 輪換法及其實(shí)現(xiàn)

44、 用于組相聯(lián)映象方式中，有兩種實(shí)現(xiàn)方法。方法一：每塊一個(gè)計(jì)數(shù)器在塊表內(nèi)增加一個(gè)替換計(jì)數(shù)器字段， 計(jì)數(shù)器的長度與Cache地址中的組內(nèi)塊號(hào)字段的長度相同。替換方法及計(jì)數(shù)器的管理規(guī)則：新裝入或替換的塊，它的計(jì)數(shù)器清0，同組其它塊的計(jì)數(shù)器都加“1”。在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換的塊。9/11/2022116計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.11：Solar-16/65小型機(jī)的Cache采用位選擇組相聯(lián)映象方式。Cache每組的塊數(shù)為4，因此，每塊用一個(gè)2位的計(jì)數(shù)器。9/11/2022117計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)方法二：每組一個(gè)計(jì)數(shù)器替換規(guī)則和計(jì)數(shù)器的管理： 本組有替換時(shí)，計(jì)

45、數(shù)器加“1”， 計(jì)數(shù)器的值就是要被替換出去的塊號(hào)。例3.12：NOVA3機(jī)的Cache采用組相聯(lián)映象方式，Cache每組的塊數(shù)為8，每組設(shè)置一個(gè)3位計(jì)數(shù)器。在需要替換時(shí)，計(jì)數(shù)器的值加“1”，用計(jì)數(shù)器的值直接作為被替換塊的塊號(hào)。輪換法的優(yōu)點(diǎn)：實(shí)現(xiàn)比較簡單，能夠利用歷史上的塊地址流情況輪換法的缺點(diǎn)：沒有利用程序的局部性特點(diǎn)9/11/2022118計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. LRU算法及其實(shí)現(xiàn)為每一塊設(shè)置一個(gè)計(jì)數(shù)器 計(jì)數(shù)器的長度與塊號(hào)字段的長度相同計(jì)數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計(jì)數(shù)器清0，同組中其它塊的計(jì)數(shù)器加1。命中塊的計(jì)數(shù)器清0，同組的其它計(jì)數(shù)器中，凡計(jì)數(shù)器的值小于命中塊計(jì)

46、數(shù)器原來值的加1，其余計(jì)數(shù)器不變。需要替換時(shí)，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)值最大的計(jì)數(shù)器，它所對應(yīng)的塊被替換。9/11/2022119計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)LRU算法的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)： (1)命中率比較高， (2)能夠比較正確地利用程序的局部性特點(diǎn)， (3)充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，命中率單調(diào)上升。主要缺點(diǎn)： 控制邏輯復(fù)雜，因?yàn)樵黾恿伺袛嗪吞幚硎欠衩械那闆r。 9/11/2022120計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.13：IBM 370/165機(jī)的Cache采用組相聯(lián)映象方式。每組有4塊，為了實(shí)現(xiàn)LRU替換算法，在塊表中為每

47、一塊設(shè)置一個(gè) 2 位的計(jì)數(shù)器。在訪問Cache的過程中，塊的裝入、替換及命中時(shí)，計(jì)數(shù)器的工作情況如表：9/11/2022121計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. 比較對法 以三個(gè)塊為例，分別稱為塊A、塊B、塊C 表示方法：用TAB1表示 B塊比 A 塊更久沒有被訪問過。如果表示塊 C 最久沒有被訪問過： 每次訪問之后要改變觸發(fā)器的狀態(tài) 在訪問塊A之后：TAB1，TAC1 在訪問塊B之后：TAB0，TBC1 在訪問塊C之后：TAC0，TBC09/11/2022122計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 每組個(gè)塊的比較對法9/11/2022123計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)比較對法硬件需求量計(jì)算

48、：需要的觸發(fā)器個(gè)數(shù)為：與門個(gè)數(shù)為Gb，每個(gè)門的輸入端個(gè)數(shù)為Gb-1當(dāng)每組的塊數(shù)比較多時(shí), 采用分級(jí)辦法實(shí)現(xiàn) 實(shí)質(zhì)上是用降低速度來換取節(jié)省器件。例3.14：IBM 3033機(jī)的Cache，每組的塊數(shù)為16，分3級(jí)。從第1級(jí)到第3級(jí)分別為4、2、2。共需要觸發(fā)器個(gè)數(shù)為：64818。如果不分級(jí)則需要觸發(fā)器120個(gè)。9/11/2022124計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)比較對法中每組塊數(shù)與所需硬件的關(guān)系9/11/2022125計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)4. 堆棧法堆棧法的管理規(guī)則：把本次訪問的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)行相聯(lián)比較。如果有相等的，則Cache命中。把本次訪問塊號(hào)從棧頂壓入，堆棧

49、內(nèi)各單元中的塊號(hào)依次往下移，直至與本次訪問的塊號(hào)相等的那個(gè)單元為止，再往下的單元直止棧底都不變。如果沒有相等的，則Cache塊失效。本次訪問的塊號(hào)從棧頂壓入，堆棧內(nèi)各單元的塊號(hào)依次往下移，直至棧底，棧底單元中的塊號(hào)被移出堆棧，它就是要被替換的塊號(hào)。9/11/2022126計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例如：每組為4塊，則堆棧有4個(gè)存儲(chǔ)單元， 每個(gè)單元2位。9/11/2022127計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 每組4塊的堆棧法邏輯圖堆棧法的主要優(yōu)點(diǎn)： 塊失效率比較低，因?yàn)樗捎昧薒RU算法。 硬件實(shí)現(xiàn)相對比較簡單。堆棧法的主要缺點(diǎn)： 速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。堆棧法與比較對法所用

50、觸發(fā)器的比例： 其中，Gb是Cache每一組的塊數(shù)。當(dāng)Gb大于8時(shí)，堆棧法所用的器件明顯少于比較對法。9/11/2022129計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.3.4 Cache存儲(chǔ)系統(tǒng)的加速比1. 加速比與命中率的關(guān)系Cache存儲(chǔ)系統(tǒng)的加速比SP為： 其中：Tm為主存儲(chǔ)器的訪問周期， Tc為Cache的訪問周期， T為Cache存儲(chǔ)系統(tǒng)的等效訪問周期， H為命中率。提高加速比的最好途徑是提高命中率9/11/2022130計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) 加速比 SP 能夠接近于期望值是： 加速比SP與命中率H的關(guān)系9/11/2022131計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)2. Cache命

51、中率與容量的關(guān)系 Cache的命中率隨它的容量的增加而提高。 關(guān)系曲線可以近似地表示為：9/11/2022132計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3. Cache命中率與塊大小的關(guān)系 在組相聯(lián)方式中, 塊大小對命中率非常敏感 塊很小時(shí)，命中率很低。 隨著塊大小增加命中率也增加, 有一個(gè)極大值 當(dāng)塊非常大時(shí), 進(jìn)入Cache中的數(shù)據(jù)可能無用 當(dāng)塊大小等于Cache容量時(shí), 命中率將趨近零4. Cache命中率與組數(shù)的關(guān)系 在組相聯(lián)方式中, 組數(shù)對命中率的影響很明顯 隨著組數(shù)的增加，Cache的命中率要降低。 當(dāng)組數(shù)不太大時(shí)(小于512), 命中率的降低很少 當(dāng)組數(shù)超過一定數(shù)量時(shí), 命中率的下降非常

52、快9/11/2022133計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) Cache命中率與塊大小的關(guān)系9/11/2022134計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)3.3.5 Cache的一致性造成Cache與主存的不一致的原因： (1) 由于CPU寫Cache，沒有立即寫主存 (2) 由于IO處理機(jī)或IO設(shè)備寫主存Cache的更新算法 (1)寫直達(dá)法，寫通過法，WT(Write-through) CPU的數(shù)據(jù)寫入Cache時(shí)，同時(shí)也寫入主存 (2) 寫回法，抵觸修改法，WB(Write-Back) CPU的數(shù)據(jù)只寫入Cache，不寫入主存，僅當(dāng)替換時(shí)，才把修改過的Cache塊寫回主存寫回法與寫直達(dá)法的優(yōu)缺點(diǎn)比

53、較： (1)可靠性，寫直達(dá)法優(yōu)于寫回法。寫直達(dá)法能夠始終保證Cache是主存的副本。如果Cache發(fā)生錯(cuò)誤，可以從主存得到糾正。9/11/2022136計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) (2)與主存的通信量，寫回法少于寫直達(dá)法。對于寫回法： 大多數(shù)操作只需要寫Cache，不需要寫主存； 當(dāng)發(fā)生塊失效時(shí)，可能要寫一個(gè)塊到主存； 即使是讀操作，也可能要寫一個(gè)塊到主存。對于寫直達(dá)法： 每次寫操作，必須寫、且只寫一個(gè)字到主存。實(shí)際上： 寫直達(dá)法的寫次數(shù)很多、每次只寫一個(gè)字； 寫回法是的寫次數(shù)很少、每次要寫一個(gè)塊。舉例說明：9/11/2022137計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng)例3.15：寫操作占總訪

54、存次數(shù)的20, Cache的命中率為99，每塊為4個(gè)字。當(dāng)Cache發(fā)生塊替換時(shí)，有30塊需要寫回到主存，其余的塊因?yàn)闆]有被修改過而不必寫回主存。試比較寫回法與寫直達(dá)法的訪存通信量。解： 對于寫直達(dá)法： 寫主存次數(shù)占總訪存次數(shù)的20， 對于寫回法：(199)3041.2。 因此，與主存的通信量，寫回法要比寫直達(dá)法少10多倍。9/11/2022138計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) (3)控制的復(fù)雜性, 寫直達(dá)法比寫回法簡單。對于寫回法： 要為每塊設(shè)置一個(gè)修改位，而且要對修改位進(jìn)行管理； 為了保證Cache的正確性，通常要采用比較復(fù)雜的校驗(yàn)方式或校正方式。對于寫直達(dá)法： 不需要設(shè)置修改位； 只需要采用簡單的奇偶校驗(yàn)即可。由于Cache始終是主存的副本，Cache一旦有錯(cuò)誤可以從主存得到糾正。9/11/2022139計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章 存儲(chǔ)系統(tǒng) (4)硬件實(shí)現(xiàn)的代價(jià), 寫回法要比寫直達(dá)法好。對于寫直達(dá)法： 為了縮短寫Cache流水段的時(shí)間，通