Cache的作用及替換策略

在計(jì)算機(jī)技術(shù)發(fā)展過(guò)程中,主存儲(chǔ)器存取速度一直比中央處理器操作速度慢得多，使中央處理器的高速處理能力不能充分發(fā)揮，整個(gè)計(jì)算機(jī)系統(tǒng)的工作效率受到影響。有很多方法可用來(lái)緩和中央處理器和主存儲(chǔ)器之間速度不匹配的矛盾，如采用多個(gè)通用寄存器、多存儲(chǔ)體交叉存取等，在存儲(chǔ)層次上采用高速緩沖存儲(chǔ)器也是常用的方法之一。

很多大、中型計(jì)算機(jī)以及新近的一些小型機(jī)、微型機(jī)也都采用高速緩沖存儲(chǔ)器。高速緩沖存儲(chǔ)器的容量一般只有主存儲(chǔ)器的幾百分之一，但它的存取速度能與中央處理器相匹配。根據(jù)程序局部性原理，正在使用的主存儲(chǔ)器某一單元鄰近的那些單元將被用到的可能性很大。因而，當(dāng)中央處理器存取主存儲(chǔ)器某一單元時(shí)，計(jì)算機(jī)硬件就自動(dòng)地將包括該單元在內(nèi)的那一組單元內(nèi)容調(diào)入高速緩沖存儲(chǔ)器，中央處理器即將存取的主存儲(chǔ)器單元很可能就在剛剛調(diào)入到高速緩沖存儲(chǔ)器的那一組單元內(nèi)。于是，中央處理器就可以直接對(duì)高速緩沖存儲(chǔ)器進(jìn)行存取。在整個(gè)處理過(guò)程中，如果中央處理器絕大多數(shù)存取主存儲(chǔ)器的操作能為存取高速緩沖存儲(chǔ)器所代替，計(jì)算機(jī)系統(tǒng)處理速度就能顯著提高。

1. 根據(jù)程序局部性規(guī)律可知：程序在運(yùn)行中，總是頻繁地使用那些最近被使用過(guò)的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。綜合命中率、實(shí)現(xiàn)的難易及速度的快慢各種因素，替換策略可有隨機(jī)法、先進(jìn)先出法、最近最少使用法等。

(1).隨機(jī)法(RAND法)隨機(jī)法是隨機(jī)地確定替換的存儲(chǔ)塊。設(shè)置一個(gè)隨機(jī)數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機(jī)數(shù)，確定替換塊。這種方法簡(jiǎn)單、易于實(shí)現(xiàn)，但命中率比較低。(2).先進(jìn)先出法(FIFO法)先進(jìn)先出法是選擇那個(gè)最先調(diào)入的那個(gè)塊進(jìn)行替換。當(dāng)最先調(diào)入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機(jī)法好些，但還不滿(mǎn)足要求。先進(jìn)先出方法易于實(shí)現(xiàn)，(3).最近最少使用法(LRU法)LRU法是依據(jù)各塊使用的情況， 總是選擇那個(gè)最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規(guī)律。 實(shí)現(xiàn)LRU策略的方法有多種。

2 在多體并行存儲(chǔ)系統(tǒng)中，由于 I/O 設(shè)備向主存請(qǐng)求的級(jí)別高于 CPU 訪(fǎng)存，這就出現(xiàn)了 CPU 等待 I/O 設(shè)備訪(fǎng)存的現(xiàn)象，致使 CPU 空等一段時(shí)間，甚至可能等待幾個(gè)主存周期，從而降低了 CPU 的工作效率。為了避免 CPU 與 I/O 設(shè)備爭(zhēng)搶訪(fǎng)存，可在 CPU 與主存之間加一級(jí)緩存，這樣，主存可將 CPU 要取的信息提前送至緩存，一旦主存在與 I/O 設(shè)備交換時(shí)， CPU 可直接從緩存中讀取所需信息，不必空等而影響效率。3 目前提出的算法可以分為以下三類(lèi)(第一類(lèi)是重點(diǎn)要掌握的)：(1)傳統(tǒng)替換算法及其直接演化，其代表算法有 ：①LRU( Least Recently Used)算法：將最近最少使用的內(nèi)容替換出Cache ;②LFU( Lease Frequently Used)算法：將訪(fǎng)問(wèn)次數(shù)最少的內(nèi)容替換出Cache;③如果Cache中所有內(nèi)容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU算法進(jìn)行替換 。④FIFO( First In First Out)：遵循先入先出原則，若當(dāng)前Cache被填滿(mǎn)，則替換最早進(jìn)入Cache的那個(gè)。(2)基于緩存內(nèi)容關(guān)鍵特征的替換算法，其代表算法有：①Size替換算法：將最大的內(nèi)容替換出Cache②LRU— MIN替換算法：該算法力圖使被替換的文檔個(gè)數(shù)最少。設(shè)待緩存文檔的大小為S，對(duì)Cache中緩存的大小至少是S的文檔，根據(jù)LRU算法進(jìn)行替換;如果沒(méi)有大小至少為S的對(duì)象，則從大小至少為S/2的文檔中按照LRU算法進(jìn)行替換;③LRU—Threshold替換算法：和LRU算法一致，只是大小超過(guò)一定閾值的文檔不能被緩存;④Lowest Lacency First替換算法：將訪(fǎng)問(wèn)延遲最小的文檔替換出Cache。(3)基于代價(jià)的替換算法，該類(lèi)算法使用一個(gè)代價(jià)函數(shù)對(duì)Cache中的對(duì)象進(jìn)行評(píng)估，最后根據(jù)代價(jià)值的大小決定替換對(duì)象。其代表算法有：①Hybrid算法：算法對(duì)Cache中的每一個(gè)對(duì)象賦予一個(gè)效用函數(shù)，將效用最小的對(duì)象替換出Cache;②Lowest Relative Value算法：將效用值最低的對(duì)象替換出Cache;③Least Normalized Cost Replacement(LCNR)算法：該算法使用一個(gè)關(guān)于文檔訪(fǎng)問(wèn)頻次、傳輸時(shí)間和大小的推理函數(shù)來(lái)確定替換文檔;④Bolot等人 提出了一種基于文檔傳輸時(shí)間代價(jià)、大小、和上次訪(fǎng)問(wèn)時(shí)間的權(quán)重推理函數(shù)來(lái)確定文檔替換;⑤Size—Adjust LRU(SLRU)算法：對(duì)緩存的對(duì)象按代價(jià)與大小的比率進(jìn)行排序，并選取比率最小的對(duì)象進(jìn)行替換。