作業系統是如何管理記憶體的
最近在看 ofollow,noindex" target="_blank">Operating Systems: Three Easy Pieces 這本書，作者在這方面有 20 多年的積累，同時文風非常樸實，不會被各種術語繞暈。該書進從虛擬化、併發、持久化這三個方面來剖析作業系統，從要達到的目標到遇到的問題到解決方案到新的問題，一層層地告訴你為什麼會變成現在這個樣子。
今天要講的內容主要是對該書裡面關於記憶體管理這塊的一個小結，由於看的是 0.8 版，跟最新的 1.0 版可能會有些許出入。
前言
每個程序建立的記憶體地址都是虛擬地址，作業系統使用了虛擬化技術，讓程序覺得它擁有了大塊可支配的記憶體的假象，作業系統拿到這個地址後會將它轉變為真實的記憶體地址，從而拿到對應的資訊。比如下面這段程式碼：
1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
printf("location of code : %p\n", (void *) main);
printf("location of heap : %p\n", (void *) malloc(1));
int x = 3;
printf("location of stack : %p\n", (void *) &x);
return x;
}
輸出：
1 2 3 location of code : 0x10df2aec0 location of heap : 0x7fdeea400350 location of stack : 0x7ffee1cd560c
這些都是虛擬地址。對於記憶體的虛擬化，有三個最重要的要素：透明（就像記憶體只為當前的程序所用）、高效（就像直接操作實體記憶體那樣）、保護（程序之間不能隨意讀寫各自的記憶體區域），伴隨著這三個要素，就開始了探索之旅。
遠古時代
一開始，只有一個程序，一切都很美好，除了作業系統的自留地外，剩下的都給那個程序，想怎麼折騰都行，只要別超出最大的容量。
但我們知道，那個時候，一臺計算機是很貴的，比 iPhone XS Max 還貴，在這麼昂貴的機器上同時只能執行一個程式實在浪費，於是就有了支援多程序的需求，所謂多程序，並不需要同時執行這些程序，只要它們都處於 ready 狀態，作業系統快速地在它們之間切換，就能達到同時執行的假象。每個程序都需要記憶體，Context Switch 時，之前記憶體裡的內容怎麼辦？簡單粗暴的方式就是先 dump 到磁碟上，然後再從磁碟上 restore 之前 dump 的內容（如果有的話），但效果並不好，太慢了！
那怎麼才能不慢呢？把程序對應的記憶體依舊留在實體記憶體中，需要的時候就切換到特定的區域。這就涉及到了記憶體的保護機制，畢竟程序之間可以隨意讀取、寫入內容就亂套了，非常不安全。因此作業系統需要對實體記憶體做一層抽象，也就是「地址空間」(Address Space)，一個程序的地址空間包含了該程序所有相關記憶體，比如 code / stack / heap。一個 16 KB 的地址空間可能長這樣：
當程式執行時，heap 和 stack 共用中間 free 的區域，當然這只是 OS 層面的抽象。比如下面這段程式碼：
1 2 int x; x = x + 3; // this is the line of code we are interested in
變成彙編指令後，大概是這樣：
128: movl 0x0(%ebx), %eax;load 0+ebx into eax 132: addl $0x03, %eax ;add 3 to eax register 135: movl %eax, 0x0(%ebx) ;store eax back to mem
最前面的是 PC (Program Counter)，用來表示當前 code 的索引，比如 CPU 執行到 128 時，進行了 Context Switch，那麼在 Switch 回來後，還可以接著從 132 開始執行（當然需要先把 PC 存起來）。之後的就是彙編程式碼，告訴 CPU 該如何操作。
從程序的角度看，記憶體可能是這樣的：
真實的實體記憶體可能是這樣的：
從 32KB 處作為開始，48KB 作為結束。那 32 / 48 可不可以動態設定呢，只要在 CPU 上整兩個暫存器，base 和 bounds 就可以了，base 指明從哪裡開始，bounds 指定哪裡是邊界。 因此真實實體地址和虛擬地址之間的關係是：
1 physical address = virtual address + base
有時，CPU 上用來做記憶體地址翻譯的也會被叫做「記憶體管理單元 MMU」(Memory Management Unit)，隨著功能越來越強大，MMU 也會變得越來越複雜。
base and bounds 這種做法最大的問題在於空間浪費，Stack 和 Heap 中間有一塊 free space，即使沒有用，也被佔著，那如何才能解放這塊區域呢，就有了下面的做法。
分段（Segmentation）
分段的思想很簡單，之前不是一大塊都是連在一起的麼，現在要把你們都分開，code / stack / heap 各自成為一段，段內的空間是連續的，段與段之間不必連續，這樣空間利用率上就更高了。
接下來問題就來了，一個程序會有多個段，如何知道一個記憶體地址對應的是哪個段呢？一個方法是用地址的前兩個位元組來表示：
比如00表示 code,01表示 heap。獲取實體地址的過程大概像這樣：
1 2 3 4 5 6 7 8 9 10 // 獲取前兩個位元 Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT // 獲取 Offset Offset = VirtualAddress & OFFSET_MASK if (Offset >= Bounds[Segment]) RaiseException(PROTECTION_FAULT) else PhysAddr = Base[Segment] + Offset
可能有些同學已經忘了位操作，這裡簡單複習下，所謂掩碼就是用來遮蔽指定位的一串二進位制，結合&操作就可以讓其他位都變為 0，需要保留的位保持原樣，比如110110這串二進位制，想要保留前三位，同時把後三位清零，只需要與111000執行&操作即可。如果只想要前 3 位，那麼向右移 3 位，>> 3，因此上面那段程式碼Segment就變成了前兩個位元。
拿到了Segment和Offset，先判斷下是否在安全區域內，如果超出則丟擲異常，不然就去找到真實的實體地址。
每個段依舊會有 Base 和 Bounds，但注意到有些段是向上擴張，有些是向下擴張，這個資訊也需要被額外記錄：
除此之外，還會有其他的資訊需要記錄，比如是否可讀寫等。
那這個做法有沒有問題呢，有的：
- 當 Context Switch 時，Segment Registers 必須被儲存起來方便下次使用。
- 更大的問題是，每個程序自帶了好幾個段，且大小不一，容易形成碎片化(之前申請的記憶體被釋放了)，建立新的地址空間時，就不那麼方便了。
在這個例子中，當一個程序想要申請 20KB 的段時，雖然有 24KB 的剩餘空間，但並不連續，因此會申請失敗。一種解決方法是讓記憶體空間變得更緊湊，比如暫停正在執行的程序，把記憶體拷貝到連續的地址空間，修改 Segment Register，這樣就可以變成右圖那樣了。但是代價有點大，拷貝段會花費顯著的時間。無論使用何種演算法，碎片化一定會存在，只是好點的演算法能降低碎片化程度。
順便提一下 C 裡面的記憶體申請，當malloc(size_t size)時，會返回一個指標，當free(void *pointer)時，會釋放指標對應的區域，也就是說free時，不需要知道size，這是因為申請記憶體時，有一塊額外的區域用來儲存這些資訊，比如當用戶執行ptr = malloc(20)時
除了那 20 個位元組，頭部還留了點空間用來放size和magic
1
2
3
4
5
6
7
8
typedef struct __header_t {
int size;
int magic;
} header_t;
void free(void *ptr) {
header_t *hptr = (void *)ptr - sizeof(header_t);
}
拿到指標後，可以判斷 magic number 是否相等，然後計算需要 free 的 size (header + body)，這裡有一個 簡易的 malloc 實現 供參考。
既然段模式會有碎片化的問題，那如何才能避免呢？
分頁（Paging）
Paging 的思想是把地址空間切分成固定大小的單元。比如下面一個只有 64 位元組的地址空間，每個 Page 16 個位元組
對應到真實的實體地址：
可以看到，雖然地址空間是連續的，但實體地址並不是。這樣的好處是，不用去考慮 heap / stack 會被申請多少 size，比如要申請 64 位元組地址空間，只要給 4 個 free 的 page 即可，這樣 OS 管理起來也很簡單，比如只要維護一份 free pages list，然後給出前 4 個。為了記錄虛擬頁(Virtual Page)跟實體地址之間的關係，OS 需要維護給每個程序維護一份 Page Table，它的作用就是地址翻譯。比如movl <virtual address>, %eax，由於程序的地址空間是 64 位元組，因此需要 6 個位元來表示（2^6 = 64）
由於 Page Size 為 16 位元組，因此 offset 為 4（4 個位元就能表示全一個 Page 裡的任意位置），剩下的前兩位作為 VPN (Virtual Page Number)
比如movl 21, %eax, 21 轉成 2 進位制就是010101
經過地址翻譯後，就能找到實體記憶體中的地址了
那麼問題又來了，Page Tables (用來將虛擬地址翻譯成實體地址)存在哪裡呢？在想這個問題前，先想下 Page Tables 大概有多大？
如果每個 Page Table Entry (PTE) 需要 4 個位元組來儲存 實體地址(PFN, Physical Frame Number)和其他的狀態碼，一個程序會有多少個 PTE 呢？假設地址空間為 32 位，Page Size 為 4KB，那麼虛擬地址就可以被拆分成 20 bits 的 VPN 和 12 bits 的 Offset，有 2^20 個 VPN 可能需要翻譯，就需要有對應數量的 PTE，因此一個程序大概需要 4MB 的記憶體來儲存 Page Tables，想想如果有 100 個程序在執行，就需要 400MB，這個數量可不算小。
既然 Page Tables 如此之大，放 CPU 的暫存器裡是不可能了，那就只能放記憶體了，因此在獲取虛擬地址對應的實體記憶體地址時，需要先訪問一次記憶體，這比直接訪問 CPU 的暫存器會慢很多。
順便來看一下 PTE 到底長啥樣：
前幾位都是狀態位，用來表示這段記憶體目前的狀態，比如是否有效（Valid），是否可讀，是否在 Swap 等。PFN 是真正的實體記憶體地址。
採用分頁模式後，實體地址的獲取過程就變成了這樣：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 // 把 VPN 摘出來 VPN = (VirtualAddress & VPN_MASK) >> SHIFT // 把 PTE 的地址組裝好 PTEAddr = PTBR + (VPN * sizeof(PTE)) // 訪問地址，拿到內容，注意，這裡訪問了記憶體，會影響速度 PTE = AccessMemory(PTEAddr) // 檢查是否有效 if (PTE.Valid == False) RaiseException(SEGMENTATION_FAULT) else if (CanAccess(PTE.ProtectBits) == False) RaiseException(PROTECTION_FAULT) else // 有效的話，再去拿真實的實體地址 Offset = VirtualAddress & OFFSET_MASK PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
那麼如何對這個過程進行加速呢？
TLB (Translation-Lookaside Buffer)
如果要加速，最容易想到的就是加快取，TLB 就是 CPU 晶片 MMU 的一部分，首先 check TLB 中有沒有該虛擬地址對應的實體地址，有的話直接返回，這樣就不用再訪問記憶體了，自然也就快了。那這個 TLB 到底長怎樣呢？可以認為是很簡單的 Key-Value 對，再加上額外的一些狀態碼VPN | PFN | other bits。注意這裡也會有 valid bit，只不過這裡表示的是當前這個是不是一個有效的翻譯，而 Page Table 裡的 valid 狀態碼錶示的是該記憶體是否被初始化過，如果沒有被初始化，那麼 valid 就為 0。
再來看看 Context Switch。每個程序的 VPN 和 PFN 的對應關係是不一樣的，因此上一個程序的對應關係對於下一個程序來說，完全無用。那怎麼辦？最簡單粗暴的方式就是程序切換時，直接清空，這樣雖然不會出問題，但也降低了快取命中率，尤其是頻繁切換的話。還有一種方法是多加一個欄位來表示該段翻譯對應的是哪個地址空間（ASID），有點像 PID。
但 CPU 這寸土寸金的地方，不可能放很大的快取，而且 size 越小，訪問速度才會越快，當快取滿了之後怎麼辦？可以採用常見的策略，比如 LRU 或 Random。所以雖然記憶體被叫做 Random Access Memory，但也分是否命中快取，那些命中 TLB 快取的才是最快的。
OK，訪問速度這個問題算是解決了，還有一個體積大的問題又該怎麼處理呢？
Smaller Tables
When you have two good and seemingly opposing ideas, you should always see if you can combine them into a hybrid that manages to achieve the best of both worlds.
回顧之前，我們採用段模式時，並沒有體積大的問題，因為只需要 base and bounds 就可以了，那有沒有可能把段和頁結合起來呢？我們來試試，如果每個 Segment 對應一個 Table，這樣就只需要 3 個 Table。對於 Segment 來說，現在 Bounds 變為了判斷 Page Table 的邊界（比如有多少個 Pages）。假設 32 位的地址空間，4KB Pages，就會變成這樣：
如果 TLB 沒有命中的話，過程大概如此
1 2 3 SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))
但這樣 Segment 自帶的碎片化問題依舊存在，到時 malloc 尋找可用空間時依舊會比較複雜。回過頭來，我們再來看下，佔用的這 4MB 空間真的是必須的麼？
可以看到，中間的一大部分都是空的，但依舊會被填充（因為是採用陣列的方式來訪問），那有沒有辦法既能表達「無」的資訊，又不佔用空間呢？
Multi-level Page Tables
多級分頁表。比如要去宿舍找同學玩，發現宿舍大樓門關著，那麼就不用再到寢室了，多級分頁表的思路也類似，在最前面先做一次粗檢，如果粗檢都不符合就直接打回，粗檢通過之後再來一次細檢，這樣就能把空間給省下來，具體是怎麼做的呢？
把 PTE(Page Table Entry, 包含了實體地址和狀態碼)放進 page-sized units（比如一個 Page 裡放 16 個 PTE），如果該 Page 的 PTE 都無效，那麼壓根就不申請記憶體，然後外面包一層 Page Directory 用來表示裡面是否有有效的 PTE。就像資料夾一樣，如果資料夾裡沒有檔案，自然就不會佔用空間。
左邊是單層 Page Table 的實現，可以看到，雖然只有最下面兩層是 valid 的，但中間依舊會有很多被佔用的空間（就像要訪問陣列的第 1000 個元素，必須先要把這 1000 個元素填滿）。
右邊是兩層 Page Table 的實現，通過 Valid 狀態碼就可以知道是否有必要去實體地址拿內容，如果第一層的 Valid 為 1，那麼地址轉換後就可以拿到第二層 PTE 的內容，如果此時 Valid 為 0，丟擲 Exception，為 1，那麼繼續去拿真正的存放在實體記憶體中的內容。 因此最外層的 Valid 為 1，只是表示裡面至少有一個 Valid 的 PTE。
相比之下，空間上是不是節省了不少。但也有弊端，比如需要兩次記憶體訪問才能拿到真正的虛擬地址對應的內容，所以這是一個典型的時間換空間的做法。還有一個弊端就是複雜度，無論是硬體還是作業系統，處理起來肯定比一個線性的 Page Table 查詢複雜，但為了省出來的記憶體，這個 tradeoff 還是可以接受的。
Demo
假設 CPU 在解析指令時，遇到了一個 14 位長的虛擬地址，現在要把它轉換為真實地址，並取出其中的內容：
Page Directory Index 告訴 CPU 去第幾層找 PDE(Page Directory Entry)
1 PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))
PageDirBase 對應具體的實體地址。如果 PDE 的 valid 位為 0，則直接拋異常，不然就把 Page Table Index 拿出來，找到 PTE，看看它的 valid 狀態碼，如果為 0，拋異常，為 1 則去取最終的實體地址中的內容。
小結
如果要看更詳細的，最好還是閱讀原著，會有更細緻的描述和一些沒提到的內容，比如跟磁碟的記憶體交換。
瞭解這些底層的執行機制除了滿足好奇外，還可以學到不少複雜系統的應對策略，對於其他的專案也會有所啟發。比如其中提到的 Mechanism 和 Policy，前者指定大方向，後者處理實現；時間/空間上的取捨；當有兩種看起來相反的思路時，如何有效地混合；複雜度和效能之間的取捨等等。這些對於設計、編寫高質量的程式都大有裨益。