为了达到降低随后发生缺页中断的次数或者概率，人们设计出了各种各样的页面替换算法，这些算法大致可分为公平算法和非公平算法。

• 公平算法：随机算法、FIFO算法、时钟算法。

• 非公平算法：NRU算法、LRU算法、工作集算法。

随机算法

这种就是简单的随机选择进行页替换，无需多言，简单粗暴。

FIFO算法

这种就是先来后到，可以使用链表记录页分配的先后顺序，淘汰时按照顺序淘汰即可，也是非常的简单粗暴。

时钟算法

内存使用中的页按照时钟的逻辑形状，淘汰页时按照时钟顺序检查，如果页未访问到（每个页对应一个访问标识，未访问到时设置为0），则直接替换；如果访问过则设置访问位为0，方便下次淘汰。时钟逻辑图如下：

NRU算法

最近未使用算法，将最近一段时间没有访问过的页面进行替换，作出这种选择是基于程序访问的时空局域性。依据时空局域性，一个最近没有访问过的页面，在随后的时间内也不太可能被访问，而NRU的实现就是利用页面的访问和修改位来实现的。

时空局限性在很多程序设计思想中有体现，比如rocketmq中page cache缓存最近读写的消息数据等。

LRU算法

LRU是对NRU算法的改进，其考虑的是最近使用的频率而不是最近是否使用过。LRU算法的实现必须以某种方式记录每个页面被访问的次数，简单的办法就是在页表的记录项里面增加一个计数域，一个页面被访问一次，则这个计数器的值加1；或者使用链表结构，每访问一次就将该页移动到链表头。

工作集算法

考虑到LRU算法实现，其需要对每个页面保持某种记录，并在每次页面访问时或周期性对这些记录更新，造成时间空间成本高。工作集概念来源于程序访问的时空局域性，在一段时间内，程序访问的页面将局限在一组页面集合上。

例如，最近K次访问均发生在某m个页面上，那么m就是参数为k时的工作集。用w(k, t)表示时间t时k次访问所涉及的页面数量。显然随着k的增长，w(k, t)的值将随之增长，在k增长至某个数值后，w(k, t)值增长将及其缓慢甚至接近停滞，并维持一段时间。

工作集算法就是操作系统局限性的一种体现，一段时间内，CPU操作的数据大都集中在少量数据上，因此可以应用工作集算法来进行页的替换操作。

Redis中的内存淘汰

以上分析了操作系统中的页面更换算法，更广义来讲，页面更换就是内存淘汰，操作系统的页面更换算法可能不能直接让开发者感同身受，毕竟这是OS层面的东东。下面就以实际开发中常用到的Redis为例，来分析下Redis内存淘汰策略，对比加深对内存淘汰的理解。

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据。目前Redis的内存淘汰策略有如下几种：

• noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。

• allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。

• allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。

• volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。

• volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。

• volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

对于LRU（Least Recent Used），淘汰掉最不经常使用的，LRU可以通过hashMap + 双向链表来实现，如果Redis也基于hashMap + 双向链表实现，显然要对目前的数据结构做较大改动，为了追求空间的利用率，Redis采用权衡的实现方案：Redis会基于server.maxmemory_samples配置选取固定数目的key，然后比较它们的lru访问时间，然后淘汰最近最久没有访问的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于严格LRU算法，但是相应消耗也变高，对性能有一定影响，样本值默认为5。

从Redis的内存淘汰实现方案来看，虽然遵循了LRU思想但不完全照搬，根据实际应用场景进行trade-off。