Page Replacement
Concept
當發生 page fault 但沒有 free frame 時，OS 就必須選擇一個 page swap out，把需要的 page swap in。這個「選誰出去」的過程就叫 page replacement
Steps
Step 1: 確認 target page 位置
確認 target page 在哪裡？
- 在 frame 上 → 直接用
- 在 swap space → 繼續
Step 2: 找 free frame
- 如果有 free frame → 直接用
- 如果沒有 free frame → 繼續
Step 3: Swapping
透過 replacement 演算法挑一個 victim frame，然後
- 如果 modify bit 有被設置 → swap out
- 如果 modify bit 沒被設置 → 直接覆寫
可以直接覆寫是因為 disk 上有相同的內容所以不用存到 swap space，下次要用時再從 disk 讀就好
Step 4: Restart Instruction
Page Replacement Algorithm
Goal
我們希望找到最佳的 victim page 選擇方式使「page replacement 次數最少」
Belady’s Anomaly
Reference String
Reference string 就是 process 存取 page 的順序
Methods
FIFO Page Replacement
維護一個 queue 當需要選 victim 就選擇最先建立的 page 作為 victim
Optimal Page Replacement
當我們知道完整的 reference string 我們就可以透過將「最晚會用到的 page」作為 victim 來找到此問題最優解
實際上我們無法知道完整的 reference string 所以這個方法只能用來和其它演算法比較看他們的好壞
LRU Page Replacement
D-OS-Ch10ec-LRU_Page_Replacement
Counting-Based Page Replacement
紀錄每個 page 被存取的次數，用計數高低來決定 victim
- Least Frequently Used (LFU)：踢掉計數最小的——用最少的，假設以後也不需要
- Most Frequently Used (MFU)：踢掉計數最大的——用最多的，假設已經「用完了」；邏輯罕見成立，效果差
Not Frequently Used (NFU)：