存儲(chǔ)器山

首先上 CSAPP 的存儲(chǔ)器山鎮(zhèn)文￣□￣。雖然說(shuō) Java 程序員不像 C 程序員需要特別關(guān)心內(nèi)存分配等操作耐薯，但是學(xué)習(xí)下計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)蜓陌，明確各個(gè)層次的存儲(chǔ)器特性，對(duì)寫(xiě)高性能的代碼還是很有幫助的含友。所以基于“深入理解計(jì)算機(jī)系統(tǒng)”替裆，一起學(xué)習(xí)下存儲(chǔ)器相關(guān)的一些知識(shí)。

存儲(chǔ)器分類(lèi)

存儲(chǔ)器系統(tǒng)是一個(gè)不同容量窘问、成本和訪問(wèn)時(shí)間的存儲(chǔ)設(shè)備的層次結(jié)構(gòu)辆童。越靠近 CPU 的存儲(chǔ)器越快也越貴、越小惠赫，從磁盤(pán)上讀取信息比從 DRAM 中讀取慢了 10 萬(wàn)倍把鉴，比 SRAM 慢了 100 萬(wàn)倍。計(jì)算機(jī)巧妙的運(yùn)用了各種存儲(chǔ)器的特性儿咱，構(gòu)建了一個(gè)既運(yùn)行高效又支持大容量存儲(chǔ)的系統(tǒng)庭砍。

SRAM

SRAM 全稱(chēng)“Static Random Access Memory”，之所以被稱(chēng)為“靜態(tài)”存儲(chǔ)器混埠，是因?yàn)橹灰须姷「祝蜁?huì)永遠(yuǎn)保持它的值。即使有干擾來(lái)擾亂電壓钳宪，當(dāng)干擾消除時(shí)揭北，依然會(huì)恢復(fù)到穩(wěn)定值。而一旦斷電吏颖，里面的數(shù)據(jù)就會(huì)丟失了搔体。SRAM 對(duì)諸如光和電噪聲這樣干擾不敏感，是因?yàn)?SRAM 比 DRAM 使用了更多的晶體管侦高，因而密集度較低嫉柴，也就更貴，功耗更大奉呛。

由于 SRAM 速度快计螺、容量小夯尽、價(jià)格貴，所以多用來(lái)制造高速緩存登馒，如現(xiàn)在計(jì)算機(jī)中基本都有的 L1匙握，L2，L3 緩存陈轿。

DRAM

DRAM 全稱(chēng)“Dynamic Random Access Memory”圈纺，相比 SRAM，DRAM 需要定時(shí)刷新麦射，所以也被稱(chēng)為“動(dòng)態(tài)”存儲(chǔ)器蛾娶。DRAM 每個(gè)單元由一個(gè)電容和一個(gè)晶體管組成，由于組成簡(jiǎn)單潜秋，所以 DRAM 可以制造的非常密集蛔琅，因而容量可以做的較大。但DRAM 對(duì)干擾非常敏感峻呛。因?yàn)閿?shù)據(jù)存儲(chǔ)在電容里面泪勒，而電容會(huì)不斷漏電弊予，所以要定時(shí)刷新，才能保證數(shù)據(jù)不會(huì)丟失举户。

DRAM 由于容量大详民、價(jià)格便宜玻粪，多用來(lái)制作計(jì)算機(jī)主存周叮，或者各種顯卡的顯存等揩尸。

ROM

ROM 全程“Read Only Memory”方面，由于歷史原因话肖，雖然 ROM 中有的類(lèi)型即可以讀也可以寫(xiě)，但是他們整體上被稱(chēng)為只讀存儲(chǔ)器葡幸。相比于 SRAM，DRAM 最大的不同就是斷電后不會(huì)丟失信息贺氓，因?yàn)槭欠且资源鎯?chǔ)器蔚叨。

存儲(chǔ)在 ROM 中的程序通常被稱(chēng)為“固件”，當(dāng)計(jì)算機(jī)通電后就會(huì)運(yùn)行存儲(chǔ)在 ROM 中的固件辙培，例如我們所熟知的 BIOS 程序蔑水，就存儲(chǔ)在 ROM 中，每次計(jì)算機(jī)開(kāi)機(jī)會(huì)引導(dǎo)操作系統(tǒng)啟動(dòng)扬蕊。復(fù)雜的設(shè)備搀别，如顯卡和磁盤(pán)驅(qū)動(dòng)控制器，也依賴(lài)固件翻譯來(lái)自 CPU 的 I/O 請(qǐng)求尾抑。

磁盤(pán)

磁盤(pán)是由“盤(pán)片”構(gòu)成歇父，每個(gè)盤(pán)片有兩面或者一面稱(chēng)為“表面”蒂培，表面覆蓋著磁性記錄材料。盤(pán)片中央有一個(gè)旋轉(zhuǎn)主軸榜苫，使得盤(pán)片以固定的旋轉(zhuǎn)速率旋轉(zhuǎn)护戳，通常 5400 ~ 15000 轉(zhuǎn)/分鐘。磁盤(pán)通常包含一個(gè)或多個(gè)盤(pán)片垂睬，并封閉在一個(gè)容器中媳荒。

磁盤(pán)的表面由一組組稱(chēng)為“磁道”的同心圓組成，每個(gè)磁道被劃分為一組“扇區(qū)”驹饺，每個(gè)扇區(qū)包含相同數(shù)量的數(shù)據(jù)位（通常 512 byte)钳枕。扇區(qū)之間由一些間隙分隔開(kāi)，間隙不存儲(chǔ)數(shù)據(jù)位赏壹，只用來(lái)標(biāo)識(shí)扇區(qū)的格式化位鱼炒。

盤(pán)片	磁盤(pán)

磁盤(pán)容量

一個(gè)磁盤(pán)可以記錄的最大位數(shù)稱(chēng)為他的容量。磁盤(pán)容量由以下技術(shù)因素決定：

• 記錄密度：磁道一英寸的段中可以放入的位數(shù)卡儒。
• 磁道密度：從盤(pán)片中心向外半徑一英寸可以有的磁道數(shù)田柔。

磁盤(pán)的容量 = 字節(jié)數(shù)/扇區(qū) * 平均扇區(qū)數(shù)/磁道 * 磁道數(shù)/表面 * 表面數(shù)/盤(pán)片 * 盤(pán)片數(shù)/磁盤(pán)

磁盤(pán)操作

磁盤(pán)用“讀/寫(xiě)頭”來(lái)讀寫(xiě)存儲(chǔ)在磁性表面的位，讀寫(xiě)頭連接到一個(gè)傳動(dòng)臂骨望。通過(guò)沿著半徑軸前后移動(dòng)傳動(dòng)臂硬爆，可以將讀/寫(xiě)頭定位到期望磁道，這個(gè)過(guò)程稱(chēng)為“尋道”擎鸠。有多個(gè)盤(pán)面的磁盤(pán)針對(duì)每個(gè)盤(pán)面都有一個(gè)獨(dú)立的讀/寫(xiě)頭缀磕，讀/寫(xiě)頭垂直排列，一致行動(dòng)劣光，在任何時(shí)刻袜蚕，所有讀/寫(xiě)頭都位于同一柱面上。

讀寫(xiě)	統(tǒng)一移動(dòng)

磁盤(pán)以扇區(qū)大小的塊來(lái)讀寫(xiě)數(shù)據(jù)绢涡，對(duì)扇區(qū)的訪問(wèn)時(shí)間主要由下面幾個(gè)部分決定牲剃。

• 尋道時(shí)間：移動(dòng)傳動(dòng)臂到指定磁道上的時(shí)間。現(xiàn)在驅(qū)動(dòng)器中平均尋到時(shí)間通常是 3~9 ms雄可，并且受限于物理性能局限凿傅，很難再縮小。
• 旋轉(zhuǎn)時(shí)間：讀/寫(xiě)頭到指定磁道后数苫，需要等待磁盤(pán)旋轉(zhuǎn)到目標(biāo)扇區(qū)聪舒，目標(biāo)扇區(qū)第一個(gè)位旋轉(zhuǎn)到讀/寫(xiě)頭下的時(shí)間為旋轉(zhuǎn)時(shí)間。以 7200 轉(zhuǎn)磁盤(pán)為例虐急，平均旋轉(zhuǎn)時(shí)間約為 4ms箱残。
• 傳送時(shí)間：從讀取扇區(qū)第一個(gè)位到扇區(qū)讀取完畢的時(shí)間為傳送時(shí)間，主要取決于磁盤(pán)的旋轉(zhuǎn)速度及磁道的扇區(qū)數(shù)目止吁。相比于尋道時(shí)間及旋轉(zhuǎn)時(shí)間被辑，傳送時(shí)間很小基本可以忽略不計(jì)燎悍。

由于尋道時(shí)間和旋轉(zhuǎn)時(shí)間大致相等，所以經(jīng)常用尋道時(shí)間*2 來(lái)估算磁盤(pán)訪問(wèn)時(shí)間敷待。

邏輯磁盤(pán)塊

為了對(duì)操作系統(tǒng)隱藏磁盤(pán)構(gòu)造的復(fù)雜性间涵，現(xiàn)代磁盤(pán)將其構(gòu)造呈現(xiàn)為一個(gè)簡(jiǎn)單的視圖：一個(gè) B 個(gè)扇區(qū)大小的邏輯塊序列，編號(hào)為0榜揖，1勾哩，...，B-1举哟。磁盤(pán)中有一個(gè)小的硬件稱(chēng)為磁盤(pán)控制器思劳，維護(hù)著邏輯塊號(hào)與實(shí)際磁盤(pán)扇區(qū)的映射關(guān)系。

當(dāng)操作系統(tǒng)想要讀寫(xiě)一個(gè)磁盤(pán)的扇區(qū)數(shù)據(jù)時(shí)候妨猩，將會(huì)發(fā)送一個(gè)命令到磁盤(pán)控制器潜叛，讓他讀取某個(gè)邏輯塊號(hào)。磁盤(pán)控制器將邏輯塊號(hào)翻譯成一個(gè)（盤(pán)面壶硅，磁道威兜，扇區(qū)）的三元組，唯一的標(biāo)識(shí)了對(duì)應(yīng)的物理扇區(qū)庐椒。然后將讀/寫(xiě)頭移動(dòng)到相應(yīng)的物理扇區(qū)椒舵，進(jìn)行讀寫(xiě)操作。

磁盤(pán)讀取

固態(tài)硬盤(pán)

固態(tài)硬盤(pán)（SSD）是一種基于閃存的存儲(chǔ)技術(shù)约谈，有一個(gè)或多個(gè)閃存芯片和閃存翻譯層組成笔宿。閃存芯片替代傳統(tǒng)磁盤(pán)中的機(jī)械驅(qū)動(dòng)器，閃存翻譯層則是類(lèi)似于磁盤(pán)控制器的存在棱诱。

固態(tài)硬盤(pán)

相比傳統(tǒng)磁盤(pán)泼橘，SSD 有很多優(yōu)點(diǎn)。由于由半導(dǎo)體存儲(chǔ)器構(gòu)成迈勋，因而隨機(jī)訪問(wèn)時(shí)間比旋轉(zhuǎn)磁盤(pán)要快很多炬灭，功耗更低，也更結(jié)實(shí)靡菇。同樣也有一些缺點(diǎn)担败，閃存塊會(huì)磨損，因而 SSD 壽命較普通磁盤(pán)短镰官。SSD 較傳統(tǒng)磁盤(pán)價(jià)格更貴，因而常用的存儲(chǔ)容量也比傳統(tǒng)磁盤(pán)較小吗货。

硬件技術(shù)趨勢(shì)

硬件技術(shù)趨勢(shì)

上圖是各種硬件按年統(tǒng)計(jì)的運(yùn)行速度泳唠，可以看出，雖然 SRMA 的性能滯后于 CPU 的性能宙搬，但是在持續(xù)保持增長(zhǎng)笨腥，追趕 CPU 的增長(zhǎng)曲線拓哺。而 DRAM 和磁盤(pán)的性能增長(zhǎng)緩慢，嚴(yán)重滯后于 CPU 的性能脖母，與 CPU 性能之間的差距在不斷擴(kuò)大士鸥。

CPU 在 2003 年開(kāi)始出現(xiàn)變化，是由于當(dāng)時(shí)無(wú)法再通過(guò)增加 CPU 的頻率來(lái)提升性能谆级，因?yàn)檫@樣芯片的功耗會(huì)太大烤礁。解決辦法就是用多個(gè)小處理器取代單個(gè)大處理器，從而提升性能肥照。CPU 頻率在 2003 年達(dá)到了最低點(diǎn)脚仔，上升后又開(kāi)始以比以前慢一些的速率下降。不過(guò)舆绎，CPU 的有效周期時(shí)間還是以接近以前的速率持續(xù)下降鲤脏。

局部性

從上面我們可以看到不同硬件的運(yùn)行效率差距簡(jiǎn)直天壤之別，那么計(jì)算機(jī)是如何將這些運(yùn)行效率差異如此之大的硬件組合在一起吕朵，并能保證高效運(yùn)行呢猎醇？這里就要了解一個(gè)很重要的概念--局部性原理。

一個(gè)編寫(xiě)良好的計(jì)算機(jī)程序常常有良好的“局部性”努溃。也就是硫嘶，它們傾向于引用的數(shù)據(jù)項(xiàng)多臨近與其他最近引用過(guò)的數(shù)據(jù)項(xiàng)，或者是最近引用過(guò)的數(shù)據(jù)項(xiàng)本身茅坛。這種傾向性音半，被稱(chēng)為“局部性原理”。這是一個(gè)很重要的概念贡蓖，對(duì)硬件和軟件系統(tǒng)的設(shè)計(jì)和性能都有著極大的影響曹鸠。

局部性有兩種不同的形式：

• 時(shí)間局部性：被引用過(guò)的內(nèi)存位置很可能在不遠(yuǎn)的將來(lái)再被多次引用。
• 空間局部性：如果一個(gè)內(nèi)存位置被引用了一次斥铺，那么程序很可能在不遠(yuǎn)的將來(lái)引用其附近的一個(gè)位置彻桃。

/**
 * 局部性驗(yàn)證小程序
 * @author 魚(yú)蠻 on 2021/11/1
 **/
public class Locality extends AbstractBenchMark {

    /**
     * 緩存組是8路的，所以需要大于8才會(huì)比較明顯的緩存沖突情況
     */
    final static int ROW = 16;
    
    /**
     * Core i7晾蜘，L1 d-cache是32KB邻眷，L2 cache 是256K，這個(gè)值可以根據(jù) cache 情況調(diào)整
     * 一個(gè)Integer值16byte剔交，32KB/16byte=2048肆饶，數(shù)組的一行正好可以填充滿L1緩存
     */
    final static int COLUMN = 2048;

    static Integer[][] arr;

    @Benchmark
    public void locality() {
        int tmp = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COLUMN; j++) {
                tmp += arr[i][j];
            }
        }
    }

    @Benchmark
    public void noneLocality() {
        int tmp = 0;
        for (int j = 0; j < COLUMN; j++) {
            for (int i = 0; i < ROW; i++) {
                tmp += arr[i][j];
            }
        }
    }
    
    static {
        int counter = 0;
        arr = new Integer[ROW][COLUMN];
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COLUMN; j++) {
                // 主要Integer的常量池影響
                arr[i][j] = new Integer(counter++);
            }
        }
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(Locality.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();

        /// 用來(lái)打印數(shù)據(jù)內(nèi)存地址，來(lái)實(shí)際驗(yàn)證
        printAddress(arr[0][0]);
        printAddress(arr[0][1]);
        printAddress(arr[1][0]);
    }

    public static void printAddress(Object o) {
        System.out.println("number:" + o + ",address:"+ Long.toHexString(VM.current().addressOf(o)) + "##" + Long.toBinaryString(VM.current().addressOf(o)));
    }
}

可以用上面的小程序來(lái)驗(yàn)證局部性的重要性岖常，兩種方式的運(yùn)行效率差距還是比較大的驯镊。

Benchmark              Mode  Cnt      Score      Error  Units
Locality.locality      avgt    5  18587.618 ± 1567.916  ns/op
Locality.noneLocality  avgt    5  37490.564 ± 5833.672  ns/op

存儲(chǔ)器層次結(jié)構(gòu)

基于各種存儲(chǔ)技術(shù)特性及局部性原理，硬件和軟件可以很好的互相補(bǔ)充。它們這種互相補(bǔ)充的性質(zhì)使人們想到一種組織存儲(chǔ)系統(tǒng)的方法板惑，稱(chēng)為“存儲(chǔ)器層次結(jié)構(gòu)”橄镜，所有的現(xiàn)代計(jì)算機(jī)系統(tǒng)都使用了這種方法。下圖展示了一個(gè)典型的存儲(chǔ)器層次結(jié)構(gòu)冯乘。一般洽胶，從高處往底層走，存儲(chǔ)設(shè)備變的更慢裆馒、更大姊氓、更便宜。

存儲(chǔ)器層次

緩存

一般而言领追，緩存是一個(gè)相對(duì)小而快速的設(shè)備他膳，他作為儲(chǔ)存在更大、更慢的設(shè)備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域绒窑。在存儲(chǔ)器層次結(jié)構(gòu)中棕孙，任何一層都可以看做是其下一層的緩存。在計(jì)算機(jī)系統(tǒng)中些膨，緩存主要是為了加速 CPU 的訪問(wèn)蟀俊，畢竟 CPU 跟底層的存儲(chǔ)系統(tǒng)運(yùn)行效率差距巨大。

在 CSAPP 里面老師描述緩存舉得例子特別形象：對(duì)一個(gè)學(xué)生來(lái)說(shuō)订雾，家就好比主存肢预，里面有各種各樣的東西。而背包就好比高速緩存洼哎，只裝了你最需要的東西烫映。當(dāng)你從書(shū)包拿出課本的時(shí)候可以很快，否則你就需要跑回家拿噩峦。

現(xiàn)代操作系統(tǒng)可以說(shuō)是各種緩存的集合锭沟，如下表所見(jiàn)，從 CPU 都瀏覽器识补，到時(shí)都運(yùn)用了緩存技術(shù)族淮。

緩存數(shù)據(jù)總是以塊大小為傳送單元，在第 k 層跟 k+1 層之間來(lái)回拷貝凭涂。相鄰層次之間塊大小是固定的祝辣，但其他層次對(duì)之間可以有不同的塊大小。L1 和 L0 之間傳送通常使用 1 個(gè)字的塊切油，L2 和 L1蝙斜、L3 和 L2、L4 和 L3 之間傳遞通常使用幾十個(gè)字節(jié)的塊澎胡。而 L5 跟 L4 之間傳遞通常用幾百或者幾千字節(jié)的塊孕荠。一般而言離CPU越遠(yuǎn)的設(shè)備訪問(wèn)時(shí)間越長(zhǎng)绢片，為了補(bǔ)償這些時(shí)間，傾向于使用較大的塊岛琼。

緩存不命中

緩存不命中主要分為三類(lèi)：

• 冷不命中：一個(gè)空的緩存被稱(chēng)為冷緩存，此類(lèi)不命中稱(chēng)為冷不命中巢株。應(yīng)對(duì)這種情況就是在使用前需要暖身（warm up）槐瑞，也就是常說(shuō)的預(yù)熱。
• 沖突不命中：由于緩存的容量限制阁苞，讀取不同的內(nèi)容命中同一緩存塊稱(chēng)為沖突不命中困檩。比如一個(gè)容量為 4 的緩存（采用取余的放置策略），程序來(lái)回請(qǐng)求塊 0 和塊 8那槽，就會(huì)導(dǎo)致每次請(qǐng)求都無(wú)法命中緩存悼沿。
• 容量不命中：當(dāng)緩存太小無(wú)法緩存工作集的時(shí)候稱(chēng)為容量不命中。
  只要發(fā)生了緩存不命中骚灸，就需要執(zhí)行嚴(yán)格的緩存“放置策略”糟趾，來(lái)決定將 k+1 層的塊放置何處，而不是放置在任意地方甚牲，否則定位起來(lái)代價(jià)很高义郑。

高速緩存

早起計(jì)算機(jī)系統(tǒng)的存儲(chǔ)器只有三層：CPU 寄存器、DRAM 主存和磁盤(pán)丈钙。不過(guò)非驮，由于 CPU 和主存（DRAM）之間的差距逐漸增大，于是在 CPU 寄存器和主存之間插入了小的 SRAM 高速緩存雏赦，稱(chēng)為 L1 高速緩存劫笙，訪問(wèn)速度大約 4 個(gè)時(shí)鐘周期。如下圖所示星岗。

高速緩存

隨著 CPU 和主存的性能差距不斷變大填大，于是又在 L1 和主存之間增加了 L2 高速緩存，L2 高速緩存訪問(wèn)速度大約 10 個(gè)時(shí)鐘周期∥榍眩現(xiàn)代計(jì)算機(jī)在 L2 和主存之間又插入了一個(gè) L3 緩存栋盹，訪問(wèn)速度大約 50 個(gè)時(shí)鐘周期。

高速緩存組織結(jié)構(gòu)

高速緩存通常按組形式來(lái)組織敷矫，如下圖所示例获，高速緩存被組織成 S 個(gè)高速緩存組。每個(gè)緩存組有 E 個(gè)高速緩存行曹仗，每行包含 B 字節(jié)的數(shù)據(jù)塊及 1 個(gè)有效位和 t 位的標(biāo)記位（用來(lái)標(biāo)識(shí)緩存組中惟一的緩存行）榨汤。所以高速緩存的容量計(jì)算也非常容易計(jì)算：SEB。

高速緩存組織

內(nèi)存地址根據(jù)高速緩存的組織形式怎茫，被劃分為了三部分收壕，用于快速定位到緩存：

• 塊偏移：簡(jiǎn)稱(chēng)（CO）妓灌，用于在緩存塊中快速定位數(shù)據(jù)，位數(shù)等于
• 組索引：簡(jiǎn)稱(chēng)（CI）蜜宪，用于查找緩存所在的緩存組虫埂，位數(shù)等于
• 標(biāo)記：簡(jiǎn)稱(chēng)（CT），查找到的緩存組如果有多行時(shí)圃验，需要依次比較緩存標(biāo)記是否相同掉伏，來(lái)確定緩存是否存在，位數(shù)等于：內(nèi)存地址位數(shù)-CO位數(shù)-CI位數(shù)澳窑。

直接映射高速緩存

每個(gè)緩存組只有一行（E=1）的高速緩存被稱(chēng)為直接映射高速緩存斧散。

讓我們一起看一個(gè)高速緩存的查找實(shí)例，假設(shè)內(nèi)存地址為 4 位摊聋。高速緩存有 4 組鸡捐，每組 1 行，每個(gè)緩沖塊 2 字節(jié)麻裁。那么根據(jù)之前的知識(shí)我們可以知道箍镜，4 位地址被劃分成了如下圖所示的 3 部分。

直接映射高速緩存

假設(shè) CPU 每次讀取 1 字節(jié)的數(shù)據(jù)悲立，我們按照下表來(lái)依次讀取鹿寨，則會(huì)有相應(yīng)的緩存命中情況。

當(dāng)程序訪問(wèn)地址大小為 2 的冪的數(shù)組時(shí)薪夕，直接映射高速緩存中通常會(huì)發(fā)生沖突不命中脚草。這是因?yàn)檫@些塊被映射到了同一個(gè)高速緩存組，例如上表中的內(nèi)存地址 0 跟內(nèi)存地址 8 就映射到了一個(gè)緩存組原献，從而產(chǎn)生沖突馏慨。即使程序有良好的空間局部性，而且我們的高速緩存有足夠的空間來(lái)存放數(shù)據(jù)（組 1 跟 組 2 還未被使用）姑隅，也無(wú)法有效利用緩存來(lái)提升性能写隶。

組相連高速緩存

直接映射高速緩存中沖突不命中造成的原因源于每組只有一行，而組相連高速緩存就是組數(shù)大于 1 組讲仰，并且小于緩存大小/塊大小的情況慕趴，所以每組都存在多個(gè)緩存行。我們讓上面中的緩存每組有 2 行鄙陡，則緩存組變成 2冕房，再看下緩存命中情況。

我們會(huì)發(fā)現(xiàn)趁矾，相比直接映射高速緩存產(chǎn)生了更少的緩存未命中耙册。緩存組內(nèi)較多的緩存行降低了緩存沖突的可能性，但是也需要更多的標(biāo)記位毫捣，也會(huì)增加命中時(shí)間详拙，因?yàn)樽顗那闆r下需要遍歷組內(nèi)所有的標(biāo)記位帝际，才能找到對(duì)應(yīng)的緩存行。

當(dāng) CPU 請(qǐng)求的數(shù)據(jù)不在緩存中饶辙，而查找到的緩存組已滿時(shí)候蹲诀，高速緩存必須替換緩存組中的某一個(gè)行，這其中就需要用到高速緩存替換策略弃揽，常見(jiàn)的有 LFU（最不常使用）侧甫，LRU（最近最少使用）等。

全相連高速緩存

全相連高速緩存即只有一個(gè)組蹋宦，包含所有緩存行。全相連高速緩存因?yàn)橹挥幸粋€(gè)組咒锻，所以組選擇非常簡(jiǎn)單冷冗。全相連高速緩存擁有最大的緩存空間利用率，但是必須搜索許多標(biāo)記惑艇，構(gòu)造一個(gè)又大又快的全相連高速緩存很困難蒿辙，也很昂貴，因此全相連高速緩存只適合做小的高速緩存滨巴。有些虛擬系統(tǒng)中使用的小容量的 TLB 采用這種形式思灌。

實(shí)際高速緩存示例

高速緩存示例

在高緩存中其實(shí)不止保存程序數(shù)據(jù)，也可以保存指令恭取。只保存指令的高速緩存稱(chēng)為 i-cache泰偿，只保存數(shù)據(jù)的高速緩存稱(chēng)為 d-cache。

上圖給出的是 Intel Core i7（Haswell）處理器的高速緩存層次結(jié)構(gòu)蜈垮。每個(gè) CPU 芯片有四個(gè)核耗跛。每個(gè)核有自己私有的 L1 i-cache，L1 d-cache 及 L2 統(tǒng)一高速緩存攒发。所有的核共享 L3 統(tǒng)一高速緩存调塌。所有的 SRAM 高速緩存都在 CPU 芯片上。下表是 Core i7 處理器高速緩存的基本特性惠猿。

存儲(chǔ)器山

一個(gè)程序從存儲(chǔ)系統(tǒng)中讀取數(shù)據(jù)速率稱(chēng)為吞吐量羔砾，或者稱(chēng)為讀帶寬。通常以 MB/s 為單位偶妖。

存儲(chǔ)器山

這張圖是開(kāi)頭的那張圖姜凄，描繪的是 Intel Core i7 系統(tǒng)的存儲(chǔ)器山。展示了一個(gè)豐富的地勢(shì)結(jié)構(gòu)餐屎，垂直于大小軸的是四條山脊檀葛，對(duì)應(yīng) L1 高速緩存、L2 高速緩存腹缩、L3 高速緩存和主存的時(shí)間局部性區(qū)域屿聋。L1 山脊的最高點(diǎn)（讀速率為 14GB/s）與主存山脊的最低點(diǎn)（讀取速率為 900MB/s）之間的差別有一個(gè)數(shù)量級(jí)空扎。

在 L2、L3润讥、主存山脊上转锈，隨著步長(zhǎng)的增加，有一個(gè)空間局部性的斜坡楚殿，空間局部性下降撮慨。即使工作集太大，不能全部裝入任何一個(gè)高速緩存是脆粥，主存山脊的最高點(diǎn)仍然比它的最低點(diǎn)高 8 倍砌溺。因此，即使當(dāng)程序的時(shí)間局部性很差時(shí)变隔，空間局部性仍能補(bǔ)救规伐，并且是非常重要的。

有一條特別的平坦的山脊線匣缘，對(duì)于步長(zhǎng) 1 垂直于步長(zhǎng)軸猖闪，此時(shí)吞吐量相對(duì)保持不變，為 12GB/s肌厨，即使工作集超過(guò) L2培慌、L3 的大小。這是由于 Core i7 存儲(chǔ)器系統(tǒng)中的硬件預(yù)期機(jī)制柑爸，它會(huì)自動(dòng)的識(shí)別順序的吵护、步長(zhǎng)為 1 的引用模式，試圖在一些塊被訪問(wèn)之前表鳍，將他們?nèi)〉礁咚倬彺嬷泻沃贰拇鎯?chǔ)器山可以明顯看出算法對(duì)小步長(zhǎng)效果最好--這也是代碼中要使用步長(zhǎng)為 1 的順序訪問(wèn)的另一個(gè)理由。

存儲(chǔ)器系統(tǒng)的性能不是一個(gè)數(shù)字就能描述的进胯，而是一座時(shí)間和空間局部性的山用爪。我們應(yīng)該構(gòu)造運(yùn)行在山峰而不是山谷的程序。主要就是利用時(shí)間局部性胁镐，使得頻繁使用的字從 L1 中取出偎血，還要利用空間局部性，使得盡可能多的字從一個(gè) L1 高速緩存行中訪問(wèn)到盯漂。

深入理解計(jì)算機(jī)系統(tǒng)

2015 CMU 15-213 CSAPP 深入理解計(jì)算機(jī)系統(tǒng) 課程視頻