前言

Cache是位于CPU與主存儲(chǔ)器即DRAM（Dynamic RAM，動(dòng)態(tài)存儲(chǔ)器）之間的少量超高速靜態(tài)存儲(chǔ)器SRAM（Static RAM），它是為了解決CPU與主存之間速度匹配問(wèn)題而設(shè)置的，不能由用戶直接尋址訪問(wèn)。

隨著科技的發(fā)展和生產(chǎn)工藝水平的提高，高性能處理器中Cache的容量將越來(lái)越大，而且級(jí)數(shù)將越來(lái)越多，從而大大提高系統(tǒng)的性能。

1 Cache和Write Buffer一般性介紹

1.1 Cache工作原理

具有Cache的計(jì)算機(jī)，當(dāng)CPU需要進(jìn)行存儲(chǔ)器存取時(shí)，首先檢查所需數(shù)據(jù)是否在Cache中。如果存在，則可以直接存取其中的數(shù)據(jù)而不必插入任何等待狀態(tài)，這是最佳情況，稱為高速命中；

當(dāng)CPU所需信息不在Cache中時(shí)，則需切換存取主儲(chǔ)器，由于速度較慢，需要插入等待，這種情況稱高速未命中；

在CPU存取主存儲(chǔ)器的時(shí)候，按照最優(yōu)化原則將存儲(chǔ)信息同時(shí)寫入到Cache中以保證下次可能的高速緩存命中。

因此 ，同一數(shù)據(jù)可能同時(shí)存儲(chǔ)在主存儲(chǔ)器和Cache中 。同樣，按照優(yōu)化算法， 可以淘汰Cache中一些不常使用的數(shù)據(jù) 。

傳統(tǒng)的Socket架構(gòu)通常采用兩級(jí)緩沖結(jié)構(gòu)，即在CPU中集成了一級(jí)緩存（L1Cache），在主板上裝二級(jí)緩存（L2 Cache），而SlotⅠ架構(gòu)下的L2 Cache則與CPU做在同一塊電路板上，以內(nèi)核速度或者內(nèi)核速度的一半運(yùn)行，速度比Socket下的以系統(tǒng)外頻運(yùn)行的L2 Cache更快，能夠更大限度發(fā)揮高主頻的優(yōu)勢(shì)，當(dāng)然對(duì)Cache工藝要求也更高。

?CPU首先在L1 Cache中查找數(shù)據(jù)，如找不到，則在L2Cache中尋找。?若數(shù)據(jù)在L2 Cache中，控制器在傳輸數(shù)據(jù)的同時(shí)，修改L1Cache；?若數(shù)據(jù)既不在L1 Cache中，又不在L2 Cache中，Cache控制器則從主存中獲取數(shù)據(jù)，將數(shù)據(jù)提供給CPU的同時(shí)修改兩級(jí)Cache。?K6-Ⅲ則比較特殊，64KB L1 Cache，256KB Full Core Speed L2 Cache，原先主板上的緩存實(shí)際上就成了L3 Cache。

根據(jù)有關(guān)測(cè)試表明：

當(dāng)512K2MB的三級(jí)緩存發(fā)揮作用時(shí)，系統(tǒng)性能還可以有2%10%的提高；

Tri-level成為PC系統(tǒng)出現(xiàn)以來(lái)提出的解決高速CPU與低速內(nèi)存之間瓶頸最為細(xì)致復(fù)雜的方案；而且，今后Cache的發(fā)展方向也是大容。

在主存-Cache存儲(chǔ)體系中， 所有的指令和數(shù)據(jù)都存在主存中 ，Cache只是存放主存中的一部分程序塊和數(shù)據(jù)塊的副本，只是一種以塊為單位的存儲(chǔ)方式。

Cache和主存被分為塊，每塊由多個(gè)字節(jié)組成。

由上述的程序局部性原理可知，Cache中的程序塊和數(shù)據(jù)塊會(huì)使CPU要訪問(wèn)的內(nèi)容在大多數(shù)情況下已經(jīng)在Cache中，CPU的讀寫操作主要在CPU和Cache之間進(jìn)行。

CPU訪問(wèn)存儲(chǔ)器時(shí)，送出訪問(wèn)單元的地址，由地址總線傳送到Cache控制器中的主存地址寄存器MAR， 主存-Cache地址轉(zhuǎn)換機(jī)構(gòu)從MA獲取地址并判斷該單元內(nèi)容是否已在Cache中存有副本 ，如果副本已存在于Cache中，即命中。當(dāng)命中時(shí)，立即把訪問(wèn)地址變換成它在Cache中的地址，然后訪問(wèn)Cache。

• 存儲(chǔ)體由若跟個(gè)存儲(chǔ)單元組成，存儲(chǔ)單元由多個(gè)存儲(chǔ)元件組成
• 存儲(chǔ)體----存儲(chǔ)單元（存儲(chǔ)一串二進(jìn)制串）----存儲(chǔ)元件（存儲(chǔ)一個(gè)0/1）
• 存儲(chǔ)單元：存放一串二進(jìn)制代碼。
• 存儲(chǔ)字：存儲(chǔ)單元中的二進(jìn)制代碼
• 存儲(chǔ)字長(zhǎng)：存儲(chǔ)單元中二進(jìn)制代碼位數(shù)。
• 存儲(chǔ)單元按照地址進(jìn)行尋址
• MAR：存儲(chǔ)器地址寄存器，反應(yīng)存儲(chǔ)單元個(gè)數(shù)。保存了存儲(chǔ)體的地址（存儲(chǔ)單元的編號(hào)），反應(yīng)了存儲(chǔ)單元的個(gè)數(shù)。所以MAR的位數(shù)和存儲(chǔ)單元的個(gè)數(shù)有關(guān)。
• MDR：存儲(chǔ)器數(shù)據(jù)寄存器，反應(yīng)存儲(chǔ)字長(zhǎng)（存儲(chǔ)單元長(zhǎng)度）。保存了要送入CPU中的數(shù)據(jù)或要保存到存儲(chǔ)體中的數(shù)據(jù)或者剛剛從存儲(chǔ)體中取出來(lái)來(lái)的數(shù)據(jù)。這個(gè)寄存器的長(zhǎng)度和存儲(chǔ)單元的長(zhǎng)度相同。

如果CPU要訪問(wèn)的內(nèi)容不在Cache中，即不命中，則CPU轉(zhuǎn)去直接訪問(wèn)主存，并將包含此存儲(chǔ)單元的整個(gè)數(shù)據(jù)塊（包括該塊數(shù)據(jù)的地址信息）傳到Cache中，使得以后的若干次對(duì)內(nèi)存的訪問(wèn)可轉(zhuǎn)化為對(duì)Cache的訪問(wèn)。

若Cache存儲(chǔ)器已滿，則需在替換控制部件的控制下，根據(jù)某種替換算法/策略，用此塊信息替換掉Cache中原來(lái)的某塊信息。

之前記得當(dāng)時(shí)面試的時(shí)候讓我用golang手寫緩存管理算法，哈哈哈。

所以，要想提高系統(tǒng)效率，必須提高Cache命中率 ，而Cache命中率的提高則 取決于Cache的映像方式和Cache刷新算法等一系列因素 ，同時(shí)Cache中內(nèi)容應(yīng)與主存中的部分保持一致，也就是說(shuō)，如果主存中的內(nèi)容在調(diào)入Cache之后發(fā)生了變化，那么它在Cache中的映像也應(yīng)該隨之發(fā)生相應(yīng)改變，反之，當(dāng)CPU修改了Cache中的內(nèi)容后，主存中的相應(yīng)內(nèi)容也應(yīng)作修改。

1.2 地址映像方式

所謂地址映像方式是指如何確定Cache中的內(nèi)容是主存中的哪一部分的副本，即必須應(yīng)用某種函數(shù)把主存地址映像到Cache中定位。

信息按某種方式裝入Cache中后，執(zhí)行程序時(shí)，應(yīng)將主存地址變換為Cache地址，這個(gè)變換過(guò)程叫作地址變換。

地址映像方式通常采用直接映像、全相聯(lián)映像、組相聯(lián)映像三種：

1-直接映像

每個(gè)主存地址映像到Cache中的一個(gè)指定地址的方式，稱為直接映像方式。在直接映像方式下，主存中存儲(chǔ)單元的數(shù)據(jù)只可調(diào)入Cache中的一個(gè)位置，如果主存中另一個(gè)存儲(chǔ)單元的數(shù)據(jù)也要調(diào)入該位置則將發(fā)生沖突。

地址映像的方法一般是將主存空間按Cache的尺寸分區(qū)，每區(qū)內(nèi)相同的塊號(hào)映像到Cache中相同的塊位置。一般地，Cache被分為2N塊，主存被分為大小為2MB的塊，主存與Cache中塊的對(duì)應(yīng)關(guān)系可用如下映像函數(shù)表示：j = i mod 2N。式中，j是Cache中的塊號(hào)；i是主存中的塊號(hào)。

直接映像是一種最簡(jiǎn)單的地址映像方式，它的地址變換速度快，而且不涉及其他兩種映像方式中的替換策略問(wèn)題。但是這種方式的塊沖突概率較高，當(dāng)程序往返訪問(wèn)兩個(gè)相互沖突的塊中的數(shù)據(jù)時(shí)，Cache的命中率將急劇下降，因?yàn)檫@時(shí)即使Cache中有其他空閑塊，也因?yàn)楣潭ǖ牡刂酚诚耜P(guān)系而無(wú)法應(yīng)用。

2-全相聯(lián)映像

主存中的每一個(gè)字塊可映像到Cache任何一個(gè)字塊位置上，這種方式稱為全相聯(lián)映像。這種方式只有當(dāng)Cache中的塊全部裝滿后才會(huì)出現(xiàn)塊沖突，所以塊沖突的概率低，可達(dá)到很高的Cache命中率，但它實(shí)現(xiàn)很復(fù)雜。

當(dāng)訪問(wèn)一個(gè)塊中的數(shù)據(jù)時(shí)，塊地址要與Cache塊表中的所有地址標(biāo)記進(jìn)行比較已確定是否命中。在數(shù)據(jù)塊調(diào)入時(shí)存在著一個(gè)比較復(fù)雜的替換問(wèn)題，即決定將數(shù)據(jù)塊調(diào)入Cache中什么位置，將Cache中哪一塊數(shù)據(jù)調(diào)出主存。為了達(dá)到較高的速度，全部比較和替換都要用硬件實(shí)現(xiàn)。

3-組相聯(lián)映像

組相聯(lián)映像方式是直接映像和全相聯(lián)映像的一種折中方案。這種方法將存儲(chǔ)空間分為若干組，各組之間是直接映像，而組內(nèi)各塊之間則是全相聯(lián)映像。

它是上述兩種映像方式的一般形式，如果組的大小為1，即Cache空間分為2N組，就變?yōu)橹苯佑诚瘢蝗绻M的大小為Cache整個(gè)的尺寸，就變?yōu)槿嗦?lián)映像。組相聯(lián)方式在判斷塊命中及替換算法上都要比全相聯(lián)方式簡(jiǎn)單，塊沖突的概率比直接映像低，其命中率也介于直接映像和全相聯(lián)映像方式之間。

1.3 Cache寫入方式原理簡(jiǎn)介

提高高速緩存命中率的最好方法是盡量使Cache存放CPU最近一直在使用的指令與數(shù)據(jù)，當(dāng)Cache裝滿后，可將相對(duì)長(zhǎng)期不用的數(shù)據(jù)刪除，提高Cache的使用效率。

為保持Cache中數(shù)據(jù)與主存儲(chǔ)器中數(shù)據(jù)的一致性，避免CPU在讀寫過(guò)程中將Cache中的新數(shù)據(jù)遺失，造成錯(cuò)誤地讀數(shù)據(jù)，確保Cache中更新過(guò)程的數(shù)據(jù)不會(huì)因覆蓋而消失，必須將Cache中的數(shù)據(jù)更新及時(shí)準(zhǔn)確地反映到主存儲(chǔ)器中，這是一個(gè)Cache寫入過(guò)程，Cache寫入的方式通常采用直寫式、緩沖直寫式與回寫式三種，下面比較介紹這三種Cache寫入方式。

1- 直寫式（Write Through）系統(tǒng)

CPU對(duì)Cache寫入時(shí)，將數(shù)據(jù)同時(shí)寫入到主存儲(chǔ)器中，這樣可保證Cache中的內(nèi)容與主存儲(chǔ)器的內(nèi)容完全一致。這種方式比較直觀，而且簡(jiǎn)單、可靠，但由于每次對(duì)Cache更新時(shí)都要對(duì)主存儲(chǔ)器進(jìn)行寫操作，而這必須通過(guò)系統(tǒng)總線來(lái)完成，因此總線工作頻繁，系統(tǒng)運(yùn)行速度就會(huì)受到影響。

2-緩沖直寫式（Post Wirte）系統(tǒng)

為解決直寫式系統(tǒng)對(duì)總線速度的影響問(wèn)題，在主存儲(chǔ)器的數(shù)據(jù)寫入時(shí)增加緩沖器區(qū)。當(dāng)要寫入主存儲(chǔ)器的數(shù)據(jù)被緩沖器鎖存后，CPU便可執(zhí)行下一個(gè)周期的操作，不必等待數(shù)據(jù)寫入主存儲(chǔ)器。這相對(duì)于給主存儲(chǔ)器增加了一個(gè)單向單次高速緩存。

比如，在寫入周期之后可以緊接著一個(gè)數(shù)據(jù)已存在于Cache中的讀取周期，這樣就可避免直寫式系統(tǒng)造成的操作延時(shí)，但這個(gè)緩沖器只能存儲(chǔ)一次寫入的數(shù)據(jù)，當(dāng)連續(xù)兩次寫操作發(fā)生時(shí)，CPU仍需等待。

3-回寫式（Write Back）系統(tǒng)

前面兩種寫入方式系統(tǒng)，都是在寫Cache的同時(shí)對(duì)主存儲(chǔ)器進(jìn)行寫操作。實(shí)際上這不僅是對(duì)總線帶寬的占用，浪費(fèi)了寶貴的執(zhí)行時(shí)間，而且在有些情況下是不必要的，可以通過(guò)增加額外的標(biāo)準(zhǔn)來(lái)判斷是否有必要更新數(shù)據(jù)。回寫式系統(tǒng)就是通過(guò)在Cache中的每一數(shù)據(jù)塊的標(biāo)志字段中加入一更新位，解決主存儲(chǔ)器不必要的寫操作。

比如，若Cache中的數(shù)據(jù)曾被CPU更新過(guò)但還未更新主存儲(chǔ)器，則該更新位被置1。每次CPU將一塊新內(nèi)容寫入Cache時(shí)，首先檢查Cache中該數(shù)據(jù)塊的更新位，若更新位為0，則將數(shù)據(jù)直接寫入Cache；反之，若更新位為1，則先將Cache中的該項(xiàng)內(nèi)容寫入到主存儲(chǔ)器中相應(yīng)的位置，再將新數(shù)據(jù)寫回Cache中。

與直寫式系統(tǒng)相比，回寫式系統(tǒng)可省下一些不必要的立即回寫操作，而在許多情況下這是很頻繁出現(xiàn)的。即使一個(gè)Cache被更新，若未被新的數(shù)據(jù)所取代，則沒(méi)有必要立刻進(jìn)行主存儲(chǔ)器的寫操作。也就是說(shuō)，實(shí)際寫入主存儲(chǔ)器的次數(shù)，可能少于CPU實(shí)際所執(zhí)行寫入周期的次數(shù)，但回寫式系統(tǒng)的結(jié)構(gòu)較復(fù)雜，Cache也必須用額外的容量來(lái)存儲(chǔ)標(biāo)志。由于回寫系統(tǒng)的高效率，現(xiàn)代的Cache大多采取這種方式進(jìn)行操作。

1.4 關(guān)于Write-through和Write-back

1-對(duì)于磁盤操作來(lái)說(shuō)

write-through的意思是寫操作根本不使用緩存，數(shù)據(jù)總是直接寫入磁盤，關(guān)閉寫緩存，可釋放緩存用于讀操作（緩存被讀寫操作共用）。

write-back的意思是數(shù)據(jù)不直接被寫入磁盤，而是先寫入緩存，再由控制器將緩存內(nèi)未寫入磁盤的數(shù)據(jù)寫入磁盤，從應(yīng)用程序的角度看，比等待完成磁盤寫入操作要快得多，因此可以提高寫性能。

但是write-back（write cache）方式通常在磁盤負(fù)荷較輕時(shí)速度更快。負(fù)荷重時(shí)，每當(dāng)數(shù)據(jù)被寫入緩存后，就要馬上再寫入磁盤以釋放緩存來(lái)保存將要寫入的新數(shù)據(jù)，這時(shí)如果數(shù)據(jù)直接寫入磁盤，控制器會(huì)以更快的速度運(yùn)行。因此，負(fù)荷重時(shí)，將數(shù)據(jù)先寫入緩存反而會(huì)降低吞吐量。

2-對(duì)于CPU內(nèi)部的cache緩沖模式來(lái)說(shuō)

Write-Through和Write-Back，前者是按順序來(lái)一個(gè)寫一個(gè)，而后者則是先將資料按一定數(shù)量保存在緩沖區(qū)中，然后將相同位置的數(shù)據(jù)一次性寫出。舉例說(shuō)明：有一部電梯，如果按先入先出的原則，即write through模式，第一個(gè)人去3樓，第二個(gè)去2樓，第三個(gè)也去3樓，那么這電梯就得先到3樓，然后到2樓，再去3樓。

但如果在write back模式下，電梯先到2樓把第二個(gè)人送出去，然后再到3樓把第一個(gè)人和第三個(gè)人送出去，效率顯然高多了。早期的cache只有write through模式，但現(xiàn)在的cache都使用write back模式了。

3-其他的解釋

• Write-Through：在write的時(shí)候，同步更新cache和memory中的數(shù)據(jù)。Write-Back：在write的時(shí)候更新cache，但是memory中的數(shù)據(jù)不一定同步更新，只有當(dāng)cache到一定程度才會(huì)把cache中的數(shù)據(jù)刷到memory中，或者通過(guò)cache指令刷新，不會(huì)同步自動(dòng)刷新。
• cache line的意思是假設(shè)你那條指令只要從memory中讀4個(gè)字節(jié)，但是一般來(lái)說(shuō)你接下來(lái)的指令很有可能要讀這4個(gè)字節(jié)后面的數(shù)據(jù)，所以一般硬件會(huì)多讀一些數(shù)據(jù)進(jìn)入cache，比如64字節(jié)，那么這64字節(jié)就是一個(gè)cache line。而如果你這個(gè)cache line里的數(shù)據(jù)長(zhǎng)時(shí)間不被CPU訪問(wèn)，那么這個(gè)cache line可能會(huì)被選中換出，這時(shí)候就必須把cache里被改過(guò)的信息寫回memory了。

1.5 Cache替換策略

Cache和存儲(chǔ)器一樣具有兩種基本操作，即讀操作和寫操作。當(dāng)CPU發(fā)出讀操作命令時(shí)，根據(jù)它產(chǎn)生的主存地址分為兩種情形：一種是需要的數(shù)據(jù)已在Cache中，那么只需要直接訪問(wèn)Cache，從對(duì)應(yīng)單元中讀取信息到數(shù)據(jù)總線即可；

另一種是需要的數(shù)據(jù)尚未裝入Cache，CPU需要從主存中讀取信息的同時(shí)，Cache替換部件把該地址所在的那塊存儲(chǔ)內(nèi)容從主存復(fù)制到Cache中。若Cache中相應(yīng)位置已被字塊占滿，就必須去掉舊的字塊。常見(jiàn)的替換策略有以下兩種：

1-先進(jìn)先出策略（FIFO）

FIFO（First In First Out）策略總是把最先調(diào)入的Cache字塊替換出去，它不需要隨時(shí)記錄各個(gè)字塊的使用情況，較容易實(shí)現(xiàn)。缺點(diǎn)是經(jīng)常使用的塊，如一個(gè)包含循環(huán)程序的塊也可能由于它是最早的塊而被替換掉。

2-最近最少使用策略（LRU）

LRU（Least Recently Used）策略是把當(dāng)前近期Cache中使用次數(shù)最少的信息塊替換出去，這種替換算法需要隨時(shí)記錄Cache中字塊的使用情況。LRU的平均命中率比FIFO高，在組相聯(lián)映像方式中，當(dāng)分組容量加大時(shí)，LRU的命中率也會(huì)提高。

1.6 使用Cache的必要性

所謂Cache即高速緩沖存儲(chǔ)器，它位于CPU與主存即DRAM之間，是通常由SRAM構(gòu)成的規(guī)模較小但存取速度很快的存儲(chǔ)器。

目前計(jì)算機(jī)主要使用的內(nèi)存為DRAM，它具有價(jià)格低、容量大等特點(diǎn)，但由于使用電容存儲(chǔ)信息，存取速度難以提高，而CPU每執(zhí)行一條指令都要訪問(wèn)一次或多次主存，DRAM的讀寫速度遠(yuǎn)低于CPU速度，因此為了實(shí)現(xiàn)速度上的匹配，只能在CPU指令周期中插入wait狀態(tài)，高速CPU處于等待狀態(tài)將大大降低系統(tǒng)的執(zhí)行效率。

由于SRAM采用了與CPU相同的制作工藝，因此與DRAM相比，它的存取速度快，但體積大、功耗大、價(jià)格高，不可能也不必要將所有的內(nèi)存都采用SRAM。

因此為了解決速度與成本的矛盾就產(chǎn)生了一種分級(jí)處理的方法，即在主存和CPU之間加裝一個(gè)容量相對(duì)較小的SRAM作為高速緩沖存儲(chǔ)器。

當(dāng)采用Cache后，在Cache中保存著主存中部分內(nèi)容的副本（稱為存儲(chǔ)器映像），CPU在讀寫數(shù)據(jù)時(shí)，首先訪問(wèn)Cache（由于Cache的速度與CPU相當(dāng)，所以CPU可以在零等待狀態(tài)下完成指令的執(zhí)行），只有當(dāng)Cache中無(wú)CPU所需的數(shù)據(jù)時(shí)（這稱之“未命中”，否則稱為“命中”），CPU才去訪問(wèn)主存。

而目前大容量Cache能使CPU訪問(wèn)Cache命中率高達(dá)90%~98%，從而大大提高了CPU訪問(wèn)數(shù)據(jù)的速度，提高了系統(tǒng)的性能。

1.7 使用Cache的可行性

對(duì)大量的典型程序的運(yùn)行情況分析結(jié)果表明，在一個(gè)較短的時(shí)間內(nèi)，由程序產(chǎn)生的地址往往集中在存儲(chǔ)器邏輯地址空間的很小范圍內(nèi)。

在多數(shù)情況下，指令是順序執(zhí)行的，因此指令地址的分布就是連續(xù)的，再加上循環(huán)程序段和子程序段要重復(fù)執(zhí)行多次，因此對(duì)這些地址的訪問(wèn)就自然具有時(shí)間上集中分布的趨向。

數(shù)據(jù)的這種集中傾向不如指令明顯，但對(duì)數(shù)組的訪問(wèn)以及工作單元的選擇都可以使存儲(chǔ)器地址相對(duì)集中。這種對(duì)局部范圍的存儲(chǔ)器地址的頻繁訪問(wèn)，而對(duì)此范圍以外的地址則訪問(wèn)甚少的現(xiàn)象稱為程序訪問(wèn)的局部性。

根據(jù)程序的局部性原理，在主存和CPU之間設(shè)置Cache，把正在執(zhí)行的指令地址附近的一部分指令或數(shù)據(jù)從主存裝入Cache中，供CPU在一段時(shí)間內(nèi)使用，是完全可行的。