ARM920T的MMU與Cache之cache

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

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

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

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

圖 18. 直接映射Cache

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

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

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

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

有了前面兩種Cache概念的基礎(chǔ)，這種Cache應(yīng)該很好理解，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中的任何一條，依此類推。為什么說組相聯(lián)Cache是全相聯(lián)和直接映射Cache的一個折衷呢？如果把組分得很大，把全部Cache Line都分到一個組里面去，就變成了全相聯(lián)Cache；如果把組分得很小，每組只有一個Cache Line，就變成了直接映射Cache。作為練習(xí)，請讀者自己計算一下為什么VA Tag是VA[31:8]，為什么組的編號用VA[7:5]表示。

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

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

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

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

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

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

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

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

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

圖 20. PA Tag

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

表 2. 頁描述符中C、B位的含義

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