本文讲解了操作系统中进程读内存时，维护高速缓存的页面淘汰算法，其中重点讲解了先进先出算法和最近最少使用算法，学习高速缓存 Cache 提高程序执行效率的原理。
一、为什么要用页面淘汰算法
在计算机的存储结构中，存在着局部性原理（在《【软考学习6】计算机存储结构——局部性原理、Cache、主存地址单元、磁盘存取、总线和可靠性》中有介绍）。
简单来说，如果一个数据正在被使用，那么在近期它很可能还会被再次使用。
正是有这样一个现象，所以高速缓存 Cache 的存在就非常必要，它虽然容量很小，但速度很快，可以大大提升执行效率。
计算机的存储结构如下图所示。
使用了高速缓存（Cache）后，CPU 首先到高速缓存（Cache）中尝试取数据，如果拿到了数据则直接返回，速度有大量的提升。
如果没拿到，则发生了缺页现象，再到主存中去取数据，如下图所示。
主存容量大、速度慢，高速缓存（Cache）容量小、速度快。
为了整体的提升系统运行效率，需要把经常执行的放在高速缓存（Cache）中，其余的放在主存。
在高速缓存（Cache）存放满后，又有新数据需要进来时，就涉及到页面淘汰算法了，也就是要把现有的某个数据淘汰掉，给新进来的数据留地方。
如果页面淘汰算法使用不妥当，会发送倒挂现象（抖动现象）。
比如一个高速缓存有 3 个单位的空间，运行一段程序有 8 次缺页；如果用另外一个 4 个单位的高速缓存，运行同样的程序有 10 次缺页，那么就出现了倒挂现象（抖动现象）。
常用的页面淘汰算法有四种：最优算法、随机算法、先进先出算法和最近最少使用算法。
最优算法只是一个理论算法，通常是事后去人为分析最优的算法，这一类算法存在的意义是分析其他算法的优劣性，以及评估某个算法距离最优算法还差多远，所以没有实际求解意义。
随机算法也是一个计算机模拟的算法，采用随机的方式进行页面淘汰，因为随机具有较大的不确定性，所以也没有多大的实际求解意义。
接下来重点讲解先进先出算法和最近最少使用算法。
二、 先进先出算法
先进先出算法顾名思义，就是最先进来的最先出去。
这种算法有可能出现倒挂现象（抖动现象）。
对于 1 2 3 4 4 4 3 2 1 4 5 3 2 2 5 1 序列，进程内存空间为 3 位，开始内存为空，使用先进先出算法，计算缺页次数。
首先填充第一个数据 1，因为缓存为空，所以触发缺页，如下图所示。
接着同理填入数据 2 和 3，触发两次缺页，因为缓存表为空，如下图所示。
接着填入数据 4 的时候，因为无法从现有的 1、2、3 中查询到 数据 4，所以触发页面淘汰，并且缺页。按照先进先出的规则，将最先进来的 1 淘汰出去，结果如下图所示。
在填入第五位数据 4 的时候，发现已在缓存表中有 4，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
同理填入第六位数据 4，发现已在缓存表中有 4，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第七位数据 3 时，缓存表中依然存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第八位数据 2 时，缓存表中依然存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第九位数据 1 时，缓存表中查不到 1，所以发生缺页现象，将最先进入的数据 2 淘汰，如下图所示。
填入第十位数据 4 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第十一位数据 5 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 3 淘汰，如下图所示。
填入第十二位数据 3 时，缓存表中不存在，非常可惜刚刚被上轮淘汰，所以发生缺页现象，将最先进来的数据 4 淘汰，如下图所示。
填入第十三位数据 2 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 1 淘汰，如下图所示。
填入第十四位数据 2 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第十五位数据 5 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。
填入第十六位数据 1 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 5 淘汰，如下图所示。
最终模拟计算可得，发生缺页次数 9 次。
三、 最近最少使用算法
最近最少使用算法是每次淘汰最低频使用的数据。
这种算法不会出现倒挂现象（抖动现象）。
还是对于 1 2 3 4 4 4 3 2 1 4 5 3 2 2 5 1 序列，进程内存空间为 3 位，开始内存为空，使用最近最少使用算法，计算缺页次数。
首先对于第 1 - 3 个数据 ，因为缓存为空，所以会触发缺页，如下图所示。
对于第四个数据 4，无法在现有缓存中查询到，所以触发了缺页，需要页面淘汰。
根据最近最少使用算法，1 2 3 三个数据最近最常使用的是 3，其次是 2，所以淘汰掉数据 1，如下图所示。
对于第五个数据 4，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第六个数据 4，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第七个数据 3，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第八个数据 2，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第九个数据 2，现有缓存中没有数据 2，所以触发缺页，进行页面淘汰。
数据 2 从第二步加入缓存后，使用了 2 次。
数据 3 使用了 2 次。
数据 4 使用了 3 次。
可以肯定的是，数据 4 不会被淘汰。在数据 2 和 3 中，虽然都使用了 2 次，但数据 2 比数据 3 更最近被使用，所以数据 3 淘汰，这就是**【最近】【最少】使用算法**，结果如下图所示。
对于第十个数据 4，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第十一个数据 5，现有缓存中没有数据 2，所以触发缺页，进行页面淘汰。
现有缓存中数据 2 使用了 2 次。
数据 4 使用了 4 次。
数据 1 使用了 1 次，请注意是最后一次加入缓存后的使用次数，不是全局使用次数。
所以数据 1 淘汰，如下图所示。
对于第十二个数据 3，现有缓存中没有数据 3，所以触发缺页，进行页面淘汰。
现有缓存中数据 2 使用了 2 次。
数据 4 使用了 4 次。
数据 5 使用了 1 次。
所以数据 5 淘汰，如下图所示。
对于第十三个数据 2，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第十四个数据 2，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。
对于第十五个数据 5，现有缓存中没有数据 5，所以触发缺页，进行页面淘汰。
现有缓存中数据 2 使用了 4 次。
数据 4 使用了 4 次。
数据 3 使用了 1 次。
所以数据 3 淘汰，如下图所示。
对于第十六个数据 1，现有缓存中没有数据 1，所以触发缺页，进行页面淘汰。
现有缓存中数据 2 使用了 4 次。
数据 4 使用了 4 次。
数据 5 使用了 1 次。
所以数据 5 淘汰，如下图所示。
所以使用最近最少使用算法，最终缺页次数为 9 次。
四、总结
本文讲解了操作系统中进程读内存时，维护高速缓存的页面淘汰算法，其中重点讲解了先进先出算法和最近最少使用算法，学习高速缓存 Cache 提高程序执行效率的原理。
