塞不下的那張表
到目前為止，你已經有了第 2 篇導覽裡那張平面的圖像：一張分頁表就是一個大陣列，用分頁編號當索引，它的每一筆告訴你該用哪個框。它就像一本書的索引——查那個分頁編號，讀出它真正住在哪裡。這幅圖像是對的，對一台小機器來說也夠用了。麻煩從位址變大時開始，而現代的位址非常大。
我們來算一下算術，因為這正是這篇導覽存在的全部理由。取一個 32 位元位址、一頁 4 KB。位移吃掉低 12 個位元，因為 2^12 = 4096 = 4 KB。剩下 32 - 12 = 20 個位元給分頁編號，所以有 2^20 大約一百萬頁，因此一百萬筆。如果每筆分頁表項是 4 位元組，這張平面表就是 2^20 乘以 4 = 4 MB。而現在是刺人的地方：那是「每個行程」4 MB，而且整張表必須在記憶體裡、還要連續。有一百個行程，你光在表上就花了 400 MB。
而 32 位元還是輕鬆的情況。把這道算式套到 64 位元位址上：現在分頁編號是 64 - 12 = 52 個位元，所以一張平面表會有 2^52 筆——那是好幾百萬 GB，比有史以來製造過的全部 RAM 還大，而且這是為「單一一個行程」。在這裡，平面表根本不可能。但要注意一件令人懷抱希望的事：一個擁有 64 位元位址空間的行程，其實絕大部分都用不到。它的程式碼、堆積、堆疊只佔據少數幾個小區域，而中間那一大片是空的。我們是在花錢儲存一個幾乎全空的索引。這篇導覽裡的每一招，都是一種「不再為空的部分付錢」的辦法。
一棵由小表組成的樹
第一條、也是最常見的逃生路線是多層（階層式）分頁表。它的想法是「把分頁表本身也拿來分頁」：不再用一個巨大的陣列，而是把分頁編號切成數段，用第一段去查一張小小的頂層表，這張表的每一筆指向第二層的表，第二層表的每一筆最終才指向框。把它想成一本依首字母分冊的電話簿——那本薄薄的外層索引告訴你該翻開哪一冊，而只有你真正需要的那幾冊才必須存在。具體地說，再拿那個 32 位元、4 KB 頁的情況，其中分頁編號是 20 個位元。把這 20 個位元切成 10 和 10。最高的 10 個位元索引一張有 2^10 = 1024 筆的外層表；其中每一筆指向另一張有 1024 筆的內層表；最低的 12 個位元一如既往是位移。於是一個邏輯位址現在讀成三個欄位、而不是兩個：（外層索引、內層索引、位移）。每一張個別的表都是 1024 筆乘以 4 位元組 = 4 KB——剛好一頁，這並非巧合：每一層都恰好塞進一個框，於是作業系統能儲存、甚至把這些表本身也換出去。
32-bit logical address, 4 KB pages:
| 10 bits | 10 bits | 12 bits |
| outer | inner | offset |
index index
outer table inner table frame in RAM
+----------+ +----------+ +-----------+
| [outer]--|-------->| [inner]--|------->| byte at |
+----------+ +----------+ | offset |
(1024 entries, (1024 entries, +-----------+
one page) one page)
Win: an unused outer entry = NO inner table at all (saves 4 KB).省下來的地方就在這裡。一個只用到少許記憶體的行程，需要的是它那一張外層表，加上恰好涵蓋它實際分頁的那少數幾張內層表；每一筆指向空白區域的外層項，只要單純標記成「不存在」，整張內層表就壓根不會被配置。一個小小的行程也許只用到外層表和兩張內層表——總共大約 12 KB，而不是 4 MB。位址空間中間那幾乎全空的部分，如今幾乎不花成本，這正是我們想要的。真正的 64 位元機器只是再多加幾層：典型的 x86-64 用四層（較新的晶片提供五層）來涵蓋它們實際實作的 48 或 57 位元位址。
走一遍兩層位址
我們來手動追蹤一次轉譯，好讓這個機制有真實感，用我們那套（10 位元、10 位元、12 位元）的兩層方案。假設 CPU 產生了某個邏輯位址——具體來說，假設它解碼成外層索引 1、內層索引 2、位移 3076。硬體（MMU 內部的分頁表走訪器）會做以下這些事，而關鍵是分頁表基底暫存器告訴它外層表住在哪裡。
- 拆分位址。硬體把位元切成（外層 = 1、內層 = 2、位移 = 3076）。此時還沒碰到記憶體——這只是線路。
- 讀外層表。前往分頁表基底暫存器，跳到外層表的第 1 筆，讀它。（第一次記憶體存取。）如果那一筆被標記成「不存在」，這區域就是未映射——引發錯誤。否則它存著一張內層表的實體位址。
- 讀內層表。跳到那張內層表的第 2 筆，讀它。（第二次記憶體存取。）檢查它的有效位元與保護位元；若無效，就引發錯誤。否則它給出框編號——譬如框 87。
- 組出實體位址。把框 87 和位移 3076 結合，得到真正的實體位址，最後才去讀或寫程式真正想要的資料。（第三次記憶體存取——那次有用的。）
數一數代價：為了取一個位元組要三次記憶體存取，其中兩次是純粹的額外開銷，花在走那棵樹上。這個開銷在「每一條指令」上都重演，會讓你的記憶體流量增為三倍，把機器拖垮。這就是把位址轉譯的代價講得活靈活現，也是 TLB 之所以存在的理由——它把最終（分頁編號到框）的結果快取起來，於是下一次存取附近的位址，就能完全跳過這趟走訪的步驟，直奔資料。
當這棵樹還是太高：雜湊表與反轉表
多層的樹省了空間，但在一台 64 位元機器上，這棵樹本身可能長得很高——四或五層意味著一次 TLB 失誤要走訪四或五次。有兩種替代設計繞開了這棵深樹。第一種是雜湊分頁表。不再直接用分頁編號當索引，而是把分頁編號做雜湊，拿結果當索引去查一張雜湊表。每個槽位存著一小串項的鏈，而每一項記錄它所代表的實際分頁編號（這樣你才能分辨碰撞），外加那個框。你把分頁編號雜湊，跳到那個槽位，然後沿著那條短鏈比對分頁編號，直到找到相符的那一筆。
好處是表的大小跟著「實際映射了多少頁」走，而不是跟著「位址空間能有多大」走——一個稀疏的 64 位元空間花費很少。壞處是那條鏈：一次轉譯可能要比對好幾筆，而糟糕的雜湊會讓鏈變長。雜湊表在 64 位元系統那種龐大而稀疏使用的位址空間上大放異彩。
第二種設計最為大膽：反轉分頁表。注意到目前為止每一種方案都是「每個行程一張表，並用分頁編號當索引」。反轉把這整件事倒過來：整台機器只保留一張表，RAM 的每一個實體框恰好對應一筆。每一筆說的是「目前是哪個行程的哪一個虛擬頁佔著這個框」。既然 RAM 是固定且不大的（區區幾百萬個框），這唯一一張表就很小，而且它的大小永遠不取決於位址空間有多大、有多少個。一台有 256 個框的機器，就有一張 256 筆的表，就這樣。
但反轉製造了一個新的頭痛。要轉譯時，CPU 手上有的是（行程、分頁編號），想要的是一個框——可是這張表是用「框」當索引，方向正好反了。原則上你得掃過每一筆，去找相符的（行程、分頁）配對，這在每次存取上都是沒指望的。真正的修法是把反轉表配上一個雜湊：把（行程、分頁編號）做雜湊，跳到大致正確的那一筆附近，再核對。當然 TLB 仍然坐在最前面，所以絕大多數存取根本不會碰到反轉表。還有一個值得點名的代價：在行程之間共用一個框很彆扭，因為每個框只有一筆、只記得一個擁有者——這個主題下一篇導覽會接著談。
如何選擇——以及什麼是不變的
沒有單一的贏家；每一種設計都是拿一種代價去換另一種。多層樹是常見硬體上的預設：簡單、支援完善，但它可能需要好幾次走訪存取，而且它仍然是每個行程一棵樹。雜湊表讓表的大小跟著實際使用走、適合龐大稀疏的空間，但一次轉譯可能要追一條鏈。反轉表把表的總大小綁在實體 RAM 上、不管有多少行程在跑，卻讓查找與共用都更難，並重度仰賴雜湊加 TLB。正確的選擇取決於位址空間的大小，以及你正在打造的硬體。
貫穿這三種設計，要緊抓住「不變的東西」，因為那才是耐久的理解。把一個邏輯位址拆成（分頁編號、位移）在每一處都一模一樣——這些方案只改變「分頁編號如何變成框」，從不改變那個位移。每頁的記帳位元無論結構為何都隨著該項一起走：有效位元、保護位元（讀／寫／執行），還有你在第 2 篇導覽遇過的髒位元，都仍然住在每一筆分頁表項裡。而 TLB 坐在它們全部的前面，所以一旦命中，所選結構的代價就完全消失——多層、雜湊或反轉，一次 TLB 命中在 CPU 看來都是一樣的。