頁面置換算法你學會了嗎？
一、什麼是頁面置換算法
在進程運行的過程中，若其訪問的頁面不存在內存中，則會產生缺頁中斷。如果此時內存中沒有空閑的頁面，操作系統就需要在內存中選擇一個頁面將其移出，從而可以將需要訪問的頁面調入內存中。而用來選擇淘汰哪一頁的算法就叫做頁面置換算法。
好的頁面置換算法有較低的頁面更換頻率。
二、常見的頁面置換算法
1、OPT(最佳置換算法)
最佳置換算法：每次選擇淘汰的頁面將是以後永不使用或者最長時間內不在被訪問的頁面。這樣可以保證最低的缺頁率。
例如：假如操作系統給進程分配了3個內存塊，並且該進程接下來會依次訪問7，5，2，3，6，2，7，1，6，7，2，3，7，2，7。
如圖所示，在第4步中，需要把3號頁面調入內存，此時內存已經滿了，所以需要從7，5，2中選擇一個頁面進行淘汰。按照最佳置換算法規則，往後尋找，此時2和7會被先後訪問，所以把5號頁面淘汰，即最長時間內不在被訪問的頁面。
2、FIFO(先進先出算法)
FIFO算法是最簡單的頁面置換算法。顧名思義，FIFO每次淘汰的頁面是最早進入內存的頁面。FIFO的實現方法是把調入內存的頁面按先後順序放入隊列中，當需要置換頁面時，選擇隊頭的頁面即可。
例如：假如操作系統給進程分配了3個內存塊，並且該進程接下來會依次訪問7，5，2，3，6，2，7，1，6，7，2，3，7，2，7。頁面在內存中的表現如下所示：
3、LRU(最近最久未使用算法)
LRU(Least Recently Used),每次淘汰的頁面是最近最久未使用的頁面。所以需要去記錄該頁面上次被訪問以來所經歷的時間t。當需要淘汰頁面是，選擇內存中現有頁面中t最大的，即最近最久未使用的頁面。
如：假如操作系統給進程分配了3個內存塊，並且該進程接下來會依次訪問7，5，2，3，6，2，7，1，6，7，2，3，7，2，7。頁面在內存中的表現如下所示：
如圖所示，在第四步中需要把3號頁面調入內存，而此時內存已滿，需要從7、5、2中選擇一個頁面進行淘汰。按照LRU規則，7號頁面上次被訪問以來所經歷的時間為3，他為最大的，所以把7號頁面淘汰出去。
4、LFU(最近最少使用算法)
LFU(最近最少使用算法)，它是基於”如果一個數據在最近一段時間內使用次數很少，那麼在將來一段時間內被使用的可能性也很小「的思路。注意LFU和LRU算法的不同之處，LRU的淘汰規則是基於訪問時間，而LFU是基於訪問次數的。
如：假如操作系統給進程分配了3個內存塊，並且該進程接下來會依次訪問5，4，5，3，3、2、5、1、4。頁面在內存中的表現如下所示：
如圖所示，在第八步中需要把1號頁面調入內存，而此時內存已滿，需要從5、2、3中選擇一個頁面進行淘汰。按照LFU規則，2號頁面最近一段時間內使用次數為1，他是最小的。所以把2號頁面淘汰出去。
了解更多的技術文章，請掃碼關注公眾號。
