作業系統中的頁面置換演算法
作業系統中的頁面置換演算法
1. 什麼是頁面置換演算法
當作業系統發生缺頁中斷時，作業系統必須在記憶體中選擇一個頁面，將其換出記憶體，為即將調入的頁面騰出空間。這時我們就需要一個頁面置換演算法。
值得注意的是，頁面置換演算法不僅用於記憶體和硬碟之間的頁面置換，也用於電腦其他部分。例如 CPU 高速快取的置換，以及應用程式應用快取的置換，都是相通的。
2. 常用頁面置換演算法
2.1 最優頁面置換演算法 OPT
這是最好但不可能實現的演算法。即在缺頁中斷髮生時，我們把當前記憶體中下一次被使用時間最晚的頁面置換出去。
這是不可能實現的，因為作業系統不可能知道各個頁面下一次什麼時候被訪問。
2.2 最近未使用頁面置換演算法 NRU
作業系統中一般為每一個頁面設置了兩個狀態位，當頁面被讀操作或寫操作訪問時，設置 R 位；當頁面被寫入時，設置 M 位。每次訪問記憶體時就更新這些位。
當啟動一個進程時，所有頁面的兩個狀態位都被置為 0，除此之外 R 位還被定期清零，相當於標記為最近未使用頁面。
當發生缺頁中斷時，作業系統檢查所有頁面並根據 R 位和 M 位的值，把他們分為四類：
- 沒有被訪問，沒有被修改。
- 沒有被訪問，已被修改。
- 已被訪問，沒有被修改。
- 已被訪問，已被修改。
NRU 演算法隨即從類編號最小的非空類中選擇一個頁面淘汰。原理是易於理解的。
2.3 先進先出頁面置換演算法 FIFO
FIFO 演算法維護一個所有當前在記憶體中的頁面的鏈表，最新加入的頁面在表尾，最早加入的頁面在表頭。發生缺頁中斷時總是淘汰表頭頁面並將新調入的頁面放在表尾。
FIFO 演算法過於簡單，沒有考慮到頁面訪問的熱點性，所以很少使用純粹的 FIFO 演算法。
2.4 第二次機會頁面置換演算法 SC
FIFO 演算法可能會置換出經常使用的頁面，為了避免這個問題，我們改進出了第二次機會演算法。
當我們使用 FIFO 檢查最老頁面頁面，即表頭頁面時。如果 R 位是 0，那麼說明這個頁面又老又不被使用，直接置換；如果 R 位置是 1，就將 R 位清零，並被頁面放到鏈表的尾端。然後再重新從表頭取頁面。
2.5 時鐘頁面置換演算法
第二次機會演算法是一個比較合理的演算法，為了減少它在鏈表中移動頁面的開銷，我們使用一個環形鏈表來進行優化。
時鐘演算法維護一個錶針指向最老的頁面，當發生缺頁中斷就檢查這個錶針所指的頁面。如果 R 位是 0，就直接置換，並前移指針。如果 R 位是 1，則將 R 位清零，也前移指針。
2.6 最近最少使用頁面置換演算法 LRU
LRU 是最優演算法的一個很好的近似。但我們要在記憶體中完全實現 LRU 有很高的代價，這要求我們維護一個包含所有頁面的鏈表。或者也可以用一個特殊的硬體來專門服務於這個需求。
NFU 演算法是一種常用的軟體模擬 LRU 的方式，他將每個頁面和一個計數器相關聯。每次時鐘中斷時，將每個頁面的 R 位（0 或 1）累加到計數器上。這個計數器大體上跟蹤了各個頁面被訪問的頻繁程度。發生缺頁中斷時，就置換計數器值最小的頁面。
老化演算法是對 NFU 演算法的進一步改良，因為 NFU 演算法從不忘記任何事情，一個擁有很高計數值的頁面會擁有很高的優先順序。而老化演算法會將每一次檢查時的 R 位記錄下來，並只保留有限長度，每次比較這些數字的值，並置換計數值最小的頁面。
2.7 工作集頁面置換演算法
一個進程當前正在使用的頁面的集合稱為工作集。如果在進程運行過程中，工作集中的相當一部分都沒有在記憶體中，那就會出現大量的缺頁中斷，極大地影響系統的性能，稱這個程式發生了顛簸。
所以許多分頁系統會設法跟蹤進程的工作集，以確保在進程運行之前工作集就已經在記憶體中了，這個方法稱為工作集模型。其目的在於大大減少缺頁中斷率，在進程運行前預先裝入其工作集頁面稱為預先調頁。
工作集頁面置換演算法的基本思路是找出一個不在工作集中的頁面並淘汰，我們看下面的圖，這是頁表的一部分：
在處理每個表項時，演算法會檢查 R 位：
-
如果它是 1，就把當前實際時間寫進頁表項的上次使用時間域，以表示缺頁中斷髮生時該頁面正在被使用。既然該頁面在當前時鐘滴答中已經被訪問過，那麼顯然他應該出現在工作集中，而不是被刪除。並將 R 位置為 0。
-
如果它是 0，那麼表示當前時間滴答中該頁面還沒有被訪問過，則它可以被置換。為了知道它是否應該被置換，需要用當前實際運行時間減去上次使用時間，計算出生存時間，並與通常進程運行時間進行比較。
- 如果當前生存時間更大，則該頁面不在工作集中，說明可以用新頁面置換它。在找到所有這樣的頁面後，會隨機選擇其中一個進行置換。
- 如果當前生存時間更小，則頁面在工作集中，那就繼續檢查下一個表項。
2.8 工作集時鐘頁面置換演算法
當缺頁中斷髮生後，需要掃描整個頁表才能確定被淘汰的頁面，因此基本工作集演算法有很大的開銷。工作集時鐘演算法是基於時鐘演算法和工作集演算法的一種改進演算法。
每次缺頁中斷時先檢查指針指向的頁面：
- 如果 R 位被置為 1，那麼該頁面在當前時間滴答中被使用過，那麼把 R 位置為 0，並將指針移動到下一個頁面。
- 如果 R 位被置為 0，那麼要令頁面生存時間和進程通常運行時間相比較。
- 如果頁面生存時間大於通常運行時間，那麼不在工作集中，則置換。
- 如果頁面生村時間小於通常運行時間，那麼將指針移動到下一個頁面。
3. 頁面置換演算法小結
