為什么需要cache

如果CPU需要將一個(gè)變量（假設(shè)地址是A）加1，一般分為以下3個(gè)步驟：

CPU 從主存中讀取地址A的數(shù)據(jù)到內(nèi)部通用寄存器 x0（ARM64架構(gòu)的通用寄存器之一）

通用寄存器 x0 加1

CPU 將通用寄存器 x0 的值寫(xiě)入主存

我們將這個(gè)過(guò)程可以表示如下：

其實(shí)現(xiàn)實(shí)中，CPU通用寄存器的速度和主存之間存在著太大的差異。兩者之間的速度大致如下關(guān)系：

CPU register的速度一般小于1ns，主存的速度一般是65ns左右。速度差異近百倍。在硬件上，我們將cache放置在CPU和主存之間，作為主存數(shù)據(jù)的緩存。當(dāng)CPU試圖從主存中l(wèi)oad/store數(shù)據(jù)的時(shí)候， CPU會(huì)首先從cache中查找對(duì)應(yīng)地址的數(shù)據(jù)是否緩存在cache 中。如果其數(shù)據(jù)緩存在cache中，直接從cache中拿到數(shù)據(jù)并返回給CPU。當(dāng)存在cache的時(shí)候，以上程序如何運(yùn)行的例子的流程將會(huì)變成如下：

CPU和主存之間直接數(shù)據(jù)傳輸?shù)姆绞睫D(zhuǎn)變成CPU和cache之間直接數(shù)據(jù)傳輸。cache負(fù)責(zé)和主存之間數(shù)據(jù)傳輸。

多級(jí)cache存儲(chǔ)結(jié)構(gòu)

前面提到的cache，稱(chēng)之為L(zhǎng)1 cache（第一級(jí)cache）。我們?cè)贚1 cache 后面連接L2 cache，在L2 cache 和主存之間連接L3 cache。等級(jí)越高，速度越慢，容量越大。但是速度相比較主存而言，依然很快。不同等級(jí)cache速度之間關(guān)系如下：

經(jīng)過(guò)3級(jí)cache的緩沖，各級(jí)cache和主存之間的速度最萌差也逐級(jí)減小。在一個(gè)真實(shí)的系統(tǒng)上，各級(jí)cache之間硬件上是如何關(guān)聯(lián)的呢？我們看下Cortex-A53架構(gòu)上各級(jí)cache之間的硬件抽象框圖如下：

在Cortex-A53架構(gòu)上，L1 cache分為單獨(dú)的instruction cache（ICache）和data cache（DCache）。L1 cache是CPU私有的，每個(gè)CPU都有一個(gè)L1 cache。一個(gè)cluster 內(nèi)的所有CPU共享一個(gè)L2 cache，L2 cache不區(qū)分指令和數(shù)據(jù)，都可以緩存。所有cluster之間共享L3 cache。L3 cache通過(guò)總線(xiàn)和主存相連。

多級(jí)cache之間的配合工作

首先引入兩個(gè)名詞概念，命中和缺失。CPU要訪(fǎng)問(wèn)的數(shù)據(jù)在cache中有緩存，稱(chēng)為“命中” (hit)，反之則稱(chēng)為“缺失” (miss)。多級(jí)cache之間是如何配合工作的呢？我們假設(shè)現(xiàn)在考慮的系統(tǒng)只有兩級(jí)cache。

inclusive cache(某一地址的數(shù)據(jù)可能存在多級(jí)緩存中) 當(dāng)CPU試圖從某地址load數(shù)據(jù)時(shí)，首先從L1 cache中查詢(xún)是否命中，如果命中則把數(shù)據(jù)返回給CPU 如果L1 cache缺失，則繼續(xù)從L2 cache中查找。當(dāng)L2 cache命中時(shí)，數(shù)據(jù)會(huì)返回給L1 cache以及CPU 如果L2 cache也缺失，很不幸，我們需要從主存中l(wèi)oad數(shù)據(jù)，將數(shù)據(jù)返回給L2 cache、L1 cache及CPU

exclusive cache 這種cache保證某一地址的數(shù)據(jù)緩存只會(huì)存在于多級(jí)cache其中一級(jí)

直接映射緩存(Direct mapped cache)

我們繼續(xù)引入一些cache相關(guān)的名詞。cache的大小稱(chēng)之為cahe size，代表cache可以緩存最大數(shù)據(jù)的大小。我們將cache平均分成相等的很多塊，每一個(gè)塊大小稱(chēng)之為cache line，其大小是cache line size。例如一個(gè)64 Bytes大小的cache。如果我們將64 Bytes平均分成64塊，那么cache line就是1字節(jié)，總共64行cache line。如果我們將64 Bytes平均分成8塊，那么cache line就是8字節(jié)，總共8行cache line。現(xiàn)在的硬件設(shè)計(jì)中，一般cache line的大小是4-128 Byts。

這里有一點(diǎn)需要注意，cache line是cache和主存之間數(shù)據(jù)傳輸?shù)淖钚挝?。什么意思呢？?dāng)CPU試圖load一個(gè)字節(jié)數(shù)據(jù)的時(shí)候，如果cache缺失，那么cache控制器會(huì)從主存中一次性的load cache line大小的數(shù)據(jù)到cache中。例如，cache line大小是8字節(jié)。CPU即使讀取一個(gè)byte，在cache缺失后，cache會(huì)從主存中l(wèi)oad 8字節(jié)填充整個(gè)cache line。

我們假設(shè)下面的講解都是針對(duì)64 Bytes大小的cache，并且cache line大小是8字節(jié)。我們可以類(lèi)似把這塊cache想想成一個(gè)數(shù)組，數(shù)組總共8個(gè)元素，每個(gè)元素大小是8字節(jié)。就像下圖這樣。

現(xiàn)在我們考慮一個(gè)問(wèn)題，CPU從0x0654地址讀取一個(gè)字節(jié)，cache控制器是如何判斷數(shù)據(jù)是否在cache中命中呢？cache大小相對(duì)于主存來(lái)說(shuō)，可謂是小巫見(jiàn)大巫。所以cache肯定是只能緩存主存中極小一部分?jǐn)?shù)據(jù)。我們?nèi)绾胃鶕?jù)地址在有限大小的cache中查找數(shù)據(jù)呢？現(xiàn)在硬件采取的做法是對(duì)地址進(jìn)行散列（可以理解成地址取模操作）。我們接下來(lái)看看是如何做到的？

我們一共有8行cache line，cache line大小是8 Bytes。所以我們可以利用地址低3 bits（如上圖地址藍(lán)色部分）用來(lái)尋址8 bytes中某一字節(jié)，我們稱(chēng)這部分bit組合為offset。同理，8行cache line，為了覆蓋所有行。我們需要3 bits（如上圖地址黃色部分）查找某一行，這部分地址部分稱(chēng)之為index?，F(xiàn)在我們知道，如果兩個(gè)不同的地址，其地址的bit3-bit5如果完全一樣的話(huà)，那么這兩個(gè)地址經(jīng)過(guò)硬件散列之后都會(huì)找到同一個(gè)cache line。所以，當(dāng)我們找到cache line之后，只代表我們?cè)L問(wèn)的地址對(duì)應(yīng)的數(shù)據(jù)可能存在這個(gè)cache line中，但是也有可能是其他地址對(duì)應(yīng)的數(shù)據(jù)。所以，我們又引入tag array區(qū)域，tag array和data array一一對(duì)應(yīng)。每一個(gè)cache line都對(duì)應(yīng)唯一一個(gè)tag，tag中保存的是整個(gè)地址位寬去除index和offset使用的bit剩余部分（如上圖地址綠色部分）。tag、index和offset三者組合就可以唯一確定一個(gè)地址了。因此，當(dāng)我們根據(jù)地址中index位找到cache line后，取出當(dāng)前cache line對(duì)應(yīng)的tag，然后和地址中的tag進(jìn)行比較，如果相等，這說(shuō)明cache命中。如果不相等，說(shuō)明當(dāng)前cache line存儲(chǔ)的是其他地址的數(shù)據(jù)，這就是cache缺失。

我們可以從圖中看到tag旁邊還有一個(gè)valid bit，這個(gè)bit用來(lái)表示cache line中數(shù)據(jù)是否有效（例如：1代表有效；0代表無(wú)效）。當(dāng)系統(tǒng)剛啟動(dòng)時(shí)，cache中的數(shù)據(jù)都應(yīng)該是無(wú)效的，因?yàn)檫€沒(méi)有緩存任何數(shù)據(jù)。cache控制器可以根據(jù)valid bit確認(rèn)當(dāng)前cache line數(shù)據(jù)是否有效。所以，上述比較tag確認(rèn)cache line是否命中之前還會(huì)檢查valid bit是否有效。只有在有效的情況下，比較tag才有意義。如果無(wú)效，直接判定cache缺失。

上面的例子中，cache size是64 Bytes并且cache line size是8 bytes。offset、index和tag分別使用3 bits、3 bits和42 bits（假設(shè)地址寬度是48 bits）。我們現(xiàn)在再看一個(gè)例子：512 Bytes cache size，64 Bytes cache line size。根據(jù)之前的地址劃分方法，offset、index和tag分別使用6 bits、3 bits和39 bits。如下圖所示。

直接映射緩存的優(yōu)缺點(diǎn)

直接映射緩存在硬件設(shè)計(jì)上會(huì)更加簡(jiǎn)單，因此成本上也會(huì)較低。根據(jù)直接映射緩存的工作方式，我們可以畫(huà)出主存地址0x00-0x88地址對(duì)應(yīng)的cache分布圖。

我們可以看到，地址0x00-0x3f地址處對(duì)應(yīng)的數(shù)據(jù)可以覆蓋整個(gè)cache。0x40-0x7f地址的數(shù)據(jù)也同樣是覆蓋整個(gè)cache。我們現(xiàn)在思考一個(gè)問(wèn)題，如果一個(gè)程序試圖依次訪(fǎng)問(wèn)地址0x00、0x40、0x80，cache中的數(shù)據(jù)會(huì)發(fā)生什么呢？首先我們應(yīng)該明白0x00、0x40、0x80地址中index部分是一樣的。因此，這3個(gè)地址對(duì)應(yīng)的cache line是同一個(gè)。所以，當(dāng)我們?cè)L問(wèn)0x00地址時(shí)，cache會(huì)缺失，然后數(shù)據(jù)會(huì)從主存中加載到cache中第0行cache line。當(dāng)我們?cè)L問(wèn)0x40地址時(shí)，依然索引到cache中第0行cache line，由于此時(shí)cache line中存儲(chǔ)的是地址0x00地址對(duì)應(yīng)的數(shù)據(jù)，所以此時(shí)依然會(huì)cache缺失。然后從主存中加載0x40地址數(shù)據(jù)到第一行cache line中。同理，繼續(xù)訪(fǎng)問(wèn)0x80地址，依然會(huì)cache缺失。這就相當(dāng)于每次訪(fǎng)問(wèn)數(shù)據(jù)都要從主存中讀取，所以cache的存在并沒(méi)有對(duì)性能有什么提升。訪(fǎng)問(wèn)0x40地址時(shí)，就會(huì)把0x00地址緩存的數(shù)據(jù)替換。這種現(xiàn)象叫做cache顛簸（cache thrashing）。針對(duì)這個(gè)問(wèn)題，我們引入多路組相連緩存。我們首先研究下最簡(jiǎn)單的兩路組相連緩存的工作原理。

兩路組相連緩存(Two-way set associative cache)

我們依然假設(shè)64 Bytes cache size，cache line size是8 Bytes。什么是路（way）的概念。我們將cache平均分成多份，每一份就是一路。因此，兩路組相連緩存就是將cache平均分成2份，每份32 Bytes。如下圖所示。

cache被分成2路，每路包含4行cache line。我們將所有索引一樣的cache line組合在一起稱(chēng)之為組。例如，上圖中一個(gè)組有兩個(gè)cache line，總共4個(gè)組。我們依然假設(shè)從地址0x0654地址讀取一個(gè)字節(jié)數(shù)據(jù)。由于cache line size是8 Bytes，因此offset需要3 bits，這和之前直接映射緩存一樣。不一樣的地方是index，在兩路組相連緩存中，index只需要2 bits，因?yàn)橐宦分挥?行cache line。上面的例子根據(jù)index找到第2行cache line（從0開(kāi)始計(jì)算），第2行對(duì)應(yīng)2個(gè)cache line，分別對(duì)應(yīng)way 0和way 1。因此index也可以稱(chēng)作set index（組索引）。先根據(jù)index找到set，然后將組內(nèi)的所有cache line對(duì)應(yīng)的tag取出來(lái)和地址中的tag部分對(duì)比，如果其中一個(gè)相等就意味著命中。

因此，兩路組相連緩存較直接映射緩存最大的差異就是：第一個(gè)地址對(duì)應(yīng)的數(shù)據(jù)可以對(duì)應(yīng)2個(gè)cache line，而直接映射緩存一個(gè)地址只對(duì)應(yīng)一個(gè)cache line。那么這究竟有什么好處呢？

兩路組相連緩存優(yōu)缺點(diǎn)

兩路組相連緩存的硬件成本相對(duì)于直接映射緩存更高。因?yàn)槠涿看伪容^tag的時(shí)候需要比較多個(gè)cache line對(duì)應(yīng)的tag（某些硬件可能還會(huì)做并行比較，增加比較速度，這就增加了硬件設(shè)計(jì)復(fù)雜度）。為什么我們還需要兩路組相連緩存呢？因?yàn)槠淇梢杂兄诮档蚦ache顛簸可能性。那么是如何降低的呢？根據(jù)兩路組相連緩存的工作方式，我們可以畫(huà)出主存地址0x00-0x4f地址對(duì)應(yīng)的cache分布圖。

我們依然考慮直接映射緩存一節(jié)的問(wèn)題“如果一個(gè)程序試圖依次訪(fǎng)問(wèn)地址0x00、0x40、0x80，cache中的數(shù)據(jù)會(huì)發(fā)生什么呢？”?，F(xiàn)在0x00地址的數(shù)據(jù)可以被加載到way 1，0x40可以被加載到way 0。這樣是不是就在一定程度上避免了直接映射緩存的尷尬境地呢？在兩路組相連緩存的情況下，0x00和0x40地址的數(shù)據(jù)都緩存在cache中。試想一下，如果我們是4路組相連緩存，后面繼續(xù)訪(fǎng)問(wèn)0x80，也可能被被緩存。

因此，當(dāng)cache size一定的情況下，組相連緩存對(duì)性能的提升最差情況下也和直接映射緩存一樣，在大部分情況下組相連緩存效果比直接映射緩存好。同時(shí)，其降低了cache顛簸的頻率。從某種程度上來(lái)說(shuō)，直接映射緩存是組相連緩存的一種特殊情況，每個(gè)組只有一個(gè)cache line而已。因此，直接映射緩存也可以稱(chēng)作單路組相連緩存。

全相連緩存(Full associative cache)

既然組相連緩存那么好，如果所有的cache line都在一個(gè)組內(nèi)。豈不是性能更好。是的，這種緩存就是全相連緩存。我們依然以64 Byts大小cache為例說(shuō)明。

由于所有的cache line都在一個(gè)組內(nèi)，因此地址中不需要set index部分。因?yàn)?，只有一個(gè)組讓你選擇，間接來(lái)說(shuō)就是你沒(méi)得選。我們根據(jù)地址中的tag部分和所有的cache line對(duì)應(yīng)的tag進(jìn)行比較（硬件上可能并行比較也可能串行比較）。哪個(gè)tag比較相等，就意味著命中某個(gè)cache line。因此，在全相連緩存中，任意地址的數(shù)據(jù)可以緩存在任意的cache line中。所以，這可以最大程度的降低cache顛簸的頻率。但是硬件成本上也是更高。

Cache分配策略(Cache allocation policy)

cache的分配策略是指我們什么情況下應(yīng)該為數(shù)據(jù)分配cache line。cache分配策略分為讀和寫(xiě)兩種情況。

讀分配(read allocation) 當(dāng)CPU讀數(shù)據(jù)時(shí)，發(fā)生cache缺失，這種情況下都會(huì)分配一個(gè)cache line緩存從主存讀取的數(shù)據(jù)。默認(rèn)情況下，cache都支持讀分配。

寫(xiě)分配(write allocation) 當(dāng)CPU寫(xiě)數(shù)據(jù)發(fā)生cache缺失時(shí)，才會(huì)考慮寫(xiě)分配策略。當(dāng)我們不支持寫(xiě)分配的情況下，寫(xiě)指令只會(huì)更新主存數(shù)據(jù)，然后就結(jié)束了。當(dāng)支持寫(xiě)分配的時(shí)候，我們首先從主存中加載數(shù)據(jù)到cache line中（相當(dāng)于先做個(gè)讀分配動(dòng)作），然后會(huì)更新cache line中的數(shù)據(jù)。

Cache更新策略(Cache update policy)

cache更新策略是指當(dāng)發(fā)生cache命中時(shí)，寫(xiě)操作應(yīng)該如何更新數(shù)據(jù)。cache更新策略分成兩種：寫(xiě)直通和回寫(xiě)。

寫(xiě)直通(write through) 當(dāng)CPU執(zhí)行store指令并在cache命中時(shí)，我們更新cache中的數(shù)據(jù)并且更新主存中的數(shù)據(jù)。cache和主存的數(shù)據(jù)始終保持一致。

寫(xiě)回(write back) 當(dāng)CPU執(zhí)行store指令并在cache命中時(shí)，我們只更新cache中的數(shù)據(jù)。并且每個(gè)cache line中會(huì)有一個(gè)bit位記錄數(shù)據(jù)是否被修改過(guò)，稱(chēng)之為dirty bit（翻翻前面的圖片，cache line旁邊有一個(gè)D就是dirty bit）。我們會(huì)將dirty bit置位。主存中的數(shù)據(jù)只會(huì)在cache line被替換或者顯示的clean操作時(shí)更新。因此，主存中的數(shù)據(jù)可能是未修改的數(shù)據(jù)，而修改的數(shù)據(jù)躺在cache中。cache和主存的數(shù)據(jù)可能不一致。

同時(shí)思考個(gè)問(wèn)題，為什么cache line大小是cache控制器和主存之間數(shù)據(jù)傳輸?shù)淖钚挝荒?？這也是因?yàn)槊總€(gè)cache line只有一個(gè)dirty bit。這一個(gè)dirty bit代表著整個(gè)cache line是否被修改的狀態(tài)。

Cache組織方式

但是，我們一直避開(kāi)了一個(gè)關(guān)鍵問(wèn)題。我們都知道cache控制器根據(jù)地址查找判斷是否命中，這里的地址究竟是虛擬地址(virtual address，VA)還是物理地址(physical address，PA)？

虛擬高速緩存(VIVT)

我們首先介紹的是虛擬高速緩存，這種cache硬件設(shè)計(jì)簡(jiǎn)單。在cache誕生之初，大部分的處理器都使用這種方式。虛擬高速緩存以虛擬地址作為查找對(duì)象。如下圖所示。

虛擬地址直接送到cache控制器，如果cache hit。直接從cache中返回?cái)?shù)據(jù)給CPU。如果cache miss，則把虛擬地址發(fā)往MMU，經(jīng)過(guò)MMU轉(zhuǎn)換成物理地址，根據(jù)物理地址從主存(main memory)讀取數(shù)據(jù)。但是，正是使用了虛擬地址作為tag，所以引入很多軟件使用上的問(wèn)題。操作系統(tǒng)在管理高速緩存正確工作的過(guò)程中，主要會(huì)面臨兩個(gè)問(wèn)題。歧義(ambiguity)和別名(alias)。為了保證系統(tǒng)的正確工作，操作系統(tǒng)負(fù)責(zé)避免出現(xiàn)歧義和別名。

歧義(ambiguity)

歧義是指不同的數(shù)據(jù)在cache中具有相同的tag和index。cache控制器判斷是否命中cache的依據(jù)就是tag和index，因此這種情況下，cache控制器根本沒(méi)辦法區(qū)分不同的數(shù)據(jù)。這就產(chǎn)生了歧義。什么情況下發(fā)生歧義呢？我們知道不同的物理地址存儲(chǔ)不同的數(shù)據(jù)，只要相同的虛擬地址映射不同的物理地址就會(huì)出現(xiàn)歧義。操作系統(tǒng)如何避免歧義的發(fā)生呢？當(dāng)我們切換進(jìn)程的時(shí)候，可以選擇flush所有的cache。flush cache操作有兩種：- 使主存儲(chǔ)器有效。針對(duì)write back高速緩存，首先應(yīng)該使主存儲(chǔ)器有效，保證已經(jīng)修改數(shù)據(jù)的cacheline寫(xiě)回主存儲(chǔ)器，避免修改的數(shù)據(jù)丟失。- 使高速緩存無(wú)效。保證切換后的進(jìn)程不會(huì)錯(cuò)誤的命中上一個(gè)進(jìn)程的緩存數(shù)據(jù)

因此，切換后的進(jìn)程剛開(kāi)始執(zhí)行的時(shí)候，將會(huì)由于大量的cache miss導(dǎo)致性能損失。所以，VIVT高速緩存明顯的缺點(diǎn)之一就是經(jīng)常需要flush cache以保證歧義不會(huì)發(fā)生，最終導(dǎo)致性能的損失。VIVT高速緩存除了面對(duì)歧義問(wèn)題外，還面臨另一個(gè)問(wèn)題：別名(alias)。

別名(alias)

當(dāng)不同的虛擬地址映射相同的物理地址，而這些虛擬地址的index不同，此時(shí)就發(fā)生了別名現(xiàn)象(多個(gè)虛擬地址被稱(chēng)為別名)。通俗點(diǎn)來(lái)說(shuō)就是指同一個(gè)物理地址的數(shù)據(jù)被加載到不同的cacheline中就會(huì)出現(xiàn)別名現(xiàn)象。

針對(duì)共享數(shù)據(jù)所在頁(yè)的映射方式采用nocache映射。例如上面的例子中，0x2000和0x4000映射物理地址0x8000的時(shí)候都采用nocache的方式，這樣不通過(guò)cache的訪(fǎng)問(wèn)，肯定可以避免這種問(wèn)題。但是這樣就損失了cache帶來(lái)的性能好處。這種方法既適用于不同進(jìn)程共享數(shù)據(jù)，也適用于同一個(gè)進(jìn)程共享數(shù)據(jù)。如果是不同進(jìn)程之間共享數(shù)據(jù)，還可以在進(jìn)程切換時(shí)主動(dòng)flush cache(使主存儲(chǔ)器有效和使高速緩存無(wú)效)的方式避免別名現(xiàn)象。但是，如果是同一個(gè)進(jìn)程共享數(shù)據(jù)該怎么辦？除了nocache映射之外，還可以有另一種解決方案。這種方法只針對(duì)直接映射高速緩存，并且使用了寫(xiě)分配機(jī)制有效。在建立共享數(shù)據(jù)映射時(shí)，保證每次分配的虛擬地址都索引到相同的cacheline。這種方式，后面還會(huì)重點(diǎn)說(shuō)。

物理高速緩存(PIPT)

基于對(duì)VIVT高速緩存的認(rèn)識(shí)，我們知道VIVT高速緩存存在歧義和名別兩大問(wèn)題。主要問(wèn)題原因是：tag取自虛擬地址導(dǎo)致歧義，index取自虛擬地址導(dǎo)致別名。所以，如果想讓操作系統(tǒng)少操心，最簡(jiǎn)單的方法是tag和index都取自物理地址。物理的地址tag部分是獨(dú)一無(wú)二的，因此肯定不會(huì)導(dǎo)致歧義。而針對(duì)同一個(gè)物理地址，index也是唯一的，因此加載到cache中也是唯一的cacheline，所以也不會(huì)存在別名。我們稱(chēng)這種cache為物理高速緩存，簡(jiǎn)稱(chēng)PIPT(Physically Indexed Physically Tagged)。PIPT工作原理如下圖所示。

CPU發(fā)出的虛擬地址經(jīng)過(guò)MMU轉(zhuǎn)換成物理地址，物理地址發(fā)往cache控制器查找確認(rèn)是否命中cache。雖然PIPT方式在軟件層面基本不需要維護(hù)，但是硬件設(shè)計(jì)上比VIVT復(fù)雜很多。因此硬件成本也更高。同時(shí)，由于虛擬地址每次都要翻譯成物理地址，因此在查找性能上沒(méi)有VIVT方式簡(jiǎn)潔高效，畢竟PIPT方式需要等待虛擬地址轉(zhuǎn)換物理地址完成后才能去查找cache。順便提一下，為了加快MMU翻譯虛擬地址的速度，硬件上也會(huì)加入一塊cache，作用是緩存虛擬地址和物理地址的映射關(guān)系，這塊cache稱(chēng)之為T(mén)LB(Translation Lookaside Buffer)。當(dāng)MMU需要轉(zhuǎn)換虛擬地址時(shí)，首先從TLB中查找，如果cache hit，則直接返回物理地址。如果cache miss則需要MMU查找頁(yè)表。這樣就加快了虛擬地址轉(zhuǎn)換物理地址的速度。如果系統(tǒng)采用的PIPT的cache，那么軟件層面基本不需要任何的維護(hù)就可以避免歧義和別名問(wèn)題。這是PIPT最大的優(yōu)點(diǎn)?，F(xiàn)在的CPU很多都是采用PIPT高速緩存設(shè)計(jì)。在Linux內(nèi)核中，可以看到針對(duì)PIPT高速緩存的管理函數(shù)都是空函數(shù)，無(wú)需任何的管理。

物理標(biāo)記的虛擬高速緩存(VIPT)

為了提升cache查找性能，我們不想等到虛擬地址轉(zhuǎn)換物理地址完成后才能查找cache。因此，我們可以使用虛擬地址對(duì)應(yīng)的index位查找cache，與此同時(shí)(硬件上同時(shí)進(jìn)行)將虛擬地址發(fā)到MMU轉(zhuǎn)換成物理地址。當(dāng)MMU轉(zhuǎn)換完成，同時(shí)cache控制器也查找完成，此時(shí)比較cacheline對(duì)應(yīng)的tag和物理地址tag域，以此判斷是否命中cache。我們稱(chēng)這種高速緩存為VIPT(Virtually Indexed Physically Tagged)。

VIPT以物理地址部分位作為tag，因此我們不會(huì)存在歧義問(wèn)題。但是，采用虛擬地址作為index，所以可能依然存在別名問(wèn)題。是否存在別名問(wèn)題，需要考慮cache的結(jié)構(gòu)，我們需要分情況考慮。

VIPT Cache為什么不存在歧義

在這里重點(diǎn)介紹下為什么VIPT Cache不存在歧義。假設(shè)以32位CPU為例，頁(yè)表映射最小單位是4KB。我們假設(shè)虛擬地址<12:4>位(這是一個(gè)有別名問(wèn)題的VIPT Cache)作為index，于此同時(shí)將虛擬地址<31:12>發(fā)送到MMU轉(zhuǎn)換得到物理地址的<31:12>，這里我們把<31:12>作為tag，并不是<31:13>。這地方很關(guān)鍵，也就是說(shuō)VIPT的tag取決于物理頁(yè)大小的剩余位數(shù)，而不是去掉index和offset的剩余位數(shù)。物理tag是惟一的，所以不存在歧義。

VIPT Cache什么情況不存在別名

我們知道VIPT的優(yōu)點(diǎn)是查找cache和MMU轉(zhuǎn)換虛擬地址同時(shí)進(jìn)行，所以性能上有所提升。歧義問(wèn)題雖然不存在了，但是別名問(wèn)題依舊可能存在，那么什么情況下別名問(wèn)題不會(huì)存在呢？Linux系統(tǒng)中映射最小的單位是頁(yè)，一頁(yè)大小是4KB。那么意味著虛擬地址和其映射的物理地址的位<11...0>是一樣的。針對(duì)直接映射高速緩存，如果cache的size小于等于4KB，是否就意味著無(wú)論使用虛擬地址還是物理地址的低位查找cache結(jié)果都是一樣呢？是的，因?yàn)樘摂M地址和物理地址對(duì)應(yīng)的index是一樣的。這種情況，VIPT實(shí)際上相當(dāng)于PIPT，軟件維護(hù)上和PIPT一樣。如果示例是一個(gè)四路組相連高速緩存呢？只要滿(mǎn)足一路的cache的大小小于等于4KB，那么也不會(huì)出現(xiàn)別名問(wèn)題。

VIPT Cache的別名問(wèn)題

假設(shè)系統(tǒng)使用的是直接映射高速緩存，cache大小是8KB，cacheline大小是256字節(jié)。這種情況下的VIPT就存在別名問(wèn)題。因?yàn)閕ndex來(lái)自虛擬地址位<12...8>，虛擬地址和物理地址的位<11...8>是一樣的，但是bit12卻不一定相等。假設(shè)虛擬地址0x0000和虛擬地址0x1000都映射相同的物理地址0x4000。那么程序讀取0x0000時(shí)，系統(tǒng)將會(huì)從物理地址0x4000的數(shù)據(jù)加載到第0x00行cacheline。然后程序讀取0x1000數(shù)據(jù)，再次把物理地址0x4000的數(shù)據(jù)加載到第0x10行cacheline。這不，別名出現(xiàn)了。相同物理地址的數(shù)據(jù)被加載到不同cacheline中。

如何解決VIPT Cache別名問(wèn)題

我們接著上面的例子說(shuō)明。首先出現(xiàn)問(wèn)題的場(chǎng)景是共享映射，也就是多個(gè)虛擬地址映射同一個(gè)物理地址才可能出現(xiàn)問(wèn)題。我們需要想辦法避免相同的物理地址數(shù)據(jù)加載到不同的cacheline中。如何做到呢？那我們就避免上個(gè)例子中0x1000映射0x4000的情況發(fā)生。我們可以將虛擬地址0x2000映射到物理地址0x4000，而不是用虛擬地址0x1000。0x2000對(duì)應(yīng)第0x00行cacheline，這樣就避免了別名現(xiàn)象出現(xiàn)。因此，在建立共享映射的時(shí)候，返回的虛擬地址都是按照cache大小對(duì)齊的地址，這樣就沒(méi)問(wèn)題了。如果是多路組相連高速緩存的話(huà)，返回的虛擬地址必須是滿(mǎn)足一路cache大小對(duì)齊。在Linux的實(shí)現(xiàn)中，就是通過(guò)這種方法解決別名問(wèn)題。

不存在的PIVT高速緩存

按照排列組合來(lái)說(shuō)，應(yīng)該還存在一種PIVT方式的高速緩存。因?yàn)镻IVT沒(méi)有任何優(yōu)點(diǎn)，卻包含以上的所有缺點(diǎn)。你想想，PIVT方式首先要通過(guò)MMU轉(zhuǎn)換成物理地址，然后才能根據(jù)物理地址index域查找cache。這在速度上沒(méi)有任何優(yōu)勢(shì)，而且還存在歧義和別名問(wèn)題。請(qǐng)忘記它吧。不，應(yīng)該不算是忘記，因?yàn)樗鼜膩?lái)就沒(méi)出現(xiàn)過(guò)。

總結(jié)

VIVT Cache問(wèn)題太多，軟件維護(hù)成本過(guò)高，是最難管理的高速緩存。所以現(xiàn)在基本只存在歷史的文章中。現(xiàn)在我們基本看不到硬件還在使用這種方式的cache?，F(xiàn)在使用的方式是PIPT或者VIPT。如果多路組相連高速緩存的一路的大小小于等于4KB，一般硬件采用VIPT方式，因?yàn)檫@樣相當(dāng)于PIPT，豈不美哉。當(dāng)然，如果一路大小大于4KB，一般采用PIPT方式，也不排除VIPT方式，這就需要操作系統(tǒng)多操點(diǎn)心了。

編輯：黃飛