2.3 高速緩沖存儲器（Cache）2.3.1 高速緩沖存儲器的功能、結構與工作原理
高速緩沖存儲器是存在于主存與CPU之間的一級存儲器， 由靜態存儲芯片(SRAM)組成，容量比較小但速度比主存高得多， 接近于CPU的速度。 Cache的功能是用來存放那些近期需要運行的指令與數據。目的是提高CPU對存儲器的訪問速度。為此需要解決2個技術問題：一是主存地址與緩存地址的映象及轉換； 二是按一定原則對Cache的內容進行替換。
Cache的結構和工作原理如圖2.3.1所示。
主要由三大部分組成：
Cache存儲體：存放由主存調入的指令與數據塊。
地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。
替換部件：在緩存已滿時按一定策略進行數據塊替換，并修改地址轉換部件。地址映象是指某一數據在內存中的地址與在緩沖中的地址，兩者之間的對應關系。下面介紹三種地址映象的方式。
1.全相聯方式
地址映象規則：主存的任意一塊可以映象到Cache中的任意一塊
(1) 主存與緩存分成相同大小的數據塊。
(2) 主存的某一數據塊可以裝入緩存的任意一塊空間中。
全相聯方式的對應關系如圖2.3.2所示。如果Cache的塊數為Cb，主存的塊數為Mb，則映象關系共有Cb×Mb種。
圖2.3.3示出了目錄表的格式及地址變換規則。 目錄表存放在相關（聯）存儲器中，其中包括三部分：數據塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱裝入位）。由于是全相聯方式，因此，目錄表的容量應當與緩存的塊數相同。
舉例：某機主存容量為1M，Cache的容量為32KB， 每塊的大小為16個字（或字節）。 劃出主、緩存的地址格式、 目錄表格式及其容量。
容量：與緩沖塊數量相同即211＝2048（或32K/16＝2048）。 優點：命中率比較高，Cache存儲空間利用率高。
缺點：訪問相關存儲器時，每次都要與全部內容比較，速度低，成本高，因而應用少。2.直接相聯方式
地址映象規則： 主存儲器中一塊只能映象到Cache的一個特定的塊中。
(1) 主存與緩存分成相同大小的數據塊。
(2) 主存容量應是緩存容量的整數倍，將主存空間按緩存的容量分成區，主存中每一區的塊數與緩存的總塊數相等。
(3) 主存中某區的一塊存入緩存時只能存入緩存中塊號相同的位置。
圖2.3.4示出了直接相聯映象規則。 可見，主存中各區內相同塊號的數據塊都可以分別調入緩存中塊號相同的地址中，但同時只能有一個區的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調入塊的區號即可。
圖2.3.5示出了主、 緩沖地址格式、目錄表的格式及地址變換規則。主、緩存塊號及塊內地址兩個字段完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數據塊在主存的區號和有效位。目錄表的容量與緩存的塊數相同。
地址變換過程：用主存地址中的塊號B去訪問目錄存儲器， 把讀出來的區號與主存地址中的區號E進行比較， 比較結果相等，有效位為1，則Cache命中，可以直接用塊號及塊內地址組成的緩沖地址到緩存中取數；比較結果不相等，有效位為1， 可以進行替換，如果有效位為0，可以直接調入所需塊。
優點：地址映象方式簡單，數據訪問時，只需檢查區號是否相等即可，因而可以得到比較快的訪問速度，硬件設備簡單。
缺點：替換操作頻繁，命中率比較低。
舉例：上例中，主存容量為1M， Cache的容量為32KB，每塊的大小為16個字（或字節）。劃出主、緩存的地址格式、目錄表格式及其容量。
容量：與緩沖塊數量相同即211＝2048（或32K/16＝2048）。3.組相聯映象方式
組相聯的映象規則：
(1) 主存和Cache按同樣大小劃分成塊。
(2) 主存和Cache按同樣大小劃分成組。
(3) 主存容量是緩存容量的整數倍，將主存空間按緩沖區的大小分成區，主存中每一區的組數與緩存的組數相同。
(4) 當主存的數據調入緩存時，主存與緩存的組號應相等，也就是各區中的某一塊只能存入緩存的同組號的空間內，但組內各塊地址之間則可以任意存放， 即從主存的組到Cache的組之間采用直接映象方式；在兩個對應的組內部采用全相聯映象方式。
圖2.3.6示出了組相聯的映象關系， 圖中緩存共分Cg個組，每組包含有Gb塊； 主存是緩存的Me倍，所以共分有Me個區， 每個區有Cg組，每組有Gb塊。那么， 主存地址格式中應包含4個字段：區號、區內組號、組內塊號和塊內地址。 而緩存中包含3個字段：組號、組內塊號、塊內地址。主存地址與緩存地址的轉換有兩部分，組地址是按直接映象方式，按地址進行訪問，而塊地址是采用全相聯方式，按內容訪問。組相聯的地址轉換部件也是采用相關存儲器實現，見圖2.3.7。
相關存儲器中每個單元包含有： 主存地址中的區號E與組內塊號B，兩者結合在一起，其對應的字段是緩存塊地址b。相關存儲器的容量，應與緩存的塊數相同。當進行數據訪問時，先根據組號，在目錄表中找到該組所包含的各塊的目錄，然后將被訪數據的主存區號與組內塊號，與本組內各塊的目錄同時進行比較。如果比較相等，而且有效位為“1”則命中。
可將其對應的緩存塊地址b送到緩存地址寄存器的塊地址字段，與組號及塊內地址組裝即形成緩存地址。如果比較不相等，說明沒命中，所訪問的數據塊尚沒有進入緩存，則進行組內替換；如果有效位為0，則說明緩存的該塊尚未利用， 或是原來數據作廢，可重新調入新塊。
優點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。
缺點：實現難度和造價要比直接映象方式高。根據程序局部性規律可知：程序在運行中，總是頻繁地使用那些最近被使用過的指令和數據。這就提供了替換策略的理論依據。綜合命中率、實現的難易及速度的快慢各種因素，替換策略可有隨機法、先進先出法、最近最少使用法等。
1.隨機法（RAND法）
隨機法是隨機地確定替換的存儲塊。設置一個隨機數產生器，依據所產生的隨機數，確定替換塊。這種方法簡單、易于實現，但命中率比較低。
2.先進先出法（FIFO法）
先進先出法是選擇那個最先調入的那個塊進行替換。當最先調入并被多次命中的塊，很可能被優先替換，因而不符合局部性規律。這種方法的命中率比隨機法好些，但還不滿足要求。先進先出方法易于實現，例如Solar－16/65機Cache采用組相聯方式，每組4塊，每塊都設定一個兩位的計數器，當某塊被裝入或被替換時該塊的計數器清為0，而同組的其它各塊的計數器均加1，當需要替換時就選擇計數值最大的塊被替換掉。
3.最近最少使用法（LRU法）
LRU法是依據各塊使用的情況， 總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規律。
實現LRU策略的方法有多種。 下面簡單介紹計數器法、寄存器棧法及硬件邏輯比較對法的設計思路。
計數器方法：緩存的每一塊都設置一個計數器，計數器的操作規則是：
(1) 被調入或者被替換的塊， 其計數器清“0”，而其它的計數器則加“1”。
(2) 當訪問命中時，所有塊的計數值與命中塊的計數值要進行比較，如果計數值小于命中塊的計數值， 則該塊的計數值加“1”；如果塊的計數值大于命中塊的計數值，則數值不變。最后將命中塊的計數器清為0。
(3) 需要替換時，則選擇計數值最大的塊被替換。
例如IBM 370/65機的Cache用組相聯方式，每組4塊，每一塊設置一個2位的計數器，其工作狀態如表2.3.1。表2.3.1 計數器法實現LRU策略
寄存器棧法：設置一個寄存器棧， 其容量為Cache中替換時參與選擇的塊數。如在組相聯方式中，則是同組內的塊數。堆棧由棧頂到棧底依次記錄主存數據存入緩存的塊號， 現以一組內4塊為例說明其工作情況，如表2.3.2所示，表中1～4為緩存中的一組的4個塊號。
表2.3.2 寄存器棧法實現
(1) 當緩存中尚有空閑時，如果不命中，則可直接調入數據塊，并將新訪問的緩沖塊號壓入堆棧，位于棧頂。其他棧內各單元依次由頂向下順壓一個單元，直到空閑單元為止。
(2) 當緩存已滿，如果數據訪問命中，則將訪問的緩存塊號壓入堆棧，其他各單元內容由頂向底逐次下壓直到被命中塊號的原來位置為止。如果訪問不命中，說明需要替換，此時棧底單元中的塊號即是最久沒有被使用的。所以將新訪問塊號壓入堆棧，棧內各單元內容依次下壓直到棧底，自然，棧底所指出的塊被替換。
比較對法：比較對法是用一組硬件的邏輯電路來記錄各塊使用的時間與次數。
假設Cache的每組中有4塊， 替換時，是比較4塊中那一塊是最久沒使用的，4塊之間兩兩相比可以有6種比較關系。如果每兩塊之間的對比關系用一個RS觸發器，則需要6個觸發器（T12，T13，T14，T23，T24，T34）， 設T12＝0表示塊1比塊2最久沒使用，T12＝1表示塊2比塊1最久沒有被使用。 在每次訪問命中或者新調入塊時，與該塊有關的觸發器的狀態都要進行修改。 按此原理，由6個觸發器組成的一組編碼狀態可以指出應被替換的塊。例如，塊1被替換的條件是：T12＝0，T13＝0，T14＝0；塊2被替換的條件是：T12＝1，T23＝0，T24＝0等等。Cache的內容是主存內容的一部分， 是主存的副本，內容應該與主存一致。由于：
(1) CPU寫Cache，沒有立即寫主存；
(2) I/O處理機或I/O設備寫主存。
從而造成Cache與主存內容的不一致，如圖2.3.8所示。
對Cache進行寫操作時引起的不一致的解決方法：
1.全寫法亦稱寫直達法（WT法-Write through）
方法：在對Cache進行寫操作的同時，也對主存該內容進行寫入。
優點：可靠性較高，操作過程比較簡單。
缺點：寫操作速度得不到改善，與寫主存的速度相同。2.寫回法（WB法-Write back）
方法：在CPU執行寫操作時，只寫入Cache，不寫入主存。
優點：速度較高。
缺點：可靠性較差，控制操作比較復雜。1.Cache系統的加速比
存儲系統采用Cache技術的主要目的是提高存儲器的訪問速度，加速比是其重要的性能參數。Cache存儲系統的加速比SP（Speedup）為：
其中：Tm為主存儲器的訪問周期，Tc為Cache的訪問周期，T則為Cache存儲系統的等效訪問周期，H為命中率。
可以看出，加速比的大小與兩個因素有關：命中率H及Cache與主存訪問周期的比值Tc/Tm，命中率越高加速比越大。圖2.3.9示出了加速比與命中率的關系。
2.Cache的命中率
影響Cache命中率的因素很多，如Cache的容量，塊的大小，映象方式，替換策略以及程序執行中地址流的分布情況等等。一般地說，Cache容量越大則命中率越高， 當容量達到一定程度后，容量的增加命中率的改善并不大；Cache塊容量加大， 命中率也明顯增加，但增加到一定值之后反而出現命中率下降的現象；直接映象法命中率比較低，全相聯方式命中率比較高，在組相聯方式中，組數分得越多，則命中率下降。
轉載于:https://www.cnblogs.com/freebye/archive/2005/04/08/133699.html
![linux面試題中的簡答題,[計算機]linux面試題簡答題部分.doc](http://pic.xiahunao.cn/linux面試題中的簡答題,[計算機]linux面試題簡答題部分.doc)
