高速緩存替換策略

『壹』 高速緩沖存儲器的組成結構

高速緩沖存儲器是存在於主存與CPU之間的一級存儲器， 由靜態存儲晶元(SRAM)組成，容量比較小但速度比主存高得多， 接近於CPU的速度。
主要由三大部分組成：
Cache存儲體：存放由主存調入的指令與數據塊。
地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。
替換部件：在緩存已滿時按一定策略進行數據塊替換，並修改地址轉換部件。

『貳』 什麼是Cachecache有什麼用說明cache的幾種替換策略

Cache是什麼
Cache是一種特殊的存儲器，它由Cache 存儲部件和Cache控制部件組成。Cache 存儲部件一般採用與CPU同類型的半導體存儲器件，存取速度比內存快幾倍甚至十幾倍。而Cache 控制器部件包括主存地址寄存器、Cache 地址寄存器，主存—Cache地址變換部件及替換控制部件等。至於它們各自又是怎樣工作的、有何作用等等，我想我們就沒有必要做進一步的研究，知道一般Cache分為L1 Cache(其中又分為數據Cache、代碼Cache)、L2 Cache就行了。
根據程序局部性規律可知：程序在運行中，總是頻繁地使用那些最近被使用過的指令和數據。這就提供了替換策略的理論依據。綜合命中率、實現的難易及速度的快慢各種因素，替換策略可有隨機法、先進先出法、最近最少使用法等。

1.隨機法（RAND法）

隨機法是隨機地確定替換的存儲塊。設置一個隨機數產生器，依據所產生的隨機數，確定替換塊。這種方法簡單、易於實現，但命中率比較低。

2.先進先出法（FIFO法）

先進先出法是選擇那個最先調入的那個塊進行替換。當最先調入並被多次命中的塊，很可能被優先替換，因而不符合局部性規律。這種方法的命中率比隨機法好些，但還不滿足要求。先進先出方法易於實現，例如Solar－16/65機Cache採用組相聯方式，每組4塊，每塊都設定一個兩位的計數器，當某塊被裝入或被替換時該塊的計數器清為0，而同組的其它各塊的計數器均加1，當需要替換時就選擇計數值最大的塊被替換掉。

3.最近最少使用法（LRU法）

LRU法是依據各塊使用的情況， 總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規律。
實現LRU策略的方法有多種。 下面簡單介紹計數器法、寄存器棧法及硬體邏輯比較對法的設計思路。
計數器方法：緩存的每一塊都設置一個計數器，計數器的操作規則是：
(1) 被調入或者被替換的塊， 其計數器清「0」，而其它的計數器則加「1」。
(2) 當訪問命中時，所有塊的計數值與命中塊的計數值要進行比較，如果計數值小於命中塊的計數值，則該塊的計數值加「1」；如果塊的計數值大於命中塊的計數值，則數值不變。最後將命中塊的計數器清為0。
(3) 需要替換時，則選擇計數值最大的塊被替換。

『叄』 高速緩沖存儲器的工作原理

高速緩沖存儲器通常由高速存儲器、聯想存儲器、替換邏輯電路和相應的控制線路組成。在有高速緩沖存儲器的計算機系統中，中央處理器存取主存儲器的地址劃分為行號、列號和組內地址三個欄位。於是，主存儲器就在邏輯上劃分為若干行；每行劃分為若乾的存儲單元組；每組包含幾個或幾十個字。高速存儲器也相應地劃分為行和列的存儲單元組。二者的列數相同，組的大小也相同，但高速存儲器的行數卻比主存儲器的行數少得多。
聯想存儲器用於地址聯想，有與高速存儲器相同行數和列數的存儲單元。當主存儲器某一列某一行存儲單元組調入高速存儲器同一列某一空著的存儲單元組時，與聯想存儲器對應位置的存儲單元就記錄調入的存儲單元組在主存儲器中的行號。
當中央處理器存取主存儲器時，硬體首先自動對存取地址的列號欄位進行解碼，以便將聯想存儲器該列的全部行號與存取主存儲器地址的行號欄位進行比較：若有相同的，表明要存取的主存儲器單元已在高速存儲器中，稱為命中，硬體就將存取主存儲器的地址映射為高速存儲器的地址並執行存取操作；若都不相同，表明該單元不在高速存儲器中，稱為脫靶，硬體將執行存取主存儲器操作並自動將該單元所在的那一主存儲器單元組調入高速存儲器相同列中空著的存儲單元組中，同時將該組在主存儲器中的行號存入聯想存儲器對應位置的單元內。
當出現脫靶而高速存儲器對應列中沒有空的位置時，便淘汰該列中的某一組以騰出位置存放新調入的組，這稱為替換。確定替換的規則叫替換演算法，常用的替換演算法有:最近最少使用演算法（LRU）、先進先出法（FIFO）和隨機法（RAND）等。替換邏輯電路就是執行這個功能的。另外，當執行寫主存儲器操作時，為保持主存儲器和高速存儲器內容的一致性，對命中和脫靶須分別處理。
主-輔存存儲層次 由於計算機主存容量相對於程序員所需要的容量來說總是太小，程序與數據從輔存調入主存是由程序員自己安排的，程序員必須花費很大精力和時間把大程序預先分成塊，確定好這些程序塊在輔存中的位置和裝入主存的地址，而且還要預先安排好程序運行時各塊如何和何時調入調出，因此存在存儲空間的分配問題。操作系統的形成和發展使得程序員盡可能擺脫主、輔存之間的地址定位，同時形成了支持這些功能的「輔助硬體」，通過軟體、硬體的結合，把主存和輔存統一成了一個整體，如圖所示。這時，由主存、輔存形成了一個存儲層次，即存儲系統。從整體看，其速度接近於主存的速度，其容量則接近於輔存的容量，而每位的平均價格也接近於廉價的慢速的輔存平均價格。這種系統不斷發展和完善，就逐步形成了現在廣泛使用的虛擬存儲系統。在系統中，應用程序員可用機器指令地址碼對整個程序統一編址，如同程序員具有對應這個地址碼寬度的全部虛存空間一樣。該空間可以比主存實際空間大得多，以致可以存得下整個程序。這種指令地址碼稱為虛地址（虛存地址、虛擬地址）或邏輯地址，其對應的存儲容量稱為虛存容量或虛存空間；而把實際主存的地址稱為物理地址、實（存）地址，其對應的存儲容量稱為主存容量、實存容量或實（主）存空間
主-輔存存儲層次 地址映象是指某一數據在內存中的地址與在緩沖中的地址，兩者之間的對應關系。下面介紹三種地址映象的方式。
1.全相聯方式
地址映象規則：主存的任意一塊可以映象到Cache中的任意一塊
(1) 主存與緩存分成相同大小的數據塊。
(2) 主存的某一數據塊可以裝入緩存的任意一塊空間中。如果Cache的塊數為Cb，主存的塊數為Mb，則映象關系共有Cb×Mb種。
目錄表存放在相關（聯）存儲器中，其中包括三部分：數據塊在主存的塊地址、存入緩存後的塊地址、及有效位（也稱裝入位）。由於是全相聯方式，因此，目錄表的容量應當與緩存的塊數相同。
優點：命中率比較高，Cache存儲空間利用率高。
缺點：訪問相關存儲器時，每次都要與全部內容比較，速度低，成本高，因而應用少。
2.直接相聯方式
地址映象規則： 主存儲器中一塊只能映象到Cache的一個特定的塊中。
(1) 主存與緩存分成相同大小的數據塊。
(2) 主存容量應是緩存容量的整數倍，將主存空間按緩存的容量分成區，主存中每一區的塊數與緩存的總塊數相等。
(3) 主存中某區的一塊存入緩存時只能存入緩存中塊號相同的位置。
主存中各區內相同塊號的數據塊都可以分別調入緩存中塊號相同的地址中，但同時只能有一個區的塊存入緩存。由於主、緩存塊號相同，因此，目錄登記時，只記錄調入塊的區號即可。主、緩存塊號及塊內地址兩個欄位完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數據塊在主存的區號和有效位。目錄表的容量與緩存的塊數相同。
優點：地址映象方式簡單，數據訪問時，只需檢查區號是否相等即可，因而可以得到比較快的訪問速度，硬體設備簡單。
缺點：替換操作頻繁，命中率比較低。
3.組相聯映象方式
組相聯的映象規則：
(1) 主存和Cache按同樣大小劃分成塊。
(2) 主存和Cache按同樣大小劃分成組。
(3) 主存容量是緩存容量的整數倍，將主存空間按緩沖區的大小分成區，主存中每一區的組數與緩存的組數相同。
(4) 當主存的數據調入緩存時，主存與緩存的組號應相等，也就是各區中的某一塊只能存入緩存的同組號的空間內，但組內各塊地址之間則可以任意存放，即從主存的組到Cache的組之間採用直接映象方式；在兩個對應的組內部採用全相聯映象方式。
主存地址與緩存地址的轉換有兩部分，組地址是按直接映象方式，按地址進行訪問，而塊地址是採用全相聯方式，按內容訪問。組相聯的地址轉換部件也是採用相關存儲器實現。
優點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。
缺點：實現難度和造價要比直接映象方式高。 1. 根據程序局部性規律可知：程序在運行中，總是頻繁地使用那些最近被使用過的指令和數據。這就提供了替換策略的理論依據。綜合命中率、實現的難易及速度的快慢各種因素，替換策略可有隨機法、先進先出法、最近最少使用法等。
（1）.隨機法（RAND法）
隨機法是隨機地確定替換的存儲塊。設置一個隨機數產生器，依據所產生的隨機數，確定替換塊。這種方法簡單、易於實現，但命中率比較低。
（2）.先進先出法（FIFO法）
先進先出法是選擇那個最先調入的那個塊進行替換。當最先調入並被多次命中的塊，很可能被優先替換，因而不符合局部性規律。這種方法的命中率比隨機法好些，但還不滿足要求。先進先出方法易於實現，
（3）.最近最少使用法（LRU法）
LRU法是依據各塊使用的情況， 總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規律。 實現LRU策略的方法有多種。
2 在多體並行存儲系統中，由於 I/O 設備向主存請求的級別高於 CPU 訪存，這就出現了 CPU 等待 I/O 設備訪存的現象，致使 CPU 空等一段時間，甚至可能等待幾個主存周期，從而降低了 CPU 的工作效率。為了避免 CPU 與 I/O 設備爭搶訪存，可在 CPU 與主存之間加一級緩存，這樣，主存可將 CPU 要取的信息提前送至緩存，一旦主存在與 I/O 設備交換時， CPU 可直接從緩存中讀取所需信息，不必空等而影響效率。
3 目前提出的演算法可以分為以下三類（第一類是重點要掌握的）：
（1）傳統替換演算法及其直接演化，其代表演算法有 ：①LRU（ Least Recently Used）演算法：將最近最少使用的內容替換出Cache ；②LFU（ Lease Frequently Used）演算法：將訪問次數最少的內容替換出Cache；③如果Cache中所有內容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU演算法進行替換 。④FIFO( First In First Out)：遵循先入先出原則，若當前Cache被填滿，則替換最早進入Cache的那個。
（2）基於緩存內容關鍵特徵的替換演算法，其代表演算法有：①Size替換演算法：將最大的內容替換出Cache②LRU— MIN替換演算法：該演算法力圖使被替換的文檔個數最少。設待緩存文檔的大小為S，對Cache中緩存的大小至少是S的文檔，根據LRU演算法進行替換；如果沒有大小至少為S的對象，則從大小至少為S/2的文檔中按照LRU演算法進行替換；③LRU—Threshold替換演算法：和LRU演算法一致，只是大小超過一定閾值的文檔不能被緩存；④Lowest Lacency First替換演算法：將訪問延遲最小的文檔替換出Cache。
（3）基於代價的替換演算法，該類演算法使用一個代價函數對Cache中的對象進行評估，最後根據代價值的大小決定替換對象。其代表演算法有：①Hybrid演算法：演算法對Cache中的每一個對象賦予一個效用函數，將效用最小的對象替換出Cache；②Lowest Relative Value演算法：將效用值最低的對象替換出Cache；③Least Normalized Cost Replacement（LCNR）演算法：該演算法使用一個關於文檔訪問頻次、傳輸時間和大小的推理函數來確定替換文檔；④Bolot等人 提出了一種基於文檔傳輸時間代價、大小、和上次訪問時間的權重推理函數來確定文檔替換；⑤Size—Adjust LRU（SLRU）演算法：對緩存的對象按代價與大小的比率進行排序，並選取比率最小的對象進行替換。

『肆』 計算機中為什麼要採用高速緩存器(CACHE)

是為了解決低速的外設和高速的CPU之間速度不匹配的問題。

主要由三大部分組成：

1、Cache存儲體：存放由主存調入的指令與數據塊。

2、地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。

3、替換部件：在緩存已滿時按一定策略進行數據塊替換，並修改地址轉換部件。

在有高速緩沖存儲器的計算機系統中，中央處理器存取主存儲器的地址劃分為行號、列號和組內地址三個欄位。

於是，主存儲器就在邏輯上劃分為若干行；每行劃分為若乾的存儲單元組；每組包含幾個或幾十個字。高速存儲器也相應地劃分為行和列的存儲單元組。二者的列數相同，組的大小也相同，但高速存儲器的行數卻比主存儲器的行數少得多。

(4)高速緩存替換策略擴展閱讀

當中央處理器存取主存儲器時，高速緩存器首先自動對存取地址的列號欄位進行解碼，以便將聯想存儲器該列的全部行號與存取主存儲器地址的行號欄位進行比較：若有相同的，表明要存取的主存儲器單元已在高速存儲器中，稱為命中，硬體就將存取主存儲器的地址映射為高速存儲器的地址並執行存取操作。

若都不相同，表明該單元不在高速存儲器中，稱為脫靶，硬體將執行存取主存儲器操作並自動將該單元所在的那一主存儲器單元組調入高速存儲器相同列中空著的存儲單元組中，同時將該組在主存儲器中的行號存入聯想存儲器對應位置的單元內。

當出現脫靶而高速存儲器對應列中沒有空的位置時，便淘汰該列中的某一組以騰出位置存放新調入的組，這稱為替換。確定替換的規則叫替換演算法，常用的替換演算法有:最近最少使用演算法（LRU）、先進先出法（FIFO）和隨機法（RAND）等。

替換邏輯電路就是執行這個功能的。另外，當執行寫主存儲器操作時，為保持主存儲器和高速存儲器內容的一致性，對命中和脫靶須分別處理。

『伍』 高速緩沖存儲器的作用是什麼

高速緩沖存儲器的容量一般只有主存儲器的幾百分之一，但它的存取速度能與中央處理器相匹配。

根據程序局部性原理，正在使用的主存儲器某一單元鄰近的那些單元將被用到的可能性很大。因而，當中央處理器存取主存儲器某一單元時，計算機硬體就自動地將包括該單元在內的那一組單元內容調入高速緩沖存儲器，中央處理器即將存取的主存儲器單元很可能就在剛剛調入到高速緩沖存儲器的那一組單元內。

所以中央處理器就可以直接對高速緩沖存儲器進行存取。在整個處理過程中，如果中央處理器絕大多數存取主存儲器的操作能為存取高速緩沖存儲器所代替，計算機系統處理速度就能顯著提高。

(5)高速緩存替換策略擴展閱讀：

提高高速緩沖存儲器讀取命中率的演算法：

1、隨機法：隨機替換演算法就是用隨機數發生器產生一個要替換的塊號，將該塊替換出去，此演算法簡單、易於實現，而且它不考慮Cache塊過去、現在及將來的使用情況，但是沒有利用上層存儲器使用的「歷史信息」、沒有根據訪存的局部性原理。

2、先進先出法：先進先出演算法就是將最先進入Cache的信息塊替換出去。FIFO演算法按調入Cache的先後決定淘汰的順序，選擇最早調入Cache的字塊進行替換，它不需要記錄各字塊的使用情況，比較容易實現，系統開銷小。

3、近期最少使用法：近期最少使用（Least Recently Used，LRU）演算法。這種方法是將近期最少使用的Cache中的信息塊替換出去。該演算法較先進先出演算法要好一些。但此法也不能保證過去不常用將來也不常用。

『陸』 計算機內，配置高速緩沖存儲器（CACHE）是為了解決什麼

B，CPU與內存儲器之間速度不匹配問題。

高速緩沖存儲器（Cache）其原始意義是指存取速度比一般隨機存取記憶體（RAM）來得快的一種RAM，一般而言它不像系統主記憶體那樣使用DRAM技術，而使用昂貴但較快速的SRAM技術，也有快取記憶體的名稱。

高速緩沖存儲器是存在於主存與CPU之間的一級存儲器， 由靜態存儲晶元(SRAM)組成，容量比較小但速度比主存高得多， 接近於CPU的速度。在計算機存儲系統的層次結構中，是介於中央處理器和主存儲器之間的高速小容量存儲器。它和主存儲器一起構成一級的存儲器。高速緩沖存儲器和主存儲器之間信息的調度和傳送是由硬體自動進行的。

(6)高速緩存替換策略擴展閱讀：

高速緩沖存儲器組成結構

高速緩沖存儲器是存在於主存與CPU之間的一級存儲器， 由靜態存儲晶元(SRAM)組成，容量比較小但速度比主存高得多， 接近於CPU的速度。

主要由三大部分組成：

1、Cache存儲體：存放由主存調入的指令與數據塊。

2、地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。

3、替換部件：在緩存已滿時按一定策略進行數據塊替換，並修改地址轉換部件。

『柒』 在主存和CPU之間增加cache的目的是_______。

解決CPU與內存之間的速度匹配問題。cache是電腦中的高速緩沖存儲器，其主要工作原理是保存CPU剛用過或循環使用的一部分數據。如果CPU需要再次使用該部分數據時可從Cache中直接調用，這樣就避免了重復存取數據，減少了CPU的等待時間，因而提高了系統的效率。

Cache容量小但速度快，通過優化調度演算法，系統的性能會大大改善，彷彿其存儲系統容量與內存相當而訪問速度近似Cache。Cache一般可以分為L1Cache（一級緩存）和L2Cache（二級緩存），L1Cache主要是集成在CPU內部，L2Cache集成在主板上或是CPU上。

(7)高速緩存替換策略擴展閱讀：

cache的組成結構：

1、Cache存儲體：存放由主存調入的指令與數據塊。

2、地址轉換部件：建立目錄表以實現主存地址到緩存地址的轉換。

3、替換部件：在緩存已滿時按一定策略進行數據塊替換，並修改地址轉換部件。

cache命中率演算法：

1、隨機法，用隨機數發生器產生一個要替換的塊號，將該塊替換出去，此演算法簡單、易於實現，而且它不考慮Cache塊過去、現在及將來的使用情況，但是沒有利用上層存儲器使用的「歷史信息」、沒有根據訪存的局部性原理，故不能提高Cache的命中率，命中率較低。

2、先進先出法，將最先進入Cache的信息塊替換出去。FIFO演算法按調入Cache的先後決定淘汰的順序，選擇最早調入Cache的字塊進行替換。

3、近期最少使用法，將近期最少使用的Cache中的信息塊替換出去。該演算法較先進先出演算法要好一些。但此法也不能保證過去不常用將來也不常用。

『捌』 急！！！cache和虛擬存儲器在原理和功能上有什麼相同和不同。

正確答案：

相同處是都利用了程序局部性原理，把程序劃分為許多信息塊，運行時能自動地把信息塊從慢速存儲器向快速存儲器調度，信息塊調度都採用一定的替換策略以提高繼續運行時的命中率。它們採用的地址變換、地址映象方式和替換演算法是相同的。

不同處是CACHE用於彌補主存與CPU之間的速度差異，而虛存用於彌補主存容量的不足；CACHE每次傳送的信息塊是定長的，只有幾十個位元組。虛存的信息塊可定長（頁）的，也可是不定長的（段），長度也比較大；CPU可直接訪問CACHE，但不能直接訪問輔存；CACHE的信息交換過程全由硬體實現，主輔存間的信息交換則通過輔助硬體與存儲管理軟體來完成。

2、答：一次重疊把一條指令解釋的過程分解成兩個過程，而流水則把指令的解釋分解為更多的過程；一次重疊可同時解釋兩條指令，而流水則可解釋多條命令；一次重疊是流水的特徵。

3、答：由三部分組成：（1）外部設備：是圍繞主機而設置的各種信息媒體轉換的傳遞的設備。（2）設備控制器與介面：控制主機與外部設備之間的信息格式轉換、交換過程及外部設備運行狀態的硬、軟體，也叫設備適配器，它與外部設備的特性有關。（3）I/O匯流排：是主機與外部設備之間的信息傳送通路。

從使用角度，可分成人-機交互設備，如鍵盤、列印機、顯示器等；機-機通信設備，如MODEM等；計算機信息的駐在設備，如磁碟、光碟、磁帶等。

『玖』 關於cache的一道題

解釋下為什麼會發編譯錯誤。由於PackagedClass和Foreign存在不同包中。而classPackagedClass並沒有聲明為public。Foreign又要引用PackagedClass，所以會發生編譯錯誤。解決方法是把classPackagedClass改成publicclassPackagedClass

『拾』 主存與cache有什麼區別

主存儲器一般指的是內存，cache指的是高速緩存，高速緩存內是CPU和內存之間交換的數據，內存裡面一般是CPU和硬碟之間的數據，由於硬碟的讀寫速度遠遠低於CPU的處理速度，所以要把數據預讀在內存里，另外，內存還存放著系統當前正在運行的數據。還有一種虛擬內存，是用於解決內存不足的問題而產生的。