計(jì)系第六章-存儲(chǔ)-2(1)

1、Shenzhen University1Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition高速緩存存儲(chǔ)器高速緩存存儲(chǔ)器Shenzhen University2Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition存儲(chǔ)器層次結(jié)構(gòu)舉例存儲(chǔ)器層次結(jié)構(gòu)舉例寄存器L1高速緩存(SRAM)主存(DRAM)本地二級(jí)存儲(chǔ)(本地磁盤(pán))更大, 更慢, 更廉價(jià) (每字節(jié))的存儲(chǔ)器遠(yuǎn)程二級(jí)存儲(chǔ)(分布式文件

2、系統(tǒng)、Web服務(wù)器)本地磁盤(pán)保存著從遠(yuǎn)程本地磁盤(pán)保存著從遠(yuǎn)程網(wǎng)絡(luò)服務(wù)器磁盤(pán)上取出網(wǎng)絡(luò)服務(wù)器磁盤(pán)上取出的文件的文件L2 高速緩存 (SRAM)L1 L1 高速緩存保存著從高速緩存保存著從 L2 L2 高速緩高速緩存取出的緩存行存取出的緩存行. .CPU CPU 寄存器保存著從高速緩存存儲(chǔ)寄存器保存著從高速緩存存儲(chǔ)器取出的字器取出的字L2 L2 高速緩存保存著從高速緩存保存著從L3L3高速緩高速緩存取出的緩存行存取出的緩存行 L0:L0:L1:L1:L2:L2:L3:L3:L4:L4:L5:L5:更小,更快,更貴(每字節(jié))的存儲(chǔ)器L3 高速緩存 (SRAM)L3 L3 高速緩存保存著從主存高速緩高

3、速緩存保存著從主存高速緩存取出的緩存行存取出的緩存行L6:L6:主存保存著從本地磁盤(pán)取主存保存著從本地磁盤(pán)取出的磁盤(pán)塊出的磁盤(pán)塊Shenzhen University3Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition層次存儲(chǔ)器系統(tǒng)的運(yùn)行原理層次存儲(chǔ)器系統(tǒng)的運(yùn)行原理 選用生產(chǎn)與運(yùn)行選用生產(chǎn)與運(yùn)行成本不同成本不同的、存儲(chǔ)的、存儲(chǔ)容量不同容量不同的、的、讀寫(xiě)讀寫(xiě)速度不同速度不同的多種存儲(chǔ)介質(zhì)，組成一個(gè)統(tǒng)一的存儲(chǔ)的多種存儲(chǔ)介質(zhì)，組成一個(gè)統(tǒng)一的存儲(chǔ)器系統(tǒng)，使每種介質(zhì)都處于不同的地位，發(fā)揮不同的

4、器系統(tǒng)，使每種介質(zhì)都處于不同的地位，發(fā)揮不同的作用，充分發(fā)揮各自在作用，充分發(fā)揮各自在速度速度、容量容量、成本成本方面的優(yōu)勢(shì)，方面的優(yōu)勢(shì)，從而達(dá)到最優(yōu)性能價(jià)格比，以滿(mǎn)足使用要求。從而達(dá)到最優(yōu)性能價(jià)格比，以滿(mǎn)足使用要求。 例如，用容量更小但速度最快的例如，用容量更小但速度最快的 SRAM芯片組成芯片組成 Cache，容量較大速度適中的，容量較大速度適中的 DRAM芯片組成芯片組成 主存主存，用容量特大但速度極慢的磁盤(pán)設(shè)備構(gòu)成用容量特大但速度極慢的磁盤(pán)設(shè)備構(gòu)成 二級(jí)存儲(chǔ)二級(jí)存儲(chǔ)Shenzhen University4Bryant and OHallaron, Computer Systems: A

5、 Programmers Perspective, Third EditionCPUCPU與與DRAMDRAM性能比較性能比較處理器性能每年處理器性能每年增長(zhǎng)增長(zhǎng)60%動(dòng)態(tài)存儲(chǔ)器性能每年增長(zhǎng)9%110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982CPU與主存儲(chǔ)器的性能差與主存儲(chǔ)器的性能差異，每年增長(zhǎng)異，每年增長(zhǎng)50%性能性能摩爾定律年份年份CPUCPU著力提高處理速度，主存以提高容量為主，兼顧訪(fǎng)問(wèn)速度的提高著力提高處理速度，主存以提高容量為主，兼

6、顧訪(fǎng)問(wèn)速度的提高CacheCacheShenzhen University5Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition高速緩存高速緩存cachecache基本概念基本概念0 01 12 23 34 45 56 67 78 89 91010111112121313141415158 89 914143 3高速緩存高速緩存主存主存更大、更慢、更廉價(jià)的主存更大、更慢、更廉價(jià)的主存被分成被分成“塊塊”數(shù)據(jù)以塊大小為傳輸單元數(shù)據(jù)以塊大小為傳輸單元在層與層之間拷貝在層與層之間拷貝更小、更快

7、、更昂貴的存儲(chǔ)器更小、更快、更昂貴的存儲(chǔ)器緩存緩存“塊塊”的一個(gè)子集的一個(gè)子集4 44 44 4101010101010Shenzhen University6Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器(CACHE)的運(yùn)行原理的運(yùn)行原理用途：用途：設(shè)置在設(shè)置在 CPU 和和 主存儲(chǔ)器之間，完成高速與主存儲(chǔ)器之間，完成高速與 CPU 交換信息，交換信息，盡量避免盡量避免 CPU不必要地多次直接不必要地多次直接訪(fǎng)問(wèn)慢速的主存儲(chǔ)器訪(fǎng)問(wèn)慢速的主存儲(chǔ)器，從而提

8、高計(jì)算機(jī)系統(tǒng)的運(yùn)，從而提高計(jì)算機(jī)系統(tǒng)的運(yùn)行效率。行效率。實(shí)現(xiàn)：實(shí)現(xiàn)：這是一個(gè)這是一個(gè)存儲(chǔ)容量很小存儲(chǔ)容量很小，但，但讀寫(xiě)速度更快讀寫(xiě)速度更快的，以的，以關(guān)聯(lián)存儲(chǔ)器方式關(guān)聯(lián)存儲(chǔ)器方式運(yùn)行、用運(yùn)行、用靜態(tài)存儲(chǔ)器靜態(tài)存儲(chǔ)器芯片芯片實(shí)現(xiàn)的存儲(chǔ)器系統(tǒng)。實(shí)現(xiàn)的存儲(chǔ)器系統(tǒng)。要求：要求：有有足夠高的命中率足夠高的命中率，既當(dāng)，既當(dāng) CPU需用主存中需用主存中的數(shù)據(jù)時(shí)，多數(shù)情況可以直接從的數(shù)據(jù)時(shí)，多數(shù)情況可以直接從CACHE中得到，中得到，稱(chēng)二者之比為命中率。稱(chēng)二者之比為命中率。Shenzhen University7Bryant and OHallaron, Computer Systems: A Progr

9、ammers Perspective, Third EditionMEMORY CACHE CONTROLCache的基本運(yùn)行原理的基本運(yùn)行原理數(shù)據(jù)總線(xiàn)數(shù)據(jù)總線(xiàn)譯碼選一單元譯碼選一單元比較選一行比較選一行讀過(guò)程為例讀過(guò)程為例地址總線(xiàn)地址總線(xiàn)ADDR DATA CACHE CPU Cache通常采用通常采用 3 種映像方式：種映像方式：全相聯(lián)，直接映像，多路組相聯(lián)全相聯(lián)，直接映像，多路組相聯(lián)Shenzhen University8Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third EditionCach

10、e的幾個(gè)參數(shù)的幾個(gè)參數(shù)塊（塊（Line）：數(shù)據(jù)交換的最小單位）：數(shù)據(jù)交換的最小單位命中（命中（Hit）：在較高層次中發(fā)現(xiàn)要訪(fǎng)問(wèn)的內(nèi)容）：在較高層次中發(fā)現(xiàn)要訪(fǎng)問(wèn)的內(nèi)容命中率（Hit Rate）：命中次數(shù)/訪(fǎng)問(wèn)次數(shù)命中時(shí)間：訪(fǎng)問(wèn)在較高層次中數(shù)據(jù)的時(shí)間失效（失效（Miss）：需要在較低層次中訪(fǎng)問(wèn)塊）：需要在較低層次中訪(fǎng)問(wèn)塊失效率（Miss Rate）：1-命中率失效損失（Miss Penalty）：替換較高層次數(shù)據(jù)塊的時(shí)間+將該塊交付給處理器的時(shí)間命中時(shí)間命中時(shí)間失效損失失效損失Shenzhen University9Bryant and OHallaron, Computer Systems: A

11、 Programmers Perspective, Third Edition Cache的工作原理的工作原理 1、Cache以塊為單位進(jìn)行操作以塊為單位進(jìn)行操作 2、當(dāng)、當(dāng)CPU發(fā)出訪(fǎng)內(nèi)操作請(qǐng)求后，首先由發(fā)出訪(fǎng)內(nèi)操作請(qǐng)求后，首先由Cache控制器判斷當(dāng)前請(qǐng)求的字是控制器判斷當(dāng)前請(qǐng)求的字是否在否在Cache中，若在，叫命中，否則，不命中中，若在，叫命中，否則，不命中 3、 若命中：若命中：若是“讀”請(qǐng)求，則直接對(duì)Cache讀，與主存無(wú)關(guān)若是“寫(xiě)”請(qǐng)求：Cache單元與主存單元同時(shí)寫(xiě)（單元與主存單元同時(shí)寫(xiě)（Write through寫(xiě)）寫(xiě)）只更新只更新Cache單元并加標(biāo)記，移出時(shí)修改主存（寫(xiě)回

12、單元并加標(biāo)記，移出時(shí)修改主存（寫(xiě)回Copy back） 4、未命中時(shí)：、未命中時(shí)：若是“讀”請(qǐng)求，則從主存讀出所需字送CPU，且把含該字的一塊送Cache，稱(chēng)“裝入通過(guò)”，若Cache已滿(mǎn)，置換算法；若是“寫(xiě)”請(qǐng)求，直接寫(xiě)入主存。Shenzhen University10Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third EditionCache的命中率：的命中率：在一個(gè)程序執(zhí)行期間，設(shè)在一個(gè)程序執(zhí)行期間，設(shè)Nc表示表示cache完成存取的總次數(shù)，完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，表示主

13、存完成存取的總次數(shù)，h定定義為命中率。則有：義為命中率。則有：mccNNNh平均訪(fǎng)問(wèn)時(shí)間：平均訪(fǎng)問(wèn)時(shí)間：若若tc表示命中時(shí)的表示命中時(shí)的Cache訪(fǎng)問(wèn)時(shí)間，訪(fǎng)問(wèn)時(shí)間，tm表示未表示未命中時(shí)的主存訪(fǎng)問(wèn)時(shí)間，命中時(shí)的主存訪(fǎng)問(wèn)時(shí)間，1-h表示未命中率，則表示未命中率，則Cache/主存主存系統(tǒng)的平均訪(fǎng)問(wèn)時(shí)間系統(tǒng)的平均訪(fǎng)問(wèn)時(shí)間ta為為： ta= h tc + (1 - h) tmShenzhen University11Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition練習(xí)：練習(xí)：某計(jì)算機(jī)系統(tǒng)

14、的內(nèi)存儲(chǔ)器由某計(jì)算機(jī)系統(tǒng)的內(nèi)存儲(chǔ)器由cachecache和主存構(gòu)成，和主存構(gòu)成，cachecache的存取周期為的存取周期為45ns45ns，主存的存取周期為，主存的存取周期為200ns200ns。已知在。已知在一段給定的時(shí)間內(nèi)，一段給定的時(shí)間內(nèi)，CPUCPU共訪(fǎng)問(wèn)內(nèi)存共訪(fǎng)問(wèn)內(nèi)存45004500次，其中次，其中340340次訪(fǎng)問(wèn)主存。問(wèn)：次訪(fǎng)問(wèn)主存。問(wèn)：CacheCache的命中率是多少？的命中率是多少？CpuCpu訪(fǎng)問(wèn)內(nèi)存的平均時(shí)間是多少納秒？訪(fǎng)問(wèn)內(nèi)存的平均時(shí)間是多少納秒？Cache-Cache-主存系統(tǒng)的效率是多少？主存系統(tǒng)的效率是多少？Shenzhen University12Bryan

15、t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition解：解：1 1、cachecache的命中率的命中率h=Nc/(Nc+Nm)=h=Nc/(Nc+Nm)=（4500-3404500-340）/4500=0.92 /4500=0.92 2 2、cpucpu訪(fǎng)存的平均時(shí)間訪(fǎng)存的平均時(shí)間t ta a=ht=htc c+(1-h)t+(1-h)tm m=0.92 =0.92 45+(1-0.92) 45+(1-0.92) 200=57.4ns200=57.4ns3 3、cache-cache-主存系統(tǒng)的

16、效率主存系統(tǒng)的效率e=tc/ ta=45/57.4=0.78=78%e=tc/ ta=45/57.4=0.78=78%Shenzhen University13Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition2. Cache的組織的組織直接映像方式直接映像方式全相連映像全相連映像多路組相連映像多路組相連映像Shenzhen University14Bryant and OHallaron, Computer Systems: A Programmers Perspective, Th

17、ird EditionCache存儲(chǔ)器存儲(chǔ)器地址映射地址映射直接映射方式：直接映射方式： j = i mod 8 （b） 直接映象024631570246315781012141191315塊號(hào)塊號(hào)塊號(hào)塊號(hào)Cache主存主存Shenzhen University15Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition圖7.3 直接映像cache組織Shenzhen University16Bryant and OHallaron, Computer Systems: A Programm

18、ers Perspective, Third Edition直接映射方式直接映射方式C P U數(shù)據(jù)數(shù)據(jù)地址地址有效位有效位主存儲(chǔ)器主存儲(chǔ)器CACHE比較比較譯碼譯碼譯碼譯碼頁(yè)頁(yè)內(nèi)內(nèi)地地址址頁(yè)頁(yè)號(hào)號(hào)標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)Shenzhen University17Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third EditionCache 舉例舉例8 塊塊 cache每塊每塊16 字節(jié)字節(jié)“直接映射直接映射”: 內(nèi)存中內(nèi)存中的每個(gè)單元在的每個(gè)單元在Cache中中只會(huì)有一個(gè)唯一的位只會(huì)有一個(gè)唯一的位置和它對(duì)應(yīng)。置

19、和它對(duì)應(yīng)。 0-1532-4716-31128-143160-175144-159Shenzhen University18Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition直接映射直接映射Cache 舉例舉例假定有如下訪(fǎng)問(wèn)操作假定有如下訪(fǎng)問(wèn)操作:Read location 0Read location 16Read location 32Read location 4Read location 8Read location 36Read location 32Read locatio

20、n 128Read location 148cache中命中和缺失各中命中和缺失各有多少次有多少次?0-1532-4716-31128-143160-175144-1590-1516-3132-47XXX 128-143XXX 144-159Shenzhen University19Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third EditionCache 舉例：續(xù)舉例：續(xù)Cache中命中和缺失次數(shù)中命中和缺失次數(shù)?Read location 0: MissRead location 16: Mis

21、sRead location 32: MissRead location 4: HitRead location 8: HitRead location 36: HitRead location 32: HitRead location 128: MissRead location 148: Miss命中率命中率 = 4/9 = 45%注意注意:失效的原因失效的原因啟動(dòng)失效沖突失效0-1532-4716-31128-143160-175144-1590-1516-3132-47XXX 128-143XXX 144-159Shenzhen University20Bryant and OHall

22、aron, Computer Systems: A Programmers Perspective, Third Edition增加塊大小可以更好地利用空間局部性增加塊大小可以更好地利用空間局部性直接映射直接映射Cache: 硬件實(shí)現(xiàn)硬件實(shí)現(xiàn) Address (showing bit positions)1612ByteoffsetVTagDataHitData16324Kentries16 bits128 bitsMux323232232Block offsetIndexTag31 16 15 4 32 1 0Shenzhen University21Bryant and OHallaron

23、, Computer Systems: A Programmers Perspective, Third Edition直接映射方式的地址映射特點(diǎn)1. 主存的字塊只可以和固定的Cache字塊對(duì)應(yīng)，方式直接，利用率低。2. 標(biāo)志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標(biāo)志位只要有m-c位。且僅需要比較一次。利用率低，命中率低，效率較低Shenzhen University22Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition全相聯(lián)映象全相聯(lián)映象地址映射

24、地址映射024631570246315781012141191315塊號(hào)塊號(hào)Cache主存全相聯(lián)映像全相聯(lián)映像 主存中的塊可以和主存中的塊可以和Cache中的任意一塊相對(duì)應(yīng)。中的任意一塊相對(duì)應(yīng)。 全相聯(lián)映像方式是最靈活但成本最高的一種方式，可提高全相聯(lián)映像方式是最靈活但成本最高的一種方式，可提高 Cache命中率。命中率。Shenzhen University23Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition全相聯(lián)映像全相聯(lián)映像cache組織組織Shenzhen Universit

25、y24Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition全相聯(lián)方式全相聯(lián)方式C P U數(shù)據(jù)數(shù)據(jù)地址地址有效位有效位主存儲(chǔ)器主存儲(chǔ)器CACHE比較比較譯碼譯碼標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)Shenzhen University25Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition全相連映射硬件實(shí)現(xiàn)舉例全相連映射硬件實(shí)現(xiàn)舉例Shenzhen University26Bryant and OHal

26、laron, Computer Systems: A Programmers Perspective, Third Edition全相聯(lián)方式的地址映射特點(diǎn)1. 主存的字塊可以和Cache的任何字塊對(duì)應(yīng)，利用率高，方式靈活。2. 標(biāo)志位較長(zhǎng)，比較電路的成本太高。如果主存空間有2m塊，則標(biāo)志位要有m位。同時(shí)，如果Cache有n塊，則需要有n個(gè)比較電路。使用成本太高Shenzhen University27Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition組相聯(lián)映象組相聯(lián)映象塊號(hào)塊號(hào)Cach

27、e主存02463157第0組第1組第2組第3組0246315781012141191315多路組相聯(lián)映像多路組相聯(lián)映像 主存中的塊可以和主存中的塊可以和Cache中的任意一塊相對(duì)應(yīng)。中的任意一塊相對(duì)應(yīng)。 全相聯(lián)映像方式是最靈活但成本最高的一種方式，可提全相聯(lián)映像方式是最靈活但成本最高的一種方式，可提 高高 Cache命中率。命中率。Shenzhen University28Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition組相聯(lián)映像cache組織 Shenzhen University

28、29Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition兩路組相聯(lián)方式兩路組相聯(lián)方式C P U數(shù)據(jù)數(shù)據(jù)主存儲(chǔ)器主存儲(chǔ)器CACHE地址地址譯碼譯碼比較比較比較比較譯碼譯碼譯碼譯碼有效位有效位標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)Shenzhen University30Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition兩路組組相聯(lián)方式的地址映射特點(diǎn)1. 前兩種方式的折衷方案。組間為全相連，組內(nèi)為直接映射

29、。2. 集中了兩個(gè)方式的優(yōu)點(diǎn)。成本也不太高。是常用的方式Shenzhen University31Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition組相連組相連Cache訪(fǎng)問(wèn)舉例訪(fǎng)問(wèn)舉例z 假設(shè)有下列訪(fǎng)問(wèn)主存順序:yRead location 0: MissyRead location 16: MissyRead location 32: MissyRead location 4: HityRead location 8: HityRead location 36: HityRead

30、location 32: HityRead location 128: MissyRead location 148: MissyRead location 0: HityRead location 128: HityRead location 4: HityRead location 132: Hit0-1564-790-1516-3132-47128-143144-159Shenzhen University32Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition四路組相連四路組相連

31、Cache實(shí)現(xiàn)實(shí)現(xiàn)Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData1238910111230310Shenzhen University33Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition三種映射方式比較三種映射方式比較直接映射直接映射主存中的一塊只能映射到主存中的一塊只能映射到Cache中唯一的一個(gè)位置中唯一的一個(gè)位置定位時(shí)，不需要判斷，只需替換定位時(shí)，不

32、需要判斷，只需替換全相連映射全相連映射主存中的一塊可以映射到主存中的一塊可以映射到Cache中任何一個(gè)位置中任何一個(gè)位置N路組相連映射路組相連映射主存中的一塊可以選擇映射到主存中的一塊可以選擇映射到Cache中中N個(gè)位置個(gè)位置全相連映射和全相連映射和N路組相連映射的失效處理路組相連映射的失效處理從主存中取出新塊從主存中取出新塊為了騰出為了騰出Cache空間，需要替換出一個(gè)空間，需要替換出一個(gè)Cache塊塊不唯一，則需要判斷應(yīng)替出哪塊不唯一，則需要判斷應(yīng)替出哪塊Shenzhen University34Bryant and OHallaron, Computer Systems: A Progr

33、ammers Perspective, Third Edition習(xí)題習(xí)題設(shè)某計(jì)算機(jī)主存容量為設(shè)某計(jì)算機(jī)主存容量為16MB，緩存的容量為，緩存的容量為16KB。每。每個(gè)字塊有個(gè)字塊有8個(gè)字，每個(gè)字個(gè)字，每個(gè)字32位。設(shè)計(jì)一個(gè)四路組相聯(lián)映位。設(shè)計(jì)一個(gè)四路組相聯(lián)映射（緩存每組內(nèi)共有射（緩存每組內(nèi)共有4個(gè)字塊）的緩存組織。請(qǐng)畫(huà)出主個(gè)字塊）的緩存組織。請(qǐng)畫(huà)出主存地址字段中各段的位數(shù)。存地址字段中各段的位數(shù)。Shenzhen University35Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Editi

34、on1. 先進(jìn)先出算法（先進(jìn)先出算法（FIFO）將最早調(diào)入將最早調(diào)入Cache的字塊替換出的字塊替換出去。容易實(shí)現(xiàn)，開(kāi)銷(xiāo)小。去。容易實(shí)現(xiàn)，開(kāi)銷(xiāo)小。2. 最近最少使用算法（最近最少使用算法（LRU）需要計(jì)算字塊的使用次數(shù)，開(kāi)銷(xiāo)需要計(jì)算字塊的使用次數(shù)，開(kāi)銷(xiāo)大，但平均命中率比大，但平均命中率比FIFO要高。要高。3. 隨機(jī)替換（隨機(jī)替換（RAND）3. Cache 替換算法替換算法 當(dāng)新的主存字塊需要調(diào)入當(dāng)新的主存字塊需要調(diào)入cache存儲(chǔ)器而它的可用位置又存儲(chǔ)器而它的可用位置又已被占滿(mǎn)時(shí)，就產(chǎn)生替換算法問(wèn)題。已被占滿(mǎn)時(shí)，就產(chǎn)生替換算法問(wèn)題。Shenzhen University36Bryant a

35、nd OHallaron, Computer Systems: A Programmers Perspective, Third EditionLRU算法替換登記表Shenzhen University37Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 若若 CPU 改寫(xiě)了改寫(xiě)了 Cache一單元內(nèi)容后且尚未改變主存相一單元內(nèi)容后且尚未改變主存相應(yīng)單元內(nèi)容，則出現(xiàn)應(yīng)單元內(nèi)容，則出現(xiàn)數(shù)據(jù)不一致性數(shù)據(jù)不一致性。 當(dāng)其它當(dāng)其它CPU或外設(shè)讀主存時(shí)，必須保證或外設(shè)讀主存時(shí)，必須保證數(shù)據(jù)一致

36、性數(shù)據(jù)一致性。寫(xiě)直達(dá)寫(xiě)直達(dá)(write through)當(dāng)寫(xiě)當(dāng)寫(xiě)Cache命中時(shí)，命中時(shí)，Cache與主存同時(shí)發(fā)生寫(xiě)修改，因而較與主存同時(shí)發(fā)生寫(xiě)修改，因而較好地維護(hù)了好地維護(hù)了Cache和主存內(nèi)容的一致性。和主存內(nèi)容的一致性。當(dāng)寫(xiě)當(dāng)寫(xiě)Cache未命中時(shí)，只能直接向主存進(jìn)行寫(xiě)入。未命中時(shí)，只能直接向主存進(jìn)行寫(xiě)入。實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是降低了實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是降低了Cache的效率。的效率。4. 寫(xiě)寫(xiě)Cache策略策略Shenzhen University38Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third E

37、dition拖后寫(xiě)拖后寫(xiě)(write back)拖后改寫(xiě)主存單元內(nèi)容，一直拖到有另外的設(shè)備要讀該內(nèi)容拖后改寫(xiě)主存單元內(nèi)容，一直拖到有另外的設(shè)備要讀該內(nèi)容過(guò)時(shí)的主存單元時(shí)，則首先停止這一讀操作，接下來(lái)改寫(xiě)主過(guò)時(shí)的主存單元時(shí)，則首先停止這一讀操作，接下來(lái)改寫(xiě)主存內(nèi)容，之后再啟動(dòng)已停下來(lái)的讀操作；存內(nèi)容，之后再啟動(dòng)已停下來(lái)的讀操作；總線(xiàn)監(jiān)聽(tīng)：總線(xiàn)監(jiān)聽(tīng)：減少了訪(fǎng)問(wèn)主存的次數(shù)，減少了訪(fǎng)問(wèn)主存的次數(shù)，不出現(xiàn)徒勞的寫(xiě)操作，不出現(xiàn)徒勞的寫(xiě)操作，但是存在不但是存在不一致性的隱患；一致性的隱患；控制復(fù)雜些，但可以提供更高系統(tǒng)的運(yùn)行效率?？刂茝?fù)雜些，但可以提供更高系統(tǒng)的運(yùn)行效率。4. 寫(xiě)寫(xiě)Cache策略（續(xù)）策略（

38、續(xù)）Shenzhen University39Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition5. 提高提高Cache的性能的性能提高命中率提高命中率 縮短缺失后的處理時(shí)間縮短缺失后的處理時(shí)間提高訪(fǎng)問(wèn)提高訪(fǎng)問(wèn)Cache的速度的速度Shenzhen University40Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third EditionCache缺失的原因缺失的原因必然缺失必然缺失 （開(kāi)機(jī)或

39、進(jìn)程切換）：首次訪(fǎng)問(wèn)數(shù)據(jù)塊（開(kāi)機(jī)或進(jìn)程切換）：首次訪(fǎng)問(wèn)數(shù)據(jù)塊世事總是有缺憾世事總是有缺憾注意：如果我們運(yùn)行幾百萬(wàn)條指令，有點(diǎn)必然缺失又注意：如果我們運(yùn)行幾百萬(wàn)條指令，有點(diǎn)必然缺失又何妨？何妨？沖突缺失沖突缺失多個(gè)多個(gè) memory塊映射到同一塊映射到同一 cache塊塊解決辦法解決辦法 1：增大：增大 cache 容量容量解決辦法解決辦法 2：增加相連組數(shù)：增加相連組數(shù)容量沖突容量沖突Cache無(wú)法裝入程序需要訪(fǎng)問(wèn)的所有塊無(wú)法裝入程序需要訪(fǎng)問(wèn)的所有塊方案：增大方案：增大 cache 容量容量無(wú)效缺失：其它進(jìn)程（如無(wú)效缺失：其它進(jìn)程（如I/O）修改了主存）修改了主存Shenzhen University41Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition影響影響 CACHE 命中率的因素命中率的因素從從Cache本身諸因素看，可能：本身諸因素看，可能：1. Cache的容量，大一些好的容量，大一些好2. Cache與主存儲(chǔ)器每次交換信息的單位量與主存儲(chǔ)器每次交換信息的單位量(塊塊)適中適中3. Cac