概述
上一篇文章把分段和分頁介紹了一下，以及兩者的尋址方式和優化方法都介紹了，這節主要介紹另一個重要問題，頁面置換算法，當記憶體空間不足時，需要把記憶體中的頁放入磁盤，那到底選擇哪些頁放到磁盤上比較好呢？這篇文章會回答這個問題。
如何解決記憶體不夠用
早期的解決辦法是采用覆寫技術，但是覆寫技術需要程式員做大量的工作，非常麻煩且低效，後來就發明了交換技術，這裡注意，這裡的交換是把整個程式在記憶體和磁盤之間交換并不是頁之間的交換，其缺點就是開銷太大，是以後來就發明了虛存技術，這種技術解決了上面兩種技術的痛點。下面就分别介紹一下這三種技術。
覆寫技術
把程式按照其自身邏輯結構，劃分為若幹個功能上相對獨立的程式子產品，那些不會同時執行的子產品共享同一塊記憶體區域，按時間先後來運作。
把程式分成如下幾個部分：
- 常駐部分：這部分代碼和資料需要常駐記憶體，比如一個程式的main函數。
- 可選部分：需要運作時從磁盤加載到記憶體，平時就放在磁盤。
如果可選部分，兩個不同的子產品之間沒有互相調用關系，那麼這兩者就可以共享同一片記憶體區域，隻是執行的先後不同而已，下面舉個例子。
public class Test {
public static void module1(){
System.out.println("i am module1");
}
public static void module2(){
System.out.println("i am module2");
}
public static void main(String[] args) {
module1();
module2();
}
} 上面的代碼是一個簡單的java程式，其中main函數就是上面介紹的常駐部分，而module1和module2就是可選部分，并且兩者沒有互相調用關系，是以module1和module2可以共享同一片記憶體區域，當module1運作的時候，module2沒有必要加載到記憶體中，當module1運作結束之後，module2再加載到記憶體中占用module1使用的記憶體區域。
缺點：
需要程式員自己來界定子產品，并且确定哪些子產品之間沒有互相調用關系，對于程式的設計一點也不友好。
交換技術
當有多個程式在記憶體中運作的時候，如果有一個新的程式要進來執行，發現記憶體不足了，這個時候有一種解決辦法就是把記憶體中正在運作的某個程式儲存到磁盤上，然後把空間騰出來讓新的程式使用。
缺點：
把整個程式從記憶體搬到磁盤，開銷是很大的，如果頻繁做這個操作，會非常影響程式的執行效率。
虛存技術
虛存技術基本原理如下
- 在程式裝載到記憶體的時候不把全部内容一次性全部裝入記憶體，隻是部分載入
- 當程式執行過程中發現有些資料或指令不在記憶體中，就把需要的資料或指令加載到記憶體中
- 把記憶體中沒有使用的頁放到磁盤上，以騰出記憶體空間
和交換技術相比，他的粒度更低，是以頁為機關（上節把分頁已經介紹了，不懂的朋友可以看上一篇文章^_^），而不像交換技術一次性把整個程式交換。與覆寫技術相比，他也是把部分指令和資料加載到記憶體中，但是不用考慮把程式分成互相不調用的子產品，是以虛存技術綜合了覆寫技術和交換技術的優點，并且解決了交換技術和覆寫技術的缺點。
虛存技術理論基礎
其實也說不上是理論基礎，隻是一個觀察的結果，該結果就是程式在執行的過程中，目前通路的指令和接下來要通路的指令，目前通路的資料和接下來要通路的資料都集中在一個較小的區域内。這個就是“局部性原理”，不要看這隻是一個簡單的結果，其實使用非常廣泛。
ok，上面把三種技術都介紹完了，下面的部分講解虛存技術使用的頁面置換算法
最優頁面置換算法
當發生缺頁中斷，并且記憶體不足時，需要把記憶體中的頁和磁盤中的頁進行交換。所謂最優頁面置換算法就是記憶體中的頁在下一次被通路之前等待的時間最長的頁，那問題來了，怎麼預知哪個頁需要等待的時間最長呢？事實上是無法預知的，是以這個算法是無法實作的，但是無法實作并不是沒有意義，當一個程式跑完之後，通路的頁的序列确定下來之後，自然知道在每次缺頁中斷時應該交換哪個頁，是以這個算法可以用來評估别的頁面置換算法的好壞，如果有一種頁面置換算法的結果和最優頁面置換算法的結果很接近，那這種算法就ok，反之，就不行。
圖檔來源：清華大學作業系統公開課
圖檔内容說明：a,b,c,d表示要通路的頁，最上面1,2,3,4,5，，，表示時間序列，記憶體中最多儲存4頁，而且a,b,c,d都已經加載到記憶體，在1,2,3,4時刻分别通路c,a,d,b，這個是沒有問題的，因為記憶體中已經存在，當通路到e的時候就會發生缺頁中斷，這個時候由于記憶體最多儲存4頁，那就需要把其中的一頁放到磁盤上，騰出來空間供e使用，根據最優頁面置換算法，我們可以發現d在第10時刻才會通路，等待的時間最長，是以在第5時刻，把d頁換成e頁是最優的。
先進先出頁面置換算法
這種算法其實就是我們常說的隊列的方式（FIFO），最先進去的頁面，最先被置換出去，這種方式思路确實很簡單，但是并不是簡單的就是有效的，這種算法隻考慮頁面在記憶體中的存活時間，并沒有考慮這個頁面是不是經常被通路的頁面，有時候會把經常通路的頁面給置換到磁盤上，這就很尴尬，是以這個算法很少被單獨使用。
最近最久未使用頁面置換算法
簡稱LRU算法，這個算法應用太廣泛了，redis,mysql中都可以看到他的身影，以至于現在找工作，很多面試官都變态的要求現場手寫一個LRU算法，于我個人看來，沒必要，除非面試的崗位确實需要很多牛逼的算法實作，不然進去擰螺絲，搞那麼複雜幹啥。下面就介紹一下這個算法的思想，需要維護一個清單，記錄每個頁面被通路的時間，當發生缺頁中斷時，把最久沒有被通路的頁面給置換掉，這個其實是對最優頁面置換算法的一個逼近，因為根據局部性原理，最近被頻繁通路的，在未來的一小段時間内還會頻繁被通路。反過來說，很久未被通路的，将來也會很長時間不會被通路。
實作方法
可以采用連結清單實作，把剛剛通路的頁面作為連結清單的首節點，當通路頁面在連結清單中存在，就把那個節點移動至首節點，當發生缺頁中斷的時候，把連結清單的尾節點淘汰。
時鐘頁面置換算法
圖檔來源：清華大學作業系統公開課
在圖檔開頭第一句話，時鐘頁面置換算法是LRU的近似，是對FIFO的改進，下面就解釋一下為什麼這麼說，LRU算法是需要詳細記錄每個頁面的通路時間的，但是這個算法并沒有記錄詳細的通路時間，隻是使用一個标志位，也就是之前介紹過的頁表中的通路位，如果被通路過，無論是讀還是寫，就把這個标志位改為1，否則為0，這個算法淘汰的時候，優先選擇通路标志位為0的頁面，這樣淘汰的頁面可能并不是最久未被通路的，因為這個是采用一個指針類似于鐘表一樣來旋轉，找到那個标志為0的就淘汰，是以說是LRU的一種近似。
為什麼說是FIFO（先進先出）的改進呢？如果所有的頁面都沒有被通路過，标志位都是0，如果這個時候發生了缺頁中斷，就把最先放入記憶體的給淘汰掉。如果所有的頁面都被通路過，标志位都是1，如果在标志位變成1的過程中沒有發生缺頁中斷，那淘汰的依然是最先進入的頁面。但是這個算法考慮到最近是否被通路，而不像FIFO直接淘汰最早通路的頁面，是以說是FIFO的改進。
算法過程如下：
- 如果指針指向的頁面通路位是0，直接淘汰
- 如果是1，就把通路位改成0，指向下一個
- 如果周遊一遍發現都是1，就把最開始的那個頁淘汰
下面舉個例子來說明這個指針旋轉的過程。
圖檔來源：清華大學作業系統公開課
圖中過程如下：
- t = 1,t = 2,t = 3,t = 4,連續通路a,b,c,d，把每個頁的通路位都修改為1
- t = 5,指針旋轉一周，發現都是1，把所有的1都改成0，然後把開始的那個頁給淘汰，把e頁加入進來
- t = 6,命中，把b頁通路位改成1
- t = 7,缺頁中斷，此時指針指向b頁，但是b頁通路位為1，是以尋找下一個c,發現通路位為0，淘汰掉
- ...
- 後面的分析都是如此
二次機會法
二次機會法，其實對時鐘算法的優化，因為時鐘置換算法在淘汰頁面的時候隻考慮了頁面是否被通路過，如果所有的頁面都被通路過，那讓一個未被寫過的頁面淘汰比一個已經被寫過的頁面淘汰成本低很多，因為被寫過的頁面是髒頁，還要把這個頁面的内容先寫到磁盤，如果一個頁面沒有被寫過，可以直接丢棄。是以二次機會法，就是使用了兩個标志位，第一個标志位是通路位，第二個标志位修改位，當發生缺頁中斷時，具體的淘汰流程如下：
- 如果通路位和修改位都是0，就直接淘汰
- 如果通路位是1，修改位是0，把通路位的1改成0，繼續檢視下一頁
- 如果通路位和修改位都是1，先把通路位修改為0，修改位不變，下一輪循環如果又通路到這一頁，把髒頁重新整理會磁盤，同時把修改位設定為0（這個頁會有兩次存活的機會，是以叫二次機會法），繼續檢視下一頁
通過上面的分析，大家可以發現，被修改過的頁有兩次機會存活下來，而被淘汰的一定是通路位和修改位都是0的。
最不常用算法
這個算法的核心思想是使用一個計數器記錄每個頁面被通路的次數，然後把通路次數最少的淘汰。這個算法有一個很明顯的缺點就是，如果某一個頁在程式的初始階段通路非常頻繁，如果之後執行過程中再也沒有通路，但是根據這個算法，這個頁會一直留在記憶體中，占用空間。
LRU，FIFO，Clock的比較
在比較這幾個算法之前，先介紹一個現象，在使用FIFO算法時，有時會出現配置設定的實體頁數增多，缺頁率反而上升的異常現象，這個現象叫做belady現象。
看下面的例子：
在圖中，使用的是FIFO頁面置換算法，給程式配置設定的實體頁的個數是3頁，從圖中可以看出總共命中了3次。上圖第一行是通路序列，下面三行是隊列中頁。
再看下面的圖
在圖中，依然是FIFO算法，但是這次使用的實體頁是4頁，可以看出總共就命中了2次，是以缺頁率反而提高了。
FIFO算法發生belady現象的原因
頁面置換的一個原則就是要把最不經常使用的頁給淘汰掉，而FIFO隻是簡單的按照通路時間先後進行淘汰，完全沒有考慮通路頻率和最近有沒有被使用，是以可能會把一些經常被使用的頁給換出去。
LRU算法沒有belady現象，但是LRU算法實作起來的開銷比較大，是以CLOCK算法是比較理想的實作方法，開銷相對較小，因為隻需要修改特定的标志位，而且是硬體實作的修改，同時又可以把最近通路的頁保留下來。
工作集
為了介紹和工作集相關的算法，需要先了解一些有關工作集和常住集的概念，同時要了解一下在程式的運作過程中工作集變化的特征。
工作集定義如下：
- 從t時刻開始
- 經過一個小的時間間隔Δ
- 在這個小的時間間隔Δ中通路的頁為W(t,Δ)，就是工作集
注意工作集是一個集合，集合有三個特性，1、确定性 2、互異性 3、無序性，是以工作集中的頁面不能重複，下面舉個例子說明一下什麼是工作集。
上圖中，第一個工作集是從 t1 開始，經過時間間隔Δ，工作集為W(t1, Δ) = {1, 2, 5, 6, 7}，第二個圖類似就不說了。
程式運作過程中，工作集變化符合什麼特征呢？看下圖
在圖的最上方的解釋其實已經很清晰了，如果程式符合局部性原理，那就會進入一段非常平穩的曲線，因為這段時間工作集發生變化很小，一旦程式局部性區域改變，工作集就會有一個劇烈的變化。
常駐集定義：
目前時刻，記憶體中實際駐留的實體頁面的個數。簡單來說就是給某個程序配置設定的實體頁框的多少，舉個例子，比如給程序A限制在記憶體中最多存在10頁，如果達到10頁，又有新的頁要放入記憶體，就需要把記憶體中某個頁給淘汰掉，那常住集的大小就是10。注意，常住集不是越大越好，當常住集達到一定的大小之後，再增大也不會使缺頁率明顯下降。
ok,上面把工作集和常住集的概念介紹完了，同時介紹了程式運作過程中工作集的特性，下面就介紹一個與工作集相關的算法。
工作集頁面置換算法
學過計算機網絡的都知道，在TCP協定接收和發送封包的時候會使用滑動視窗，這個也是類似，也有一個視窗大小，至于這個視窗是什麼，看下面的例子
在上圖中，視窗為時間視窗τ = 4
- 在t = -2時刻，把e頁加入記憶體
- 在t = -1時刻，把d頁加入記憶體
- 在t = 0時刻，把a頁加入記憶體
- 在t = 1時刻，通路c頁，c不在記憶體中，把c加入進來，由于視窗的開始時-2,目前時刻是1,視窗大小剛好為4，可以在t = 1時刻看到4個笑臉，不用淘汰。
- 在t = 2時刻，通路c頁，但是c在記憶體中，命中，但是由于在t = 2時刻，視窗大小變成5 > 4,是以要淘汰掉一個頁面，把最開始放進入的e淘汰掉。
- ....
- 下面的都是按照這個思路分析
缺頁率頁面置換算法
首先看一下缺頁率的定義
缺頁率 = 缺頁次數/記憶體通路次數
有了上面的公式，看一下這個算法
這個圖的縱軸表示缺頁率，橫軸表示記憶體中工作集的大小，圖中有兩個橫線，上面那條表示缺頁率過高，需要增加工作集大小，下面那條線表示缺頁率很低，可以減小工作集大小。
這個算法也有視窗的概念，但是和上面工作集頁面置換算法不同，這個算法的視窗是兩次發生缺頁異常中間間隔的頁面個數叫做視窗（其實這樣叙述并不準确，還是看下面的例子吧）
圖中，window size = 2，表明，兩次缺頁中斷間隔大于2，就要把在兩次間隔沒有通路的頁面淘汰掉。如果小于等于2就繼續增大工作集大小。
- 在t = 0時刻，記憶體中已經放入了e,d,a三個頁面
- 在t = 1時刻，放入c,ok視窗大小從這裡開始記錄（這裡有朋友可能會覺得應該從第一個記錄，其實不對，因為前4個頁都發生了缺頁中斷，是以要從這裡幾錄），也就是tlast
- 在t = 2時刻，命中，此時tcurrent - tlast = 1 ,小于視窗大小，繼續
- 在t = 3時刻，通路d，命中，此時tcurrent - tlast = 2，等于視窗大小，繼續
- 在t = 4時刻，通路b，缺頁中斷，此時tcurrent - tlast > 2,把兩次中斷中沒有通路到的頁面都淘汰，兩次中斷中通路的頁面為c,d,b，而e沒有通路到，淘汰
- ...
- 在t = 6時刻，通路e,缺頁中斷，此時tcurrent - tlast < 2,不做處理，說明缺頁很頻繁，将t = 6設定為 tlast
- ...
- 在t = 9時刻，通路a,缺頁中斷，此時tcurrent - tlast > 2，幹掉在t = 6到t = 9中間沒有通路的頁面
- ...
最後總結
FIFO通過維護一個隊列，淘汰最老的頁面，但是該頁面可能正在被使用，是以FIFO不是一個很好的算法。
時鐘頁面置換算法和二次機會法算是對FIFO的一種改進，增加了通路位控制，用來檢測頁面是否被使用，優化了FIFO算法。
LRU是一種非常優秀的算法，但是隻能通過特定的硬體實作，如果硬體不支援，則無法實作，而最不常用算法是一種近似LRU算法，但是性能不是非常好。
最後兩個算法是工作集相關的算法，性能還可以，但是實作開銷太大，在清華大學的作業系統公開課中，這兩種算法都被歸類為全局頁面置換算法，但是在《現代作業系統》中把工作集頁面置換算法歸類為局部頁面置換算法，原話如下：
至于哪個是正确的，大家自己思考吧。。。
可能有些胖友不太了解全局頁面置換算法和局部置換算法有什麼差別，這裡就補充一下。
局部頁面置換算法：針對單個程序的頁面置換算法，頁的換入和換出都是目前程序相關的。
全局頁面置換算法：針對計算機中的全部程序，比如程序A發生缺頁中斷，可以把程序B的某個頁淘汰，用于騰出空間。