從區塊到一張查找表
第 1 篇導覽留給你分頁的兩半。一個行程眼中的記憶體被切成等大的分頁，實體 RAM 被切成同樣大小的等大框，而任何一頁都能坐進任何一個框。因為每個區塊都一樣大，一頁塞進一個框就像一本書塞進任何一個空的書架縫隙——這正是分頁之所以能消滅外部碎裂的全部理由。但這留下了一個明擺著的問題懸在那裡：如果我程式的第 5 頁可以在第 200 框、第 17 框、或任何地方，硬體究竟怎麼找到它？總得有個東西記住每一頁實際落在哪裡。
那個東西就是分頁表。把它想成一本書的索引：每一頁一列、依分頁編號排序，而每一列告訴你那一頁此刻住在哪個框裡。程式從來看不到它——程式自始至終只用邏輯位址（第 5 頁、第 40 位元組），也就是它編譯時所用的、那種好用的虛構位址。分頁表就是那本字典，把這些轉成實體位址（第 200 框、第 40 位元組），也就是 RAM 裡真正的位置。每個行程各有一張分頁表，因為每個行程都有它自己對分頁的私有編號，而核心把它當作這個行程記帳的一部分保管著。
把一個位址一分為二
這裡有個讓分頁變得便宜的聰明把戲：一個邏輯位址其實不是一個數字，而是兩個數字穿著同一件外套。高位的位元是分頁編號——是哪一頁——而低位的位元是位移——在那一頁裡走多遠。這就是分頁編號／位移的拆分，硬體只要讀同一個位址裡不同的位元就免費完成它。沒有人需要做除法；分頁大小是 2 的次方，正是為了讓這個拆分是位元範圍之間乾淨的一刀。
我們來親手走一個位址。就說一頁 4 KB，因為那是經典的大小。一頁 4 KB 是 2^12 = 4096 位元組，所以位移恰好需要 12 個位元才能指名一頁裡的任何一個位元組。在一台 32 位元機器上，這就剩下 32 - 12 = 20 個位元給分頁編號，所以有 2^20 大約一百萬個可能的分頁。現在取一個具體的邏輯位址：分頁編號 5、位移 40。硬體把最高的 20 個位元讀成 5，去查分頁表的第 5 列，找到——我們就說——第 200 框。它接著把第 200 框和原封不動的位移 40 重新黏回去，組成實體位址。位移從來沒有經過那張表；發生的只有分頁換成框這件事。
logical address = ( page number , offset ) <- one address, two fields
32-bit address, 4 KB page (offset = 12 bits, page# = 20 bits)
[ page number = 5 | offset = 40 ]
| |
| look up row 5 | (unchanged, rides along)
v in page table |
page table[5] = frame 200 |
| |
v v
[ frame number = 200 | offset = 40 ] = physical address注意位移的大小悄悄地把一件事固定下來：它就是分頁大小。一個 12 位元的位移意味著一頁 4 KB，就這樣——你不可能只要一個而不要另一個。這也正是分頁那點小小自白所在之處。因為記憶體是一次發整整一頁，一個行程的最後一頁幾乎從不會剛好填到滿，而它裡面剩下的空檔就浪費掉了。那份浪費就是內部碎裂：分頁拿掉了可變空洞那種雜亂的外部碎裂，換來一點點整齊的內部浪費，每個區域至多一頁。這是一筆真正划算的交易，但它是交易，不是免費的午餐。
表住在哪裡，以及兩次存取的問題
那麼分頁表本身在哪裡？它太大了，無法放在 CPU 暫存器裡——一百萬列塞不進晶片——所以分頁表住在主記憶體裡，就跟普通資料一樣。因此必須有人告訴 CPU 它在哪，而這就是分頁表基底暫存器（PTBR）的工作：一個單一暫存器，存著目前這個行程那張表起點的實體位址。要讀第 5 列，硬體就算出 PTBR 加上 5 乘以每筆的大小，再去讀那個位置。這也正是分頁讓行程切換變便宜的原因：要切換到另一個行程，核心只要把 PTBR 重新載入，指向那個行程的表。整個位址空間靠一次暫存器寫入就換掉了。
但把表放進記憶體有個殘酷的代價，而你應該感受得到它。程式所做的每一次記憶體參照，如今都變成了兩次記憶體參照：硬體先讀分頁表去轉譯位址，然後才讀程式真正想要的那筆實際資料。想要陣列裡的一個位元組？那是一次存取去查表，加上一次存取去取那個位元組——每一次、在每一條指令上都這樣。這就是兩次記憶體存取的問題，它意味著天真的分頁會讓你的機器以大約一半的速度運轉。記憶體本來就已經是記憶體階層裡慢的那一截；把每一次觸碰都加倍，不是一筆你付得起的稅。
值得精確地說一說這一切到底是誰在做。轉譯不是軟體——核心並不會在每一次記憶體存取上跑程式碼，那樣會毫無指望。它是硬體：一個叫做記憶體管理單元（MMU）的專用單元坐在 CPU 與記憶體之間，為每一個位址即時執行「查找並替換」。核心的角色是在記憶體裡把表架設好、並載入 PTBR；MMU 則以硬體速度做每次存取的粗活。這整套硬體舞步——拆分位址、查表、組出實體位址——就是我們所說的位址轉譯。
解法：一小撮近期轉譯的快取
從兩次存取問題逃脫的辦法是轉譯後備緩衝區（TLB）。把它想成你貼在剛用過那幾頁上的便利貼。完整的分頁表是那本書的索引，坐在慢速的記憶體裡；TLB 則是一小撮便利貼——一個小而極快、就在 MMU 上的硬體快取——它記住最近用過的那幾組（分頁編號到框編號）的對應。在大老遠跑去查分頁表之前，MMU 會先瞄一眼它的便利貼。
在TLB 命中時，分頁編號已經在某張便利貼上了：那個框幾乎是瞬間就回來，沒有額外的記憶體跑腿——轉譯幾乎不花成本。在 TLB 失誤時，分頁編號不在那裡，於是 MMU 必須做那趟慢慢的、跑去記憶體裡分頁表的走訪（完整的第二次存取），找到那個框，然後把這一組加進 TLB 以備下次，並趕走一張舊便利貼好騰出空間。這整場賭注押在區域性上：程式一遍又一遍地觸碰同樣那少數幾頁（一個迴圈、一段堆疊、當前的資料），所以一旦某頁上了便利貼，接下來對它的上千次存取都會是命中。
你可以給「為什麼這管用」標上一個數字，而它很驚人。假設一次記憶體存取要 100 奈秒、TLB 查找快到我們把它約成 0、而 TLB 命中率是 99%。有效存取時間把這兩種情況平均起來：命中花一次存取（100 奈秒），失誤花兩次（200 奈秒，一次讀表加一次讀資料）。所以平均是 0.99 乘以 100 加 0.01 乘以 200 = 99 加 2 = 101 奈秒。我們付的只比沒分頁的記憶體成本多了區區 1%，而不是兩次存取問題所威脅的那 100% 罰則。一個命中率高的小快取，把一筆災難性的稅變成了四捨五入的誤差——這正是第 3 篇導覽整篇都獻給 TLB 的原因。
分頁表項裡還住著什麼
分頁表的一列不只是一個框編號。每一筆分頁表項（PTE）都帶著幾個額外的位元，由 MMU 即時檢查，而它們把這張表從單純的位址地圖，變成記憶體安全的執法者。其中三個最要緊。有效位元說的是這一頁究竟有沒有真的對應到一個框；如果程式碰了一頁、而它的有效位元是關的，MMU 就會拒絕並引發一個陷阱。那個陷阱正是核心藉以得知「程式要嘛做了個野指的參照，要嘛——更有用地——碰到了一頁此刻不在 RAM 裡」的方式，而那是通往下一階分頁錯誤與虛擬記憶體的門。
保護位元說的是你被允許對這頁做什麼：可讀、可寫、可執行，以任何組合——就是你早已以檔案權限（像 rwxr-xr-x）見過的那套讀／寫／執行的想法，如今套用到記憶體的每一頁上。如果程式試圖寫一頁被標成唯讀的、或執行一頁被標成不可執行的，MMU 會在任何損害發生之前就引發陷阱。這就是作業系統讓一個行程無法在自己的程式碼上亂塗的方式，也是它能為了安全把程式碼頁標成「只可執行」的方式。因為這些檢查就住在 PTE 裡、並由硬體在每次存取上執法，保護在執行期不花任何額外成本。
第三個位元是髒位元，它純粹是為了日後的記帳。MMU 在這一頁第一次被寫入時自動把它設起來。為什麼要費這個事？因為當虛擬記憶體日後需要趕走這一頁以騰出空間時，一頁乾淨的（從未被寫過的）頁可以直接丟掉——它在磁碟上的副本仍然有效——而一頁髒的頁則必須先寫回去。髒位元讓作業系統能為沒被更動過的頁略過那次寫回，這是一筆實實在在的速度收益，你在兩階之後會大量倚賴它。一個由下一篇導覽展開的相關小點：因為 PTE 指名那個框，兩個行程可以有各自指向同一個框的項，這正是共用分頁讓一個函式庫或唯讀資料被映射一次、卻供多方使用的方式。