CPU在一段較短的時間內(nèi)涧衙，是對連續(xù)地址的一段很小的主存空間頻繁地進(jìn)行訪問哪工，而對此范圍以外地址的訪問甚少，這種現(xiàn)象稱為程序訪問的局部性绍撞。
Cache技術(shù)就是利用程序訪問的局部性原理正勒，把程序中正在使用的部分（活躍塊）存放在一個小容量的高速Cache中，使CPU的訪存操作大多針對Cache進(jìn)行傻铣，從而解決高速CPU和低速主存之間速度不匹配的問題章贞，使程序的執(zhí)行速度大大提高。
Cache技術(shù)是為了解決CPU和主存之間速度不匹配而采用的一項重要技術(shù)。
CPU與Cache之間的數(shù)據(jù)交換是以字為單位的鸭限，而Cache與主存之間的數(shù)據(jù)交換則是以塊為單位的蜕径。一個塊由若干個定長字組成。
當(dāng)CPU讀取主存中的一個字時败京，該字的主存地址被發(fā)給Cache和主存兜喻，此時，Cache控制邏輯依據(jù)地址判斷該字當(dāng)前是否存在于Cache中：若在赡麦，該字立即被從Cache傳送給CPU朴皆；若不在，則用主存讀周期把該字從主存讀出送到CPU泛粹，同時把含有這個字的整個數(shù)據(jù)塊從主存讀出送到Cache中遂铡，并采用一定的替換策略將Cache中的某一塊替換掉，替換算法由Cache管理邏輯電路來實(shí)現(xiàn)晶姊。

Cache的命中率

Cache的工作效率通常用“命中率”來表示吼鳞。
命中率指的是CPU要訪問的信息在Cache中的概率挺益，Cache的命中率越高，CPU訪問主存的速度就越接近訪問Cache的速度。通常Cache的容量越大竭钝，存儲的塊也越多占遥，CPU的命中率就越高幼东。但是颖系，當(dāng)Cache的容量達(dá)到一定值時，命中率并不會隨著容量的增大而增加脆荷，而且Cache容量的增大將導(dǎo)致成本的增加凝垛，所以，Cache的容量一般是命中率與成本價格的折中蜓谋。
命中率h與程序的行為梦皮、Cache的容量、組織方式桃焕、塊的大小有關(guān)剑肯。

Cache的替換算法

Cache的容量很小，它保存的內(nèi)容只是主存內(nèi)容的一個子集观堂，且Cache與主存的數(shù)據(jù)交換是以塊為單位的让网。為了把信息放到Cache中，必須應(yīng)用某種函數(shù)把主存地址定位到Cache中师痕，這稱為地址映射溃睹。
Cache的地址映射方式有直接映射、全相聯(lián)映射和組相聯(lián)映射胰坟。
假設(shè)某臺計算機(jī)主存容量為l MB因篇，被分為2048塊，每塊512B；
Cache容量為8KB竞滓，被分為16塊咐吼，每塊也是512B。
下面以此為例介紹三種基本的地址映射方法商佑。

1. 直接映射

直接映射的Cache組織如圖所示锯茄。
主存中的一個塊只能映射到Cache的某一特定塊中去。例如茶没，主存的第0塊肌幽、第16塊、……礁叔、第2032塊牍颈，只能映射到Cache的第0塊；而主存的第1塊琅关、第17塊、……讥蔽、第2033塊涣易，只能映射到Cache的第1塊……。

327.gif

2. 全相聯(lián)映射

圖3-15 是全相聯(lián)映射的Cache組織惰拱，主存中任何一塊都可以映射到Cache中的任何一塊位置上雌贱。

328.gif

3. 組相聯(lián)映射

組相聯(lián)映射實(shí)際上是直接映射和全相聯(lián)映射的折中方案款票，其組織結(jié)構(gòu)如圖3-16所示。
主存和Cache都分組泽论，主存中一個組內(nèi)的塊數(shù)與Cache中的分組數(shù)相同艾少，組間采用直接映射，組內(nèi)采用全相聯(lián)映射翼悴。

也就是說缚够，將Cache分成u組，每組v塊鹦赎，主存塊存放到哪個組是固定的谍椅，至于存到該組哪一塊則是靈活的。例如古话，主存分為256組雏吭，每組8塊，Cache分為8組陪踩，每組2塊杖们。

329.gif

主存中的各塊與Cache的組號之間有固定的映射關(guān)系，但可自由映射到對應(yīng)Cache組中的任何一塊肩狂。例如摘完，主存中的第0塊、第8塊……均映射于Cache的第0組婚温，但可映射到Cache第0組中的第0塊或第1塊描焰；主存的第1塊、第9塊……均映射于Cache的第1組栅螟，但可映射到Cache第1組中的第2塊或第3塊荆秦。
常采用的組相聯(lián)結(jié)構(gòu)Cache，每組內(nèi)有2力图、4步绸、8、16塊吃媒，稱為2路瓤介、4路吕喘、8路、16路組相聯(lián)Cache刑桑。組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案氯质，適度兼顧二者的優(yōu)點(diǎn)，盡量避免二者的缺點(diǎn)祠斧，因而得到普遍采用闻察。

替換策略

Cache工作原理要求它盡量保存最新數(shù)據(jù)，當(dāng)從主存向Cache傳送一個新塊琢锋，而Cache中可用位置已被占滿時辕漂，就會產(chǎn)生Cache替換的問題。
替換問題與Cache的組織方式緊密相關(guān)：對直接映射Cache來說吴超，只要把此可用位置上的主存塊換出Cache即可钉嘹；對全相聯(lián)和組相聯(lián)Cache來說，要從若干個可用位置中選取一個位置鲸阻，把其中的主存塊換出Cache跋涣。

常用的替換算法有下面三種。

1. 最不經(jīng)常使用（LFU）算法

LFU（Least Frequently Used鸟悴，最不經(jīng)常使用）算法將一段時間內(nèi)被訪問次數(shù)最少的那個塊替換出去仆潮。每塊設(shè)置一個計數(shù)器，從0開始計數(shù)遣臼，每訪問一次，被訪塊的計數(shù)器就增1拾并。當(dāng)需要替換時揍堰，將計數(shù)值最小的塊換出，同時將所有塊的計數(shù)器都清零嗅义。
這種算法將計數(shù)周期限定在對這些特定塊兩次替換之間的間隔時間內(nèi)屏歹，不能嚴(yán)格反映近期訪問情況，新調(diào)入的塊很容易被替換出去之碗。

2. 近期最少使用（LRU）算法

LRU（Least Recently Used蝙眶，近期最少使用）算法是把CPU近期最少使用的塊替換出去。這種替換方法需要隨時記錄Cache中各塊的使用情況褪那，以便確定哪個塊是近期最少使用的塊幽纷。每塊也設(shè)置一個計數(shù)器，Cache每命中一次博敬，命中塊計數(shù)器清零友浸，其他各塊計數(shù)器增1。當(dāng)需要替換時偏窝，將計數(shù)值最大的塊換出收恢。
LRU算法相對合理武学，但實(shí)現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大伦意。這種算法保護(hù)了剛調(diào)入Cache的新數(shù)據(jù)塊火窒，具有較高的命中率。

3. 隨機(jī)替換

最簡單的替換算法是隨機(jī)替換驮肉。隨機(jī)替換算法完全不管Cache的情況熏矿，簡單地根據(jù)一個隨機(jī)數(shù)選擇一塊替換出去。隨機(jī)替換算法在硬件上容易實(shí)現(xiàn)缆八，且速度也比前兩種算法快曲掰。缺點(diǎn)則是降低了命中率和Cache工作效率。
Cache命中率除了和替換算法有關(guān)外奈辰，還與Cache的容量及塊的大小有
關(guān)栏妖。

寫回算法

由于Cache的內(nèi)容只是主存內(nèi)容的一個子集，應(yīng)當(dāng)與主存內(nèi)容保持一致奖恰，而CPU對Cache的寫入更改了Cache的內(nèi)容吊趾。為此，可選用寫操作策略使Cache內(nèi)容與主存內(nèi)容保持一致瑟啃。

寫回法

當(dāng)CPU寫Cache命中時论泛，只修改Cache的內(nèi)容，而不是立即寫入主存蛹屿；只有當(dāng)此塊被換出時才寫回主存屁奏。
使用這種方法寫Cache和寫主存異步進(jìn)行，顯著減少了訪問主存的次數(shù)错负，但是存在數(shù)據(jù)不一致的隱患坟瓢。實(shí)現(xiàn)這種方法時，每個Cache塊必須配置一個修改位犹撒，以反映此塊是否被CPU修改過折联。

全寫法

當(dāng)寫 Cache命中時，Cache與主存同時發(fā)生寫修改识颊。
使用這種方法寫Cache和寫主存同步進(jìn)行诚镰，因而較好地維護(hù)了Cache與主存的內(nèi)容一致性。實(shí)現(xiàn)這種方法時祥款，Cache中的每個塊無需設(shè)置修改位以及相應(yīng)的判斷邏輯清笨，但由于Cache對CPU向主存的寫操作沒有高速緩沖功能，從而降低了Cache的功效镰踏。

寫一次法

寫一次法是基于寫回法并結(jié)合全寫法的寫操作策略函筋，寫命中與寫未命中的處理方法與寫回法基本相同，只是第一次寫命中時要同時寫入主存奠伪，以便于維護(hù)系統(tǒng)全部Cache的一致性跌帐。