第3章 華東理工大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 計(jì)141阿金

1、現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心 3.1 存儲(chǔ)系統(tǒng)原理存儲(chǔ)系統(tǒng)原理 3.2 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 3.3 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器(Cache) 3.4 三級(jí)存儲(chǔ)系統(tǒng)三級(jí)存儲(chǔ)系統(tǒng)第第3章章 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng) 3.1 3.1 存儲(chǔ)系統(tǒng)原理存儲(chǔ)系統(tǒng)原理3.1.1 存儲(chǔ)系統(tǒng)的定義存儲(chǔ)系統(tǒng)的定義3.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)3.1.3 存儲(chǔ)系統(tǒng)的頻帶平衡存儲(chǔ)系統(tǒng)的頻帶平衡3.1.4 并行訪問(wèn)存儲(chǔ)器并行訪問(wèn)存儲(chǔ)器 3.1.5 交叉訪問(wèn)存儲(chǔ)器交叉訪問(wèn)存儲(chǔ)器 3.1.6 無(wú)沖突訪問(wèn)存儲(chǔ)器無(wú)沖突訪問(wèn)存儲(chǔ)器3.1.1 3.1.1 存儲(chǔ)系統(tǒng)的定義存儲(chǔ)系統(tǒng)的定義 在一臺(tái)

2、計(jì)算機(jī)中，通常有多種存儲(chǔ)器在一臺(tái)計(jì)算機(jī)中，通常有多種存儲(chǔ)器種類：種類：主存儲(chǔ)器、主存儲(chǔ)器、Cache、通用寄存器、緩沖、通用寄存器、緩沖存儲(chǔ)器、磁盤存儲(chǔ)器、磁帶存儲(chǔ)器、光盤存存儲(chǔ)器、磁盤存儲(chǔ)器、磁帶存儲(chǔ)器、光盤存儲(chǔ)器等儲(chǔ)器等材料工藝：材料工藝：ECL、TTL、MOS、磁表面、激、磁表面、激光，光，SRAM，DRAM訪問(wèn)方式：訪問(wèn)方式：隨機(jī)訪問(wèn)、直接譯碼、先進(jìn)先出、隨機(jī)訪問(wèn)、直接譯碼、先進(jìn)先出、 相聯(lián)訪問(wèn)、相聯(lián)訪問(wèn)、 塊傳送、文件組塊傳送、文件組 存儲(chǔ)器的主要性能：存儲(chǔ)器的主要性能：速度、容量、價(jià)格速度、容量、價(jià)格 速度速度用存儲(chǔ)器的訪問(wèn)周期、讀出時(shí)間、頻帶寬度等表示。 容量容量用字節(jié)B、千字節(jié)

3、KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。 價(jià)格價(jià)格用單位容量的價(jià)格表示，例如：$C/bit。 組成存儲(chǔ)系統(tǒng)的關(guān)鍵：組成存儲(chǔ)系統(tǒng)的關(guān)鍵：把速度、容量和價(jià)格把速度、容量和價(jià)格不同的多個(gè)物理存儲(chǔ)器組織成一個(gè)存儲(chǔ)器，這不同的多個(gè)物理存儲(chǔ)器組織成一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度最快，存儲(chǔ)容量最大，單位容個(gè)存儲(chǔ)器的速度最快，存儲(chǔ)容量最大，單位容量的價(jià)格最便宜。量的價(jià)格最便宜。1. 1. 存儲(chǔ)系統(tǒng)的定義存儲(chǔ)系統(tǒng)的定義 兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來(lái)成為一個(gè)存儲(chǔ)系統(tǒng)。

4、這個(gè)存儲(chǔ)系統(tǒng)對(duì)應(yīng)用連接起來(lái)成為一個(gè)存儲(chǔ)系統(tǒng)。這個(gè)存儲(chǔ)系統(tǒng)對(duì)應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一程序員是透明的，并且，從應(yīng)用程序員看，它是一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。虛擬存儲(chǔ)器系統(tǒng)：對(duì)應(yīng)用程序員透明虛擬存儲(chǔ)器系統(tǒng)：對(duì)應(yīng)用程序員透明Cache存儲(chǔ)系統(tǒng)：對(duì)系統(tǒng)程序員以上均透明存儲(chǔ)系統(tǒng)：對(duì)系統(tǒng)程序員以上均透明 從從外外部部看看 T Tm mi in n（T T1 1，

5、T T2 2，T Tn n） ，用用存存儲(chǔ)儲(chǔ)周周期期表表示示 S Sm ma ax x（S S1 1，S S2 2，S Sn n） ，用用M MB B或或G GB B表表示示 C Cm mi in n（C C1 1，C C2 2，C Cn n） ，用用每每位位的的價(jià)價(jià)格格表表示示1 1( (T T1 1, ,S S1 1, ,C C1 1) )2 2( (T T2 2, ,S S2 2, ,C C2 2) )n n( (T Tn n, ,S Sn n, ,C Cn n) )由多個(gè)存儲(chǔ)器構(gòu)成的存儲(chǔ)系統(tǒng)由多個(gè)存儲(chǔ)器構(gòu)成的存儲(chǔ)系統(tǒng) 系系 統(tǒng)統(tǒng) 程程 序序 員員 看看 ： 速速 度度 接接 近近 C

6、Ca ac ch he e 的的 速速 度度 ， 存存 儲(chǔ)儲(chǔ) 容容 量量 是是 主主 存存 的的 容容 量量 ， 每每 位位 價(jià)價(jià) 格格 接接 近近 主主 存存 儲(chǔ)儲(chǔ) 器器 。C Ca ac ch he e 存存 儲(chǔ)儲(chǔ) 系系 統(tǒng)統(tǒng)C Ca ac ch he e主主 存存 儲(chǔ)儲(chǔ) 器器 在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲(chǔ)系統(tǒng)：在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲(chǔ)系統(tǒng)：CacheCache存儲(chǔ)系統(tǒng)：由存儲(chǔ)系統(tǒng)：由CacheCache和主存儲(chǔ)器構(gòu)成和主存儲(chǔ)器構(gòu)成 主要目的：提高存儲(chǔ)器速度主要目的：提高存儲(chǔ)器速度 應(yīng)應(yīng)用用程程序序員員看看： 速速度度接接近近主主存存儲(chǔ)儲(chǔ)器器的的速速度度， 存存儲(chǔ)儲(chǔ)容容量量是是虛虛

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

8、.存儲(chǔ)系統(tǒng)的價(jià)格存儲(chǔ)系統(tǒng)的價(jià)格計(jì)算公式：當(dāng)S2S1時(shí)，CC2 S2與S1不能相差太大 （S S，C C，T T）由由兩兩個(gè)個(gè)存存儲(chǔ)儲(chǔ)器器構(gòu)構(gòu)成成的的存存儲(chǔ)儲(chǔ)系系統(tǒng)統(tǒng)M1（S1，C1，T1）M2（S2，C2，T2）CC SC SSS1122124. 4. 存儲(chǔ)系統(tǒng)的速度存儲(chǔ)系統(tǒng)的速度表示方法：表示方法：訪問(wèn)周期、存取周期、存儲(chǔ)周期、存取時(shí)間等命中率定義：命中率定義：在在M1存儲(chǔ)器中訪問(wèn)到的概率存儲(chǔ)器中訪問(wèn)到的概率 其中：N1是對(duì)M1存儲(chǔ)器的訪問(wèn)次數(shù) N2是對(duì)M2存儲(chǔ)器的訪問(wèn)次數(shù)訪問(wèn)周期與命中率的關(guān)系：訪問(wèn)周期與命中率的關(guān)系： THT1(1H)T2 當(dāng)命中率H1時(shí)，TT1HNNN112存儲(chǔ)系統(tǒng)的訪

9、問(wèn)效率：存儲(chǔ)系統(tǒng)的訪問(wèn)效率：訪問(wèn)效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之訪問(wèn)效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān)比有關(guān)例例3.13.1：假設(shè)T2T，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問(wèn)效率。解：解：eTTTH TH THHf HTTTT11111122121()()(,)當(dāng)當(dāng)H H0.90.9時(shí)，時(shí)，e e1 11 1(0.9(0.95(15(10.9)0.9)0.720.72當(dāng)當(dāng)H H0.990.99時(shí)，時(shí)，e e2 21 1(0.99(0.995(15(10.99)0.99)0.960.96提高存儲(chǔ)系統(tǒng)速度的兩條途徑：提高存儲(chǔ)系統(tǒng)速度的兩條途徑：一是提高命中率一

10、是提高命中率H H，二是兩個(gè)存儲(chǔ)器的速度不要相差太大二是兩個(gè)存儲(chǔ)器的速度不要相差太大其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率依靠提高命中率例例3.23.2：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2105 T。如果要使訪問(wèn)效率到達(dá)e0.9，問(wèn)需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999計(jì)算得：計(jì)算得： H0.999998888877777 0.9999990 9111 05.()HH5. 采用預(yù)取技術(shù)提高命中率采用預(yù)取技術(shù)提高命中率 方法：方法：不命中時(shí)，把不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單存儲(chǔ)器中相鄰多個(gè)單元組

11、成的一個(gè)數(shù)據(jù)塊取出來(lái)送入元組成的一個(gè)數(shù)據(jù)塊取出來(lái)送入M1存儲(chǔ)器中。存儲(chǔ)器中。 計(jì)算公式：計(jì)算公式： 其中：H是采用預(yù)取技術(shù)之后的命中率 H是原來(lái)的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積HHnn1例例3.33.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ì)算訪問(wèn)效率。99. 0201208 . 01 2nnHH0.558 .1/10.8)5(1(0.81e10.8H:Cache訪問(wèn)效率為：，塊大小為一個(gè)字時(shí)當(dāng)0.9604. 1/10.99)5(1(0.991e2

12、 0.99H:4Cache2訪問(wèn)效率為：，個(gè)字時(shí)塊大小為當(dāng)解：解：n4520， 采用預(yù)取技術(shù)之后，命中率提高到：3.1.2 3.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)多個(gè)層次的存儲(chǔ)器多個(gè)層次的存儲(chǔ)器： 第第1層：層：Register Files(寄存器堆寄存器堆) 第第2層：層： Buffers(Lookahead)(先行緩沖站先行緩沖站) 第第3層：層： Cache(高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器) 第第4層：層： Main Memory(主存儲(chǔ)器主存儲(chǔ)器) 第第5層：層： Online Storage(聯(lián)機(jī)存儲(chǔ)器聯(lián)機(jī)存儲(chǔ)器) 第第6層：層： Off-line Storage(脫機(jī)存儲(chǔ)器

13、脫機(jī)存儲(chǔ)器)用用i表示層數(shù)，表示層數(shù)，則有：工作周期工作周期TiTi+1， 存儲(chǔ)容量：存儲(chǔ)容量：SiSi+1，單位單位價(jià)格：價(jià)格：CiCi+1 第第 1 層層 第第 2 層層 第第 3 層層 第第 4 層層 第第 5 層層 第第 6 層層CPU內(nèi)內(nèi)部部通通用用寄寄存存器器堆堆聯(lián)聯(lián)機(jī)機(jī)外外部部存存儲(chǔ)儲(chǔ)器器（磁磁盤盤存存儲(chǔ)儲(chǔ)器器等等）脫脫機(jī)機(jī)外外部部存存儲(chǔ)儲(chǔ)器器（磁磁帶帶，光光盤盤存存儲(chǔ)儲(chǔ)器器等等）指指令令和和數(shù)數(shù)據(jù)據(jù)緩緩沖沖棧棧C Ca ac ch he e（靜靜態(tài)態(tài)隨隨機(jī)機(jī)存存儲(chǔ)儲(chǔ)器器）SRAM）主主存存儲(chǔ)儲(chǔ)器器（動(dòng)動(dòng)態(tài)態(tài)隨隨機(jī)機(jī)存存儲(chǔ)儲(chǔ)器器 DRAM）存存儲(chǔ)儲(chǔ)容容量量越越來(lái)來(lái)越越大大每每位位

14、的的價(jià)價(jià)格格越越來(lái)來(lái)越越便便宜宜訪訪問(wèn)問(wèn)速速度度越越來(lái)來(lái)越越快快各級(jí)存儲(chǔ)器的主要主要性能特性各級(jí)存儲(chǔ)器的主要主要性能特性 CPUCPU與主存儲(chǔ)器的速度差距越來(lái)越大與主存儲(chǔ)器的速度差距越來(lái)越大 目前相差目前相差兩個(gè)數(shù)量級(jí) 今后今后CPUCPU與主存儲(chǔ)器的速度差距會(huì)更大與主存儲(chǔ)器的速度差距會(huì)更大存存儲(chǔ)儲(chǔ)器器層層次次 通通用用寄寄存存器器 緩緩沖沖棧棧 C Ca ac ch he e 主主存存儲(chǔ)儲(chǔ)器器 磁磁盤盤存存儲(chǔ)儲(chǔ)器器 脫脫機(jī)機(jī)存存儲(chǔ)儲(chǔ)器器 存存儲(chǔ)儲(chǔ)周周期期 1 10 0n ns s 1 10 0n ns s 1 10 06 60 0n ns s 6 60 03 30 00 0n ns s 1

15、10 03 30 0m ms s 2 22 20 0m mi in n 存存儲(chǔ)儲(chǔ)容容量量 5 51 12 2B B 20002000字字 頁(yè)面大小應(yīng)該為頁(yè)面大小應(yīng)該為2K2K字。字。10P034 . 01H15Pn時(shí)時(shí)間間t t1 12 23 34 45 56 67 78 89 91 10 0實(shí)實(shí)際際頁(yè)頁(yè)地地址址流流P P1 1P P2 2P P1 1P P5 5P P4 4P P1 1P P3 3P P4 4P P2 2P P4 4命命中中次次數(shù)數(shù)1 11 11 11 1* *4 44 44 4* *4 4* *2 22 2先先進(jìn)進(jìn)先先出出算算法法2 22 22 22 2* *1 11 11

16、 11 1* *4 4（F FI IF FO O 算算法法）5 55 55 5* *3 33 33 33 3* *調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 替替換換 替替換換 命命中中 替替換換 替替換換2 2 次次1 11 11 11 11 11 11 11 1* *2 22 2最最久久沒(méi)沒(méi)有有使使用用算算法法2 22 22 2* *4 44 44 4* *4 44 44 4（L LR RU U 算算法法）5 55 5* *5 5* *3 33 33 3* *3 3* *調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 命命中中 替替換換 命命中中 替替換換 命命中中4 4 次次1

17、11 11 11 11 11 1* *3 3* *3 3* *3 33 3最最優(yōu)優(yōu)替替換換算算法法2 22 22 22 2* *2 22 22 22 22 2（O OP PT T 算算法法）5 5* *4 44 44 44 44 44 4調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 命命中中 替替換換 命命中中 命命中中 命命中中5 5 次次三三種種頁(yè)頁(yè)面面替替換換算算法法對(duì)對(duì)同同一一個(gè)個(gè)頁(yè)頁(yè)地地址址流流的的調(diào)調(diào)度度過(guò)過(guò)程程例例3.10：一個(gè)循環(huán)程序，依次使用P1，P2，P3， P4頁(yè)面，分配給它的主存頁(yè)面數(shù)只有3個(gè)。在 FIFO和LRU算法中，發(fā)生“顛簸顛簸”現(xiàn)象。時(shí)時(shí)間間 t t1 1

18、2 23 34 45 56 67 78 8實(shí)實(shí)際際頁(yè)頁(yè)地地址址流流P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P3 3P P4 4命命中中次次數(shù)數(shù)1 11 11 1* *4 44 44 4* *3 33 3先先進(jìn)進(jìn)先先出出算算法法2 22 22 2* *1 11 11 1* *4 4（F FI IF FO O 算算法法）3 33 33 3* *2 22 22 2* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換替替換換0 0 次次1 11 11 1* *4 44 44 4* *3 33 3最最久久沒(méi)沒(méi)有有使使用用算算法法2 22 22 2* *1 1

19、1 11 1* *4 4（L LR RU U 算算法法）3 33 33 3* *2 22 22 2* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換替替換換0 0 次次1 11 11 11 11 1* *1 11 11 1最最優(yōu)優(yōu)替替換換算算法法2 22 22 22 22 2* *3 3* *3 3（O OP PT T 算算法法）3 3* *4 4* *4 44 44 44 4* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換命命中中命命中中替替換換命命中中3 3 次次5. 5. 堆棧型替換算法堆棧型替換算法 定義：定義：對(duì)任意一個(gè)程序的頁(yè)地址流作兩次主對(duì)任意一個(gè)程序的頁(yè)地址流作兩次主存頁(yè)面數(shù)

20、分配，分別分配存頁(yè)面數(shù)分配，分別分配 m 個(gè)主存頁(yè)面和個(gè)主存頁(yè)面和 n 個(gè)個(gè)主存頁(yè)面，并且有主存頁(yè)面，并且有 mn。如果在任何時(shí)刻。如果在任何時(shí)刻 t，主存頁(yè)面數(shù)集合主存頁(yè)面數(shù)集合 Bt 都滿足關(guān)系：都滿足關(guān)系： Bt（m） Bt（n），），則這類算法稱為堆棧型替換算法。則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點(diǎn)是：堆棧型算法的基本特點(diǎn)是： 隨著分配給程序的主存頁(yè)面數(shù)增加，主存的隨著分配給程序的主存頁(yè)面數(shù)增加，主存的命中率也提高，至少不下降。命中率也提高，至少不下降。時(shí)時(shí)間間t t1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 2實(shí)實(shí)際際頁(yè)頁(yè)地

21、地址址流流P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P5 5P P1 1P P2 2P P3 3P P4 4P P5 5命命中中次次數(shù)數(shù)1 11 11 1* *4 44 44 4* *5 55 55 55 55 5* *5 5* *主主存存頁(yè)頁(yè)面面數(shù)數(shù)2 22 22 2* *1 11 11 1* *1 1* *1 1* *3 33 33 3N N3 33 33 33 3* *2 22 22 22 22 2* *4 44 4調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換命命中中命命中中替替換換替替換換命命中中3 3次次1 11 11 11 11 1*

22、*1 1* *5 55 55 55 5* *4 44 4主主存存頁(yè)頁(yè)面面數(shù)數(shù)2 22 22 22 22 2* *2 2* *1 11 11 11 1* *5 5N N4 43 33 33 33 33 33 3* *2 22 22 22 2* *4 44 44 44 44 44 4* *3 33 33 3調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換替替換換替替換換替替換換替替換換2 2次次F FI IF FO O算算法法在在主主存存頁(yè)頁(yè)面面數(shù)數(shù)增增加加時(shí)時(shí)命命中中率率反反而而下下降降3.2.5 3.2.5 提高主存命中率的方法提高主存命中率的方法影響主存命中率的主要因素：影響

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

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

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

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

27、e 存儲(chǔ)系統(tǒng)與虛擬存儲(chǔ)系統(tǒng)的比較存儲(chǔ)系統(tǒng)與虛擬存儲(chǔ)系統(tǒng)的比較 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng) Cache 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng) 虛擬存儲(chǔ)虛擬存儲(chǔ)系統(tǒng)系統(tǒng) 要達(dá)到的目標(biāo)要達(dá)到的目標(biāo) 提高速度提高速度 擴(kuò)大容量擴(kuò)大容量 實(shí)現(xiàn)方法實(shí)現(xiàn)方法 全部硬件全部硬件 軟件為主軟件為主, 硬件為輔硬件為輔 兩級(jí)存儲(chǔ)器速度比兩級(jí)存儲(chǔ)器速度比 310 倍倍 105倍倍 頁(yè)（塊）大小頁(yè)（塊）大小 116 字字 1KB16KB 等效存儲(chǔ)容量等效存儲(chǔ)容量 主存儲(chǔ)器主存儲(chǔ)器 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 透明性透明性 對(duì)系統(tǒng)和應(yīng)用程序員對(duì)系統(tǒng)和應(yīng)用程序員 僅對(duì)應(yīng)用程序員僅對(duì)應(yīng)用程序員 不命中時(shí)處理方式不命中時(shí)處理方式 等待主存儲(chǔ)器等待主存儲(chǔ)器 任務(wù)

28、切換任務(wù)切換 主存儲(chǔ)器地址（來(lái)自主存儲(chǔ)器地址（來(lái)自 CPU） 塊號(hào)塊號(hào) B 塊內(nèi)地址塊內(nèi)地址 W 主存地址主存地址 未命中未命中 主存主存Cache 地址變換地址變換 命中命中 已滿已滿 未滿未滿 塊號(hào)塊號(hào) b 塊內(nèi)地址塊內(nèi)地址 w Cache地址地址 Cache 替換策略替換策略 替換塊替換塊 裝入塊裝入塊 Cache 數(shù)據(jù)送數(shù)據(jù)送 CPU（一個(gè)字）（一個(gè)字） 主存儲(chǔ)器 3.3.1 3.3.1 基本工作原理基本工作原理3.3.2 3.3.2 地址映象與變換方法地址映象與變換方法 地址映象：地址映象： 把主存中的程序按照某種規(guī)則裝入到把主存中的程序按照某種規(guī)則裝入到Cache中，并中，并建立主

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

30、 中的任意一塊。中的任意一塊。（映象關(guān)系有CbMb種）塊塊 0塊塊 1塊塊 0塊塊 1塊塊 i塊塊 Cb-1Cache塊塊 Mb-1主主存存儲(chǔ)儲(chǔ)器器 地址變換規(guī)則地址變換規(guī)則 用硬件實(shí)現(xiàn)非常復(fù)雜用硬件實(shí)現(xiàn)非常復(fù)雜 塊塊號(hào)號(hào) B 塊塊內(nèi)內(nèi)地地址址W 主主存存地地址址 Cache 地地址址 塊塊號(hào)號(hào) b 塊塊內(nèi)內(nèi)地地址址 w 相相聯(lián)聯(lián)比比較較 命命中中 B b 主主存存塊塊號(hào)號(hào) B Cache 塊塊號(hào)號(hào) b 有有效效位位 目目錄錄表表（由由相相聯(lián)聯(lián)存存儲(chǔ)儲(chǔ)器器構(gòu)構(gòu)成成，共共 Cb個(gè)個(gè)字字） 2. 2. 直接映象及其變換直接映象及其變換 映象規(guī)則：映象規(guī)則： 主存儲(chǔ)器中一塊只能映象到主存儲(chǔ)器中一塊只

31、能映象到Cache的一個(gè)特的一個(gè)特定的塊中。定的塊中。 Cache地址的計(jì)算公式：地址的計(jì)算公式： bB mod Cb 其中：b為Cache塊號(hào)， B是主存塊號(hào)， Cb是Cache塊數(shù)。 實(shí)際上，Cache地址與主存儲(chǔ)器地址的低位部地址與主存儲(chǔ)器地址的低位部分完全相同。分完全相同。 直接映象方式的地址映象規(guī)則直接映象方式的地址映象規(guī)則 塊塊 0 塊塊 1 區(qū)區(qū) 0 塊塊 Cb-1 塊塊 0 塊塊 Cb 塊塊 1 塊塊 Cb+1 區(qū)區(qū) 1 塊塊 Cb-1 塊塊 2Cb-1 Cache 塊塊 Mb-Cb 塊塊 Mb-Cb+1 區(qū)區(qū) Me-1 塊塊 Mb-1 主主存存儲(chǔ)儲(chǔ)器器 直接映象方式的地址變換

32、過(guò)程：直接映象方式的地址變換過(guò)程：用主存地址中的塊號(hào)用主存地址中的塊號(hào)B去訪問(wèn)區(qū)號(hào)存儲(chǔ)器，把去訪問(wèn)區(qū)號(hào)存儲(chǔ)器，把讀出來(lái)的區(qū)號(hào)與主存地址中的區(qū)號(hào)讀出來(lái)的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比進(jìn)行比較：較：比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。比較結(jié)果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。 主主存存地地址址 區(qū)區(qū)號(hào)號(hào) E 塊塊號(hào)號(hào) B 塊塊內(nèi)內(nèi)地地址址W Cache 地地址址 塊塊號(hào)號(hào) b 塊塊內(nèi)內(nèi)地地址址 w 塊塊失失效效 相相等等比比較較 比比較較相相等等且且有有效效為為 1 E 1 訪訪問(wèn)問(wèn) Cache 區(qū)區(qū)號(hào)號(hào) E（按按地地址址訪訪問(wèn)問(wèn)） 有有效效

33、位位 區(qū)區(qū)表表存存儲(chǔ)儲(chǔ)器器 直接映象方式的地址變換規(guī)則直接映象方式的地址變換規(guī)則 提高提高Cache速度的一種方法：速度的一種方法： 把區(qū)號(hào)存儲(chǔ)器與把區(qū)號(hào)存儲(chǔ)器與Cache合并成一個(gè)存儲(chǔ)器合并成一個(gè)存儲(chǔ)器 區(qū)區(qū)號(hào)號(hào) E 塊塊號(hào)號(hào) B 塊塊內(nèi)內(nèi)地地址址W Cache 地地址址 塊塊號(hào)號(hào) b 塊塊內(nèi)內(nèi)地地址址 w 送送 CPU 訪訪問(wèn)問(wèn)主主存存 相相等等比比較較 相相等等 1/w 選選擇擇 1 E D0 D1 Dw-1 有有效效位位 區(qū)區(qū)號(hào)號(hào) E 數(shù)數(shù)據(jù)據(jù) D0 數(shù)數(shù)據(jù)據(jù) D1 數(shù)數(shù)據(jù)據(jù) Dw-1 按按地地址址訪訪問(wèn)問(wèn)的的 Cache 2. 2. 直接映象及其變換的優(yōu)缺點(diǎn)直接映象及其變換的優(yōu)缺點(diǎn)

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

35、低，塊的沖突概率比較低， 塊的利用率大幅度提高，塊的利用率大幅度提高， 塊失效率明顯降低。塊失效率明顯降低。 組相聯(lián)映象方式的缺點(diǎn)：組相聯(lián)映象方式的缺點(diǎn)： 實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。 塊塊 0 組組 0 Gb-1 Gb 組組 1 2Gb-1 區(qū)區(qū) 0 塊塊 0 GbCg-Gb 組組 0 組組 Cg-1 Gb-1 Cb-1=GbCg-1 Gb 1 2Gb-1 GbCg(Me-1) Cg(Me-1) GbCg(Me-1)+Gb-1 Cb-Gb=CgGb-Gb GbCg(Me-1)+Gb Cg-1 CgMe-Cg+1 Cb-1=CgGb-1 GbCg(Me-

36、1)+2Gb-1 塊塊 2（ Cb-1） Me-1 Cache Me-Gb=GbCgMe-Gb CgMe-1 Mb-1=GbCgMe-1 主主 存存 儲(chǔ)儲(chǔ) 器器 組組 相相 聯(lián)聯(lián) 映映 象象 方方 式式 組相聯(lián)映象的地址變換過(guò)程：組相聯(lián)映象的地址變換過(guò)程：用主存地址中的組號(hào)用主存地址中的組號(hào)G按地址訪問(wèn)塊表存儲(chǔ)器。按地址訪問(wèn)塊表存儲(chǔ)器。 把讀出來(lái)的一組區(qū)號(hào)和塊號(hào)與主存地址中的把讀出來(lái)的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒(méi)有命中。 區(qū)區(qū)號(hào)號(hào) E 組組號(hào)號(hào) G 組組內(nèi)內(nèi)塊塊號(hào)號(hào) B 塊塊內(nèi)內(nèi)地地

37、址址 W 主主存存地地址址 組組號(hào)號(hào) g 組組內(nèi)內(nèi)塊塊號(hào)號(hào) b 塊塊內(nèi)內(nèi)地地址址 w Cache 地地址址 不不等等 相相聯(lián)聯(lián)比比較較 相相等等 相相聯(lián)聯(lián)比比較較(Gb個(gè)個(gè)塊塊) 區(qū)區(qū)號(hào)號(hào) E,組組內(nèi)內(nèi)塊塊號(hào)號(hào) B 組組內(nèi)內(nèi)塊塊號(hào)號(hào) b 塊塊 表表 組相聯(lián)映象的地址變換組相聯(lián)映象的地址變換 提高提高Cache訪問(wèn)速度的一種方法：訪問(wèn)速度的一種方法： 用多個(gè)相等比較器來(lái)代替相聯(lián)訪問(wèn)用多個(gè)相等比較器來(lái)代替相聯(lián)訪問(wèn)區(qū)區(qū)號(hào)號(hào) E區(qū)區(qū)內(nèi)內(nèi)組組號(hào)號(hào) G組組內(nèi)內(nèi)塊塊號(hào)號(hào) B塊塊內(nèi)內(nèi)地地址址 W 主主存存地地址址 塊塊失失效效組組號(hào)號(hào) g組組內(nèi)內(nèi)塊塊號(hào)號(hào) b塊塊內(nèi)內(nèi)地地址址 w 與與Cache 地地址址或或相

38、相等等比比較較相相等等比比較較相相等等比比較較E, B beE, BbE, B be 塊塊表表(按按地地址址訪訪問(wèn)問(wèn),讀讀出出的的多多個(gè)個(gè)字字段段進(jìn)進(jìn)行行相相聯(lián)聯(lián)比比較較,e 為為有有效效位位)4. 4. 位選擇組相聯(lián)映象及其變換位選擇組相聯(lián)映象及其變換地址映象規(guī)則：地址映象規(guī)則：主存和主存和Cache都按同樣大小分塊，都按同樣大小分塊，Cache在分塊的基礎(chǔ)上再分組，在分塊的基礎(chǔ)上再分組，主存按照主存按照Cache的組容量分區(qū)。的組容量分區(qū)。主存的塊與主存的塊與Cache的組之間采用直接映象方式，的組之間采用直接映象方式，主存中的塊與主存中的塊與Cache中組內(nèi)部的各個(gè)塊之間采中組內(nèi)部的各個(gè)

39、塊之間采用全相聯(lián)映象方式。用全相聯(lián)映象方式。與組相聯(lián)映象方式比較：與組相聯(lián)映象方式比較： 映象關(guān)系明顯簡(jiǎn)單，實(shí)現(xiàn)起來(lái)容易。映象關(guān)系明顯簡(jiǎn)單，實(shí)現(xiàn)起來(lái)容易。 在塊表中存放和參與相聯(lián)比較的只有區(qū)號(hào)在塊表中存放和參與相聯(lián)比較的只有區(qū)號(hào)E 位選擇組相聯(lián)的地址映象規(guī)則位選擇組相聯(lián)的地址映象規(guī)則 塊塊 0 1 區(qū)區(qū) 0 塊塊 0 組組 0 Cg-1 Gb-1 Cg Gb Cg+1 組組 1 區(qū)區(qū) 1 2Gb-1 2Cg-1 Cb-Gb=CgGb-Gb Cg-1 Cg(Mb-1) Cb-1=CgGb-1 Cg(Mb-1)+1 Cache 區(qū)區(qū) Me-1 Mb-1=CgMe-1 主主存存儲(chǔ)儲(chǔ)器器 區(qū)區(qū)號(hào)號(hào) E

40、區(qū)區(qū)內(nèi)內(nèi)塊塊號(hào)號(hào) B塊塊內(nèi)內(nèi)地地址址 W 主主存存地地址址 塊塊失失效效組組號(hào)號(hào) g組組內(nèi)內(nèi)塊塊號(hào)號(hào) b塊塊內(nèi)內(nèi) w 與與Cache 地地址址或或相相等等比比較較相相等等比比較較 相相等等比比較較 E b E b E b區(qū)區(qū)號(hào)號(hào)E塊塊號(hào)號(hào)be區(qū)區(qū)號(hào)號(hào)E塊塊號(hào)號(hào)be區(qū)區(qū)號(hào)號(hào)E塊塊號(hào)號(hào)be塊塊表表(按按地地址址訪訪問(wèn)問(wèn),讀讀出出的的多多個(gè)個(gè)區(qū)區(qū)號(hào)號(hào)進(jìn)進(jìn)行行相相聯(lián)聯(lián)比比較較,e 是是有有效效位位) 位選擇組相聯(lián)的地址變換規(guī)則位選擇組相聯(lián)的地址變換規(guī)則5. 5. 段相聯(lián)映象及其變換段相聯(lián)映象及其變換映象規(guī)則：映象規(guī)則： 主存和主存和Cache都按同樣大小分塊和段都按同樣大小分塊和段 段之間采用全相聯(lián)映

41、象方式段之間采用全相聯(lián)映象方式 段內(nèi)部的塊之間采用直接映象方式段內(nèi)部的塊之間采用直接映象方式地址變換過(guò)程：地址變換過(guò)程：用主存地址中的段號(hào)與段表中的主存段號(hào)進(jìn)行用主存地址中的段號(hào)與段表中的主存段號(hào)進(jìn)行相聯(lián)比較相聯(lián)比較如果有相等的，用主存地址的段內(nèi)塊號(hào)按地址如果有相等的，用主存地址的段內(nèi)塊號(hào)按地址訪問(wèn)訪問(wèn)Cache的段號(hào)部分。的段號(hào)部分。把讀出的段號(hào)s與主存地址的段內(nèi)塊號(hào)b及塊內(nèi)地址w拼接起來(lái)得到Cache地址； 段相聯(lián)映象地址映象規(guī)則段相聯(lián)映象地址映象規(guī)則 塊塊 0 段段 0 Sb-1 塊塊 0 Sb 段段 0 段段 1 Sb-1 2Sb-1 Sb 段段 1 2Sb-1 Cb-Sb=Sb(Cs

42、-1) Cs-1 Cb-1=SbCs-1 Cache Mb-Sb=Sb(Ms-1) Ms-1 Mb-1=SbMs-1 主主 存存 儲(chǔ)儲(chǔ) 器器 主主 存存 地地 址址段段 號(hào)號(hào) S段段 內(nèi)內(nèi) 塊塊 號(hào)號(hào) B塊塊 內(nèi)內(nèi) 地地 址址 W段段 號(hào)號(hào) s段段 內(nèi)內(nèi) 塊塊 號(hào)號(hào) b塊塊 內(nèi)內(nèi) 地地 址址 wC ache 地地 址址相相 聯(lián)聯(lián) 比比 較較 段段 0 S 按按 地地 址址 訪訪 問(wèn)問(wèn) 段段 1s1 主主 存存 段段 號(hào)號(hào) SC ache 段段 號(hào)號(hào) s有有 效效 位位 Ms-1 段段 表表 （ 按按 地地 址址 和和 相相 聯(lián)聯(lián) 兩兩 種種 訪訪 問(wèn)問(wèn) 方方 式式 ）段段相相聯(lián)聯(lián)映映象象地地址

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

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

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

46、流情況上的塊地址流情況輪換法的缺點(diǎn)：輪換法的缺點(diǎn)：沒(méi)有利用程序的局部性特點(diǎn)沒(méi)有利用程序的局部性特點(diǎn)2. LRU2. LRU算法及其實(shí)現(xiàn)算法及其實(shí)現(xiàn)為每一塊設(shè)置一個(gè)計(jì)數(shù)器為每一塊設(shè)置一個(gè)計(jì)數(shù)器 計(jì)數(shù)器的長(zhǎng)度與塊號(hào)字段的長(zhǎng)度相同計(jì)數(shù)器的使用及管理規(guī)則：計(jì)數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計(jì)數(shù)器清新裝入或替換的塊，計(jì)數(shù)器清0，同組中其它，同組中其它塊的計(jì)數(shù)器加塊的計(jì)數(shù)器加1。命中塊的計(jì)數(shù)器清命中塊的計(jì)數(shù)器清0，同組的其它計(jì)數(shù)器中，同組的其它計(jì)數(shù)器中，凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來(lái)值的加凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來(lái)值的加1，其余計(jì)數(shù)器不變。，其余計(jì)數(shù)器不變。需要替換時(shí)，在同組的所有計(jì)數(shù)器中

47、選擇計(jì)數(shù)需要替換時(shí)，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)值最大的計(jì)數(shù)器，它所對(duì)應(yīng)的塊被替換。值最大的計(jì)數(shù)器，它所對(duì)應(yīng)的塊被替換。LRU算法的優(yōu)缺點(diǎn)算法的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： (1)命中率比較高，命中率比較高， (2)能夠比較正確地利用程序的局部性特點(diǎn)，能夠比較正確地利用程序的局部性特點(diǎn)， (3)充分地利用歷史上塊地址流的分布情況，充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，命中率單調(diào)上升。命中率單調(diào)上升。主要缺點(diǎn)：主要缺點(diǎn)： 控制邏輯復(fù)雜，控制邏輯復(fù)雜，因?yàn)樵黾恿伺袛嗪吞幚硎欠衩械那闆r。 3. 3. 堆棧法堆棧法堆棧法的管

48、理規(guī)則：堆棧法的管理規(guī)則：把本次訪問(wèn)的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)把本次訪問(wèn)的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)行相聯(lián)比較。行相聯(lián)比較。如果有相等的，則如果有相等的，則Cache命中。把本次訪問(wèn)塊號(hào)命中。把本次訪問(wèn)塊號(hào)從棧頂壓入，堆棧內(nèi)各單元中的塊號(hào)依次往從棧頂壓入，堆棧內(nèi)各單元中的塊號(hào)依次往下移，直至與本次訪問(wèn)的塊號(hào)相等的那個(gè)單下移，直至與本次訪問(wèn)的塊號(hào)相等的那個(gè)單元為止，再往下的單元直止棧底都不變。元為止，再往下的單元直止棧底都不變。如果沒(méi)有相等的，則Cache塊失效。本次訪問(wèn)的塊號(hào)從棧頂壓入，堆棧內(nèi)各單元的塊號(hào)依次往下移，直至棧底，棧底單元中的塊號(hào)被移出堆棧，它就是要被替換的塊號(hào)。 本本次次訪

49、訪問(wèn)問(wèn)的的塊塊號(hào)號(hào) 棧棧頂頂 最最近近訪訪問(wèn)問(wèn)過(guò)過(guò)的的塊塊 壓壓入入過(guò)過(guò)程程到到此此為為止止 與與本本次次訪訪問(wèn)問(wèn)的的塊塊號(hào)號(hào)相相等等 棧棧底底 最最久久沒(méi)沒(méi)有有被被訪訪問(wèn)問(wèn)過(guò)過(guò)的的塊塊 堆棧法的主要優(yōu)點(diǎn)：堆棧法的主要優(yōu)點(diǎn)： 塊失效率比較低，因?yàn)樗捎昧藟K失效率比較低，因?yàn)樗捎昧薒RU算法。算法。 硬件實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。硬件實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。堆棧法的主要缺點(diǎn)：堆棧法的主要缺點(diǎn)： 速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。堆棧法與比較對(duì)法所用觸發(fā)器的比例：堆棧法與比較對(duì)法所用觸發(fā)器的比例： 其中，Gb是Cache每一組的塊數(shù)。當(dāng)Gb大于8時(shí)，堆棧法所用的器件明顯少

50、于比較對(duì)法。GGGGbbbb()log122：3.3.4 Cache3.3.4 Cache存儲(chǔ)系統(tǒng)的加速比存儲(chǔ)系統(tǒng)的加速比1. 1. 加速比與命中率的關(guān)系加速比與命中率的關(guān)系Cache存儲(chǔ)系統(tǒng)的加速比SP為： 其中：Tm為主存儲(chǔ)器的訪問(wèn)周期， Tc為Cache的訪問(wèn)周期， T為Cache存儲(chǔ)系統(tǒng)的等效訪問(wèn)周期， H為命中率。提高加速比的最好途徑是提高命中率提高加速比的最好途徑是提高命中率STTTH TH THHTTf HTTpmmcmcmmc()()(,)111 加速比加速比 SP 能夠接近于期望值是能夠接近于期望值是： 加速比加速比SP與命中率與命中率H的關(guān)系的關(guān)系SP期望值期望值1命中率命

51、中率 HSP max=TmTcTTmc2. Cache2. Cache命中率與容量的關(guān)系命中率與容量的關(guān)系 Cache的命中率隨它的容量的增加而提高。的命中率隨它的容量的增加而提高。 關(guān)系曲線可以近似地表示為：容量容量 S命中率命中率 H1SH113. Cache3. Cache命中率與塊大小的關(guān)系命中率與塊大小的關(guān)系 在組相聯(lián)方式中在組相聯(lián)方式中, 塊大小對(duì)命中率非常敏感塊大小對(duì)命中率非常敏感 塊很小時(shí)，命中率很低。 隨著塊大小增加命中率也增加, 有一個(gè)極大值有一個(gè)極大值 當(dāng)塊非常大時(shí), 進(jìn)入Cache中的數(shù)據(jù)可能無(wú)用 當(dāng)塊大小等于Cache容量時(shí), 命中率將趨近零4. Cache4. Ca

52、che命中率與組數(shù)的關(guān)系命中率與組數(shù)的關(guān)系 在組相聯(lián)方式中在組相聯(lián)方式中, 組數(shù)對(duì)命中率的影響很明顯組數(shù)對(duì)命中率的影響很明顯 隨著組數(shù)的增加，Cache的命中率要降低。 當(dāng)組數(shù)不太大時(shí)(小于512), 命中率的降低很少 當(dāng)組數(shù)超過(guò)一定數(shù)量時(shí), 命中率的下降非常快 Cache命中率與塊大小的關(guān)系命中率與塊大小的關(guān)系塊大小命中率 H1初始 最 佳3.3.5 Cache3.3.5 Cache的一致性的一致性造成造成Cache與主存的不一致的原因：與主存的不一致的原因： (1) 由于CPU寫Cache，沒(méi)有立即寫主存 (2) 由于IO處理機(jī)或IO設(shè)備寫主存CPUI/OCPUI/OCacheXCache

53、X主主存存儲(chǔ)儲(chǔ)器器X主主存存儲(chǔ)儲(chǔ)器器X(a) CPU寫寫Cache (b) I/O寫寫主主存存Cache的更新算法的更新算法 (1)寫直達(dá)法，寫直達(dá)法，寫通過(guò)法，寫通過(guò)法，WT(Write-through) CPU的數(shù)據(jù)寫入Cache時(shí)，同時(shí)也寫入主存 (2) 寫回法，寫回法，抵觸修改法，抵觸修改法，WB(Write-Back) CPU的數(shù)據(jù)只寫入Cache，不寫入主存，僅當(dāng)替換時(shí)，才把修改過(guò)的Cache塊寫回主存寫回法寫回法與與寫直達(dá)法寫直達(dá)法的優(yōu)缺點(diǎn)比較：的優(yōu)缺點(diǎn)比較： (1)可靠性，寫直達(dá)法優(yōu)于寫回法?？煽啃裕瑢懼边_(dá)法優(yōu)于寫回法。寫直達(dá)法能夠始終保證Cache是主存的副本。如果Cache

54、發(fā)生錯(cuò)誤，可以從主存得到糾正。 (2)與主存的通信量，寫回法少于寫直達(dá)法。與主存的通信量，寫回法少于寫直達(dá)法。對(duì)于寫回法： 大多數(shù)操作只需要寫Cache，不需要寫主存； 當(dāng)發(fā)生塊失效時(shí)，可能要寫一個(gè)塊到主存； 即使是讀操作，也可能要寫一個(gè)塊到主存。對(duì)于寫直達(dá)法： 每次寫操作，必須寫、且只寫一個(gè)字到主存。實(shí)際上： 寫直達(dá)法的寫次數(shù)很多、每次只寫一個(gè)字； 寫回法是的寫次數(shù)很少、每次要寫一個(gè)塊。舉例說(shuō)明： (3)控制的復(fù)雜性控制的復(fù)雜性, 寫直達(dá)法比寫回法簡(jiǎn)單。寫直達(dá)法比寫回法簡(jiǎn)單。對(duì)于寫回法： 要為每塊設(shè)置一個(gè)修改位，而且要對(duì)修改位進(jìn)行管理； 為了保證Cache的正確性，通常要采用比較復(fù)雜的校驗(yàn)方

55、式或校正方式。對(duì)于寫直達(dá)法： 不需要設(shè)置修改位； 只需要采用簡(jiǎn)單的奇偶校驗(yàn)即可。由于Cache始終是主存的副本，Cache一旦有錯(cuò)誤可以從主存得到糾正。 (4)硬件實(shí)現(xiàn)的代價(jià)硬件實(shí)現(xiàn)的代價(jià), 寫回法要比寫直達(dá)法好。寫回法要比寫直達(dá)法好。對(duì)于寫直達(dá)法： 為了縮短寫Cache流水段的時(shí)間，通常要設(shè)置一個(gè)小容量的高速寄存器堆（后行寫數(shù)緩沖站），每個(gè)存儲(chǔ)單元要有數(shù)據(jù)、地址和控制狀態(tài)等3部分組成。 每次寫主存時(shí)，首先把寫主存的數(shù)據(jù)和地址寫到高速寄存器堆中。 每次讀主存時(shí)，要首先判斷所讀數(shù)據(jù)是否在這個(gè)高速寄存器堆中。寫回法不需要設(shè)置高速緩沖寄存器堆。 寫寫Cache的兩種方法：的兩種方法： (1)不按寫分

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

57、到公共總線上，各局部Cache隨時(shí)監(jiān)聽公共總線 (4)目錄表法。目錄表法。在目錄表中存放Cache一致性的全部信息。 (5)禁止共享信息放在局部禁止共享信息放在局部Cache中。中。 Cache對(duì)系統(tǒng)程序員不透明。3.3.6 Cache3.3.6 Cache的預(yù)取算法的預(yù)取算法預(yù)取算法有如下幾種：預(yù)取算法有如下幾種： (1)按需取。按需取。當(dāng)出現(xiàn)Cache不命中時(shí)，才把需要的一個(gè)塊取到Cache中。 (2)恒預(yù)取。恒預(yù)取。無(wú)論Cache是否命中，都把下一塊取到Cache中。 (3)不命中預(yù)取。不命中預(yù)取。當(dāng)出現(xiàn)Cache不命中，把本塊和下一塊都取到Cache中。主要考慮因素：主要考慮因素： 命中率是否提高，命中率是否提高，Cache與主存間通信量。與主存間通信量。 恒預(yù)取能使Cache不命中率降低7585 不命中預(yù)