來源：https://zhuanlan.zhihu.com/p/386919471
可以隨便到網上查一查，各大互聯網公司筆試面試特別喜歡考一道演算法題，即 LRU快取機制，又順手查了一下LRU快取機制最近有哪些企業喜歡考察，超級大熱門！
今天給大家分享一篇關于 Cache 的硬核的技術文，基本上關于Cache的所有知識點都可以在這篇文章里看到，
關于 Cache 這方面內容圖比較多，不想自己畫了，所以圖都來自《Computer Architecture : A Quantitative Approach》，
這是一本體系架構方面的神書，推薦大家看一下，
本文主要內容如下，基本涉及了Cache的概念，作業原理，以及保持一致性的入門內容，
為什么需要 Cache
1.1 為什么需要 Cache
我們首先從一張圖來開始講為什么需要 Cache，
上圖是 CPU 性能和 Memory 存盤器訪問性能的發展，
我們可以看到，隨著工藝和設計的演進，CPU 計算性能其實發生了翻天覆地的變化，但是DRAM存盤性能的發展沒有那么快，
所以造成了一個問題，存盤限制了計算的發展，
容量與速度不可兼得，
如何解決這個問題呢？可以從計算訪問資料的規律入手，
我們隨便貼段代碼:
for (j = 0; j < 100; j = j + 1)
for( i = 0; i < 5000; i = i + 1)
x[i][j] = 2 * x[i][j];
可以看到，由于大量回圈的存在，我們訪問的資料其實在記憶體中的位置是相近的，
換句專業點的話說，我們訪問的資料有區域性，
我們只需要將這些資料放入一個小而快的存盤中，這樣就可以快速訪問相關資料了，
總結起來，Cache是為了給CPU提供高速存盤訪問，利用資料區域性而設計的小存盤單元，
1.2 實際系統中的 Cache
我們展示一下實際系統中的 Cache ，
如上圖所示，整個系統的存盤架構包括了 CPU 的暫存器，L1/L2/L3 CACHE，DRAM 和硬碟，
資料訪問時先找暫存器，暫存器里沒有找 L1 Cache, L1 Cache 里沒有找 L2 Cache 依次類推，最后找到硬碟中，
同時，我們可以看到，速度與存盤容量的折衷關系，容量越小，訪問速度越快！
其中，一個概念需要搞清楚，
CPU 和 Cache 是 word 傳輸的，而 Cache 到主存是以塊傳輸的，一塊大約 64Byte ，
現有 SOC 中的 Cache 一般組成如下，
1.3 Cache 的分類
Cache按照不同標準分類可以分為若干類，
- 按照資料型別劃分：I-Cache與D-Cache，其中I-Cache負責放置指令，D-Cache負責方式資料，兩者最大的不同是D-Cache里的資料可以寫回，I-Cache是只讀的，
- 按照大小劃分：分為small Cache和large Cache，沒路組（后文組相連介紹）<4KB叫small Cache, 多用于L1 Cache, 大于4KB叫large Cache，多用于L2及其他Cache.
- 按照位置劃分：Inner Cache和Outer Cache，一般獨屬于CPU微架構的叫Inner Cache, 例如上圖的L1 L2 CACHE，不屬于CPU微架構的叫outer Cache.
- 按照資料關系劃分：Inclusive/exclusive Cache: 下級Cache包含上級的資料叫inclusive Cache，不包含叫exclusive Cache，舉個例子，L3 Cache里有L2 Cache的資料，則L2 Cache叫exclusive Cache，
Cache的作業原理
要講清楚 Cache 的作業原理，需要回答 4 個問題：
- 資料如何放置
- 資料如何查詢
- 資料如何被替換
- 如果發生了寫操作，Cache如何處理
2.1 資料如何放置
這個問題也好解決，我們舉個簡單的栗子來說明問題，
假設我們主存中有 32 個塊，而我們的 Cache 一共有 8 個 Cache 行( 一個 Cache 行放一行資料），
假設我們要把主存中的塊 12 放到 Cache 里，
那么應該放到 Cache 里什么位置呢？
三種方法：
- 全相連（Fully associative），可以放在Cache的任何位置，
- 直接映射（Direct mapped），只允許放在Cache的某一行，比如12 mod 8
- 組相連（set associative），可以放在Cache的某幾行，例如2路組相連，一共有4組，所以可以放在0,1位置中的一個，
可以看到，全相連和直接映射是Cache組相連的兩種極端情況，
不同的放置方式主要影響有兩點：
1、組相連組數越大，比較電路就越大，但Cache利用率更高，Cache miss發生的概率小，
2、組相連數目變小，Cache經常發生替換，但是比較電路比較小，
這也好理解，記憶體中的塊在Cache中可放置的位置多，自然找起來就麻煩，
2.2 如何在Cache中找資料
其實找資料就是一個比對程序，如下圖所示，
我們地址都以 Byte 為單位的，
但主存于Cache之間的資料交換單位都是塊（block，現代Cache一般一個block大約64Byte)，所以地址對最后幾位是block offset，
由于我們采用了組相連，則還有幾個位元代表的是存盤到了哪個組，
組內放著若干資料，我們需要比較Tag, 如果組內有Tag出現，則說明我們訪問的資料在快取中，可以開心的使用了，
比如舉個 2 路組相連的例子，如下圖所示，
T表示Tag，直接比較Tag，就能得知是不是命中了，如果命中了，則根據index(組號）將對應的塊取出來即可，
如上圖所示，用index選出位于組相連的哪個組，然后并行的比較Tag, 判斷最后是不是在Cache中，上圖是2路組相連，也就是說兩組并行比較，
那如果不在快取中呢？這就涉及到另一個問題，
不在快取中如何替換 Cache ？
2.3 如何替換Cache中的資料
Cache中的資料如何被替換的？這個就比較簡單直接，
- 隨機替換，如果發生Cache miss里隨機替換掉一塊，
- Least recently used. LRU，最近使用的塊最后替換，
- First in, first out (FIFO), 先進先出，
實際上第一個不怎么使用，LRU 和 FIFO 根據實際情況選擇即可，
Cache 在什么時候資料會被替換內？也有幾種策略，
- 不在本 Cache 替換，如果Cache miss了，直接轉發訪問地址到主存，取到的資料不會寫到Cache.
- 在讀MISS時替換，如果讀的時候Cache里沒有該資料，則從主存讀取該資料后寫入Cache，
- 在寫MISS時替換，如果寫的時候Cache里沒有該資料，則將本資料調入Cache再寫，
2.4 如果發生了寫操作怎么辦
Cache畢竟是個臨時快取，
如果發生了寫操作，會造成Cache和主存中的資料不一致，如何保證寫資料操作正確呢？
也有三種策略，
- 通寫：直接把資料寫回Cache的同時寫回主存，極其影響寫速度，
- 回寫：先把資料寫回Cache, 然后當Cache的資料被替換時再寫回主存，
- 通寫佇列：通寫與回寫的結合，先寫回一個佇列，然后慢慢往主存盤寫，如果多次寫同一個資料，直接寫這個佇列，避免頻繁寫主存，
Cache 一致性
Cache 一致性是 Cache 中遇到的比較坑的一個問題，
什么原因需要 Cache 處理一致性呢？
主要是多核系統中，假如core 0讀了主存盤的資料，寫了資料，core 1也讀了主從的資料，這個時候core 1并不知道資料已經被改動了，也就是說，core 1 Cache中的資料過時了，會產生錯誤，
Cache一致性的保證就是讓多核訪問不出錯，
Cache一致性主要有兩種策略，
策略一：基于監聽的一致性策略
這種策略是所有Cache均監聽各Cache的寫操作，如果一個Cache中的資料被寫了，有兩種處理辦法，
寫更新協議：某個Cache發生寫了，就索性把所有Cache都給更新了，
寫失效協議：某個Cache發生寫了，就把其他Cache中的該資料塊置為無效，
策略 1 由于監聽起來成本比較大，所以只應用于極簡單的系統中，
策略二：基于目錄的一致性策略
這種策略是在主存處維護一張表，記錄各資料塊都被寫到了哪些Cache, 從而更新相應的狀態，一般來講這種策略采用的比較多，又分為下面幾個常用的策略，
- SI: 對于一個資料塊來講，有share和invalid兩種狀態，如果是share狀態，直接通知其他Cache, 將對應的塊置為無效，
- MSI：對于一個資料塊來講，有share和invalid，modified三種狀態，其中modified狀態表表示該資料只屬于這個Cache, 被修改過了，當這個資料被逐出Cache時更新主存，這么做的好處是避免了大量的主從寫入，同時，如果是invalid時寫該資料，就要保證其他所有Cache里該資料的標志位不為M，負責要先寫回主存盤，
- MESI：對于一個資料來講，有4個狀態，modified, invalid, shared, exclusive，其中exclusive狀態用于標識該資料與其他Cache不依賴，要寫的時候直接將該Cache狀態改成M即可，
我們著重講講 MESI，圖中黑線：CPU的訪問，紅線：總線的訪問，其他Cache的訪問，
當前狀態時I狀態時，如果發生處理器讀操作 prrd，
- 如果其他Cache里有這份資料，如果其他Cache里是M態，先 把M態寫回主存再讀，否則直接讀，最終狀態變為S，
- 其他Cache里沒這個資料，直接變到E狀態，
當前狀態為S態
- 如果發生了處理器讀操作，仍然在S態，
- 如果發生了處理器寫操作，則跳轉到M狀態，
- 如果其他Cache發生了寫操作，跳到I態，
當前狀態E態
- 發生了處理器讀操作還是E，
- 發生了處理器寫操作變成M，
- 如果其他Cache發生了讀操作，變到S狀態，
當前狀態M態
- 發生了讀操作依舊是M態，
- 發生了寫操作依舊是M態，
- 如果其他Cache發生了讀操作，則將資料寫回主存盤，變換到S態，
總結
Cache 在計算機體系架構中有非常重要的地位，本文講了 Cache中最主要的內容，具體細節可以再根據某個點深入研究，
近期熱文推薦：
1.1,000+ 道 Java面試題及答案整理(2022最新版)
2.勁爆！Java 協程要來了，，，
3.Spring Boot 2.x 教程，太全了！
4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優雅的方式！！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/443445.html
標籤：Java