一、為什么要使用緩存

由于不同的存儲(chǔ)技術(shù)在存儲(chǔ)速度和造價(jià)上相差巨大，為了高效的訪問數(shù)據(jù)，現(xiàn)代計(jì)算機(jī)的存儲(chǔ)系統(tǒng)會(huì)把最常用的數(shù)據(jù)放在讀存速度快的存儲(chǔ)設(shè)備上，而把不常用的數(shù)據(jù)放在讀存速度慢的存儲(chǔ)設(shè)備上。存儲(chǔ)器系統(tǒng)是一個(gè)具有不同容量、成本和訪問時(shí)間的存儲(chǔ)設(shè)備的層級(jí)結(jié)構(gòu)。從上往下容量越來越大，但訪問速度越來越慢。上一層做為下一層的緩存來存儲(chǔ)訪問頻率更高的數(shù)據(jù)，比如，cpu寄存器保存著最常用的數(shù)據(jù)?？拷麮PU的小的、快速的高速緩存存儲(chǔ)器是內(nèi)存上一部分?jǐn)?shù)據(jù)和指令的緩沖區(qū)域。主存緩存磁盤上的數(shù)據(jù)，而這些磁盤又常常作為存儲(chǔ)在通過網(wǎng)絡(luò)連接的其他機(jī)器的磁盤或磁帶上的數(shù)據(jù)的緩沖區(qū)域。存儲(chǔ)層次如下：

二、緩存如何判斷哪些數(shù)據(jù)是更常用的

緩存上存儲(chǔ)的數(shù)據(jù)是那些計(jì)算機(jī)認(rèn)為在接下來更有可能訪問到的數(shù)據(jù)，計(jì)算機(jī)如何判斷哪些數(shù)據(jù)接下來更有可能用到呢？系統(tǒng)對(duì)數(shù)據(jù)的訪問頻率有兩種假設(shè)：

1. 時(shí)間局部性

時(shí)間局部性假設(shè)目前訪問的數(shù)據(jù)在接下來也更有可能再次訪問到，所以計(jì)算機(jī)會(huì)把剛剛訪問過的數(shù)據(jù)放入緩存中；

2. 空間局部性

空間局部性假設(shè)與目前訪問的數(shù)據(jù)相鄰的那些數(shù)據(jù)接下來也更有可能訪問到，所以會(huì)把當(dāng)前數(shù)據(jù)周圍的數(shù)據(jù)放入緩存中； 一個(gè)編寫良好的代碼往往符合時(shí)間局部性和空間局部性。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?

三、數(shù)據(jù)在存儲(chǔ)器層次之間以塊為單位進(jìn)行傳遞

存儲(chǔ)器層次結(jié)構(gòu)的本質(zhì)是，每一層存儲(chǔ)設(shè)備都是較低一層的緩存。為了利用空間局部性，存儲(chǔ)器上的數(shù)據(jù)都是按塊劃分的，每個(gè)塊包含多個(gè)字節(jié)的數(shù)據(jù)。第k層的緩存包含第k+1層塊的一個(gè)子集的副本。數(shù)據(jù)總是以塊為傳送單位在第k層和第k+1層來回復(fù)制的。在層次結(jié)構(gòu)中任何一對(duì)相鄰的層次之間塊大小是一樣的。不過不同的層次之間塊大小可以不同，一般而言，越靠近底層，越傾向于使用較大的塊。

四、cup如何訪問數(shù)據(jù)

當(dāng)程序需要第k+1層的某個(gè)數(shù)據(jù)時(shí)，它首先在第k層的一個(gè)塊中查找d，這里會(huì)出現(xiàn)兩種情況：

1. 緩存命中

d剛好緩存在k層中，這里稱之為緩存命中，該程序直接從k層讀取d，根據(jù)存儲(chǔ)器層次結(jié)構(gòu)，這要比從k+1層取數(shù)據(jù)更快。

2. 緩存不命中

d沒有緩存在k中，這種情況稱之為緩存不命中，第k層的緩存從第k+1層中取出包含d的那個(gè)塊，放在k層中，然后從k層讀出d。這里涉及一個(gè)問題，即從k+1層中取出的塊應(yīng)如何放置在k層中，這里需要某種放置策略?？捎玫牟呗匀缦拢?/p>

（1）隨機(jī)放置，在k中隨機(jī)選擇一個(gè)位置進(jìn)行放置，這種策略實(shí)現(xiàn)起來通常很昂貴，因?yàn)椴缓枚ㄎ唬?/p>

（2）分組放置，將第k+1層的某個(gè)塊放置在第k層塊的某個(gè)小組（子集）中；

五、從一個(gè)簡(jiǎn)單的層次模型理解高速緩存是如何實(shí)現(xiàn)的

1. 高速緩存的結(jié)構(gòu)及與地址的映射關(guān)系

高速緩存使用分組放置策略，它把存儲(chǔ)空間分為S組，每組E行，每行包含1個(gè)塊，每個(gè)塊的大小為B，它的結(jié)構(gòu)可以用四元組（S，E，B，m）來表示，其中m代表地址位的個(gè)數(shù)。高速緩存的容量為C=SEB；

當(dāng)訪問數(shù)據(jù)時(shí)，我們唯一知道的是數(shù)據(jù)的地址。通過地址我們?nèi)绾螐木彺嬷姓业綌?shù)據(jù)所在的組號(hào)，塊號(hào)和塊中的位置呢？這里m個(gè)地址位分為了3個(gè)字段，其中高位的字段為t個(gè)標(biāo)記位，它唯一的標(biāo)記了組中的塊，中間的字段為s個(gè)索引位，它標(biāo)記了組號(hào)，最后的字段為塊偏移，通過它可以訪問塊中具體的字節(jié)。另外緩存結(jié)構(gòu)中每一行最前面還有一個(gè)有效位，它標(biāo)志了這一行有沒有存儲(chǔ)塊。緩存結(jié)構(gòu)如下：

2. 一個(gè)簡(jiǎn)單的存儲(chǔ)模型

下面定義一個(gè)簡(jiǎn)單的存儲(chǔ)層次模型：

（1）cpu和內(nèi)存之間只加了一層高速緩存；

（2）存儲(chǔ)地址為4位，即內(nèi)存中最多存16個(gè)字節(jié)；

4位的地址被分成了3段：最高位的1段為標(biāo)記位，中間2位為索引組，最后1位為塊偏移。從索引組的的位數(shù)可判斷緩存被分成了4組，1位的塊偏移說明塊的大小為2個(gè)字節(jié)。這里設(shè)每組只有1行，這種情況稱為直接映射高速緩存。從以上分段可知，緩存大小為 421=8 字節(jié)；

舉例：地址0101；其中高位的0為標(biāo)記位，標(biāo)記組中的1個(gè)塊，中間的兩位10為組索引，通過組索引可知當(dāng)前地址的塊存在組2中，最后1位為偏移位，說明要取的字節(jié)存在塊中的第2個(gè)位置。

3. 緩存過程

（1）初始狀態(tài)緩存是空的，當(dāng)cpu通過地址（假設(shè)為0001）要加載一個(gè)數(shù)據(jù)時(shí)，此時(shí)cpu會(huì)先查找高速緩存，通過中間的地址00找到第0組，通過緩存最前面的有效位判斷緩存不命中，然后從內(nèi)存中取得地址0001處的值。注意此時(shí)不會(huì)從內(nèi)存中只取0001處的值，而是根據(jù)緩存的塊的大小取得1個(gè)塊，即2個(gè)字節(jié)，即0000和0001兩處的值。然后會(huì)把這兩個(gè)值存儲(chǔ)在組索引為0，偏移量為0和1的地址處，并且把當(dāng)前行的有效位設(shè)置為1，標(biāo)記位設(shè)置為0，最后高速緩存返回新取出的高速緩存塊[1]處的值；

（2）接下來，cpu如果要取0000處的值，此時(shí)也會(huì)先查找緩存，通過中間2位00找到緩存的組數(shù)為0，通過第1個(gè)有效位（1）和標(biāo)記位（0）判斷緩存命中，此時(shí)會(huì)直接返回偏移量0處的值，不需要再查找內(nèi)存；

（3）如果接下來cpu要取1000處的值，此時(shí)會(huì)查找到組0，由于地址的標(biāo)記位為1，和緩存組0中行的標(biāo)記位（0）不符合，所以緩存不命中，cpu會(huì)從內(nèi)存中取得相應(yīng)的塊，并把緩存組0處的數(shù)據(jù)覆蓋掉，此時(shí)會(huì)把組的標(biāo)識(shí)位設(shè)置為1。

（4）接下來再讀地址0000處的值，此時(shí)又會(huì)發(fā)生緩存不命中，因?yàn)樯厦嬉玫刂?000時(shí)，把塊替換掉了。這種情況稱為沖突不命中，也就是說我們有足夠的高速緩存空間，但是卻交替地引用映射到同一個(gè)組的塊；

小結(jié)：

cpu加載機(jī)制為，通過地址先查找緩存，查找過程為，先通過地址中間的組索引位，找到組，然后根據(jù)組中行的有效位和標(biāo)記位判斷是否緩存命中，如果命中，則直接從緩存中取數(shù)據(jù)；如果沒命中，則從內(nèi)存中取出1個(gè)塊，并用某種放置策略放在緩存中，然后從緩存返回值。在直接映射高速緩中，內(nèi)存中的空間和緩存中的空間是一種多對(duì)一的映射關(guān)系，比如本例中地址0和地址8所指的內(nèi)存空間的內(nèi)容，在緩存中都存在第0組偏移量為0的空間中；他們?cè)诰彺嬷械膮^(qū)分由地址的最高位即標(biāo)記位決定。

六、解決緩存沖突問題

1. 什么是緩存沖突

當(dāng)每個(gè)組只有一行的情況下，映射為同一組的塊在緩存中將占用同一個(gè)存儲(chǔ)空間，當(dāng)反復(fù)加載位于同一組的兩個(gè)塊時(shí)，由于每次加載都會(huì)把先前加載的塊覆蓋掉，導(dǎo)致cpu對(duì)緩存的命中率為0，雖然此時(shí)在其他組依然有大量的緩存空間。

2.組相聯(lián)高級(jí)緩存

為了降低緩存沖突，可以把每個(gè)組分為多行，每行存儲(chǔ)一個(gè)塊。cpu通過組索引查找塊所在的組，然后通過有效位和標(biāo)記位檢查多行來判斷是否緩存命中。當(dāng)緩存不命中時(shí)，會(huì)從內(nèi)存中加載一個(gè)塊到緩存相對(duì)應(yīng)的組中，當(dāng)組內(nèi)有空行時(shí)，會(huì)直接加載到空的行，否則緩存會(huì)使用某種替換策略來?yè)Q掉組內(nèi)的一行。常用的替換策略有隨機(jī)替換，最近最少使用原則，即替換掉組內(nèi)最長(zhǎng)時(shí)間未使用的行。當(dāng)緩存中只有1個(gè)組，組中包含所有行時(shí)，稱為全相聯(lián)高速緩存。

七、如何編寫緩存友好的代碼

為了更好的利用緩存，提高代碼執(zhí)行速度。需要編寫局部性良好的代碼，提高緩存命中率，下面是基本方法

1. 把注意力集中在核心函數(shù)的循環(huán)上；

2. 對(duì)局部變量的反復(fù)引用有良好的時(shí)間局部性；

3. 步長(zhǎng)為1的引用模型有很好的空間局部性，當(dāng)掃描二維數(shù)組時(shí)要一行一行的掃描，而不是一列一列的掃描；