本文主要是介绍refault distance算法的一点理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个算法看了好几次了，都没太理解，今天记录一下，加深一下印象。
引用某个博客对这个算法的介绍
一次访问page cache称为fault，第二次访问该页面称为refault。page cache页面第一次被踢出LRU链表并回收(eviction)的时刻称为E，第二次再访问该页的时刻称为R，那么R-E的时间里需要移动的页面个数称为Refault Distance。
把Refault Distance概念再加上第一次读的时刻，可以用一个公式来概括第一次和第二次读之间的距离(read_distance)。
read_distance = nr_inactive + (R-E)
如果page想一直保持在LRU链表中，那么read_distance不应该比内存的大小还长，否则该page永远都会被踢出LRU链表，因此公式可以推导为：
NR_inactive+（R-E） <= NR_inactive+NR_active
(R-E) <= NR_active
看来半天，其实一直没太理解(R-E)的含义。干脆，抛开这个，讲讲自己的理解。
按当前内核设计，一个pagecache被加入系统中时，会加入到不活跃lru链表。一段时间后，这个页被挪到了不活跃链表的最尾部，记这个时间为T0，并被内核的内存回收机制发现最近没被访问，则这个page cache页会被踢出lru链表，记这个时间为T1。
一段时间后，内核需要访问该page cache里的内容，但是发现该page cache不在内存里了，只好重新从存储介质中将其内容读出来，记这个时间点为T2。
这个时候，应该将这个page cache放到活跃lru链表还是不活跃lru链表呢？这个决策就是由refault distance算法来做。
这个算法的核心思想是，是否可以通过计算，来避免pagecache这层缓存的颠簸；换成大白话来说就是，如果这个时候（第二次读入pagecache缓存），我把这个pagecache页放入活跃lru链表，有没有可能（或者说增大可能），在下次用户需要读取这个pagecache的时候，他还在lru链表上（无论是活跃还是非活跃链表），这样的话，就代表这个页还没被踢出lru链表，从而用户访问的时候，就没必要从存储介质中重新读了，毕竟从存储介质读内容的性能肯定比不上从内存里读，如果能直接从内存里（lru链表上）读到，岂不美哉？
那么，需要怎么去做这个判断呢？
首先，拿T1时刻到T2时刻之间的数据当样本值。怎么采样判断呢？本质核心是这样的，假设用户要读取的pagecache在T0时刻被加入了活跃lru链表，并且，在T2时刻进行第二次刚好没有被踢出lru链表，需要满足什么条件呢？
需要满足：T1时刻到T2时刻之间链表挪动的pagecache页数，小于等于活跃lru链表页的数量。
举个例子吧，如果T1时刻到T2时刻之间lru链表挪动的pagecache页数是10，也就是说，如果用户想读的pagecache在被踢出内存这段时间，lru链表挪动的pagecache页数是10，并且，如果一开始活跃链表上的页的数量超过10的话，那这个pagecache肯定还没有被挪动到不活跃lru链表的尾端，反之，这个pagecache肯定被挪动到不活跃lru链表的尾端并被踢出内存。这里说的lru链表挪动的pagecache页数，包括把页从不活跃lru链表踢出内存的数量，也包括把页从不活跃lru链表升级到活跃lru链表的数量。（当然这只是估算，从活跃链表尾挪到活跃链表头肯定也会产生挪动）。所以在这个情况下，无非就是统计T1时刻到T2时刻之间链表挪动的pagecache页数，小于等于活跃lru链表页面数的话，肯定是需要挪动到活跃lru链表头的，从而最大程度避免缓存颠簸，否则如果大于活跃lru链表页面数的话，即使是挪到活跃lru链表头，按采样的规律大概率也没办法在被踢出内存前重新访问到，那直接放在非活跃lru链表即可。
罗里吧嗦的，希望能看懂。
这篇关于refault distance算法的一点理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
