目錄
前言：
一、內(nèi)存置換算法的緣由
二、算法詳解
2.1? 最佳頁面置換算法（OPT） =》 理論上的最優(yōu)，實際無法保證
2.2 先進先出置換算法（FIFO）-- 按加載時間/最早訪問時間排序
2.3 最近最久未使用的置換算法（LRU）-- 按最后一次訪問時間排序
2.4 時鐘頁面置換算法（Lock）
2.5 最不頻繁使用算法（LFU）=》 訪問/命中次數(shù)排序
前言：
LRU、LFU是兩種容易混淆的替換算法。本文就是探討這個問題。
替換算法的本質(zhì)是：在崗位總數(shù)不變的情況，來了一個新人，如何淘汰掉一個老人的算法。
看似是計算機的問題，實際上是一個非常現(xiàn)實的職場問題。
替換算法的基本思想：時間局部性和空間局部性原理，用過去、現(xiàn)在推測未來?。?！
FIFO：保護的是新員工，淘汰的工齡最大的員工，對新員工最有利，對老員工不利。
LFU：保護的是歷史功勞最大，淘汰的是功勞最小，對老員工有利，對新員工不利。
LRU：保護的是最近貢獻最大，淘汰的是最近貢獻最小的，對最近最忙的員工有利，對歷史貢獻大和搞預(yù)研的人不利。
無論是cache的替換算法，還是Web頁面的替換算法，本質(zhì)是都是新人淘汰舊人的算法。
一、內(nèi)存置換算法的緣由
計算機的運行的程序和數(shù)據(jù)保存在內(nèi)存中，內(nèi)存的空間是有限的，所運行的程序可能需要新的數(shù)據(jù)，而數(shù)據(jù)不在內(nèi)存，在磁盤(硬盤)中。 CPU 訪問的頁面在物理內(nèi)存時，便會產(chǎn)生一個缺頁中斷，請求操作系統(tǒng)將所缺頁調(diào)入到物理內(nèi)存。
對于要新加載到內(nèi)存的頁面，需要一定的算法來確定把哪些頁面剔除出去給新的要加進來的頁面讓位，之所以需要算法，就是因為內(nèi)存資源是有限的。所以，頁面置換算法的功能是，當出現(xiàn)缺頁異常，需調(diào)入新頁面而內(nèi)存已滿時，選擇被置換的物理頁面，也就是說選擇?個物理頁面換出到磁盤，然后把需要訪問的頁面換入到物理頁。
那其算法目標則是，盡可能減少頁面的換入換出的次數(shù)，常見的頁面置換算法有如下幾種【1】：
- ? ? ? ? 最佳頁面置換算法（OPT）
- ? ? ? ? 先進先出置換算法（FIFO）
- ? ? ? ? 最近最久未使用的置換算法（LRU）
- ? ? ? ? 時鐘頁面置換算法（Lock）
- ? ? ? ? 最不常用置換算法（LFU）
備注：
替換算法的本質(zhì)：替換掉未來最不可能使用的頁面。
然而，未來還發(fā)生，因此，算法的本質(zhì)是：用過去的經(jīng)驗推測未來?。?！
二、算法詳解
2.1? 最佳頁面置換算法（OPT） =》 理論上的最優(yōu)，實際無法保證
最佳頁面置換算法基本思路是，置換在「未來」最?時間不訪問的頁面。所以，該算法實現(xiàn)需要計算內(nèi)存中每個邏輯頁面的「下?次」訪問時間，然后比較，選擇未來最長時間不訪問的頁面。我們舉個例?，假設(shè)?開始有 3 個空閑的物理頁，然后有請求的頁面序列，那它的置換過程如下圖【圖源自小林coding】：
在這個請求的頁面序列中，缺頁共發(fā)生了 7 次（空閑頁換入 3 次 + 最優(yōu)頁面置換 4 次），頁面置換共發(fā)生了 4 次。
第1次：7號頁面，使用空閑頁面替換。
第2次：0號頁面，使用空閑頁面替換。
第3次：1號頁面，使用空閑頁面替換。
第4次：2號頁面，替換掉7號頁面
第5次：0號頁面，不需要替換，命中。
這很理想，但是實際系統(tǒng)中無法實現(xiàn)，因為程序訪問頁面時是動態(tài)的，我們是無法預(yù)知每個頁面在「下?次」訪問前的等待時間。所以，最佳頁面置換算法作用是為了衡量你的算法的效率，你的算法效率越接近該算法的效率，那么說明你的算法是高效的。
2.2 先進先出置換算法（FIFO）-- 按加載時間/最早訪問時間排序
FIFO算法的本質(zhì)：淘汰掉年齡最大的，不管是過去和當下的貢獻值，也不管未來是否能做貢獻。
FIFO算法的核心思想是：年齡越大，未來的潛力越小?。m然這不一定對）
年齡記錄：按照加載的先后順序排序，它保護的是最年輕的人 。
很顯然，F(xiàn)IFO算法很不合理?。?！
既然我們?法預(yù)知頁面在下?次訪問前所需的等待時間，那我們可以選擇在內(nèi)存駐留時間最長，或或者說，加載到內(nèi)存中最早的（有可能反復(fù)使用）的頁面進行中置換，這個就是「先進先出置換」算法的思想。還是以前?的請求的??序列作為例子，假設(shè)使用先進先出出置換算法，則過程如下圖：
在這個請求的頁面序列中，缺頁共發(fā)生了 10 次，頁面置換共發(fā)?了 7 次，跟最佳頁面置換算法比較起來，性能明顯差了很多。
這是因為，先進入的頁面，不代表該頁面未來就再使用，很有可能，某個頁面，雖然最先加載到內(nèi)存中，但會被頻繁使用，如果把這種未來頻繁使用的頁面替換出去，就導(dǎo)致性能的下降。
最理想的情況就是替換到，為了可能不會使用或未來使用次數(shù)最少的頁面。
2.3 最近最久未使用的置換算法（LRU）-- 按最后一次訪問時間排序
LRU算法的本質(zhì)是：淘汰掉最近（Recently）最空閑，沒事干的那個人，不管他未來是否有事干。
LRU算法的核心思想是：最近最閑，意味著未來可能也是最閑，最沒有價值。
空閑值計算方法：每命中一次，空閑值-1， 沒有命中，空閑值+1，它保護過去最近最忙的人，對歷史貢獻大的人是不友好的，因為，隨著時間的推移，歷史貢獻大的人，貢獻值會抵消（空閑一次，空閑值-1），最近（Recently），疊加了時間的因素，對于過去功勞大，最近沒有貢獻的老員工是不利的。
? ? ? ? 最近最久未使用（LRU）的置換算法的基本思路是，發(fā)生缺頁時，選擇最長時間沒有被訪問的頁面進行置 換，也就是說，該算法假設(shè)：已經(jīng)很久沒有使用的頁面很有可能在未來較長的?段時間內(nèi)仍然不會被使用。
????????這種算法近似最優(yōu)置換算法，最優(yōu)置換算法是通過「未來」的使用情況來推測要淘汰的頁面，而 LRU 則是 通過「歷史」的使用情況來推測要淘汰的頁面。 還是以前?的請求的頁面序列作為例子，假設(shè)使用最近最久未使用的置換算法，則過程如下圖：
在這個請求的頁面序列中，缺頁共發(fā)?了 9 次，頁面置換共發(fā)?了 6 次，跟先進先出置換算法?較起 來，性能提高了?些。
雖然 LRU 在理論上是可以實現(xiàn)的，但代價很高。為了完全實現(xiàn) LRU，需要在內(nèi)存中維護?個所有頁面的 鏈表，最近最多使用的頁面在表頭，最近最少使用的頁面在表尾。 困難的是，在每次訪問內(nèi)存時都必須要更新「整個鏈表」。在鏈表中找到?個頁面，刪除它，然后把它移 動到表頭是?個?常費時的操作。
所以，LRU 雖然看上去不錯，但是由于開銷比較大，實際應(yīng)用中比較少使用。
2.4 時鐘頁面置換算法（Lock）
時鐘頁面置換算法就可以兩者兼得，它跟 LRU 近似，又是對 FIFO 的?種改進。
該算法的思路是，把所有的頁面都保存在?個類似鐘面的「環(huán)形鏈表」中，?個表針指向最老的頁面。 當發(fā)生缺頁中斷時，算法首先檢查表針指向的頁面： 如果它的訪問位位是 0 就淘汰該頁面，并把新的頁面插入這個位置，然后把表針前移?個位置； 如果訪問位是 1 就清除訪問位，并把表針前移?個位置，重復(fù)這個過程直到找到了?個訪問位為 0 的 頁面為止；
2.5 最不頻繁使用算法（LFU）=》 訪問/命中次數(shù)排序
LFU算法的本質(zhì)：替換掉貢獻最小的那個人
LFU核心思想是：過去貢獻最小，未來可能貢獻最小。
衡量貢獻大小的方法：每命中（使用）一次，貢獻值+1，它保護的是貢獻最大的人，貢獻大不受時間推移的影響和消耗，但對不忙的人，沒有考量。
? ? ? ? 最不常用（LFU）算法，這名字聽起來很調(diào)皮，但是它的意思不是指這個算法不常用，而是當發(fā)生缺頁中 斷時，選擇「訪問次數(shù)」最少的那個頁面，并將其淘汰。
它的實現(xiàn)方式是，對每個頁面設(shè)置?個「訪問計數(shù)器」，每當?個頁面被訪問時，該頁面的訪問計數(shù)器就累加 1。在發(fā)生缺頁中斷時，淘汰計數(shù)器值最小的那個頁面。
看起來很簡單，每個頁面加?個計數(shù)器就可以實現(xiàn)了，但是在操作系統(tǒng)中實現(xiàn)的時候，我們需要考慮效率和硬件成本的。 要增加?個計數(shù)器來實現(xiàn)，這個硬件成本是比較高的.
另外如果要對這個計數(shù)器查找哪個頁面訪問次數(shù)最 小，查找鏈表本身，如果鏈表長度很大，是非常耗時的，效率不高。
但還有個問題，LFU 算法只考慮了頻率問題，沒考慮時間的問題，比如有些頁面在過去時間里訪問的頻率很高，但是現(xiàn)在已經(jīng)沒有訪問了，而當前頻繁訪問的頁面由于沒有這些頁面訪問的次數(shù)高，在發(fā)生缺頁中 斷時，就會可能會誤傷當前剛開始頻繁訪問，但訪問次數(shù)還不高的頁面。 那這個問題的解決的辦法還是有的，可以定期減少訪問的次數(shù)，比如當發(fā)生時間中斷時，把過去時間訪問的頁面的訪問次數(shù)除以 2，也就說，隨著時間的流失，以前的高訪問次數(shù)的頁面會慢慢減少，相當于加大 了被置換的概率。
缺點：文章來源：http://www.zghlxwxcb.cn/news/detail-810567.html
過去訪問多的頁面，不代表未來訪問次數(shù)越多，比如循環(huán)結(jié)束后的頁面，未來很有可能就不再訪問了。文章來源地址http://www.zghlxwxcb.cn/news/detail-810567.html
到了這里，關(guān)于[架構(gòu)之路-188]-《軟考-系統(tǒng)分析師》-3-操作系統(tǒng) - 圖解頁面替換算法LRU、LFU的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
