作者：bearluo，騰訊IEG運營開發工程師

這篇文章主要整理了一下計算機中的内存結構，以及 CPU 是如何讀寫内存種的數據的，如何維護 CPU 緩存中的數據一緻性。什麼是虛拟内存，以及它存在的必要性。如有不對請多多指教。

目前在計算機中，主要有兩大存儲器 SRAM 和 DRAM。主存儲器是由 DRAM 實現的，也就是我們常說的内存，在 CPU 裡通常會有 L1、L2、L3 這樣三層高速緩存是用 SRAM 實現的。

SRAM 被稱為“靜态”存儲器，是因為隻要處在通電狀态，裡面的數據就可以保持存在。而一旦斷電，裡面的數據就會丢失了。

目前 SRAM 主要集成在 CPU 裡面，每個 CPU 核心都有一塊屬于自己的 L1 高速緩存，通常分成指令緩存和數據緩存，分開存放 CPU 使用的指令和數據。L2 的 Cache 同樣是每個 CPU 核心都有的，不過它往往不在 CPU 核心的内部。所以，L2 cache 的訪問速度會比 L1 稍微慢一些。而 L3 cache ，則通常是多個 CPU 核心共用的。

在 DRAM 中存儲單元使用電容保存電荷的方式來存儲數據，電容會不斷漏電，所以需要定時刷新充電，才能保持數據不丢失，這也是被稱為“動态”存儲器的原因。由于存儲 DRAM 一個 bit 隻需要一個晶體管，所以存儲的數據也大很多。

我們來看一些他們的速度：

• • L1 的存取速度：4 個CPU時鐘周期
• • L2 的存取速度： 11 個CPU時鐘周期
• • L3 的存取速度：39 個CPU時鐘周期
• • DRAM内存的存取速度：107 個CPU時鐘周期

上面我們說了，對于 CPU 來說，SRAM 被稱為 CPU 的 cache，CPU 每次獲取數據都會先訪問 cache，如果獲取不到數據則把數據加載到 cache中進行訪問。因為 cache 的大小是遠遠小于主存的，所以還需要在 cache和主存之間維護一個映射關系，這樣才能正确找到數據。

一種簡單的方式是直接映射，有點像我們把數據找出來，直接放入到 map 中進行存儲一樣，映射通過地址和 cache的數量進行取模後獲取到 cache 中主存的地址去獲取數據。

（地址）mod（cache 中的塊數）

上圖中畫了一個地址去找 cache 的情況。對于 cache 來說可以劃分為：

索引：用來取模找到對應的 cache 行；

有效位：cache 初始值一開始是空的，這個字段标記 cache 行是否有數據；

标記：用來和地址進行比較是否是對應的數據；

數據：表示存儲的實際的數據，可以通過地址的偏移來獲取到對應的數據；

比如對于這個 cache 有 1024 個字，即 4KB。假設有一個 32 位的地址要去 cache 中查找數據，那麼會取地址10位進行取模找到對應的 cache 行，然後取出20位與 cahce 标記位進行比較，如果相等，并且有效位開啟，那麼對應請求地址在 cache 中命中。否則，發生缺失。

由于 CPU 在讀取數據的時候，并不是要讀取一整個 Block，而是讀取一個他需要的數據片段， cache 中命中之後會根據低兩位的偏移去數據裡面索引到對應的字。

除了上面說的直接映射以外還有組相聯和全相聯。

組相聯就是使用組索引代替了原來的索引，下圖中表示每組有2行數據，通過組索引找到對應的數據行之後通過有效位和标記對組中每一行進行檢索，如果能匹配上就說明命中。

先來看看讀操作，cache 在初始狀态的時候是空的，這個時候去讀數據會産生 cache 缺失（cache miss）。cache 控制器會檢測到缺失的發生，然後從主存中（或低一級 cache）中取回所需數據。如果命中，那麼就會直接使用。

當 cache 缺失時，對于亂序執行處理器而言依然能執行一些其他指令，但是對于順序執行處理器，當 cache 缺失時會被阻塞，臨時寄存器和程序員可見的寄存器中的内容基本被凍結。

再來看看寫操作，因為 cache 是由多級組成，所以寫策略一般而言有兩種：寫直達（write-through）和寫回（write-back）。通過這兩種策略使在 cache 中寫入的數據和主存中的數據保持一緻。

寫直達就是在将數據寫入 cache 之後同時将這個數據立馬寫入到主存中，但是由于主存和 cache 本身性能差異，那麼每次在寫入主存的時候都将花費大量的時間。解決辦法就是加一層寫緩沖（write buffer），這樣 CPU 在将數據寫入 cache 和緩沖之後可以繼續執行，等到緩沖寫入到主存中再釋放。

但是如果寫入速度大于緩沖釋放速度，那麼還是會阻塞 CPU 執行。那麼可以考慮一下寫回策略，這種機制會在每次寫入的時候僅将新值寫入 cache 中，隻有當修改過的塊被替換時才需要寫到較低層存儲結構中。

由于現在都是多核 CPU，并且 cache 分了多級，并且數據存在共享的情況，所以需要一種機制保證在不同的核中看到的 cache 數據必須時一緻的。最常用來處理多核 CPU 之間的緩存一緻性協議就是 MESI 協議。

MESI 協議，是一種叫作寫失效（Write Invalidate）的協議。在寫失效協議裡，隻有一個 CPU 核心負責寫入數據，其他的核心，隻是同步讀取到這個寫入。在這個 CPU 核心寫入 cache 之後，它會去廣播一個“失效”請求告訴所有其他的 CPU 核心。

MESI 協議對應的四個不同的标記，分别是：

• • M：代表已修改（Modified）
• • E：代表獨占（Exclusive）
• • S：代表共享（Shared）
• • I：代表已失效（Invalidated）

“已修改”和“已失效”比較容易理解，我們來看看 獨占”和“共享” 兩個狀态。

在獨占狀态下，對應的 cache Line 隻加載到了當前 CPU 核所擁有的 cache 裡。其他的 CPU 核，并沒有加載對應的數據到自己的 cache 裡。這個時候，如果要向獨占的 cache Block 寫入數據，我們可以自由地寫入數據，而不需要告知其他 CPU 核。

那麼對應的，共享狀态就是在多核中同時加載了同一份數據。所以在共享狀态下想要修改數據要先向所有的其他 CPU 核心廣播一個請求，要求先把其他 CPU 核心裡面的 cache ，都變成無效的狀态，然後再更新當前 cache 裡面的數據。

在我們日常使用的 Linux 或者 Windows 操作系統下，程序并不能直接訪問物理内存。程序都是通過虛拟地址 VA（virtual address）用地址轉換翻譯成 PA 物理地址（physical address）才能獲取到數據。也就是說 CPU 操作的實際上是一個虛拟地址 VA。

如上圖，CPU 訪問主存的時候會将一個虛拟地址（virtual address）被内存管理單元（Memory Management Unint, MMU）進行翻譯成物理地址 PA（physical address） 才能訪問。

想要把虛拟内存地址，映射到物理内存地址，最直觀的辦法，就是來建一張映射表。這個映射表在計算機中叫頁表（Page Table）。

在查找頁表的時候，會将虛拟地址分成頁号（Directory）和偏移量（Offset）兩個部分。前面的高位，表示内存地址的頁号。後面的低位，表示内存地址裡面的偏移量。

查找方式和上面說的組相聯類似，首先使用虛拟頁号作為索引去頁表中找到對應的物理頁号，頁表中還會有1位表示有效位，如果該位無效就不在主存中，發生一次缺頁；如果有效，那麼就可以拿到對應的物理頁号獲取到對應的物理頁位置，再根據偏移量得到物理内存地址。

如果有效位關閉，那麼該頁就隻存在磁盤上的某個指定的磁盤地址。缺頁會觸發缺頁異常，然後在閃存或磁盤中找到該頁，将其放入到主存 DRAM 中。

如果主存滿了，那麼會選擇一個犧牲頁，大多數操作系統會使用 LRU 替換策略來進行頁的替換。操作系統會查找最少使用的頁，被替換的頁會寫入磁盤的交換區（swap 分區）。swap 分區通常被稱為交換分區，這是一塊特殊的硬盤空間，即當實際内存不夠用的時候，操作系統會從内存中取出一部分暫時不用的數據，放在交換分區中，從而為當前運行的程序騰出足夠的内存空間。

在下圖中假設選擇将存放在主存中的 VP6 進行替換，将 VP6 替換為 VP3。如果被替代的 VP6 已經被修改了，那麼内核會将它複制回磁盤。

由于局部性（locality）的存在，程序一般而言會在一個較小的活動頁面集合上工作，頁的切換開銷隻存在于程序啟動時将頁面調度到内存中，接下來的程序都會頁命中。但是如果代碼的工作集太大，超過了物理内存大小，那麼頁面就會不停地換進換出，産生抖動。

假設我們現在是一個 32位的地址空間、4KB的頁面和一個4字節的PTE，那麼需要一個 4MB 的頁表常駐在内存中，并且這個頁表是每個進程都獨占一份，所以會造成很大的内存浪費，我們需要一種方式來優化我們的頁表空間存儲。

想一下虛拟内存空間結構，整個 4 GB 的空間，操作系統用了 1 GB，從地址 0XC0000000 到 0XFFFFFFFF, 剩餘 3 GB留給用戶空間，其實很多程序根本用不到這麼大的空間，對于 64 位系統，每個進程都會擁有 256 TiB 的内存空間，那就更加用不上了。

那麼對于用不上的空間，我們可以不可以不把它加載到頁表裡面，等到用這塊空間的時候才在頁表裡面給它分配一個頁表項，是不是就可以節省大量空間。

在程序運行的時候，内存地址從頂部往下，不斷分配占用的棧的空間。而堆的空間，内存地址則是從底部往上，是不斷分配占用的。所以，在一個實際的程序進程裡面，虛拟内存占用的地址空間，通常是兩段連續的空間。而多級頁表，就特别适合這樣的内存地址分布。

假設32位虛拟地址空間被劃分位 4KB 每頁，每個條目都是 4字節，那麼我們可以讓第一級頁表中的每個 PTE （頁表項 page table entry）負責映射虛拟地址空間中一個 4MB 的片，這個片由 1024 個連續頁面組成，表示二級頁表。如果地址空間是 4GB，那麼1024個一級頁表項就可以覆蓋整個空間。

如下圖所示，内存前 2K 個頁面給代碼和數據，接下來 6K 個頁面未分配，在接下來 1023個頁面也未分配，接下來一個頁面分配給用戶棧。

這種方法從兩個方面減少了内存占用。第一，如果一級頁表中的一個 PTE 是空的，那麼相應的二級頁表就根本不會存在。由于很多程序占用内存實際遠小于頁表所能表示的大小，所以可以節約很大空間的頁表項資源；第二，隻有一級頁表才需要總是在主存中，二級頁表會在需要的時候創建或銷毀，隻有最經常使用的二級頁表才需要緩存在主存中，這就減少了主存的壓力。

Linux 在 2.6.10 中引入了四層的頁表輔助虛拟地址的轉換：

首先會找到 4 級頁表裡面對應的條目（Entry）。這個條目裡存放的是一張 3 級頁表所在的位置。4 級頁面裡面的每一個條目，都對應着一張 3 級頁表，所以我們可能有多張 3 級頁表。

找到對應這張 3 級頁表之後，我們用 3 級索引去找到對應的 3 級索引的條目。3 級索引的條目再會指向一個 2 級頁表。依次拿到 1 級頁表裡面存儲的物理頁号，我們同樣可以用“頁号 偏移量”的方式，來獲取最終的物理内存地址。

對于一個頁命中的數據獲取過程通常來說，如果沒有 TLB 加速是這樣的：

1. 1. CPU生成一個虛拟地址，并把它傳給 MMU；
2. 2. MMU生成頁表項地址 PTEA，并從高速緩存/主存請求獲取頁表項 PTE；
3. 3. 高速緩存/主存向 MMU 返回 PTE；
4. 4. MMU 構造物理地址 PA，并把它傳給高速緩存/主存；
5. 5. 高速緩存/主存返回所請求的數據給CPU。

一次簡單的數據獲取需要多次經過多次與内存的交互，如果是 4 級頁表，那麼就需要訪問 4 次内存才能獲取到對應的物理頁号。如果是缺頁，還需要有一個 PTE 的置換或加載過程。在開頭也講了，訪問内存的性能其實很低的，實際上這嚴重影響了 CPU 處理性能。

程序所需要使用的指令，都順序存放在虛拟内存裡面。我們執行的指令，也是一條條順序執行下去的。也就是說，我們對于指令地址的訪問，存在前面幾講所說的“空間局部性”和“時間局部性”，而需要訪問的數據也是一樣的。我們連續執行了 5 條指令。因為内存地址都是連續的，所以我們可以通過加緩存的方法，把之前内存轉換的地址緩存下來，減少與内存的交互。

加的這一層就是緩存芯片 TLB （Translation Lookaside Buffer），它裡面每一行保存着一個由單個 PTE 組成的塊。

那麼查詢數據的過程就變成了：

1. 1. CPU 産生一個虛拟地址；
2. 2. MMU 從 TLB 中取出相應的 PTE；
3. 3. MMU 将這個虛拟地址翻譯成一個物理地址，并且将它發送到高速緩存/主存；
4. 4. 高速緩存/主存将所請求的數據字返回給 CPU；

講完了什麼是虛拟内存，我們最後講講虛拟内存的必要性。

由于操作虛拟内存實際上就是操作頁表，從上面講解我們知道，頁表的大小其實和物理内存沒有關系，當物理内存不夠用時可以通過頁缺失來将需要的數據置換到内存中，内存中隻需要存放衆多程序中活躍的那部分，不需要将整個程序加載到内存裡面，這可以讓小内存的機器也可以運行程序。

虛拟内存可以為正在運行的進程提供獨立的内存空間，制造一種每個進程的内存都是獨立的假象。虛拟内存空間隻是操作系統中的邏輯結構，通過多層的頁表結構來轉換虛拟地址，可以讓多個進程可以通過虛拟内存共享物理内存。

并且獨立的虛拟内存空間也會簡化内存的分配過程，當用戶程序向操作系統申請堆内存時，操作系統可以分配幾個連續的虛拟頁，但是這些虛拟頁可以對應到物理内存中不連續的頁中。

再來就是提供了内存保護機制。任何現代計算機系統必須為操作系統提供手段來控制對内存系統的訪問。虛拟内存中頁表中頁存放了讀權限、寫權限和執行權限。内存管理單元可以決定當前進程是否有權限訪問目标的物理内存，這樣我們就最終将權限管理的功能全部收斂到虛拟内存系統中，減少了可能出現風險的代碼路徑。

從上面我們可以知道 CPU 的緩存結構一般由 L1、L2、L3 三層緩存結構組成，CPU 讀取數據隻與緩存交互，不會直接訪問主存，所以 CPU 緩存和主存之間維護了一套映射關系。當被查找的數據發生缺失時，需要等待數據從主存加載到緩存中，如果緩存滿了，那麼還需要進行淘汰。如果被淘汰的數據是髒數據，那麼還需要寫回到主存中，寫的策略有寫直達（write-through）和寫回（write-back）。

由于現在計算機中的 CPU 都是多核的，并且緩存數據是由多核共享的，所以就有了類似 MESI 這樣的協議來維護一個狀态機保證數據在多核之間是一緻的。

為了訪問數據安全，便捷，迅速所以加了一層虛拟内存，每個程序在啟動的時候都會維護一個頁表，這個頁表維護了一套映射關系。CPU 操作的實際上是虛拟地址，每次需要 MMU 将虛拟地址在頁表上映射成物理地址後查找數據。并且為了節省内存所以設計了多級頁表，為了從頁表中查找數據更快加了一個緩存芯片 TLB。