一步一步處理分頁錯誤

從錯誤停下的地方接手

在上一篇導覽裡，我們搭起了需求分頁：分頁住在磁碟上，只有在第一次被碰到時才被拉進記憶體。分頁表裡的每一筆都帶著一個有效/無效位元，它說「這個分頁此刻真的在某個頁框裡」或「這個分頁不在記憶體裡」。當 MMU 試著轉譯一個其分頁表項被標為無效的位址時，硬體就會觸發一個陷阱。那個陷阱就是分頁錯誤。第二篇導覽就停在那裡，停在門鈴響起的那一刻。這篇導覽要談的，是誰來應門、又做了些什麼。

把「分頁錯誤是什麼、不是什麼」講清楚會很有幫助。它不是錯誤，儘管名字取得不太走運——一次 fault 不過是一個有禮貌、預料之中的中斷，它說「你要的資料是真實存在的，只是還沒進到 RAM；請稍待，讓我去把它取回來」。拿它跟非法存取（碰到你空間之外的記憶體）相比，後者才真的致命，會讓你的行程被結束掉。作業系統靠著查同一張表來分辨兩者：如果這個位址對這個行程來說是合法的，只是分頁此刻在磁碟上，作業系統就服務這次錯誤並讓你繼續；如果這個位址從來就不屬於你的位址空間，它就用分段錯誤把你結束掉。

完整的服務流程

底下是整場救援，從頭到尾走一遍。想像你的行程執行了一道讀取某個邏輯位址上一個位元組的指令，MMU 發現該分頁無效，門鈴響了。核心——也就是這棟大樓的管理員——此刻會跑一段固定的常式，也就是分頁錯誤服務流程。先用全速讀一遍，然後我們會在那些出人意料的環節上放慢腳步。

陷入核心。出錯的那道指令在半途停住。硬體存下足夠的狀態（程式計數器、各暫存器），然後跳進核心的分頁錯誤處理常式，這就跟回應一個中斷一模一樣。你的行程此刻被阻擋了，不再執行。
檢查位址。核心拿出錯的位址，對照該行程的紀錄來查。合法但不在記憶體裡？就服務它。真的非法？就結束這個行程。從這裡開始，我們假設是合法的那種情況。
找一個空閒頁框。核心從它的空閒清單裡抓一個空的實體頁框。若一個都沒有，它得先挑一個犧牲分頁把它逐出——那就是分頁置換，是後面某個階段的主題。
排定磁碟讀取。核心請磁碟把所需的分頁，從它在置換區或檔案裡的家，複製進那個頁框。磁碟讀取很慢——數以百萬計的 CPU 週期——所以核心不會空轉等待。
讓 CPU 去做別的事。在分頁傳輸的這段時間裡，核心去執行另一個就緒的行程。磁碟稍後會用一個中斷來通知傳輸完成，所以不會有任何週期被白白空轉掉。
磁碟完成，中斷抵達。傳輸完成，磁碟觸發一個中斷。核心更新分頁表：把那一筆指向新的頁框，並把有效/無效位元翻成有效。
重啟出錯的那道指令。核心把你的行程重新標為就緒。當它下次執行時，它會重新執行那道剛才出錯的指令——而這一次轉譯成功了，位元組就在那裡，你的程式從頭到尾都不知道剛剛發生過任何事。

那張清單裡有兩件事值得再看一眼。第五步就是你在輸入輸出與排程那兩個階段認識過的同一招：一個慢速裝置絕不該凍結整顆 CPU，所以核心把等待中的行程停泊起來，把處理器交給別人。這麼說來，一次分頁錯誤不只是一樁記憶體事件——它觸發了一次完整的、離開你行程的情境切換，而且（在磁碟完成時）還要再切回來。第七步則是那個安靜的奇蹟，它值得自己一個小節。

可重啟指令的要求

第七步假設了關於硬體的一件很深的事：一道做到一半的指令可以被收回來、從頭再跑一次，而效果就跟它第一次根本沒跑過時一模一樣。這就是 可重啟指令的要求，整座需求分頁的大廈都立在它之上。如果一道指令能在做到一半時出錯，並讓機器停在一個被改了一半的狀態，那麼重跑它就會讓它的某些效果加倍，你的資料就會悄無聲息地壞掉。

把這個陷阱具體化來看。想像一道把一整塊位元組從一處複製到另一處的指令，並假設來源跨過了一道分頁邊界。它把前半段複製得好好的，然後在搆到第二個來源分頁時出錯。作業系統取回那個分頁、重啟這道指令——它此刻會把整塊再複製一次，把前半段疊著它已經寫過的位元組重做一遍。如果來源和目的地有重疊，第二次複製就會讀到錯誤的值，結果就錯了。解法純粹是一種硬體設計的紀律：支援需求分頁的 CPU 保證可重啟，做法不是在改動任何東西之前，先檢查這道指令將會碰到的所有分頁，就是記下足夠的資訊以便撤回一個半成品步驟。

計算代價：有效存取時間

分頁錯誤是正確的，但它慢得殘酷，而看清它究竟有多慢是值得的。一次正常的記憶體存取大約花 100 奈秒。一次得跑到磁碟的分頁錯誤則要花上 8 毫秒左右——那是 8,000,000 奈秒，大約是命中的 80,000 倍那麼慢。有效存取時間模型把這些調和成一個你能拿來推理的數字。設 p 為分頁錯誤率，也就是會出錯的存取所佔的比例。那麼平均代價就是這兩種情況的加權混合。

EAT = (1 - p) * 100 ns  +  p * 8,000,000 ns

   p = 0          ->  EAT = 100 ns          (no faults)
   p = 1/1000     ->  EAT ~= 8100 ns        (81x slower!)
   p = 1/400000   ->  EAT ~= 120 ns         (a tolerable 20% hit)

   one fault in a thousand accesses already
   wrecks performance by a factor of ~80

即便極小的錯誤率也會主宰一切，因為單單一次錯誤就抵得上約 80,000 次正常存取。

盯著那些數字看，因為它們承載著整個主題的核心教訓。要把拖慢控制在比方說百分之十以內，你需要把錯誤壓到大約每四十萬次存取才有不到一次——一個低到令人吃驚的比率。需求分頁在實務上之所以行得通，並不是因為錯誤便宜；它們貴得能讓人破產。它行得通，是因為錯誤罕見，而它們罕見的那個特定原因，正是下一篇導覽要整篇討論的：參考局部性。程式並不是隨機戳記憶體的；它們會在同一小片鄰里裡反覆造訪一陣子，所以一個分頁一旦被取回，它往往能在下一次錯誤之前服務上千次存取。

分頁從哪裡來，以及一個捷徑

第四步說「把分頁從它的家複製過來」，那麼家在哪裡？對於一個以檔案為後盾的分頁（你程式自己的程式碼，或一個記憶體映射檔案），家就是磁碟上那個檔案。對於匿名分頁——你的堆疊和堆積，它們不對應任何檔案——家則是磁碟上一塊專用的區域，叫做置換空間。當記憶體吃緊、作業系統需要把頁框拿回來時，它會把一個分頁寫出到置換區；這就是故事的頁出那一半，正是你剛追蹤過那次錯誤的鏡像。頁入（在錯誤時）與頁出（在壓力下）合起來，就是磁碟如何充當 RAM 那緩慢而龐大的延伸。

在逐出那一半裡藏著一個聰明的捷徑，而分頁表項讓它成為可能。每一筆都帶著一個髒位元，硬體會在分頁一被寫入的那一刻就把它設起來。當作業系統要逐出一個分頁時，它會檢查那個位元：如果分頁是乾淨的（自從被讀進來後從未被改動），磁碟上仍躺著一份一模一樣的副本，於是作業系統可以乾脆把頁框丟掉，完全不必寫回。只有髒的分頁才真的得被寫到置換區去。這單單一個位元就能把逐出時的流量大約砍掉一半，因為唯讀的程式碼和剛載入的分頁通常都是乾淨的。