深入理解 Cache 工作原理

1、為什么需要 Cache

1.1 為什么需要 Cache

1.2 實(shí)際系統(tǒng)中的 Cache

1.3 Cache 的分類

• 按照數(shù)據(jù)類型劃分：I-Cache與D-Cache。其中I-Cache負(fù)責(zé)放置指令，D-Cache負(fù)責(zé)方式數(shù)據(jù)。兩者最大的不同是D-Cache里的數(shù)據(jù)可以寫回，I-Cache是只讀的。

  
  

• 按照大小劃分：分為small Cache和large Cache。沒(méi)路組（后文組相連介紹）<4KB叫small Cache, 多用于L1 Cache, 大于4KB叫l(wèi)arge Cache。多用于L2及其他Cache.

  
  

• 按照位置劃分：Inner Cache和Outer Cache。一般獨(dú)屬于CPU微架構(gòu)的叫Inner Cache, 例如上圖的L1 L2 CACHE。不屬于CPU微架構(gòu)的叫outer Cache.

  
  

• 按照數(shù)據(jù)關(guān)系劃分：Inclusive/exclusive Cache: 下級(jí)Cache包含上級(jí)的數(shù)據(jù)叫inclusive Cache。不包含叫exclusive Cache。舉個(gè)例子，L3 Cache里有L2 Cache的數(shù)據(jù)，則L2 Cache叫exclusive Cache。

  
  

2、Cache的工作原理

• 數(shù)據(jù)如何放置

  
  

• 數(shù)據(jù)如何查詢

  
  

• 數(shù)據(jù)如何被替換

  
  

• 如果發(fā)生了寫操作，Cache如何處理

  
  

2.1 數(shù)據(jù)如何放置

• 全相連（Fully associative）?？梢苑旁贑ache的任何位置。

  
  

• 直接映射（Direct mapped）。只允許放在Cache的某一行。比如12 mod 8

  
  

• 組相連（set associative）?？梢苑旁贑ache的某幾行。例如2路組相連，一共有4組，所以可以放在0,1位置中的一個(gè)。

  
  

2.2 如何在Cache中找數(shù)據(jù)

2.3 如何替換Cache中的數(shù)據(jù)

• 隨機(jī)替換。如果發(fā)生Cache miss里隨機(jī)替換掉一塊。

  
  

• Least recently used. LRU。最近使用的塊最后替換。

  
  

• First in, first out (FIFO), 先進(jìn)先出。

  
  

• 不在本 Cache 替換。如果Cache miss了，直接轉(zhuǎn)發(fā)訪問(wèn)地址到主存，取到的數(shù)據(jù)不會(huì)寫到Cache.

  
  

• 在讀MISS時(shí)替換。如果讀的時(shí)候Cache里沒(méi)有該數(shù)據(jù)，則從主存讀取該數(shù)據(jù)后寫入Cache。

  
  

• 在寫MISS時(shí)替換。如果寫的時(shí)候Cache里沒(méi)有該數(shù)據(jù)，則將本數(shù)據(jù)調(diào)入Cache再寫。

  
  

2.4 如果發(fā)生了寫操作怎么辦

• 通寫：直接把數(shù)據(jù)寫回Cache的同時(shí)寫回主存。極其影響寫速度。

  
  

• 回寫：先把數(shù)據(jù)寫回Cache, 然后當(dāng)Cache的數(shù)據(jù)被替換時(shí)再寫回主存。

  
  

• 通寫隊(duì)列：通寫與回寫的結(jié)合。先寫回一個(gè)隊(duì)列，然后慢慢往主存儲(chǔ)寫。如果多次寫同一個(gè)數(shù)據(jù)，直接寫這個(gè)隊(duì)列。避免頻繁寫主存。

  
  

3、Cache一致性

策略一：基于監(jiān)聽(tīng)的一致性策略

策略二：基于目錄的一致性策略

• SI: 對(duì)于一個(gè)數(shù)據(jù)塊來(lái)講，有share和invalid兩種狀態(tài)。如果是share狀態(tài)，直接通知其他Cache, 將對(duì)應(yīng)的塊置為無(wú)效。

  
  

• MSI：對(duì)于一個(gè)數(shù)據(jù)塊來(lái)講，有share和invalid，modified三種狀態(tài)。其中modified狀態(tài)表表示該數(shù)據(jù)只屬于這個(gè)Cache, 被修改過(guò)了。當(dāng)這個(gè)數(shù)據(jù)被逐出Cache時(shí)更新主存。這么做的好處是避免了大量的主從寫入。同時(shí)，如果是invalid時(shí)寫該數(shù)據(jù)，就要保證其他所有Cache里該數(shù)據(jù)的標(biāo)志位不為M，負(fù)責(zé)要先寫回主存儲(chǔ)。

  
  

• MESI：對(duì)于一個(gè)數(shù)據(jù)來(lái)講，有4個(gè)狀態(tài)。modified, invalid, shared, exclusive。其中exclusive狀態(tài)用于標(biāo)識(shí)該數(shù)據(jù)與其他Cache不依賴。要寫的時(shí)候直接將該Cache狀態(tài)改成M即可。

  
  

• 如果其他Cache里有這份數(shù)據(jù)，如果其他Cache里是M態(tài)，先 把M態(tài)寫回主存再讀。否則直接讀。最終狀態(tài)變?yōu)镾。

  
  

• 其他Cache里沒(méi)這個(gè)數(shù)據(jù)，直接變到E狀態(tài)。

  
  

• 如果發(fā)生了處理器讀操作，仍然在S態(tài)。

  
  

• 如果發(fā)生了處理器寫操作，則跳轉(zhuǎn)到M狀態(tài)。

  
  

• 如果其他Cache發(fā)生了寫操作，跳到I態(tài)。

  
  

• 發(fā)生了處理器讀操作還是E。

  
  

• 發(fā)生了處理器寫操作變成M。

  
  

• 如果其他Cache發(fā)生了讀操作，變到S狀態(tài)。

  
  

• 發(fā)生了讀操作依舊是M態(tài)。

  
  

• 發(fā)生了寫操作依舊是M態(tài)。

  
  

• 如果其他Cache發(fā)生了讀操作，則將數(shù)據(jù)寫回主存儲(chǔ)，變換到S態(tài)。

  
  

4、總結(jié)

作者：桔里貓

https://zhuanlan.zhihu.com/p/386919471