三種門鈴，同一個櫃台
到目前為止，你已經認識了 CPU 被從普通的使用者程式碼裡拉出來、拽進核心的每一種方式——但你是一次認識一種、散在不同的階段裡，所以值得把它們聚到同一張表上。剛好有三種。某個裝置做完工作、按了一聲中斷：那是門鈴，非同步且非自願，在你的程式沒選的時刻抵達。你自己的程式用一個像「read(fd, buf, n)」這樣的系統呼叫，刻意向核心請求一項服務，硬體會把它當成一個陷阱送達：同步而且完全自願，是程式有意伸出手去。還有一道指令出了錯——除以零、碰到非法位址、撞上一次分頁錯誤——這會引發一個例外：像陷阱一樣同步，卻像中斷一樣非自願，是程式從未要求過的意外。
底下是把整個階段串在一起的統合性點子：核心並不為這三種事件蓋三台分開的機器。它只蓋一台。三者全被漏斗般匯進你在中斷那裡認識過的同一張對照表——在 x86 上那就是中斷描述表，也就是 IDT——其中每個事件都帶著一個小小的向量號碼，而這張表把那個號碼直接變成處理它的常式的位址。一個計時器中斷可能是向量 32；一次分頁錯誤例外是向量 14；系統呼叫陷阱則有它自己專屬的向量。同一個櫃台、貼在裡頭的同一本通訊錄、三種訪客。CPU 不在乎自己為什麼被召喚；它只是讀出向量、索引那張表、切換進核心模式，然後跳過去。
synchronous? voluntary? example ---------+--------------+-------------+--------------------------- interrupt| no | no | disk done, key pressed, timer trap | yes | yes | read(fd, buf, n) (system call) exception| yes | no | divide-by-zero, page fault all three -> vector number -> index the IDT -> handler address
同步與非同步，以及為什麼這很重要
那張小表藏著一個值得放慢腳步的區別，因為它改變了核心必須有的行為。陷阱和例外是同步的：它們是由當前正在執行的那道指令所引起的，所以它們發生在一個精確、可重現的點上——用同樣的輸入跑同樣的程式碼，同一個陷阱每次都會在同一處觸發。中斷則是非同步的：它是由外部世界引起的，所以它能落在任何兩條指令之間，而重跑你的程式並不會重現它確切的時機。這正是你從並行那個階段一路帶著的同一個誠實區別——交錯是不可預測的，而不管一個非同步事件從哪裡溜進來，核心都必須是正確的。
為什麼同步／非同步的劃分在實務上這麼要緊？因為涉及可重啟性與歸咎。當一個例外是同步且精確的，核心就確切知道是哪道指令造成的，能修好問題（取回缺少的分頁），然後重啟那一道指令——這正是需求分頁背後那個安靜的奇蹟。一個非同步的中斷不歸咎於任何特定指令；程式是無辜的，所以核心必須原封不動地保存它的狀態、完成裝置的差遣，然後返回，彷彿程式只是眨了一下眼、什麼都沒漏掉。兩者甚至連遮罩方式都不同：CPU 在處於某段微妙的區段時，能暫時停用（遮罩）大多數中斷，告訴門鈴「稍等一下」，但它無法遮罩一次除以零——那道指令已經出錯了，沒辦法把它壓回去。
現在把問題反過來：核心自己也需要記憶體
底下這個念頭會讓多數人措手不及。在處理一個中斷或一次分頁錯誤的同時，核心不斷需要配置屬於它自己的記憶體——給一個剛抵達的網路封包一塊新緩衝區、在分頁表裡放一筆新項目、一個描述核心剛開啟的某個檔案的結構。但核心沒辦法打電話求救：沒有更高的權威可以向它要記憶體，沒有從天上遞下來的 malloc。核心就是那位大樓管理員，而管理員握著儲藏室唯一的那串鑰匙。所以核心必須跑自己的配置器、在它自己的位址空間裡、快到能跟上每秒數千次中斷。這篇導覽剩下的部分，談的就是那些配置器——而令人意外的是，一個並不夠。
為什麼要兩個？因為核心的記憶體請求有兩種天差地別的形狀，而單一一種工具兩者都服務不好。有些請求又大又是頁的尺寸或更大：「給我四個連續的分頁，當一塊新的 I/O 緩衝區。」另一些則又小又頻繁到誇張：「給我一個 96 位元組的結構來描述這個行程」，隨著行程來來去去而重複上百萬次。用切割整個 4 KB 分頁的方式去服務一個 96 位元組的請求，會浪費掉幾乎一整個分頁——那就是你在分頁那個階段認識的內部碎裂，固定區塊內部的閒置空間。所以核心疊起兩個配置器：一個粗的，發出一串串整頁；一個細的，坐在它上面，把那些分頁再細分成幾乎毫無浪費的小物件。
夥伴系統：發出整頁
粗的那一層是夥伴系統，一旦你看到那幅圖，它簡單得令人愉快。核心把空閒記憶體保存成一塊塊大小全都是二的次方的區塊——1 頁、2 頁、4 頁、8 頁，依此類推——分類進一串串清單裡，每種大小一張清單。當你請求比方說 3 頁時，夥伴系統會往上湊到下一個二的次方（4 頁），並找一個那個大小的空閒區塊。如果最小的空閒區塊比你需要的大，它就把它對半切，再對半切，直到它得到一個剛好正確大小的區塊——而它每切出的兩半之中，一半就叫做另一半的夥伴。
- 往上湊。一個 3 頁的請求被湊到 4 頁（下一個二的次方）。夥伴系統絕不發出奇零的尺寸；這種湊整是它刻意接受的一點點內部碎裂代價。
- 找，或切。先看 4 頁的那張清單。若它是空的，就看 8 頁的清單，拿一個區塊，把它切成兩個 4 頁的夥伴——自己留一個，把另一個放上 4 頁的清單。
- 交出去。把選中的區塊標記為已配置，回傳它的位址。被切開的區塊記得自己的大小與位置，好讓稍後釋放時能把這次切割還原。
- 釋放並合併。當這塊被釋放時，檢查它的夥伴是不是也空閒著。若是，就把兩塊合回一個更大的區塊——並且也檢查那個更大區塊的夥伴，能往上合多遠就合多遠。
最後那一步正是整件事的重點，也是採用二的次方方案的理由。因為一塊與它的夥伴大小永遠相同、又坐落在可預測、對齊的位址上，核心能用一次快速計算就找到某個被釋放區塊的夥伴——把位址的某一個位元翻轉——並在常數時間內檢查它們能不能合併。合併對抗外部碎裂：少了合併，記憶體會慢慢碎成一地小空閒區塊的紙花、再也沒有大段連續可用，即使總量上還有大把記憶體空著。夥伴系統不斷把紙花重新縫回大張的紙。誠實的取捨在於：把每個請求都往上湊到二的次方，會在每個區塊內部浪費一點記憶體——又是內部碎裂——而這正是為什麼我們需要在它之上再加一個更細的配置器。
slab 配置器：微小物件，毫無浪費
細的那一層是slab 配置器，它解決一個夥伴系統會做得很糟的問題。核心一再配置同幾種小物件：行程控制區塊、檔案結構、網路緩衝區、目錄項。想像一間廚房不斷需要一模一樣的小碗。你不會每次需要一個碗，就砸碎一整個餐盤、再把碎片黏成一個新碗。你會改成在架子上備好現成、剛好那個尺寸的碗；需要時抓一個，用完洗一洗放回去。一個 slab（板）就是那個架子：一個或多個分頁（向夥伴系統要來的）被預先切分成一排等大的槽位，全都專屬於某一種物件。
兩個聰明的點子讓這件事快到通用配置器追不上的程度。第一，因為一個 slab 裡的每個槽位都剛好是一個物件的大小，基本上沒有內部碎裂、也不必搜尋合適的位置——配置就只是「拿下一個空槽」，一次常數時間的抓取，而釋放就是「把這個槽重新標為空閒」。第二，也更微妙的是，配置器把物件快取在它們已初始化的狀態裡。當你釋放一個行程控制區塊時，slab 配置器並不把它擦乾淨；它讓那個結構可重複使用的骨架原地留著，好讓下一次配置略過大部分的初始化。重複使用一個溫熱、半成形的物件，而不是從冷冰冰的位元組構築一個出來，正是許多速度的來源——碗已經是對的形狀，你只要把它再裝滿。
在我們繼續之前一個誠實的提醒，因為核心裡的配置器要與使用者程式從不面對的約束共處。核心記憶體往往不能被換出——一塊磁碟即將寫入的緩衝區必須固定待在某個頁框上，否則那次DMA傳輸會塗寫到錯誤的地方。而一個跑在中斷情境裡的處理常式承受不起等待：它在配置時絕不能在某條慢速路徑上阻塞，因為正如你所見，一個中斷處理常式的上半部跑在關著中斷的狀態下、又沒有任何行程可以送去睡。所以核心的配置器往往必須承諾要嘛立刻成功、要嘛立刻失敗，絕不「等我一下、我去騰點空間」。正是這些壓力，使得核心跑的是精瘦、專用的配置器，而不是你的使用者程式享有的那個舒適、會阻塞的 malloc。下一篇導覽會接起貫穿這一切的那條線——當中斷與多顆核心同時都伸手去抓核心自己的共用資料時，核心如何讓它保持正確。