1、高速緩沖存儲器是存在于主存與CPUs間的一級存儲器，由靜態存儲芯片(SRAM殂成,容量比較小但速度比主存高得多，接近于CPU勺速度。Cache的功能是用來存放那些近期需要運行的指令與數據。目的是提高CPU寸存儲器的訪問速度。為此需要解決2個技術問題：一是主存地址與緩存地址的映象及轉換；二是按一定原則對Cache的內容進行替換。Cache的結構和工作原理如圖2.3.1所示。主要由三大部分組成:Cache存儲體：存放由主存調入的指令與數據塊。地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。替換部件：在緩存已滿時按一定策略進行數據塊替換，并修改地址轉換部件。2.3.2地址映象與轉換地址映象是

2、指某一數據在內存中的地址與在緩沖中的地址，兩者之間的對應關系。下面介紹三種地址映象的方式。1 .全相聯方式地址映象規則：主存的任意一塊可以映象到Cache中的任意一塊(1)主存與緩存分成相同大小的數據塊。(2)主存的某一數據塊可以裝入緩存的任意一塊空間中。全相聯方式的又力關系如圖2.3.2所示。如果Cache的塊數為C-主存的塊數為M-則映象關系共有1xMb種圖2.3-2全相聯噢象方式圖2.3.3示出了目錄表的格式及地址變換規則。目錄表存放在相關（聯）存儲器中，其中包括三部分：數據塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱裝入位）。由于是全相聯方式，因此，目錄表的容量應當與緩存的塊數

3、相同。塊號£塊內地址|主存地址1塊號b境內畫kwCachti地址命中；TB主存塊號以Cache塊號b狎敢付目錄表（由相聯存儲器構成，共備個字）®23.3全相豉地址轉換舉例：某機主存容量為1M,Cache的容量為32KB,每塊的大小為16個字（或字節）。劃出主、緩存的地址格式、目錄表格式及其容量。主存地址舞存地址容量：與緩沖塊數量相同即211=2048(或32Kz16=2048)優點：命中率比較高Cache存儲空間利用率高。目錄表缺點：訪問相關存儲器時，每次都要與全部內容比較，速度低，成本高，因而應用少。2.直接相聯方式地址映象規則：主存儲器中一塊只能映象到Cache的一個特

4、定的塊中。(1)主存與緩存分成相同大小的數據塊。(2)主存容量應是緩存容量的整數倍，將主存空間按緩存的容量分成區，主存中每一區的塊數與緩存的總塊數相等。(3)主存中某區的一塊存入緩存時只能存入緩存中塊號相同的位置。圖2.3.4示出了直接相聯映象規則。可見，主存中各區內相同塊號的數據塊都可以分別調入緩存中塊號相同的地址中，但同時只能有一個區的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調入塊的區號即可。塊7一1Cache，區0bE1塊2Cb-i塊Mb-CLU塊Mb-1總1塊”-c口塊CL至CJ1圖2.X4直接相聯映象方式圖2.3.5示出了主、緩沖地址格式、目錄表的格式及地址變換規則

5、。主、緩存塊號及塊內地址兩個字段完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數據塊在主存的區號和有效位。目錄表的容量與緩存的塊數相同區表存儲器圖215直接相康地址轉換地址變換過程：用主存地址中的塊號B去訪問目錄存儲器，把讀出來的區號與主存地址中的區號E進行比較，比較結果相等，有效位為1,則Cache命中，可以直接用塊號及塊內地址組成的緩沖地址到緩存中取數；比較結果不相等，有效位為1,可以進行替換，如果有效位為0,可以直接調入所需塊。優點：地址映象方式簡單，數據訪問時，只需檢查區號是否相等即可，因而可以得到比較快的訪問速度，硬件設備簡單。缺點：替換操作頻繁，命中率比較低。舉例：上例

6、中，主存容量為1M,Cache的容量為32KB,每塊的大小為16個字(或字節)。劃出主、緩存的地址格式、目錄表格式及其容量。15151443主存地址緩存地址目錄表區號區內塊號塊內地址14430器存塊號塊內地址510主存區號有敕位容量：與緩沖塊數量相同即211=2048(或32Kz16=2048)3.組相聯映象方式組相聯的映象規則：(1)主存和Cache按同樣大小劃分成塊。(2)主存和Cache按同樣大小劃分成組。(3)主存容量是緩存容量的整數倍，將主存空間按緩沖區的大小分成區，主存中每一區的組數與緩存的組數相同。(4)當主存的數據調入緩存時，主存與緩存的組號應相等，也就是各區中的某一塊只能存入

7、緩存的同組號的空間內，但組內各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個對應的組內部采用全相聯映象方式。主存儲器圖2.36蛆相聯地址映象區號E組號G組內塊號B塊內地址W|主存地址V1QQ出萬g組內塊號卜塊內地址WCache地址不等F相聯比較一相等1A-相聯比較（Gd個塊）區號E,組內坎號B組內塊號b塊表圖237組相聯映象的地址轉換圖2.3.6示出了組相聯的映象關系，圖中緩存共分Cg個組，每組包含有Gb塊；主存是緩存的Me倍，所以共分有Me個區,每個區有Cg組，每組有Gb塊。那么，主存地址格式中應包含4個字段：區號、區內組號、組內塊號和塊內地址。而緩存中包

8、含3個字段：組號、組內塊號、塊內地址。主存地址與緩存地址的轉換有兩部分，組地址是按直接映象方式，按地址進行訪問，而塊地址是采用全相聯方式，按內容訪問。組相聯的地址轉換部件也是采用相關存儲器實現，見圖2.3.7o相關存儲器中每個單元包含有：主存地址中的區號E與組內塊號B,兩者結合在一起，其對應的字段是緩存塊地址bo相關存儲器的容量，應與緩存的塊數相同。當進行數據訪問時，先根據組號，在目錄表中找到該組所包含的各塊的目錄，然后將被訪數據的主存區號與組內塊號，與本組內各塊的目錄同時進行比較。如果比較相等，而且有效位為“1則命中。可將其對應的緩存塊地址b送到緩存地址寄存器的塊地址字段，與組號及塊內地址組

9、裝即形成緩存地址。如果比較不相等，說明沒命中，所訪問的數據塊尚沒有進入緩存，則進行組內替換；如果有效位為0,則說明緩存的該塊尚未利用，或是原來數據作廢，可重新調入新塊。優點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。缺點：實現難度和造價要比直接映象方式高。2.3.3 替換策略根據程序局部性規律可知：程序在運行中，總是頻繁地使用那些最近被使用過的指令和數據。這就提供了替換策略的理論依據。綜合命中率、實現的難易及速度的快慢各種因素，替換策略可有隨機法、先進先出法、最近最少使用法等。.隨機法（RAND法）隨機法是隨機地確定替換的存儲塊。設置一個隨機數產生器，依據所產生的隨機數，確定

10、替換塊。這種方法簡單、易于實現，但命中率比較低。.先進先出法（FIFO法）先進先出法是選擇那個最先調入的那個塊進行替換。當最先調入并被多次命中的塊，很可能被優先替換，因而不符合局部性規律。這種方法的命中率比隨機法好些，但還不滿足要求。先進先出方法易于實現，例如Solar16/65機Cache采用組相聯方式，每組4塊，每塊都設定一個兩位的計數器，當某塊被裝入或被替換時該塊的計數器清為0,而同組的其它各塊的計數器均加1,當需要替換時就選擇計數值最大的塊被替換掉。.最近最少使用法（LRU法）LRU法是依據各塊使用的情況，總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規律。實現L

11、RU策略的方法有多種。下面簡單介紹計數器法、寄存器棧法及硬件邏輯比較對法的設計思路。計數器方法：緩存的每一塊都設置一個計數器，計數器的操作規則是：(1)被調入或者被替換的塊，其計數器清“0”，而其它的計數器則加“1”。(2)當訪問命中時，所有塊的計數值與命中塊的計數值要進行比較，如果計數值小于命中塊的計數值，則該塊的計數值加“1”;如果塊的計數值大于命中塊的計數值，則數值不變。最后將命中塊的計數器清為0。(3)需要替換時，則選擇計數值最大的塊被替換。例如舊M370/65機的Cache用組相聯方式，每組4塊，每一塊設置一個2位的計數器，其工作狀態如表2.3.1。表2.3.1計數器法實現LRU策略

12、主存塊地址塊4塊2塊3塊5塊號計數器塊毛;計數器塊號計數器塊號計數器Cache塊0110111111500Cache塊1301310300301Cache塊2400401410411Cache塊3空XX200201210操作起始狀態調入命中替換寄存器棧法：設置一個寄存器棧，其容量為Cache中替換時參與選擇的塊數。如在組相聯方式中，則是同組內的塊數。堆棧由棧頂到棧底依次記錄主存數據存入緩存的塊號，現以一組內4塊為例說明其工作情況，如表2.3.2所示，表中14為緩存中的一組的4個塊號。2.3.4 Cache的一致性問題Cache的內容是主存內容的一部分，是主存的副本，內容應該與主存一致。由于:CPU寫Cache,沒有立即寫主存；I/O處理機或I/O設備寫主存。從而造成Cache與主存內容的不一致，如圖2.3.8所示(a)CPU寫Cache(b)I/O寫主存圖工ISCache與主存不一致的兩種情況對Cac