分頁置換與輾轉現象

髒位元(dirty bit)

想像一座圖書館,每本書都有一張小貼紙,只要有人第一次在書頁邊緣寫下筆記,貼紙就翻成紅色。當館員想把書放回倉庫時,那張貼紙告訴她一切:如果還是灰色(沒被動過),她直接上架就好,因為倉庫的副本一模一樣;如果是紅色,她就得先把寫過字的版本複印回倉庫,免得改動遺失。髒位元就正是記憶體中一個頁的那張貼紙。

具體來說,每個分頁表項目都帶有一個位元,叫修改位元或髒位元。當該頁的任何一個位元組第一次被寫入時,硬體會自動把它設為 1。作業系統在載入或存回該頁時把它清為 0。如今當這個頁被選為犧牲頁,作業系統會讀這個位元:若是 0,該頁是乾淨的,置換空間(或原始檔案)裡的副本仍然正確,這個頁可以完全不寫磁碟就丟棄;若是 1,該頁是髒的,作業系統就必須在重用該頁框之前先把頁寫回後備儲存。唯讀頁與從未被修改的程式碼頁永遠保持乾淨,這讓它們逐出起來非常便宜。

為什麼重要:髒位元大致把置換乾淨頁的成本砍了一半——而大多數程式碼與唯讀資料都是乾淨的。這正是為什麼像增強型第二次機會這樣的演算法會偏好乾淨的犧牲者,也是為什麼一個程式指令的頁可以立刻丟掉,而你編輯過的文件的頁卻不行。別把髒位元(這個頁有沒有被寫過?)和參考位元(這個頁最近有沒有被碰過,不論讀寫?)搞混——它們回答不同的問題、驅動不同的決策。

一個程式碼的頁髒位元為 0(程式碼從不被寫入),所以逐出它不花成本——直接重用頁框即可。一個裝著你正在輸入的文件的頁髒位元為 1,所以逐出前作業系統必須把那個頁寫出到置換空間,多一次磁碟操作。

乾淨的頁:免費丟棄。髒的頁:必須先寫回。

髒位元由硬體在第一次寫入時設定,談的是成本而非新近程度。一個經常被讀但從不被寫的頁,髒位元是 0(逐出便宜),就算它被大量使用也一樣——新近程度是參考位元的工作,不是髒位元的。

又称
modify bitmodified bit修改位元M 位元