ARM920T的MMU與Cache之cache

設計Cache的一種最樸素的想法是，把VA分成以32字節為單位，從任何一個(gè)對齊到32字節地址邊界的VA開(kāi)始連續的32個(gè)字節（比如0x00-0x1f，0x20-0x3f，0x40-0x5f等等）都可以緩存到512條Cache Line中的任何一條。那么一條Cache Line中的32個(gè)字節怎么知道是來(lái)自哪個(gè)VA的呢？這就需要把VA也保存在Cache中，由于這32字節的起始地址是對齊到32字節地址邊界的，末5位全為0，因此只需要保存VA[31:5]即可，這稱(chēng)為VA Tag[4]，Tag是VA的一部分，是Cache Line中數據的標識，表明這32字節數據來(lái)自哪個(gè)VA。這樣設計的Cache稱(chēng)為全相聯(lián)Cache（Fully Associative Cache），圖示如下：

圖 17. 全相聯(lián)Cache

給定一個(gè)VA，如何在Cache中查找對應的數據呢？首先到Cache中比較查找哪一行的Tag等于VA[31:5]，找到對應的Cache Line后，再根據VA[4:0]決定要訪(fǎng)問(wèn)的是該Cache Line緩存的32個(gè)字節中的哪一個(gè)字節。由于有512條Cache Line，如果這個(gè)VA沒(méi)有緩存在Cache中則需要比較512次才知道，這是最壞的情況，也是最常見(jiàn)的情況，下面我們要改進(jìn)Cache的設計來(lái)解決這個(gè)問(wèn)題。

全相聯(lián)Cache的特點(diǎn)是任何VA都可以緩存到任何一條Cache Line，給定一個(gè)VA做查找時(shí)，由于它有可能緩存在512條Cache Line中的任何一條，就只好全部都找一遍了。如果限定某一個(gè)VA只允許緩存在某一條Cache Line中，那么查找的過(guò)程就快多了：檢查一下應該緩存這個(gè)VA的那條Cache Line，看Tag一致不一致，如果一致就是Cache Hit，如果不一致就是Cache Miss，可以直接訪(fǎng)問(wèn)物理內存而不必再找其它Cache Line了。這種設計稱(chēng)為直接映射Cache（Direct Mapped Cache），如下圖所示：

圖 18. 直接映射Cache

地址0~31應該緩存在第1條Cache Line中，地址32~63應該緩存在第2條Cache Line中，依此類(lèi)推，地址16352~16383應該緩存在第512條Cache Line中，下一個(gè)地址應該是16384（16K）了，我們又回到開(kāi)頭，地址16K~16K+31應該緩存在第1條Cache Line中，地址16K+32~16K+63應該緩存在第2條Cache Line中，依此類(lèi)推，再次回到開(kāi)頭的地址應該是32K，32K~32K+31應該緩存在第1條Cache Line中，32K+32~32K+63應該緩存在第2條Cache Line中，依此類(lèi)推。讀者應該可以總結出規律了：給定一個(gè)VA，將它除以16K得的余數決定了它應該緩存在哪一條Cache Line中，那么除以16K的商數部分就應該是VA Tag，用以區別Cache Line中緩存的到底是0還是16K還是32K地址上的數據。那么除以16K的商數和余數怎么表示呢？VA[31:14]就是除以16K的商數，VA[13:0]就是余數，所以上圖的Tag處標著(zhù)VA[31:14]。余數VA[13:0]是16K Cache里的一個(gè)字節偏移量，而Cache是按32字節一個(gè)Cache Line組織的，所以余數中的高位VA[13:5]決定了是第幾條Cache Line，余數中的低位VA[4:0]決定了Cache Line內的字節偏移量。驗算一下，VA[13:5]一共是9位，作為Cache Line的編號可以表示的Cache Line數目正是512條。

直接映射Cache雖然查找速度很快，但也有缺點(diǎn)。比如，地址0~31、16K~16K+31、32K~32K+31都應該緩存到第1條Cache Line中，假如我們程序第一次訪(fǎng)問(wèn)地址30，地址0~31的數據就從內存加載到第1條Cache Line，以便下次訪(fǎng)問(wèn)能更快一些，但是我們程序第二次訪(fǎng)問(wèn)的卻是地址32770，地址32K~32K+31的數據就要從內存加載到第1條Cache Line，把Cache Line里原來(lái)存的地址0~31的數據替換掉，以便下次訪(fǎng)問(wèn)能更快一些，但是我們程序第三次訪(fǎng)問(wèn)的卻是地址16392……這樣下去，Cache起不到任何加速作用，形同虛設，這種問(wèn)題稱(chēng)為Cache抖動(dòng)（Cache Thrash）。全相聯(lián)Cache就不會(huì )有這種問(wèn)題，因為任何VA都可以緩存到任何一條Cache Line，可以把先后幾次訪(fǎng)問(wèn)的VA緩存到不同的Cache Line，就不會(huì )相互沖突。

全相聯(lián)Cache和直接映射Cache各有優(yōu)缺點(diǎn)，全相聯(lián)Cache查找很慢，但沒(méi)有抖動(dòng)問(wèn)題，直接映射Cache則正相反。為了得到更好的性能，實(shí)際CPU的Cache設計是取兩者的折衷，把所有Cache Line分成若干個(gè)組，每一組有n條Cache Line，稱(chēng)為n路組相聯(lián)Cache（n-way Set Associative Cache）。ARM920T采用64路組相聯(lián)Cache，如下圖所示：

圖 19. 64路組相聯(lián)Cache

有了前面兩種Cache概念的基礎，這種Cache應該很好理解，512條Cache Line分成8組，每組64條，地址0-31、256-587、512-543等等可以緩存到第1組64條Cache Line中的任何一條，地址32-63、288-319、544-575等等可以緩存到第2組64條Cache Line中的任何一條，依此類(lèi)推。為什么說(shuō)組相聯(lián)Cache是全相聯(lián)和直接映射Cache的一個(gè)折衷呢？如果把組分得很大，把全部Cache Line都分到一個(gè)組里面去，就變成了全相聯(lián)Cache；如果把組分得很小，每組只有一個(gè)Cache Line，就變成了直接映射Cache。作為練習，請讀者自己計算一下為什么VA Tag是VA[31:8]，為什么組的編號用VA[7:5]表示。

那么，為什么組相聯(lián)Cache的性能比直接映射Cache要好呢？一方面，組相聯(lián)Cache把一條Cache Line上的沖突分散到了64條Cache Line上，起到了64倍的積極作用。而另一方面，應該緩存到同一個(gè)組的VA更多了：對于直接映射Cache，在同一個(gè)組（也就是同一條Cache Line）互相沖突的VA有4G/512個(gè)；對于組相聯(lián)Cache，在同一個(gè)組（64條Cache Line）互相沖突的VA有4G/8個(gè)。從這個(gè)數量關(guān)系來(lái)看，組相聯(lián)Cache又起到了64倍的消極作用。難道這兩種作用不會(huì )完全抵銷(xiāo)嗎？我不打算從數學(xué)上嚴格證明，這不是本節的重點(diǎn)，讀者可以通過(guò)一個(gè)生活常識的例子來(lái)理解：層數一樣多的兩棟樓，其中一棟樓是一部電梯，每層三戶(hù)，而另一棟樓是兩部電梯，每層六戶(hù)，每戶(hù)的平均人數一樣多，你認為在哪個(gè)樓里等電梯的時(shí)間較短呢？

接下來(lái)解釋一下有關(guān)Cache寫(xiě)回內存的問(wèn)題。Cache寫(xiě)回內存有兩種模式：

Write Back：Cache Line中的數據被CPU核修改時(shí)并不立刻寫(xiě)回內存，Cache Line和內存中的數據會(huì )暫時(shí)不一致，在Cache Line中有一個(gè)Dirty位標記這一情況。當一條Cache Line要被其它VA的數據替換時(shí)，如果不是Dirty的就直接替換掉，如果是Dirty的就先寫(xiě)回內存再替換。

Write Through：每當CPU核修改Cache Line中的數據時(shí)就立刻寫(xiě)回內存，Cache Line和內存中的數據總是一致的。如果有多個(gè)CPU或設備同時(shí)訪(fǎng)問(wèn)內存，例如采用雙口RAM，那么Cache中的數據和內存保持一致就非常重要了，這時(shí)相關(guān)的內存頁(yè)面通常配置為Write Through模式。

通過(guò)讀寫(xiě)CP15的相關(guān)寄存器，可以對Cache做以下操作：

Clean：將Cache Line中的數據寫(xiě)回內存，清除Dirty位。在程序中的某些同步點(diǎn)上用于確保Cache Line和內存中的數據一致。

Invalidate：在Cache Line中有一個(gè)Invalid位表示無(wú)效，將這個(gè)位置1，下次要訪(fǎng)問(wèn)時(shí)即使VA Tag匹配也重新從內存讀取數據。例如進(jìn)程切換時(shí)需要聲明前一個(gè)進(jìn)程緩存在Cache中的數據無(wú)效。

Lock：將某個(gè)地址的數據鎖定在Cache中，確保不被替換掉。在實(shí)時(shí)系統中，這樣做可以保證某個(gè)地址的數據能在一個(gè)確定的時(shí)間內訪(fǎng)問(wèn)到。

從Cache中查找要訪(fǎng)問(wèn)的數據時(shí)用的是VA，但是Cache寫(xiě)回內存要用PA，如果寫(xiě)回內存時(shí)還需要查一遍頁(yè)表就太沒(méi)有效率了，所以實(shí)際上每條Cache Line中還保存了PA[31:5]（PA Tag），完整的Cache構造如下圖所示：

圖 20. PA Tag

最后解決我們前面遺留的一個(gè)問(wèn)題：頁(yè)描述符中的C、B位具體是什么意思？

表 2. 頁(yè)描述符中C、B位的含義

C位為1表示允許Cache，這種情況下用B位來(lái)表示W(wǎng)rite Through還是Write Back。有些頁(yè)面不允許Cache，置C位為0，這種情況下可以用B位來(lái)選擇是否允許使用Write Buffer。Write Buffer也是一種簡(jiǎn)單的Cache，CPU核執行寫(xiě)指令時(shí)可以把數據交給Write Buffer，然后由Write Buffer負責寫(xiě)回內存，這時(shí)CPU可以執行后續指令而不必等待寫(xiě)回內存這個(gè)較慢的操作結束。想一下，既然有Write Buffer，為什么沒(méi)有Read Buffer？