這個算法看了好幾次了，都沒太理解，今天記錄一下，加深一下印象。
引用某個博客對這個算法的介紹

一次訪問page cache稱為fault，第二次訪問該頁面稱為refault。page cache頁面第一次被踢出LRU鏈表并回收(eviction)的時刻稱為E，第二次再訪問該頁的時刻稱為R，那么R-E的時間里需要移動的頁面?zhèn)€數(shù)稱為Refault Distance。
把Refault Distance概念再加上第一次讀的時刻，可以用一個公式來概括第一次和第二次讀之間的距離(read_distance)。
read_distance = nr_inactive + (R-E)
如果page想一直保持在LRU鏈表中，那么read_distance不應(yīng)該比內(nèi)存的大小還長，否則該page永遠(yuǎn)都會被踢出LRU鏈表，因此公式可以推導(dǎo)為：
NR_inactive+（R-E） <= NR_inactive+NR_active
(R-E) <= NR_active

看來半天，其實一直沒太理解(R-E)的含義。干脆，拋開這個，講講自己的理解。
按當(dāng)前內(nèi)核設(shè)計，一個pagecache被加入系統(tǒng)中時，會加入到不活躍lru鏈表。一段時間后，這個頁被挪到了不活躍鏈表的最尾部，記這個時間為T0，并被內(nèi)核的內(nèi)存回收機(jī)制發(fā)現(xiàn)最近沒被訪問，則這個page cache頁會被踢出lru鏈表，記這個時間為T1。
一段時間后，內(nèi)核需要訪問該page cache里的內(nèi)容，但是發(fā)現(xiàn)該page cache不在內(nèi)存里了，只好重新從存儲介質(zhì)中將其內(nèi)容讀出來，記這個時間點為T2。
這個時候，應(yīng)該將這個page cache放到活躍lru鏈表還是不活躍lru鏈表呢？這個決策就是由refault distance算法來做。
這個算法的核心思想是，是否可以通過計算，來避免pagecache這層緩存的顛簸；換成大白話來說就是，如果這個時候（第二次讀入pagecache緩存），我把這個pagecache頁放入活躍lru鏈表，有沒有可能（或者說增大可能），在下次用戶需要讀取這個pagecache的時候，他還在lru鏈表上（無論是活躍還是非活躍鏈表），這樣的話，就代表這個頁還沒被踢出lru鏈表，從而用戶訪問的時候，就沒必要從存儲介質(zhì)中重新讀了，畢竟從存儲介質(zhì)讀內(nèi)容的性能肯定比不上從內(nèi)存里讀，如果能直接從內(nèi)存里（lru鏈表上）讀到，豈不美哉？
那么，需要怎么去做這個判斷呢？
首先，拿T1時刻到T2時刻之間的數(shù)據(jù)當(dāng)樣本值。怎么采樣判斷呢？本質(zhì)核心是這樣的，假設(shè)用戶要讀取的pagecache在T0時刻被加入了活躍lru鏈表，并且，在T2時刻進(jìn)行第二次剛好沒有被踢出lru鏈表，需要滿足什么條件呢？
需要滿足：T1時刻到T2時刻之間鏈表挪動的pagecache頁數(shù)，小于等于活躍lru鏈表頁的數(shù)量。
舉個例子吧，如果T1時刻到T2時刻之間lru鏈表挪動的pagecache頁數(shù)是10，也就是說，如果用戶想讀的pagecache在被踢出內(nèi)存這段時間，lru鏈表挪動的pagecache頁數(shù)是10，并且，如果一開始活躍鏈表上的頁的數(shù)量超過10的話，那這個pagecache肯定還沒有被挪動到不活躍lru鏈表的尾端，反之，這個pagecache肯定被挪動到不活躍lru鏈表的尾端并被踢出內(nèi)存。這里說的lru鏈表挪動的pagecache頁數(shù)，包括把頁從不活躍lru鏈表踢出內(nèi)存的數(shù)量，也包括把頁從不活躍lru鏈表升級到活躍lru鏈表的數(shù)量。（當(dāng)然這只是估算，從活躍鏈表尾挪到活躍鏈表頭肯定也會產(chǎn)生挪動）。所以在這個情況下，無非就是統(tǒng)計T1時刻到T2時刻之間鏈表挪動的pagecache頁數(shù)，小于等于活躍lru鏈表頁面數(shù)的話，肯定是需要挪動到活躍lru鏈表頭的，從而最大程度避免緩存顛簸，否則如果大于活躍lru鏈表頁面數(shù)的話，即使是挪到活躍lru鏈表頭，按采樣的規(guī)律大概率也沒辦法在被踢出內(nèi)存前重新訪問到，那直接放在非活躍lru鏈表即可。
羅里吧嗦的，希望能看懂。