誰會被趕出去？置換問題

頁框用罄的那一天

到目前為止你已經認識了需求分頁：一個行程剛開始時 RAM 裡幾乎空無一物，作業系統只在程式真正碰到某個分頁時才把它拉進來，這個碰觸由一次分頁錯誤來示意。這正是讓虛擬記憶體感覺像魔法的原因——一個擁有龐大位址空間的程式可以執行，而它只有寥寥幾頁常駐在實體頁框裡。有一段時間這運作得很漂亮，因為每次錯誤都只是找一個空閒頁框、把分頁載進去就好。

但實體記憶體是有限的，而虛擬記憶體存在的全部意義，就是要讓執行中程式的總需求超過你所擁有的 RAM。所以那一天終究會來：一次分頁錯誤抵達，卻一個空閒頁框也不剩——每個頁框都已經裝著某個行程的某個分頁了。作業系統不能就這樣拒絕——出錯的那道指令需要那一頁才能繼續。它必須騰出空間。它得挑一個目前正在使用的頁框，把住在那裡的分頁趕出去，再把那個頁框拿來重用、放進正要載入的分頁。這就是置換問題，而挑選犧牲者正是一套分頁置換策略的工作。

驅逐，一步一步來

讓我們放慢腳步，看一次「記憶體已滿時」的分頁錯誤，因為這些步驟會揭露成本藏在哪裡。回想一下，「挑哪個頁框來釋放」這個動作叫做犧牲分頁選擇——被選中的那一頁就是犧牲者。犧牲者的下場比乍看之下更有意思，而它完全取決於我們下一節會遇到的一小片記帳資訊。

某個行程碰到了一個不在記憶體裡的分頁；硬體引發一次分頁錯誤並陷入核心。
作業系統去找空閒頁框，卻一個也找不到——每個頁框都被佔用了。於是它執行置換策略，挑出一個犧牲頁框。
如果犧牲分頁自載入以來被修改過，作業系統必須先把它寫回磁碟（一次換出）；如果它未曾被動過，這一步就完全省略。
作業系統把犧牲者的分頁表項目標記為無效（不再常駐），這樣日後對它的任何存取本身都會引發錯誤。
作業系統把想要的分頁從磁碟讀進這個現在空出來的頁框，更新出錯行程的分頁表，使其指向那裡，然後重新啟動原先出錯的那道指令。

請注意，最糟情況下的一次錯誤如今牽涉到「兩次」磁碟傳輸，而不是一次：先把犧牲者寫出去，再把新分頁讀進來。磁碟（甚至 SSD）比 RAM 慢得驚人——一次記憶體存取以奈秒計，一次磁碟存取以毫秒計，差距大約是十萬倍。所以「一次磁碟傳輸」與「兩次」之間的差別極為巨大，而這一切就取決於關於犧牲者的一個是非題：它被修改過嗎？這個問題由單一一個位元來回答。

髒位元：便宜的驅逐與昂貴的驅逐

對每一個常駐分頁，硬體會在分頁表項目裡保留一個髒位元（又叫修改位元）。分頁載入時它是零。程式第一次寫入那一頁的那一刻，硬體就自動把這位元翻成一，完全不需要作業系統幫忙。所以髒位元剛好回答一個問題：這一頁自從從磁碟進來之後，有沒有被改動過？

為什麼這這麼要緊？如果髒位元是零，這一頁是乾淨的：RAM 裡的副本和仍躺在磁碟上的副本逐位元完全相同。所以當一個乾淨分頁被選為犧牲者時，作業系統可以直接覆寫它的頁框——磁碟上的副本已經正確，沒有東西需要保存。那是一次便宜的驅逐：只有一次磁碟傳輸，也就是讀進新分頁那一次。但如果髒位元是一，這一頁就是髒的：它含有別處都不存在的改動。趕走它得先做一次換出——把這一頁寫到磁碟好讓改動存活下來——之後才能重用那個頁框。那是一次昂貴的驅逐：兩次磁碟傳輸。

參考字串與我們記的分數

為了公平地比較置換策略，我們需要一個共同的測試，而標準的那一個就是參考字串：說穿了就是一個行程依序碰觸的分頁編號序列，連續重複通常會被合併（連續碰分頁 7 三次只算一次，因為第二、三次碰觸絕不會出錯）。參考字串是一個行程記憶體生命的劇本，剝到只剩置換唯一在乎的東西——哪一頁、依什麼順序。把同一條字串和同樣數量的頁框餵給兩套策略，你就能精確數出每一套各造成多少次錯誤。

Reference string (page numbers touched, in order):
   7  0  1  2  0  3  0  4  2  3

With 3 frames, walk it left to right:
   - a page already resident  -> HIT  (no fault)
   - a page not resident      -> FAULT (must load it; maybe evict)

The score we keep:
   page-fault rate = (number of faults) / (number of references)

Lower fault rate = better policy on this string.

一條參考字串加上一個頁框數，就是整個實驗。本階段裡每一套策略，都用它在像這樣的字串上產生的錯誤次數有多少來評分。

分數本身就是分頁錯誤率：錯誤次數除以總參考次數，一個介於 0 與 1 之間的數。它是整個這個階段裡最重要的一個量，因為它直接牽動速度。一次記憶體存取的有效時間，大致上「大部分時候是快速的 RAM 時間，再加上偶爾出錯時那殘酷的磁碟時間」——所以就算錯誤率極小也可能主宰一切。如果一次記憶體存取約 100 奈秒，而一次錯誤要花約 8 毫秒（多了八萬倍），那麼僅僅千分之一的錯誤率，就已經讓平均存取比單靠 RAM 慢上好幾倍。把錯誤率削下來，就是這場遊戲的全部。