1、3.6.1 Cache的基本原理 Cache 在CPU和主存之間引入速度更快的小容量存儲(chǔ)器，稱高速緩沖存儲(chǔ)器（Cache Memory）。它存放當(dāng)前最活躍的程序和數(shù)據(jù)的副本，使得在大部分情況下，CPU訪問的是Cache而不是主存，大大提高了CPU訪問內(nèi)存的速度。 CPU高速緩存Cache主存MM輔助硬設(shè)備1第1頁，共43頁。3.6.1 Cache的基本原理（續(xù)）Cache能提高訪問速度的原因： Cache由雙極型超高速半導(dǎo)體存儲(chǔ)器組成，速度通常是主存的510倍。程序執(zhí)行的局部性原理時(shí)間局部性空間局部性Cache與主存之間的地址變換和數(shù)據(jù)替換等控制全部用硬件實(shí)現(xiàn)，無需CPU的介入。合理設(shè)計(jì)映像方

2、法和替換算法，提高命中率。分塊2第2頁，共43頁。3.6.2 地址映像地址映像(Mapping)：把信息從主存復(fù)制到Cache的規(guī)則或算法。地址變換：將主存地址變換為Cache地址的過程。地址映像與變換的三種基本方式：全相聯(lián)方式（Associative Mapping）直接方式（Direct Mapping）組相聯(lián)方式（Set-Associative Mapping ）3第3頁，共43頁。3.6.2 地址映像（續(xù)） 策略：先將主存和Cache以同樣大小分塊，主存再按整個(gè)Cache的大小分為若干個(gè)區(qū)。例：內(nèi)存容量256MB，Cache容量1MB，每塊64KB，那么Cache將分為16塊,主存共分

3、為4K塊。第0塊第1塊第15塊MM第4K-1塊Tag0第0塊Tag1第1塊Tag2第2塊Tag3第3塊Tag14第14塊Tag15第15塊Cache4第4頁，共43頁。全相聯(lián)映像（Associative Mapping）映像規(guī)則：內(nèi)存中某一塊可以裝入Cache的任何一塊中。需要記錄對(duì)應(yīng)關(guān)系相聯(lián)存儲(chǔ)器單元數(shù)與Cache塊數(shù)一致且對(duì)應(yīng)內(nèi)容是對(duì)應(yīng)Cache塊所對(duì)應(yīng)的Tag（即存入Cache的主存的塊號(hào)）5第5頁，共43頁。Tag0第0塊Tag1第1塊Tag2第2塊Tag15第15塊Cache12位16位主存塊號(hào)塊內(nèi)地址相聯(lián)比較命中4位16位塊內(nèi)地址Cache塊號(hào)第0塊第1塊第X塊第4K-1塊6第6頁

4、，共43頁。全相聯(lián)映像優(yōu)點(diǎn)：主存的塊裝入Cache的位置沒有限制，只要Cache有空閑塊便可裝入，只有全部裝滿才會(huì)出現(xiàn)沖突。 不足：無法直接從主存塊號(hào)中獲取Cache塊號(hào)，使得其地址變換機(jī)構(gòu)相對(duì)復(fù)雜，使用了相聯(lián)存儲(chǔ)器。前面的例子中，使用的相聯(lián)比較器的位數(shù)為1612=192位。7第7頁，共43頁。直接方式地址映象（Direct Mapping）映像規(guī)則： 主存某一區(qū)第Y 塊只能裝入到Cache的第Y 塊。每個(gè)Cache塊對(duì)應(yīng)了255個(gè)主存塊需記錄主存的區(qū)號(hào)8第8頁，共43頁。區(qū)號(hào)XY0115比Cache地址命中Cache第Y塊第0塊第0塊第0塊第0塊第1塊第15塊第1塊第1塊第1塊第15塊第15

5、塊第15塊第15塊第0塊第1塊第0區(qū)第1區(qū)第X區(qū)第255區(qū)第Y塊主存地址 X Y Z主存區(qū)號(hào)區(qū)內(nèi)塊號(hào)塊內(nèi)地址MM地址訪問存儲(chǔ)器9第9頁，共43頁。直接方式小結(jié)優(yōu)點(diǎn)：地址變換簡單，命中時(shí)直接由主存地址提取到Cache地址。不命中時(shí)替換算法簡單不足：映像關(guān)系固定，不靈活“抖動(dòng)”現(xiàn)象會(huì)造成命中率下降。第0塊第0塊第1塊SUB: 第1塊RET第0區(qū)第1區(qū)CALL SUBNEXT:LOOP NEXTCache第0塊第1塊10第10頁，共43頁。組相聯(lián)映像（Set-Associative Mapping ）映像方法：是上兩種方式的折中。即主存和Cache按同樣大小分塊，Cache按若干塊（例如兩塊）為一組

6、進(jìn)行分組。主存按Cache的組數(shù)進(jìn)行分區(qū)。映像規(guī)則：主存任何一區(qū)的第n塊只能映像至Cache的第n組（直接方式），但主存中任何一塊可以映射到cache對(duì)應(yīng)組的任意2個(gè)塊中（全相聯(lián)方式）。即組間直接方式，組內(nèi)全相聯(lián)方式。11第11頁，共43頁。Cache第K塊第0塊第1塊第0塊第1塊第0組第Y組第7組第0塊第0塊第0塊第0塊第1塊第1塊第1塊第1塊第0區(qū)第X區(qū)第2047區(qū)第Z塊第0組第7組第0組第Y組第0塊第1塊區(qū)號(hào)XYK0115Z組相聯(lián)映像當(dāng)主存第X區(qū)、第Y組、第Z塊裝入cache時(shí)，必定裝入cache的Y組中的任一塊（設(shè)為k），將區(qū)號(hào)X和塊號(hào)Z填入地址變換機(jī)構(gòu)的Y,K單元。12第12頁，共4

7、3頁。Tag0第0塊Tag1第1塊Tag2第2塊Tag3第3塊Tag14第14塊Tag15第15塊Cache命中4位16位塊內(nèi)地址Cache塊號(hào)0組1組7組第0塊第1塊第7塊第0塊第1塊第7塊第0塊第1塊第7塊0區(qū)1區(qū) 511區(qū)9位區(qū)內(nèi)塊號(hào)16位主存區(qū)號(hào)3位塊內(nèi)地址相聯(lián)比較12313第13頁，共43頁。Cache第K塊區(qū)號(hào)X第0塊第0塊第0塊第0塊第1塊3第1塊第1塊第1塊第0塊第1塊第0塊第1塊第0區(qū)第X區(qū)第2047區(qū)YK0115比命中按地址查找第Z塊第0組第7組第0組第Y組第0組第Y組第7組第0塊第1塊19Cache地址Z11位3位9位主存區(qū)號(hào)區(qū)內(nèi)組號(hào)塊內(nèi)地址1位組內(nèi)塊號(hào)組相聯(lián)映像的地址變

8、換12314第14頁，共43頁。組相聯(lián)映像參與全相聯(lián)比較的位數(shù)為：29=18。若每組只有一塊，將成為直接方式，若總共只有一組，將成為全相聯(lián)方式。優(yōu)缺點(diǎn)：介于全相聯(lián)方式和直接方式之間，地址變換機(jī)構(gòu)比全相聯(lián)方式簡單，Cache利用率和命中率又比直接方式高。15第15頁，共43頁。3.6.3 替換算法（Replacement Algorithms）替換算法：當(dāng)引起對(duì)Cache塊的位置爭用時(shí)，更換塊的算法。只有相聯(lián)映像才需要替換算法 常用替換算法： 先進(jìn)先出算法FIFO（First In First Out）對(duì)進(jìn)入Cache的塊按先后順序排隊(duì)，先淘汰最早進(jìn)入的塊。 最近最少使用算法LRU（Least

9、Recently Used）保留最近被訪問的塊，淘汰較長時(shí)間沒有訪問的塊 最少使用頻度法LFU（Least Frequently Used）被訪問次數(shù)最少的塊最先淘汰。有可能最新裝入的塊被替換出去。 隨機(jī)法（Random）16第16頁，共43頁。最近最少使用算法LRU塊號(hào)放在表中排隊(duì)。剛訪問到的塊號(hào)移到表首，其余塊號(hào)下移。表尾是近期最少訪問的塊。例：每組4塊（4-way組相聯(lián)）的塊號(hào)表初始訪問塊3訪問塊1訪問塊0裝入新塊03102103102103132223已替換新內(nèi)容17第17頁，共43頁。最久未使用算法LRU（續(xù)）四路組相聯(lián)LRU算法的另一種實(shí)現(xiàn)：每塊用一個(gè)2位的計(jì)數(shù)器表示被訪問的時(shí)間。

10、每次訪問到的塊的計(jì)數(shù)器清0，同組中計(jì)數(shù)值比該頁原計(jì)數(shù)值低的計(jì)數(shù)器加1。調(diào)入新塊時(shí)，替換計(jì)數(shù)值最大的塊。可以證明，4塊的計(jì)數(shù)值各不相同。初始計(jì)數(shù)值訪問塊3訪問塊1訪問塊0裝入新塊塊001201塊112012塊223330塊33012318第18頁，共43頁。Pentium CPU Cache組織兩路組相聯(lián)映像的LRU算法：每個(gè)Cache塊設(shè)置一個(gè)USE位，當(dāng)某個(gè)Cache塊被訪問，該塊的USE位被置為1，同組的另一塊USE位被置為0。淘汰時(shí)，淘汰USE為0的塊。19第19頁，共43頁。 3.6.4 Cache的結(jié)構(gòu) Cache存放當(dāng)前最活躍的程序和數(shù)據(jù)。大部分情況下，CPU訪問的是Cache而不

11、是主存，提高了CPU訪存的速度。DBMMCPUABCache塊號(hào)塊內(nèi)地址塊內(nèi)地址主存塊地址地址變換替換算法部件Cache存儲(chǔ)器多字高速總線不命中(已滿)不命中(未滿)命中20第20頁，共43頁。3.6.5 Cache讀寫命中（Hit ）：要訪問的單元已在Cache中 讀操作：直接從Cache中讀。 寫操作： 寫回法：只寫入Cache，當(dāng)該塊將被置換時(shí)，再寫入主存。（Write back） 透寫法：同時(shí)寫入Cache和主存。效率低，因?yàn)橛行┲虚g結(jié)果不必寫入主存。 （Write through）未命中（Miss）：要訪問的存儲(chǔ)單元不在Cache中 讀操作： 直接從主存中讀取該單元，然后將該塊置換到

12、Cache 。 先將該塊裝入，然后再從Cache中讀。 寫操作：直接寫入主存，不裝入該塊到Cache中。21第21頁，共43頁。3.6.6 Cache的更新策略當(dāng)出現(xiàn)寫Cache不命中時(shí)，都有一個(gè)是否要把包括所寫字在內(nèi)的一個(gè)塊從主存讀入Cache的問題。不按寫分配法：直接寫入主存，不讀入到Cache。按寫分配法：直接寫入主存，并讀入該塊到Cache。一般在寫回法中采用按寫分配法，而在寫直達(dá)法中采用不按寫分配法。單處理器一般用寫回法，多處理器一般用寫直達(dá)法。22第22頁，共43頁。作業(yè)P59（2.20，2.22） 23第23頁，共43頁。3.7 虛擬存儲(chǔ)器（Virtual Memory）虛擬存儲(chǔ)

13、在主存與輔存之間，增加必要的硬件支持，經(jīng)過操作系統(tǒng)的存儲(chǔ)管理軟件的管理，使主、輔存之間的信息交換，程序的再定位，地址的轉(zhuǎn)換都能自動(dòng)進(jìn)行，使兩者形成一個(gè)有機(jī)的整體。從而得到一個(gè)足夠大的主存空間由于程序員可以用到的空間遠(yuǎn)遠(yuǎn)大于主存的實(shí)際空間，但實(shí)際上不存在這么大的主存，故稱“虛擬存儲(chǔ)器” 。是以軟件為主的技術(shù)。目的對(duì)于多任務(wù)或多用戶系統(tǒng)，有足夠的主存空間。程序員編程時(shí)不必考慮機(jī)器實(shí)際配備的主存大小.本節(jié)內(nèi)容：虛地址實(shí)地址虛擬地址（虛地址）：程序中出現(xiàn)的地址物理地址（實(shí)地址）：實(shí)際主存的地址24第24頁，共43頁。3.7.2 -3.7.4 虛擬存儲(chǔ)器的管理地址映像： 虛地址與主、輔存地址間的對(duì)應(yīng)關(guān)系

14、，稱為地址映 像。管理方式： 段式管理 頁式管理 段頁式管理25第25頁，共43頁。段式管理 將程序按其邏輯功能分段。各程序段的大小不等， 其邏輯地址均從0開始。 裝入時(shí)按段分別裝入內(nèi)存，運(yùn)行時(shí)按段進(jìn)行虛實(shí)地 址轉(zhuǎn)換。 每一個(gè)程序在內(nèi)存中都對(duì)應(yīng)一個(gè)段表，表目和每個(gè) 邏輯段一一對(duì)應(yīng)，記錄了各段存入內(nèi)存的實(shí)地址及 其它有關(guān)信息 段式管理的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：有利于程序的運(yùn)行，便于實(shí)現(xiàn)信息共享和存儲(chǔ)保護(hù)。缺點(diǎn)：隨著程序的運(yùn)行，會(huì)在主存空間產(chǎn)生較多“碎片”。 段式管理地址映像過程如下頁：26第26頁，共43頁。段表：存放虛實(shí)地址的映象關(guān)系。段表按虛段號(hào)的自然順序排列，用來記錄各段在主存中的首地址。段表大小與

15、虛存段數(shù)相同。段表存放在內(nèi)存中。段表基址寄存器：存放段表在內(nèi)存中的首地址裝入：當(dāng)程序的某一段調(diào)入主存時(shí)，將實(shí)地址所在的段號(hào)記錄在段表中，并將裝入標(biāo)志置1訪問：當(dāng)訪問主存時(shí)，根據(jù)虛段號(hào)在段表中找到對(duì)應(yīng)表項(xiàng)若該虛存段已裝入主存，將段表中存儲(chǔ)的實(shí)段首地址與段內(nèi)地址相加，即是主存的物理地址27第27頁，共43頁。頁式管理頁虛存和主存空間以大小相同的存儲(chǔ)空間分頁，虛存的頁為虛頁，主存的頁為實(shí)頁。虛、實(shí)地址格式如圖。頁表頁式管理在內(nèi)存中為每個(gè)用戶設(shè)置一頁表，頁表用來記錄虛地址各頁在內(nèi)存中的位置。頁表大小與虛存頁數(shù)相同。實(shí)頁號(hào)K頁內(nèi)地址虛頁號(hào)X頁內(nèi)地址虛頁號(hào)實(shí)頁號(hào)裝入位0X0K01裝入：當(dāng)虛存的X頁調(diào)入主存

16、時(shí)，將實(shí)地址所在的頁號(hào)記錄在頁表中，并將裝入標(biāo)志置1基號(hào)訪問方式28第28頁，共43頁。存放頁表在內(nèi)存中的起始地址訪問：當(dāng)訪問主存時(shí)，根據(jù)虛頁號(hào)在頁表中找到對(duì)應(yīng)表項(xiàng)將頁表中存儲(chǔ)的實(shí)頁號(hào)與頁內(nèi)地址組裝起來，就是主存的物理地址頁式管理29第29頁，共43頁。頁式管理的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：便于與主存輔存間的調(diào)進(jìn)調(diào)出，有利于主存空間的充分利用。 缺點(diǎn)：難以實(shí)現(xiàn)存儲(chǔ)保護(hù)和存儲(chǔ)共享。30第30頁，共43頁。段頁式管理 將程序先按邏輯功能分為段。 將每段分為頁，所以虛地址包括了段號(hào)、段內(nèi)頁 號(hào)、頁內(nèi)地址。實(shí)地址只有實(shí)頁號(hào)和頁內(nèi)地址。其 地址格式如下： 程序在內(nèi)存中分別建立段表和頁表。 段頁式管理地址映像過程如下

17、頁圖：實(shí)頁號(hào)頁內(nèi)地址實(shí)存地址：虛段號(hào)X段內(nèi)虛頁號(hào)頁內(nèi)地址虛 地址：31第31頁，共43頁。32第32頁，共43頁。 段頁式管理優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：兼有段、頁式管理的優(yōu)點(diǎn)。 缺點(diǎn)：要經(jīng)過三次讀內(nèi)存才能完成虛實(shí)地址的轉(zhuǎn)換。第一次 讀段表得頁 表首地址，第二次讀頁表得實(shí)頁號(hào)，第三次才形成實(shí)地址讀得數(shù)據(jù)。降 低了地址變換的速度。33第33頁，共43頁。3.7.5 快表與慢表快表（快頁表）：位于Cache中，由相聯(lián)存儲(chǔ)器組成 ，存放當(dāng)前最“活躍頁”的地址。其表目格式與頁表完全相同，但項(xiàng)目數(shù)遠(yuǎn)小于內(nèi)頁表（即頁表）。虛頁號(hào)頁內(nèi)地址虛存頁號(hào)實(shí)存頁號(hào)虛存地址實(shí)存地址實(shí)頁號(hào)頁內(nèi)地址相聯(lián)存儲(chǔ)器相聯(lián)比較虛實(shí)地址轉(zhuǎn)換時(shí)，先

18、查快表，若找到，則從快表產(chǎn)生實(shí)地址；若沒找到，再去內(nèi)存查頁表。并且更新快表。34第34頁，共43頁。3.7.5 快表與慢表（續(xù)） 慢表：原先存放全部虛、實(shí)地址映像關(guān)系的表稱為慢表，它位于主存。缺頁時(shí)由慢表得到虛頁在輔存中的存放位置。35第35頁，共43頁。虛擬存儲(chǔ)器的工作過程幀頁表 幀頁表：記錄當(dāng)前內(nèi)存使用情況，即實(shí)頁與虛頁的對(duì)應(yīng)關(guān)系，用來對(duì)主存進(jìn)行管理，它位于主存， 幀頁表按主存實(shí)頁號(hào)順序排列，主存實(shí)頁號(hào)不占存儲(chǔ)空間。其格式見下表：主存實(shí)頁號(hào)占用位程序號(hào)虛頁號(hào)其他012n-1占用位為1表示該頁已被占用，為0表示該頁空。36第36頁，共43頁。3.7.5 快表與慢表（續(xù)） 慢表：用來登記程序虛

19、頁號(hào)與輔存地址的對(duì)應(yīng)關(guān)系，它位于主存。缺頁時(shí)由慢表得到虛頁在輔存中的存放位置。虛頁號(hào)輔存地址012m-1柱面號(hào) 盤面號(hào) 扇區(qū)號(hào)裝入位37第37頁，共43頁。用戶號(hào)虛存頁號(hào)頁內(nèi)地址頁內(nèi)地址實(shí)存頁地址主存實(shí)地址主存輔存裝入頁替換頁替換算法主存已滿主存未滿輔存實(shí)地址幀頁表外頁表內(nèi)頁表快表內(nèi)頁表不命中快表不命中(b)更新(a)快表命中(b)頁表命中I/O通道(a)(c)(c)(d)(a) 虛地址包含用戶號(hào)、虛頁號(hào)、頁內(nèi)地址。每個(gè)用戶都有自已的頁表地址寄存器、內(nèi)頁表（即頁表）和快表。根據(jù)用戶號(hào)、虛頁號(hào)同時(shí)查快表和內(nèi)頁表，如果快表命中，則得到頁的實(shí)際地址。(b)如果快表不命中，若內(nèi)頁表命中，則由內(nèi)頁表得到主存實(shí)際頁地址，同時(shí)根據(jù)Cache替換算法，將該表目復(fù)制到快表中。(d) 根據(jù)前面得到的輔存地址和實(shí)存地址，啟動(dòng)I/O通道將所缺虛頁由輔存裝入主存。并更新內(nèi)頁表和快表的內(nèi)容。VA虛擬存儲(chǔ)器的工作過程圖解以一個(gè)多用戶、頁式管理的虛擬存儲(chǔ)器為例來講解虛擬存儲(chǔ)器的工作過程。 (c)如果內(nèi)頁表仍不命中，說明該頁尚未進(jìn)入主存，查外頁表，求得輔存實(shí)地址。同時(shí)查幀頁表，確定主存是否有空，如果有，則可得到主存實(shí)頁號(hào)；如果主存已滿，則由置換部件決定裝入地址。38第38頁，共43頁。3.8 存儲(chǔ)體系的層次結(jié)構(gòu) 多級(jí)存儲(chǔ)體系是為了解決存儲(chǔ)器容量、速度、價(jià)格之間的矛盾而引入的。 三級(jí)存儲(chǔ)