什么是缓存置换算法?

前言

前面的文章已经介绍了什么是操作系统的虚拟内存，与本文要介绍的缓存置换算法息息相关，如果还没有看的朋友，建议先读一下上篇文章，链接是：什么是操作系统的虚拟内存？

从上篇文章中，我们学习到虚拟内存的page置换算法，就是缓存过期算法的别称，可以说最早的缓存过期算法，其实是先出现操作系统中，这也是为什么，我强调学习一个东西的时候，最好能了解一下它的历史，这样能更好的帮助我们理解。

为什么需要缓存

（1）为了解决不同的存储介质之间的速度不匹配问题，比如CPU和内存，比如内存和磁盘，客户端和服务端。

（2）依据程序访问的局部性原理，近期访问的数据，在将来很有可能会被访问

（3）提升访问效率

缓存为什么需要置换

相信读过上篇文章的朋友应该可以很轻松的回答出来这个问题，操作系统本质上是一个多级缓存系统，从cpu寄存器，cpu一级缓存，cpu二级缓存，cpu三级缓存，主内存，硬盘，我们会发现从右到左，访问效率依次提升，同时设备价格也不断升高，从左到右，访问效率依次降低，同时设备价格也逐渐下降。正是出于这个原因，现代计算机都会在性价比之间做个权衡。因为越高访问效率的存储介质越贵，所以这些介质都是有限的资源，那么如何在有限的资源内处理无限的数据呢？这就提出了置换的概念，举个通俗的例子。去医院排队体验，在有限的房间里面，每次只能进入一个人做某项检查，当这个人检查完了，就离开房间，然后置换另一个人进来，依次类推，完成检查。最理想的情况是置换出未来短期内不会被再次访问的数据，但是我们无法预知未来，所以只能从数据在过去的访问情况中寻找规律进行置换。

常见的置换算法

缓存置换算法常用的策略有三种，分别是：

(1) FIFO：First In First Out，先进先出策略

(2) LFU：Least Frequently Used，最不经常使用策略

(3) LRU：Least Recently Used，最近最少使用策略

这三种淘汰数据的策略和侧重点各不一样，今天我们就来学习相关的知识。

FIFO

FIFO（First in First out）代表先进先出，提起这个概念，相信大家第一时间能够想到队列这种数据结构，在日常生活中，这种场景随处都可见，比如吃饭排队，去银行取钱排队，上地铁排队。这种策略，非常简单易懂，实现简单，而且具有公平性，符合人们思维的习惯。在计算机中这种思想也到处可见，比如在操作系统的调度系统中，IO读取等操作。其核心原则就是：最先进入缓存的数据，应该最早被淘汰。

考虑这样一串数字4, 7, 6, 1, 7, 6, 1, 2, 7, 2。如何在一个固定长度为3的容器中进行FIFO策略的淘汰？如下：

我们观察到前面6，7，4放进去之后，这是1的加入会淘汰原来最早放进去的4，接着7的到来，发现缓存命中所以不做处理，直到2出现，这个时候我们需要淘汰原来的7，就这样按照先进先出的策略淘汰。

LFU

LFU 全称 Least Frequently Used，从名字上我们就能看出来这个算法是基于数据访问频率（次数）来淘汰数据的，也就是说系统会记录一段时间内所有数据的访问次数，当缓存区满的时候，会优先淘汰访问次数最少的数据。其核心思想：如果一个数据在最近一段时间内访问次数很少，则在将来一段时间内被访问的可能性也很小。显然，这是一种合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。缓存的每个数据都有引用计数，所有数据按照引用计数排序，具有相同引用计数的数据按照时间排序。

LRU

LRU 全称 Least Recently Used，基于数据访问历史记录来执行淘汰策略，LRU是首先淘汰最长时间未被使用的页面，这种算法把近期最久没有被访问过的页面作为被替换的页面，与LFU不一样的是，LRU并不关注缓存数据的访问次数，它只关注该条数据的访问时间。核心思想：如果一个数据在最近一段时间内没被访问，则在将来一段时间内被访问的可能性也很小。

FIFO VS LRU VS LFU

FIFO完全是公平的策略，不考虑特定时间段内访问频次和访问时间，适合用在某些公平调度的场景下。

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重，此时适合使用LFU来做缓存。此外从实现的复杂度上来分析，LFU 需要维护一个队列记录所有数据的访问记录，每个数据都要维护引用计数，内存消耗和性能消耗都较高，而LRU相对来说，实现比较简单，因为不需要考虑计数的问题，仅仅考虑访问时间，非常适合使用双向链表+HashMap来实现O（1）性能的LRU。

总结

本文主要介绍了缓存置换算法的相关概念，原理和置换策略等相关内容，最后并对比分析了常见置换算法的优缺点。缓存作为一种互联网开发必备的组件，理解其置换算法的原理至关重要，值得每一位同学学习和研究。

历史文章：