Linux——缺頁中斷與記憶體置換演算法，你想知道的都在這里！
- 缺頁中斷
- 頁面置換演算法
- 缺頁次數
- 一、先進先出（FIFO）
- 二.最近最久未使用（LRU）
- 三、最佳置換演算法（OPT）
缺頁中斷
缺頁中斷就是要訪問的頁不在主存，需要作業系統將其調入主存后再進行訪問，在這個時候，被記憶體映射的檔案實際上成了一個分頁交換檔案，
一句話概括：當前虛擬地址要找的資料不在物理記憶體中
頁面置換演算法
行程運行程序中，如果發生缺頁中斷，而此時記憶體中有沒有空閑的物理塊是，為了能夠把所缺的頁面裝入記憶體，系統必須從記憶體中選擇一頁調出到磁盤的對換區，但此時應該把那個頁面換出，則需要根據一定的頁面置換演算法（Page Replacement Algorithm)來確定，
缺頁次數
物理塊+頁面置換次數
題目如下：
一、先進先出（FIFO）
把記憶體中駐留時間最久的頁面置換演算法予以淘汰
例子：
在分頁中，采用FIFO頁面置換演算法，序列 1、3、2、1、2、1、5、1、2、3，當物理塊為3時，計算缺頁次數和缺頁率？
演算法執行如下操作步驟：
- 程式運行，將1、3、2三個頁面裝入記憶體
- 接著1、2、1已經有存在記憶體，不必產生缺頁中斷
- 訪問頁面5時，記憶體中不存在該頁面，發生缺頁中斷，根據FIFO演算法，先進先出，將1置換出去
- 訪問頁面1時，記憶體中不存在該頁面，發生缺頁中斷，根據FIFO演算法，先進先出，將頁面3置換出去
- 訪問頁面3時，記憶體中不存在該頁面，發生缺頁中斷，根據FIFO演算法，先進先出，將2置換出去
總共進行了三次頁面置換，所以缺頁數=3+3=6，缺頁率為6/10=0.6；
優點：先進先出演算法實作簡單，是最直觀的一個演算法
缺點：性能最差，可能出現Belady 例外：當所分配的物理塊數增大而頁故障數不減反增的例外現象
二.最近最久未使用（LRU）
選擇最近且最久未被使用的頁面進行淘汰
例子：
在分頁中，采用LRU頁面置換演算法，序列 1、3、2、1、2、1、5、1、2、3，當物理塊為3時，計算缺頁次數和缺頁率？
演算法執行如下操作步驟：
- 程式運行，將1、3、2三個頁面裝入記憶體
- 接著1、2、1已經有存在記憶體，不必產生缺頁中斷
- 訪問頁面5時，記憶體中不存在該頁面，發生缺頁中斷，根據LRU演算法，頁面1、3、2中3最近且最久未被使用，將3置換出去
- 訪問頁面3時，記憶體中不存在該頁面，發生缺頁中斷，根據LRU演算法，頁面5、1、2中5最久未被使用，將頁面5置換出去
總共進行了兩次頁面置換，所以缺頁數=3+2=5，缺頁率為5/10=0.5；
優點：LRU性能較好，但需要暫存器和堆疊的硬體支持，LRU是堆疊類的演算法，理論上可以證明，堆疊類演算法不可能出現Belady例外，FIFO演算法基于佇列實作，不是堆疊類演算法，
三、最佳置換演算法（OPT）
當要調入一頁而必須淘汰舊頁時，應該淘汰以后不再訪問的頁，或距現在最長時間后要訪問的頁面，即被淘汰頁面是以后永不使用或最長時間內不再訪問的頁面，
例子：
在分頁中，采用OPT頁面置換演算法，序列 1、3、2、1、2、1、5、1、2、3，當物理塊為3時，計算缺頁次數和缺頁率？
演算法執行如下操作步驟：
- 程式運行，將1、3、2三個頁面裝入記憶體
- 接著1、2、1已經有存在記憶體，不必產生缺頁中斷
- 訪問頁面5時，記憶體中不存在該頁面，發生缺頁中斷，根據OPT演算法，頁面1、3、2中3最長時間內不被訪問，將3置換出去
- 訪問頁面3時，記憶體中不存在該頁面，發生缺頁中斷，根據OPT演算法，將5置換出去
總共進行了兩次頁面置換，所以缺頁數=3+2=5，缺頁率為5/10=0.5；
如有錯誤，歡迎指正！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254540.html
標籤：其他