前言

前幾天我們講到的都是關於虛擬記憶體的資訊，包含VMA的結構，malloc() , mmap() 等等，但是究竟虛擬記憶體該如何跟實體記憶體有實際的連結，怎麼在 mmap() 之後，讓實體記憶體能夠拿到資料，那就是今天要講的內容 分頁錯誤(page fault) ，以及當實體記憶體的位置不足時，要選擇某些分頁移回 swap space的方法。

分頁錯誤(page fault)

在前兩天借到 malloc() 與 mmap() 兩個函數，他們只會在使用者空間內分配虛擬記憶體，但是沒有實際建立虛擬記憶體與實體記憶體的映射關係，當CPU沒有辦法存取實體記憶體的時候就會發生分頁錯誤(page fault)。
觸發 Page Fault 的原因主要歸類為幾大類：

1. 使用共享記憶體的區域，但是還不存在虛擬位址與實體位址的對應，而產生的分頁錯誤，這種錯誤只要在分頁表中建立對應關係就好了。
2. 訪問的地址在實體記憶體中不存在，需要從硬碟或是 swap分割槽讀入才能使用，這種效能影響比較大，因為磁碟讀取的速度真的太慢了。
3. 訪問的記憶體位址非法，缺頁錯誤會進而引發 SIGSEGN 訊號結束程序，這種分頁錯誤會導致行程直接關閉。
   在 Linux 中會利用 do_page_fault 函數進行處理。

static int __kprobes do_page_fault(unsigned long addr, unsigned int esr,
				   struct pt_regs *regs)

addr : 代表分頁異常發生時的虛擬位址，由FSR提供
esr ：代表發生時的異常狀態，由ESR提供
regs：發生時的pt_regs。

記憶體回收

在Linux 中當記憶體充足的時候，kernel會盡量使用記憶體當作 page cache，進而提高系統的性能，這個頁面會加入到文件類型的 LRU鏈表中，當記憶體不足時，page cache的介面會被捨際，或是把已經丟改過的page cache介面寫回到儲存設備中，寫完便可釋放該區段的記憶體，這個行為叫做記憶體回收(page reclaim)。Linux 中採用的記憶體回收演算法，主要是LRU演算法，和二次機會法(second chance)。

LRU演算法

LRU 是 Least Recently Used 的縮寫，意味著最近最少使用，在Linux核心中使用雙項鏈表實作LRU鏈表，並且根據分頁的類型將LRU鏈表分為 LRU_ANON 和 LRU_FILE ，這兩種列表又各自有活躍LRU鏈表與不活躍LRU鏈表，再加上不可回收頁面鏈表，所以Linux核心中總共有五個LRU鏈表。
之所以要分為五種，是因為當記憶體不足時，會優先換出LRU_FILE鏈表中的頁面，而不是 LRU_ANON的頁面，因為大多數情況下的FILE是不需要寫回硬碟，除非在使用過程中有某部分被修改才需要重新寫回。
因為是一個雙向鏈表，所以可以利用 head-> prev得到尾鏈表最尾端的node。示意圖如下。

二次演算法

第二次機會演算法在經典的LRU上做了改進，在LRU設計中，並不會考慮該頁面是否頻繁被使用，如果某個頻繁使用的頁面，因為有多個新頁面進入而被擠到鏈表的最尾端，他仍然有機會被換出，在某些情況下，會浪費許多的資源。
二次機會演算法是基於LRU演算法的狀態下，在頁面內多加入一個標記，如果這個是０代表這個頁面是可以被替換的，如果這個頁面是1 就給他第二次機會，並且判斷下一個頁面是否能夠被換出，依序往下，直到找到可以被換出的頁面。當給了某個頁面第二次機會時，該標記會由1改為0；當某個頁面再次被使用時，把0恢復為1，因此某個頻繁被使用的頁面他的標記會時常保持為1，也就不那麼容易被換出了。

OOM killer 機制

當上述兩個回收機制也不能滿足記憶體需求時，OOM killer就是最後一道防線了，他會選擇記憶體佔用量比較高的行程進行終止，進而釋放記憶體。