本文參考了：git

• courses.cs.washington.edu/courses/cse…
• Cache performance measurement and metric
• Cache placement policies

簡述

相信你確定對這一張圖很熟悉了（若是仍是第一次據說就請關掉此頁面吧：））。越靠近 CPU，速度越快，可是容量小且價格昂貴。如何可以高效利用緩存（LEVEL 1），是操做系統中很是重要的一環。github

上篇文章中，咱們有講到同一個 CPU 中的 core 之間會對 last-level cache產生競爭，從而影響系統性能。UMA 架構下，假如一個 CPU 裏面有多個 threads 運行在不一樣 core 中，能夠將其中一個 core 上的 thread 移動到其餘核，從而緩解了對 last-level cahce 的競爭，達到提升速度的目的（咱們也講了這種方法在 NUMA 架構中不適用，具體緣由請看上篇文章）。緩存

Last-level cache 競爭給性能帶來影響的緣由是顯而易見的，由於 cahce 大小有限，其中一個 thread 佔據一部分 cache，頗有多是會把其餘 cache 的擠佔掉的。這種現象是 cache miss中的一種。cache miss 的大小是衡量緩存效率的重要指標。微信

此篇文章將先講講 cache 一些基礎的知識，後面再逐步深刻。架構

Direct Mapped Cache

下圖中，main memory 有16個 bytes，cache 有4個 bytes。app

簡單來說，就是把main memory 中的 0,4,8,12映射到 cache 的0；1,5,9,13映射到 cache 的2… 對，就是取模運算。這回答了咱們的第一個問題。post

這種方法叫作Direct Mapped Cache，是最簡單的一種 map方法，效率也不是最高的，還有幾種能夠經過如下連接查看 : en.wikipedia.org/wiki/Cache_…性能

若是要是複雜點，能夠看下維基百科上的這張圖，原地址以下： en.wikipedia.org/wiki/Cache_…學習

從 cache 中讀數據

用上面的方法，能夠很容易知道 main memory 某個 byte 的數據在 cache 的什麼位置，可是要知道有不少個不一樣的 block 指向cache 裏同一個位置。fetch

能夠把 main memory 的最高位做爲 tag，存在cache 裏面，如圖：

這樣，好比cache 中一個 entry 的 index 爲01，他的 tag 爲11，對應的 main memory 地址就是tag + index，即1101。

再進一步，加上一個 valid bit，用來表示該 cache block是不是合法的。

• 最開始的時候，cache 是空的，因此這個 bit 都是0.
• 當有數據被 load 到這個 block 的時候，這個 bit 就變成了1.

cache hit 的時候會發生什麼？

咱們已經知道該如何經過 main memory 的地址從 cache 中找數據了，若是正如咱們所意，確實成功在 cache 中獲取到了，這一段發生了什麼呢？

當 CPU 須要從 memory 中read 數據的時候，地址會發送給 cache controller：

• address 的最低幾位會對應到 cache 中的某個 block
• 如何 valid bit 是1，且tag 位是匹配的，就說明cache 成功 hit 了，就能夠把data 返回給 CPU 了

以下圖：

cache miss 的時候會發生什麼？

CPU 從cache 中獲取數據能夠達到 ns 級，若是是 cache miss 了，就得先把main memory 的數據load 到 cache。 如今 data 已經從 main memory 中讀取到了，經過如下步驟load 到 cache：

• 低位的 k 位指定了cache block的位置
• 高位的(m-k)位存在 cache block 的tag 位
• main memory 的 data 數據拷貝到 cache 的 data field
• 將 valid bit 置爲1

如圖：

再講講cache miss

首先 cache miss 相比 cache hit 的性能差別是數量級的，應該儘量減小 cache miss 的概率。cache miss 有不少種緣由，這裏講最主要的兩種，詳細列表請看： en.wikipedia.org/wiki/Cache_…

• 沒法避免的 miss：全部的 cache 最開始確定都是不在 cache 中的，因此這必然須要先從 main memory 中 load 進來。（除非試用 prefetch： en.wikipedia.org/wiki/Cache_… ）
• 衝突致使 miss：這種 miss 以前該數據已經在 cache 裏面，可是被另外的程序搶佔了。（回顧一下上篇文章講的 last-level cache 競爭~這種能夠經過調度來解決）

Spatial locality

前面都是一個 byte 爲一個 block 的。咱們有一個這樣的假設，訪問一個 address，下一次訪問頗有可能會訪問臨近的某一個 address。這個假設大多數狀況下都是正確的。這個假設就叫作Spatial locality，那該如何實現這種假設？能夠增長每一個block的大小。

如今將每一個 cache block 的大小設置爲2個 bytes，因而咱們就能夠一次性 load 兩個 bytes 的數據。當咱們要 load 位置12的數據到 cache 的時候，同時也會把位置13的也 load 過去。

這時候，能夠把 main memory 也劃分紅兩個 byte 一個 block。byte address 和 block address 的對應關係也很簡單，0和1對應一個 block address：0。

導入 cache 的過程也很以前同樣，沒什麼好贅述的：如今從 main memory 中 load 第12或者第13個byte，都會同時12,13這兩個 byte load 過去。

總結

Cache資源對於整個系統性能的影響巨大，關於如何設計 cache，調度 cache 資源的方法、論文層出不窮。此文講的Direct Mapped Cache是最最簡單的，可是對於咱們理解 cache 有很大幫助。後面咱們還會繼續深刻學習一下 cache。

最後，gakki 式求贊~

廣告時間，歡迎你們關注個人微信公衆號。同時本文同步於 github： github.com/liaochangji…