為什麼需要 CPU 快取#
CPU 的快取（Cache）被設計來解決記憶體存取過慢的問題。在記憶體階層（Memory Hierarchy）中：
- 越快的記憶體容量越小
- 離 CPU 越遠，速度越慢
可能會有人問：那為什麼不直接加大 Cache 或 Register？答案很簡單：價格太貴。以 Intel i7-8700K 為例：
- L1 Cache: 384 KiB
- L2 Cache: 1.5 MiB
- L3 Cache: 12 MiB
速度上 L1 > L2 > L3。Cache 大小都是 MB 級，若擴充到 GB 級甚至 TB 級，整台電腦就會貴到不像話了。
CPU 中的 Register 數量不多且容量更小，只能供運算使用。若沒有 Cache，CPU 就需要反覆讀取主記憶體（RAM）。有了 Cache，CPU 可以在指令執行前進行 data prefetch，將需要用到的資料事先取出來。但 Cache 成本高，無法把所有資料都塞進去，所以需要一套機制決定哪些資料要被快取。
Cache 組成#
從小到大三層結構：
- cache line：cache 的最小單位
- cache set：cache line 的集合
cache_set = ["cache_line", "cache_line", "cache_line"]- cache：cache set 的集合
cache = ["cache_set", "cache_set", "cache_set"]Cache 的存取策略#
因為成本考量，Cache 大小有限，所以要設計快取機制決定哪些資料要被快取。
Direct Mapped Cache#
Direct Mapped 把資料直接映射到一條 cache line 上。可以想像：一個班級有 1 - 50 號座號，Cache 也分配了 50 個位置（第 1 個位置只有 1 號的同學能入座）。問題在於：如果有 20 個班級，就有可能造成多個來自不同班級卻同號碼的學生爭搶一個位置，讓彼此不斷被替換出去。
Fully Associative#
Fully Associative 簡單多了：50 個位置，誰都能坐，不需要按座號入座。所以可以讓不同班級座號相同的學生同時待在 Cache 中。
但缺點也很明顯：若要尋找特定的同學，最壞情況需要查找 50 個位置才能得知是否有入座。
N-way Set Associative Cache#
為了結合兩者優點，電腦科學家提出 N-way Set Associative：把 50 個位置拆成 5 組，每組 10 個位置，第一組可讓任一班級的 1 - 10 號入座，依此類推。查找範圍縮小到一個 set 內的 N 條 line。
Cache miss#
Cache miss 有三種情況：
| 類型 | 別稱 | 說明 |
|---|---|---|
| Compulsory misses（強制性） | cold start misses | 第一次存取未曾在 cache 內的 block 而發生的 miss，這種 miss 是不可避免的。 |
| Capacity misses（容量性） | — | 程式執行期間，cache 無法包含所有需要的 block 而產生的 miss。發生在一個 block 被取代後，稍後又需要用到。 |
| Conflict misses（衝突性） | collision misses | 發生在 set-associative 或 direct-mapped caches。當多個 block 競爭相同的 set。 |
Cache 的替換策略#
當 conflict misses 發生時，常見三種替換方法：
| 替換策略 | 作法 | 優缺點 |
|---|---|---|
| FIFO（First In First Out） | 將集合中最早進入的區塊替換掉 | 實作非常容易，但容易把重要資料替換掉 |
| Random | 隨機挑選一個區塊替換 | — |
| LRU（Least Recently Used） | 替換掉最近最少使用的資料 | 實作上比 FIFO 複雜，但能避免頻繁使用的資料被換掉 |
Cache 機制的其他應用#
除了 CPU 中的 Cache，Cache 思維也廣泛出現在其他地方。以作業系統的檔案系統為例：磁碟非常慢，如果所有資料都等到要用時才讀，IO 延遲會非常高。為了解決這個問題，作業系統會在檔案系統中實作一層 Buffer cache，把常用資料存放在 RAM 中，配合 LRU 等替換策略。
多核心時代的同步問題#
Cache 大幅提升處理器效率，但在多核心世代，它也為資料同步帶來麻煩。假設一顆處理器中有 4 個實體核心，每個核心都有獨立的 Cache，當複數個核心都 Cache 了同一筆資料並對其做了修改，就會讓資料發生非預期的運算結果。
60 分的解法#
學過系統程式的同學可能想到：那我用 Lock 機制保護這些資料？
但這是循環論證：Lock 的實作也是仰賴記憶體變數做紀錄，如果今天多個實體核心的 Cache 都保存了同一道鎖的狀態（未上鎖），就又讓多個核心同時拿到鎖了。
機制完整的解法#
完整的解法需要 Cache Coherence（快取一致性）協定，例如 MESI 等，會在後續作業系統章節詳述。
重點整理#
- 記憶體階層的目的：用便宜的大容量配上昂貴的小容量，模擬出「又快又大」的存取體驗。
- Cache 的三種對應方式（Direct / Fully / N-way）反映了「速度 vs. 命中率 vs. 硬體成本」的取捨。
- Cache miss 分為 compulsory / capacity / conflict 三類，理解後才能對症下藥（增加容量？提高 associativity？換替換策略？）。
- 多核時代 Cache 帶來新的同步問題，必須靠快取一致性協定來解決。
原文出處#
- 原書/iThome：https://ithelp.ithome.com.tw/articles/10264830