前言：來(lái)吧，繼續(xù)補(bǔ) Cache 的知識(shí)。

替換算法

還記得組相聯(lián)嗎？就是主存中的一塊可以放在 Cache 中的一組中的任意一行。但是 Cache 滿了怎么辦？就得覆蓋掉一個(gè)，覆蓋掉哪一個(gè)？這就是替換算法要解決的。

不去說(shuō)什么先進(jìn)先出、隨機(jī)替換的算法。直接上最難的——最近最少用算法 LRU（least-recently used）

LRU

關(guān)鍵就是：總是把最近最少用的那一塊淘汰掉

在具體到硬件的時(shí)候，Cache 每一行都有一個(gè)計(jì)數(shù)器。用來(lái)記錄少用的次數(shù)。

具體看這個(gè)圖：

現(xiàn)在有四個(gè)格子，但是有 5 個(gè)不一樣的塊要進(jìn)來(lái)，我一步一步給你解釋。

• 1 來(lái)，沒有命中，1 進(jìn)入緩存。計(jì)數(shù)器為 0
• 2 來(lái)，沒有命中，2 進(jìn)入緩存。2 計(jì)數(shù)器 0, 1計(jì)數(shù)器為 1（對(duì)應(yīng)第三條）
• 3 來(lái)同上
• 4 來(lái)同上
• 1 又來(lái)，命中，1 的計(jì)數(shù)器變?yōu)?0。其余加 1。
• 2 又來(lái)，命中，2 的計(jì)數(shù)器變?yōu)?0。其余加 1。
• 5 來(lái)了，但是現(xiàn)在 Cache 滿了。去掉哪一個(gè)呢？計(jì)數(shù)器最大的那個(gè)！
• 之后的就不說(shuō)了

做題！

為了鞏固上面的知識(shí)，我們來(lái)做題

MRU 的算法我們就不做了

假設(shè)主存以字為單位（16 位）先解決：「主存地址劃分」

主存地址 = 主存標(biāo)簽 + 組號(hào) + 塊內(nèi)地址

• 所以塊內(nèi)地址就是 6 位。因?yàn)閴K的大小是 64 字，有 64 個(gè)單元

• 由于是 4 路組相聯(lián)。并且總大小是 4K 字。每一組的大小是 4 × 64 字。相除得到 4 。所以組號(hào)就是 4 位。

• 標(biāo)志位：由于告訴你主存空間大小是 32K × 16 位。所以剩下的就是標(biāo)志位

所以得到：

現(xiàn)在要循環(huán)訪問 0~4351 10次

• 當(dāng)訪問 0 時(shí)，未命中，把 0~63 所有內(nèi)容搬到緩存中，后來(lái)全命中

• 當(dāng)訪問 64 時(shí)，未命中，把 64~127 所有內(nèi)容搬到緩存中，后來(lái)全命中

• ......（把 4352 分為每塊 64 個(gè)，一共 68 塊的塊 ）

• 當(dāng)訪問 64~67 塊（從 0 開始數(shù)）時(shí)，都不在緩存中，要替換。

第一次循環(huán)結(jié)束

第二次循環(huán)開始的時(shí)候，一共會(huì)有 20 個(gè)塊要替換。

每次循環(huán)都是這樣

所以：

命中率為：

再放個(gè)圖感受一下。。。（我是不是沒講清楚。。。）

寫策略

為什么要保持 Cache 和主存中數(shù)據(jù)的一致？

• 因?yàn)?Cache 中的內(nèi)容是主存塊副本，當(dāng)對(duì) Cache 中的內(nèi)容進(jìn)行更新時(shí)，就存在 Cache 和主存如何保持一致的問題。

• 當(dāng)多個(gè)設(shè)備都允許訪問主存時(shí)

  例如： I/O 設(shè)備可直接讀寫內(nèi)存時(shí)，如果 Cache 中的內(nèi)容被修改，則 I/O 設(shè)備讀出的對(duì)應(yīng)主存單元的內(nèi)容無(wú)效；若 I/O 設(shè)備修改了主存單元的內(nèi)容，則 Cache 中對(duì)應(yīng)的內(nèi)容無(wú)效。

• 當(dāng)多個(gè) CPU 都帶有各自的 Cache 而共享主存時(shí)某個(gè) CPU 修改了自身 Cache 中的內(nèi)容，則對(duì)應(yīng)的主存單元和其他 CPU 中對(duì)應(yīng)的內(nèi)容都變?yōu)闊o(wú)效。

寫操作也有兩種情況：

• 寫命中（Write Hit）：要寫的單元已經(jīng)在 Cache 中
• 寫不命中（Write Miss）：要寫的單元不在 Cache 中

寫策略

寫命中：

• Write Through（通過式寫、寫直達(dá)、直寫）

  同時(shí)寫 Cache 和主存單元。但是經(jīng)常要和主存操作，速度太慢?？梢允褂脤懢彌_，并行操作。

• Write Back（一次性寫、寫回、回寫）

  只寫 cache 不寫主存，缺失（沒找到）時(shí)一次寫回。每行有個(gè)修改位（叫做 dirty 位），大大降低主存帶寬需求，控制可能很復(fù)雜。

寫不命中

• Write Allocate（寫分配）

  將主存裝入 Cache 中，然后更新相應(yīng)單元。這樣可以利用空間局部特性，但是每次都要讀一個(gè)塊。速度慢

• Not Write Allocate（非寫分配）

  直接寫主存單元，不把主存放入 Cache 中。

現(xiàn)代的計(jì)算機(jī)當(dāng)然存在多級(jí) Cache，我就不繼續(xù)深挖了。。。