為什麼一個慢到難以忍受的把戲卻感覺很快
在前三篇導覽裡，我們建起了需求分頁：行程啟動時 RAM 裡幾乎什麼都沒有，每當它碰到一個不在記憶體裡的分頁，硬體就會引發一次分頁錯誤，核心從磁碟把那頁取進來，然後讓出錯的那條指令重新執行。我們很誠實地說過：從磁碟取一頁慢得殘忍——比讀 RAM 慢上數百萬倍。於是這篇導覽必須回答一個謎題：如果每次分頁錯誤都是一場災難，那需求分頁為什麼不是一場大難？為什麼你那台靠著這同一個把戲在跑的筆電，感覺起來卻是即時的？
整個答案靠的是真實程式行為的一個經驗事實，而不是什麼聰明的演算法。程式並不會把記憶體存取亂撒在整個位址空間上。它們會「聚成一團」。一個迴圈會把同樣那十幾條指令跑上幾千次；一段常式會把同一個陣列從頭讀到尾；一個函式會一再地推入、彈出同樣那幾個堆疊分頁。這種聚團現象叫做參考局部性，而它正是這個階段裡一切之下那根唯一承重的假設。
局部性的兩種風味
參考局部性有兩種截然不同的風味，把兩者都取個名字會很有幫助。時間局部性說的是：如果你剛剛碰過某個位址，你很可能很快又會碰它。迴圈計數器、你剛拿到的鎖、目前這一行程式碼——這些都會在極短的時間窗口內被一再命中。空間局部性說的是：如果你碰過某個位址，你很可能很快就會碰它的鄰居。你會一個元素接一個元素地走過陣列；你會把檔案從頭讀到尾；CPU 會一條接一條按順序執行指令。
現在把這個和分頁連起來。一個分頁是——比方說——位址空間裡 4 KB 的一塊，是一整批相鄰位址被綁在一起。空間局部性意味著：對一個新分頁的第一次存取（它要花一次分頁錯誤）之後，通常會跟著對「同一頁」其他位元組的數百乃至數千次廉價存取，不再有更多錯誤。時間局部性意味著：一旦某頁常駐了，程式在轉往別處之前，會有一陣子持續回頭找它。分頁與局部性是天作之合：分頁正好就是讓局部性收成的那個單位。
讓整個記憶體階層在每一層運作的，是同一條原則，而不只對分頁有效。CPU 快取賭的是局部性，好把熱資料留在核心附近；那為你剛翻譯過的分頁編號貼的便利貼——TLB——賭的也是局部性，好讓大多數位址翻譯能跳過走訪分頁表的步驟。局部性不是只用一次的把戲。它是同一個觀察被一再兌現，從暫存器一路向下直到磁碟。
替痛苦標上數字：有效存取時間
局部性告訴我們錯誤很罕見，但我們應該量化地問一句：要多罕見才算夠罕見。設分頁錯誤率 p 是會引發錯誤的記憶體存取所佔的比例。一次單純的 RAM 存取要花一點小小的時間——在我們的例子裡就叫它 200 奈秒吧。一次分頁錯誤的代價是這個再加上整套服務常式：陷入核心、找一個空閒頁框、從磁碟讀入該頁、更新分頁表、重啟指令。光是那次磁碟讀取就壓過其他一切；假設整套錯誤服務平均要 8 毫秒——也就是 8,000,000 奈秒。
有效存取時間不過就是個加權平均：絕大多數存取是廉價那種，比例為 p 的一小撮是毀滅性那種。公式是「有效存取時間 = (1 - p) * 200 + p * 8,000,000 奈秒」。可怕的地方在於這兩種代價有多麼懸殊。磁碟錯誤比 RAM 存取貴上四萬倍，所以一個近乎可忽略的 p 仍會把平均值拖高到驚人的地步。看看「千分之一的錯誤」會幹出什麼好事。
試試 p = 1/1000——每一千次存取一次錯誤，聽起來罕見得無害。平均值會變成大約 0.999 * 200 + 0.001 * 8,000,000 ≈ 8200 奈秒。那比 200 奈秒的理想值慢了 41 倍，而錯誤率只不過是千分之一。把 p 壓到 1/100,000，你仍要付出約 280 奈秒，慢了 40%。想保持在全速的大約 10% 以內，你需要的錯誤率必須低於大約四十萬次存取才一次。那是一份緊得驚人的預算，而它正是局部性必須做到不超支的那份預算。
請和這個結果坐一會兒，因為它把一切都重新框定了。虛擬記憶體並不會讓程式變快——這是一個值得當場戳破的常見誤解。它頂多只是不增加額外負擔；每一次錯誤都只會讓你更慢。虛擬記憶體買到的不是速度，而是「可能性」：它讓一個比 RAM 還大的程式得以根本跑得起來，或讓眾多程式得以共存。因此，這個階段裡每個機制的職責，不是把錯誤加速，而是讓錯誤罕見到那份拖慢隱形不見。上面那個數字——數十萬次存取才有一次錯誤——正是局部性必須打中的標靶。
替程式所需的東西命名：工作集
局部性說的是：程式會有一陣子把它的存取聚在一小群分頁周圍，然後當它進入新的工作階段時，又轉移到另一群。那個不斷變動的群有個名字：工作集。非正式地說，一個行程的工作集是它在「最近的過去」實際碰過的那組分頁——而依局部性，也就是它在「不久的將來」最可能會碰的那組。它是程式當下的注意力中心，並隨著程式在各階段之間移動（載入、運算、寫出輸出）而變化。
我們可以用一個滑動窗口把這件事講精確。挑一個窗口大小——比方說最近的 10,000 次記憶體存取——然後把工作集定義為「那個窗口裡被參考過的相異分頁」。隨著窗口在時間上往前滑，不再被使用的分頁會掉出這個集合，而剛被碰到的分頁會進入它。這個集合的大小，也就是工作集大小，是對「這個行程此刻需要多少頁框才能順暢執行」的誠實估計。給它這麼多頁框，錯誤就維持罕見；給它更少，錯誤就會爆炸。
reference string (page numbers touched, left = oldest):
... 2 6 1 5 7 7 7 7 5 1 6 2 3 3 4 4 4 4 3 4 4 4 ...
|<------ window of 10 refs ----->|
^now
pages seen in the window = { 3, 4 }
WORKING SET SIZE = 2 frames right now
Earlier, mid-loop, the window held { 1, 5, 6, 7 } -> 4 frames.
The set SHRANK because the program entered a tighter phase.工作集給了作業系統一條難以打敗的記憶體管理政策：盡量讓每個執行中行程的「整個工作集」都常駐在 RAM 裡，你就能免去它不停的錯誤之苦。如果所有行程的工作集總和塞得進實體記憶體，系統就會運轉如歌。可一旦那個總和超過了 RAM，就必須有什麼東西讓步——而讓步的是效能，而且是以這個階段所能端出最醜陋的方式。
當工作集再也塞不下：輾轉
假設你一次跑太多程式，使得各工作集加總所需的頁框比你擁有的還多。現在每個行程都餓著：它連自己的熱頁都留不住。於是它發生錯誤，核心為了騰位子而趕走「另一個行程」需要的某頁，那個行程立刻發生錯誤要把自己的頁拿回來，這又把第一個行程的頁趕走，如此沒完沒了。CPU 幾乎把所有時間都花在等磁碟、做換進換出分頁的記帳工作上，而幾乎沒有時間在執行真正的程式碼。這種崩潰叫做輾轉（thrashing）。
輾轉有一個鮮明、卻違反直覺的特徵。當你加入越來越多行程時，CPU 使用率一開始會往上爬——很好，更多工作可以重疊。但一過了「工作集塞不下」那個點，使用率不只是停止上升而已；它會墜崖。系統會劇烈變慢，原因恰恰是你「要它做更多」。你的筆電「凍住」了，硬碟燈長亮，游標幾乎不動——可是 CPU 卻幾乎閒著，因為每個行程都卡在等一個「即將被另一個行程偷回去」的分頁。
解藥直接從診斷推出：別讓總需求超過供給。如果作業系統偵測到輾轉，正確的舉動雖違反直覺卻是對的——把「一整個」行程暫停，將它的分頁換出到交換空間、釋放那些頁框，好讓剩下的行程終於有足夠空間留住自己的工作集。可執行的行程「變少」，弔詭地，反而意味著實際完成的工作「多得多」。這正是工作集模型的實戰運用：只有當一個新行程的工作集能與其他行程並存時才放它進來，並在頁框告急時甩掉一些行程。
這條路接下來通往何方
這篇導覽帶出了兩個大哉問，而這個階段就分頭去回答它們。第一：當錯誤來臨而 RAM 已經滿了，我們該趕走哪個常駐分頁來騰位子？這個選擇選錯了，你就會趕走某人工作集裡的一頁，幾乎立刻引發一次錯誤——這正是輾轉的種子。明智地挑選犧牲者就是分頁置換，也就是緊接在本階段之後那整個階段的主題；在那裡，局部性會再度登場，作為「藉由偏好近期用過的分頁來逼近那無法實現的最佳政策」的正當理由。
第二：我們能不能藉由「對什麼共用一頁、什麼時候才載入什麼」更聰明一點，來讓錯誤更便宜、甚至完全避免？這是本階段最後一篇導覽的主題。那裡有兩個想法，是局部性與懶惰的純粹應用。寫入時複製讓一個剛 fork 出來的子行程與它的父行程「共用每一頁」，直到其中一方寫入為止，於是一個邏輯上「複製了巨大位址空間」的 fork，幾乎什麼都不複製——只複製那難得被寫到的一頁。記憶體映射檔案讓一個檔案直接以分頁的樣貌出現在你的位址空間裡，於是讀它不過就是換了個樣子的需求分頁，由局部性決定哪些部分才真的會被載入。
退一步，整個階段的形狀就清楚了。需求分頁是機制；局部性是它行得通的原因；工作集是我們衡量「程式需要什麼」的方式；輾轉是我們無視那個衡量時會發生的事；而寫入時複製與記憶體映射檔案，則是從一開始就「需要更少分頁、更少錯誤」的聰明辦法。它們每一個都倚靠著同一個謙卑的觀察：程式在任一時刻只用到自己記憶體的一小部分，而且會一再地回頭找它。