比整棟樓還大的房間
在上一階裡，你學到了作業系統如何讓許多程式老老實實共用同一塊 RAM：每個行程用自己一套私有位址來命名記憶體，而分頁會把那些位址切成固定大小的分頁，再透過一張分頁表——一本書從頁碼到頁框的索引——對映到同樣大小的實體頁框。關鍵在於：分頁早已打破了「一個行程必須坐在一整塊連續記憶體裡」這條規矩；它的分頁可以散落在真實記憶體的各個角落，誰也不介意。那份自由，正是我們現在要走過去的那扇門。這一階要問一個更大膽的問題。如果一支程式的分頁，不必同時全都待在 RAM 裡呢？如果其中有些根本就不在 RAM 裡呢？
讓這件事成為可能的，是一個日常的觀察。在編輯器裡打開一份 50 頁的文件，你一次也只看其中一頁；載入一款龐大的遊戲，任一瞬間你也只站在它廣大世界裡的某一個房間。一支程式完整的位址空間常常大得驚人，但它此刻真正在用的那一小片卻很小。那麼，何必堅持在第一條指令執行之前，就把整個東西全搬進 RAM？虛擬記憶體這項技術，就是在執行一個行程的同時，只把它目前需要的部分留在實體記憶體裡，其餘的停放在磁碟上。換來的回報，正是標題裡那場幻覺：每支程式都可以相信——並且能定址——遠比機器實際擁有的還要多的記憶體。
兩個位址空間，只是鬆鬆地連著
要讓這件事行得通，我們得把邏輯位址和實體位址之間的分離——上一階那個承重的主意——推得比以往任何時候都更用力。在此之前，你還可以半想像著：每一個邏輯分頁，背後都默默有某個頁框在等著它。請把這個假設丟掉。邏輯位址空間如今是一張慷慨的地圖，畫著程式可能指名的一切；而實體頁框，是一池小得多的真實座位。一個邏輯分頁，可能此刻正坐在某個頁框裡，也可能跑到磁碟上去了，又或者它從來沒被碰過、因而至今背後什麼都沒有撐著。地圖很大；座位很少；而兩者之間的連結，是即時地接上、又即時地拆開的。
把它想成一套龐大的劇院訂位系統。手冊上印的座位圖標著上千個座號——那就是邏輯位址空間，每位觀眾的手冊都一模一樣。但實際的劇院只有幾百張真椅子（頁框）。手冊上多數的座位，並不對應到你此刻正坐著的任何一張椅子；它們只是印出來的可能性。分頁表，就是帶位員手上的夾板，記著你每一個真正領用過的手冊座位，被安排到了哪一張真椅子上——而其餘的，就標一句「尚未入座」。手冊可以承諾一座巨大的廳堂；建築物能容納的，永遠就是它能容納的那麼多。
有效位元，以及按需把分頁搬進來
在某一次存取時，硬體怎麼知道一個邏輯分頁此刻是坐在某個頁框裡、還是跑到磁碟上去了？每一筆分頁表項目都帶著一個小旗標，也就是有效／無效位元。當這個位元讀出來是「有效」時，這筆項目裡存著一個真實的頁框號，翻譯便以硬體全速進行。當它讀出來是「無效」時，這筆項目（目前）並沒有 RAM 在背後撐著：這個分頁在磁碟上、或越界了、或根本還沒用過。關鍵在於：這正是上一階用來做保護的同一個有效位元——用來標記那些落在行程配額之外的位址。虛擬記憶體把它拿來兼第二份差事：把「合法但此刻不在 RAM 裡」和「就在 RAM 裡，請繼續」這兩件事區分開來。
這便解鎖了核心的技術：需求分頁。作業系統不在一開始就把每個分頁都載入，而是讓行程在 RAM 裡幾乎什麼都沒有的狀態下啟動，再懶洋洋地、只在程式第一次伸手去拿某個分頁的那一刻，才把它搬進來——就像一間廚房，總是在食譜某個步驟剛好需要某項食材的當下、才從冷藏庫把它取出來，從不提前。如果一個行程從未碰過某個分頁，那個分頁就永遠不會被載入，半點時間和 RAM 都不會花在它身上。把這做到極致——讓行程啟動時記憶體裡連一個分頁都沒有，每一個都等到第一次用到時才以錯誤的方式搬進來——這就叫做純需求分頁。
Page table for one process (valid bit V):
logical page | V | where it is
-------------+---+--------------------------
0 | 1 | frame 17 (in RAM)
1 | 0 | on disk (not loaded yet)
2 | 1 | frame 04 (in RAM)
3 | 0 | never touched
... | |
CPU accesses logical page 1 -> valid bit = 0 -> trap! (a page fault)分頁錯誤，以及為什麼指令必須重新執行
當程式伸手去拿一個有效位元為 0 的分頁時，會發生什麼事？硬體沒辦法翻譯這個位址，於是它做了硬體在無法繼續時一向會做的事：朝核心拋出一個陷阱（trap），很像中斷那一聲叫喚大樓管理員的門鈴。這個特定的陷阱，叫做分頁錯誤。這名字會誤導人——它不是錯誤，也沒有任何東西出了差錯。它只不過是一個約好的訊號，意思是「這個合法的分頁不在 RAM 裡，請去把它取來」。完整的服務流程——找一個空閒頁框、從磁碟上的交換空間把分頁讀進來、修好分頁表、然後繼續——是接下來兩篇導覽的主題；在這裡我們只需要它的大致輪廓。
但這裡藏著一個微妙又漂亮的要求，值得停下來品味，因為它形塑了處理器的設計方式。當錯誤發生時，那條闖禍的指令正被攔在半途——它已經開始執行，也許甚至已經改了一半某個暫存器，才發現自己的分頁不見了。等作業系統把分頁取回之後，程式必須像什麼都沒打斷過一樣繼續下去。這就要求指令重新執行（instruction restart）這項特性：CPU 必須有能力把那條闖禍的指令從頭、完整地、得出一模一樣結果地再執行一遍，彷彿第一次的嘗試從未發生過。作業系統會把程式計數器倒帶回那條闖禍的指令，讓它重跑一次——這回分頁已經在了，它便一路順暢地通過。
為什麼連罕見的錯誤都很傷，以及為什麼它通常不會
現在來算一筆令人不安的帳。一次命中常駐分頁的記憶體存取，大約花 100 奈秒。服務一次分頁錯誤——陷入、找頁框、從磁碟讀取、重新執行——可能要花好幾毫秒，因為它碰到了磁碟。這是好幾萬倍的差距。所以一次存取的平均成本，也就是有效存取時間，是被那罕見的昂貴情況主宰的。如果 p 是分頁錯誤率（會出錯的存取所佔的比例），一次錯誤約花 8 毫秒、一次命中花 100 奈秒，那麼有效時間大約是 (1 - p) 乘 100 奈秒，加上 p 乘 8 毫秒。令人不安的地方在於：只要小得可憐的一個 p，就足以把一切毀掉。
代入數字看看。讓 p 只有千分之一，也就是每一千次存取才出錯一次。那麼有效時間大約是 0.999 乘 100 奈秒，加上 0.001 乘 8,000,000 奈秒，約等於 100 奈秒 + 8000 奈秒 = 約 8100 奈秒。我們想要的是 100 奈秒；得到的卻是 8100。千分之一的錯誤率，就讓記憶體慢了大約八十倍。要把拖慢幅度壓在比方說百分之十以內，錯誤率得降到大約四十萬分之一以下。誠實的結論很殘酷：需求分頁能成立，唯一的前提是分頁錯誤極其罕見。那麼，在實務上它為什麼不是一場大災難？
出手相救的，是關於真實程式行為的一個深刻經驗事實：參考局部性。程式並不會把它的存取均勻地撒滿整個位址空間；它們會聚成一團。一個迴圈會把同樣那寥寥幾條指令重跑上千次（時間局部性），而走訪一個陣列時，會一個接一個地碰相鄰的元素（空間局部性）。所以在任一時刻，一支程式其實只用到一小撮、緩緩漂移的分頁——也就是它的工作集。只要把那一小撮分頁留在 RAM 裡，幾乎每一次存取都會命中；錯誤之所以變得罕見，正正因為真實的程式碼既重複又愛找鄰居。局部性，是那份把上面嚇人的算式變成日常無感小事的經驗禮物——而工作集，連同寫入時複製與記憶體對映檔案，正是本階接下來要去的地方。
幻覺讓兩樣東西變得便宜
一旦你接受了「一個邏輯分頁不必擁有自己私有的頁框」這件事，兩個可愛的把戲幾乎免費地掉了出來，而它們正好替這篇開場導覽收尾。第一個是寫入時複製。回想一下，fork 會造出一個近乎完美複製其父行程的子行程。把父行程記憶體的每一個分頁都複製一份很浪費，尤其當子行程往往在片刻之後就呼叫 exec、把那一切全丟掉的時候。於是作業系統改成讓父子共用同樣那些實體頁框、標成唯讀，唯有當其中一方真的去寫某個分頁時，才默默地只替那一個分頁做一份私有副本。fork 就此變便宜了，因為在非得複製之前，幾乎什麼都不複製。
第二個是記憶體對映檔案。你可以不用 read(fd, buf, n) 這類明確的呼叫來讀檔案，而是請作業系統把檔案直接對映進你的位址空間，於是檔案的內容就單純地以一段記憶體的樣子出現。如今讀這個檔案，不過就是讀那些位址，而我們剛剛蓋好的需求分頁機制會把一切都打點好：檔案的某一頁，在你第一次碰它時，由一次平凡的分頁錯誤拉進來，而被改髒的分頁稍後再寫回去。那套撐起「無限記憶體」幻覺的同一套分頁錯誤管路，也把磁碟上的一個檔案，變成一個你可以當作普通記憶體來讀寫的東西。從一個主意——位址只是鬆鬆地連著頁框——流出了隔離、超大的位址空間、便宜的 fork，以及「檔案即記憶體」。