存儲器山

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

存儲器分類

存儲器系統(tǒng)是一個不同容量、成本和訪問時間的存儲設(shè)備的層次結(jié)構(gòu)。越靠近 CPU 的存儲器越快也越貴、越小，從磁盤上讀取信息比從 DRAM 中讀取慢了 10 萬倍，比 SRAM 慢了 100 萬倍。計算機巧妙的運用了各種存儲器的特性，構(gòu)建了一個既運行高效又支持大容量存儲的系統(tǒng)。

SRAM

SRAM 全稱“Static Random Access Memory”，之所以被稱為“靜態(tài)”存儲器，是因為只要有電，它就會永遠(yuǎn)保持它的值。即使有干擾來擾亂電壓，當(dāng)干擾消除時，依然會恢復(fù)到穩(wěn)定值。而一旦斷電，里面的數(shù)據(jù)就會丟失了。SRAM 對諸如光和電噪聲這樣干擾不敏感，是因為 SRAM 比 DRAM 使用了更多的晶體管，因而密集度較低，也就更貴，功耗更大。

由于 SRAM 速度快、容量小、價格貴，所以多用來制造高速緩存，如現(xiàn)在計算機中基本都有的 L1，L2，L3 緩存。

DRAM

DRAM 全稱“Dynamic Random Access Memory”，相比 SRAM，DRAM 需要定時刷新，所以也被稱為“動態(tài)”存儲器。DRAM 每個單元由一個電容和一個晶體管組成，由于組成簡單，所以 DRAM 可以制造的非常密集，因而容量可以做的較大。但DRAM 對干擾非常敏感。因為數(shù)據(jù)存儲在電容里面，而電容會不斷漏電，所以要定時刷新，才能保證數(shù)據(jù)不會丟失。

DRAM 由于容量大、價格便宜，多用來制作計算機主存，或者各種顯卡的顯存等。

ROM

ROM 全程“Read Only Memory”，由于歷史原因，雖然 ROM 中有的類型即可以讀也可以寫，但是他們整體上被稱為只讀存儲器。相比于 SRAM，DRAM 最大的不同就是斷電后不會丟失信息，因為是非易失性存儲器。

存儲在 ROM 中的程序通常被稱為“固件”，當(dāng)計算機通電后就會運行存儲在 ROM 中的固件，例如我們所熟知的 BIOS 程序，就存儲在 ROM 中，每次計算機開機會引導(dǎo)操作系統(tǒng)啟動。復(fù)雜的設(shè)備，如顯卡和磁盤驅(qū)動控制器，也依賴固件翻譯來自 CPU 的 I/O 請求。

磁盤

磁盤是由“盤片”構(gòu)成，每個盤片有兩面或者一面稱為“表面”，表面覆蓋著磁性記錄材料。盤片中央有一個旋轉(zhuǎn)主軸，使得盤片以固定的旋轉(zhuǎn)速率旋轉(zhuǎn)，通常 5400 ~ 15000 轉(zhuǎn)/分鐘。磁盤通常包含一個或多個盤片，并封閉在一個容器中。

磁盤的表面由一組組稱為“磁道”的同心圓組成，每個磁道被劃分為一組“扇區(qū)”，每個扇區(qū)包含相同數(shù)量的數(shù)據(jù)位（通常 512 byte)。扇區(qū)之間由一些間隙分隔開，間隙不存儲數(shù)據(jù)位，只用來標(biāo)識扇區(qū)的格式化位。

盤片	磁盤

磁盤容量

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

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

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

磁盤操作

磁盤用“讀/寫頭”來讀寫存儲在磁性表面的位，讀寫頭連接到一個傳動臂。通過沿著半徑軸前后移動傳動臂，可以將讀/寫頭定位到期望磁道，這個過程稱為“尋道”。有多個盤面的磁盤針對每個盤面都有一個獨立的讀/寫頭，讀/寫頭垂直排列，一致行動，在任何時刻，所有讀/寫頭都位于同一柱面上。

讀寫	統(tǒng)一移動

磁盤以扇區(qū)大小的塊來讀寫數(shù)據(jù)，對扇區(qū)的訪問時間主要由下面幾個部分決定。

• 尋道時間：移動傳動臂到指定磁道上的時間?，F(xiàn)在驅(qū)動器中平均尋到時間通常是 3~9 ms，并且受限于物理性能局限，很難再縮小。
• 旋轉(zhuǎn)時間：讀/寫頭到指定磁道后，需要等待磁盤旋轉(zhuǎn)到目標(biāo)扇區(qū)，目標(biāo)扇區(qū)第一個位旋轉(zhuǎn)到讀/寫頭下的時間為旋轉(zhuǎn)時間。以 7200 轉(zhuǎn)磁盤為例，平均旋轉(zhuǎn)時間約為 4ms。
• 傳送時間：從讀取扇區(qū)第一個位到扇區(qū)讀取完畢的時間為傳送時間，主要取決于磁盤的旋轉(zhuǎn)速度及磁道的扇區(qū)數(shù)目。相比于尋道時間及旋轉(zhuǎn)時間，傳送時間很小基本可以忽略不計。

由于尋道時間和旋轉(zhuǎn)時間大致相等，所以經(jīng)常用尋道時間*2 來估算磁盤訪問時間。

邏輯磁盤塊

為了對操作系統(tǒng)隱藏磁盤構(gòu)造的復(fù)雜性，現(xiàn)代磁盤將其構(gòu)造呈現(xiàn)為一個簡單的視圖：一個 B 個扇區(qū)大小的邏輯塊序列，編號為0，1，...，B-1。磁盤中有一個小的硬件稱為磁盤控制器，維護(hù)著邏輯塊號與實際磁盤扇區(qū)的映射關(guān)系。

當(dāng)操作系統(tǒng)想要讀寫一個磁盤的扇區(qū)數(shù)據(jù)時候，將會發(fā)送一個命令到磁盤控制器，讓他讀取某個邏輯塊號。磁盤控制器將邏輯塊號翻譯成一個（盤面，磁道，扇區(qū)）的三元組，唯一的標(biāo)識了對應(yīng)的物理扇區(qū)。然后將讀/寫頭移動到相應(yīng)的物理扇區(qū)，進(jìn)行讀寫操作。

磁盤讀取

固態(tài)硬盤

固態(tài)硬盤（SSD）是一種基于閃存的存儲技術(shù)，有一個或多個閃存芯片和閃存翻譯層組成。閃存芯片替代傳統(tǒng)磁盤中的機械驅(qū)動器，閃存翻譯層則是類似于磁盤控制器的存在。

固態(tài)硬盤

相比傳統(tǒng)磁盤，SSD 有很多優(yōu)點。由于由半導(dǎo)體存儲器構(gòu)成，因而隨機訪問時間比旋轉(zhuǎn)磁盤要快很多，功耗更低，也更結(jié)實。同樣也有一些缺點，閃存塊會磨損，因而 SSD 壽命較普通磁盤短。SSD 較傳統(tǒng)磁盤價格更貴，因而常用的存儲容量也比傳統(tǒng)磁盤較小。

硬件技術(shù)趨勢

硬件技術(shù)趨勢

上圖是各種硬件按年統(tǒng)計的運行速度，可以看出，雖然 SRMA 的性能滯后于 CPU 的性能，但是在持續(xù)保持增長，追趕 CPU 的增長曲線。而 DRAM 和磁盤的性能增長緩慢，嚴(yán)重滯后于 CPU 的性能，與 CPU 性能之間的差距在不斷擴大。

CPU 在 2003 年開始出現(xiàn)變化，是由于當(dāng)時無法再通過增加 CPU 的頻率來提升性能，因為這樣芯片的功耗會太大。解決辦法就是用多個小處理器取代單個大處理器，從而提升性能。CPU 頻率在 2003 年達(dá)到了最低點，上升后又開始以比以前慢一些的速率下降。不過，CPU 的有效周期時間還是以接近以前的速率持續(xù)下降。

局部性

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

一個編寫良好的計算機程序常常有良好的“局部性”。也就是，它們傾向于引用的數(shù)據(jù)項多臨近與其他最近引用過的數(shù)據(jù)項，或者是最近引用過的數(shù)據(jù)項本身。這種傾向性，被稱為“局部性原理”。這是一個很重要的概念，對硬件和軟件系統(tǒng)的設(shè)計和性能都有著極大的影響。

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

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

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

    /**
     * 緩存組是8路的，所以需要大于8才會比較明顯的緩存沖突情況
     */
    final static int ROW = 16;
    
    /**
     * Core i7，L1 d-cache是32KB，L2 cache 是256K，這個值可以根據(jù) cache 情況調(diào)整
     * 一個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();

        /// 用來打印數(shù)據(jù)內(nèi)存地址，來實際驗證
        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)));
    }
}

可以用上面的小程序來驗證局部性的重要性，兩種方式的運行效率差距還是比較大的。

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

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

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

存儲器層次

緩存

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

在 CSAPP 里面老師描述緩存舉得例子特別形象：對一個學(xué)生來說，家就好比主存，里面有各種各樣的東西。而背包就好比高速緩存，只裝了你最需要的東西。當(dāng)你從書包拿出課本的時候可以很快，否則你就需要跑回家拿。

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

緩存數(shù)據(jù)總是以塊大小為傳送單元，在第 k 層跟 k+1 層之間來回拷貝。相鄰層次之間塊大小是固定的，但其他層次對之間可以有不同的塊大小。L1 和 L0 之間傳送通常使用 1 個字的塊，L2 和 L1、L3 和 L2、L4 和 L3 之間傳遞通常使用幾十個字節(jié)的塊。而 L5 跟 L4 之間傳遞通常用幾百或者幾千字節(jié)的塊。一般而言離CPU越遠(yuǎn)的設(shè)備訪問時間越長，為了補償這些時間，傾向于使用較大的塊。

緩存不命中

緩存不命中主要分為三類：

• 冷不命中：一個空的緩存被稱為冷緩存，此類不命中稱為冷不命中。應(yīng)對這種情況就是在使用前需要暖身（warm up），也就是常說的預(yù)熱。
• 沖突不命中：由于緩存的容量限制，讀取不同的內(nèi)容命中同一緩存塊稱為沖突不命中。比如一個容量為 4 的緩存（采用取余的放置策略），程序來回請求塊 0 和塊 8，就會導(dǎo)致每次請求都無法命中緩存。
• 容量不命中：當(dāng)緩存太小無法緩存工作集的時候稱為容量不命中。
  只要發(fā)生了緩存不命中，就需要執(zhí)行嚴(yán)格的緩存“放置策略”，來決定將 k+1 層的塊放置何處，而不是放置在任意地方，否則定位起來代價很高。

高速緩存

早起計算機系統(tǒng)的存儲器只有三層：CPU 寄存器、DRAM 主存和磁盤。不過，由于 CPU 和主存（DRAM）之間的差距逐漸增大，于是在 CPU 寄存器和主存之間插入了小的 SRAM 高速緩存，稱為 L1 高速緩存，訪問速度大約 4 個時鐘周期。如下圖所示。

高速緩存

隨著 CPU 和主存的性能差距不斷變大，于是又在 L1 和主存之間增加了 L2 高速緩存，L2 高速緩存訪問速度大約 10 個時鐘周期?，F(xiàn)代計算機在 L2 和主存之間又插入了一個 L3 緩存，訪問速度大約 50 個時鐘周期。

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

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

高速緩存組織

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

• 塊偏移：簡稱（CO），用于在緩存塊中快速定位數(shù)據(jù)，位數(shù)等于
• 組索引：簡稱（CI），用于查找緩存所在的緩存組，位數(shù)等于
• 標(biāo)記：簡稱（CT），查找到的緩存組如果有多行時，需要依次比較緩存標(biāo)記是否相同，來確定緩存是否存在，位數(shù)等于：內(nèi)存地址位數(shù)-CO位數(shù)-CI位數(shù)。

直接映射高速緩存

每個緩存組只有一行（E=1）的高速緩存被稱為直接映射高速緩存。

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

直接映射高速緩存

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

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

組相連高速緩存

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

我們會發(fā)現(xiàn)，相比直接映射高速緩存產(chǎn)生了更少的緩存未命中。緩存組內(nèi)較多的緩存行降低了緩存沖突的可能性，但是也需要更多的標(biāo)記位，也會增加命中時間，因為最壞情況下需要遍歷組內(nèi)所有的標(biāo)記位，才能找到對應(yīng)的緩存行。

當(dāng) CPU 請求的數(shù)據(jù)不在緩存中，而查找到的緩存組已滿時候，高速緩存必須替換緩存組中的某一個行，這其中就需要用到高速緩存替換策略，常見的有 LFU（最不常使用），LRU（最近最少使用）等。

全相連高速緩存

全相連高速緩存即只有一個組，包含所有緩存行。全相連高速緩存因為只有一個組，所以組選擇非常簡單。全相連高速緩存擁有最大的緩存空間利用率，但是必須搜索許多標(biāo)記，構(gòu)造一個又大又快的全相連高速緩存很困難，也很昂貴，因此全相連高速緩存只適合做小的高速緩存。有些虛擬系統(tǒng)中使用的小容量的 TLB 采用這種形式。

實際高速緩存示例

高速緩存示例

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

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

存儲器山

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

存儲器山

這張圖是開頭的那張圖，描繪的是 Intel Core i7 系統(tǒng)的存儲器山。展示了一個豐富的地勢結(jié)構(gòu)，垂直于大小軸的是四條山脊，對應(yīng) L1 高速緩存、L2 高速緩存、L3 高速緩存和主存的時間局部性區(qū)域。L1 山脊的最高點（讀速率為 14GB/s）與主存山脊的最低點（讀取速率為 900MB/s）之間的差別有一個數(shù)量級。

在 L2、L3、主存山脊上，隨著步長的增加，有一個空間局部性的斜坡，空間局部性下降。即使工作集太大，不能全部裝入任何一個高速緩存是，主存山脊的最高點仍然比它的最低點高 8 倍。因此，即使當(dāng)程序的時間局部性很差時，空間局部性仍能補救，并且是非常重要的。

有一條特別的平坦的山脊線，對于步長 1 垂直于步長軸，此時吞吐量相對保持不變，為 12GB/s，即使工作集超過 L2、L3 的大小。這是由于 Core i7 存儲器系統(tǒng)中的硬件預(yù)期機制，它會自動的識別順序的、步長為 1 的引用模式，試圖在一些塊被訪問之前，將他們?nèi)〉礁咚倬彺嬷?。從存儲器山可以明顯看出算法對小步長效果最好--這也是代碼中要使用步長為 1 的順序訪問的另一個理由。

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

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

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