【软考学习13】图解页面淘汰算法，先进先出算法、最近最少使用算法

比眉伴天荒 2023-09-26 09:08 8阅读 0赞

> 本文讲解了操作系统中进程读内存时，维护高速缓存的**页面淘汰算法**，其中重点讲解了**先进先出算法**和**最近最少使用算法**，学习高速缓存 Cache 提高程序执行效率的原理。

![在这里插入图片描述][e977674a08b5462d93350135b762c510.png]

--------------------

### 一、为什么要用页面淘汰算法 ###

在计算机的存储结构中，存在着局部性原理（在《[【软考学习6】计算机存储结构——局部性原理、Cache、主存地址单元、磁盘存取、总线和可靠性》][6_Cache]中有介绍）。

简单来说，**如果一个数据正在被使用，那么在近期它很可能还会被再次使用**。

正是有这样一个现象，所以高速缓存 Cache 的存在就非常必要，它虽然容量很小，但速度很快，可以大大提升执行效率。

计算机的存储结构如下图所示。  
![在这里插入图片描述][36b214095b534a6984b81de8401aaab7.png_pic_center_pic_center]

使用了高速缓存（Cache）后，CPU **首先到高速缓存（Cache）中尝试取数据**，如果拿到了数据则直接返回，速度有大量的提升。

如果没拿到，则发生了**缺页**现象，再到主存中去取数据，如下图所示。

![在这里插入图片描述][d7d1743d9dc14f659ea6448936549a08.png_pic_center]  
主存容量大、速度慢，高速缓存（Cache）容量小、速度快。

为了整体的提升系统运行效率，需要**把经常执行的放在高速缓存（Cache）中，其余的放在主存**。

在高速缓存（Cache）存放满后，又有新数据需要进来时，就涉及到**页面淘汰算法**了，也就是要把现有的某个数据淘汰掉，给新进来的数据留地方。

如果页面淘汰算法使用不妥当，会发送**倒挂现象**（抖动现象）。

比如一个高速缓存有 **3 个单位**的空间，运行一段程序有 **8 次缺页**；如果用另外一个 **4 个单位**的高速缓存，运行同样的程序有 **10 次缺页**，那么就出现了**倒挂现象**（抖动现象）。

常用的页面淘汰算法有四种：**最优算法**、**随机算法**、**先进先出算法**和**最近最少使用算法**。

**最优算法只是一个理论算法**，通常是事后去人为分析最优的算法，这一类算法存在的意义是分析其他算法的优劣性，以及评估某个算法距离最优算法还差多远，所以没有实际求解意义。

**随机算法也是一个计算机模拟的算法**，采用随机的方式进行页面淘汰，因为随机具有较大的不确定性，所以也没有多大的实际求解意义。

接下来重点讲解**先进先出算法**和**最近最少使用算法**。

--------------------

### 二、 先进先出算法 ###

先进先出算法顾名思义，就是最先进来的最先出去。

这种算法有可能出现倒挂现象（抖动现象）。

![在这里插入图片描述][9a77d6372e24496ba554a3822f05e3dd.png_pic_center_pic_center]

> 对于 1 2 3 4 4 4 3 2 1 4 5 3 2 2 5 1 序列，进程内存空间为 3 位，开始内存为空，使用先进先出算法，计算缺页次数。

首先**填充第一个数据 1**，因为缓存为空，所以触发**缺页**，如下图所示。  
![在这里插入图片描述][d6675756eef14de6ac2972396b23d59b.png_pic_center]

接着同理**填入数据 2 和 3**，触发两次**缺页**，因为缓存表为空，如下图所示。

![在这里插入图片描述][27fabdf2b4674cc3b7044c010154df81.png_pic_center]

接着**填入数据 4** 的时候，因为无法从现有的 1、2、3 中查询到 数据 4，所以触发**页面淘汰**，并且**缺页**。按照先进先出的规则，将最先进来的 1 淘汰出去，结果如下图所示。

![在这里插入图片描述][a654d6767cdb447da280d23b069bc543.png_pic_center]  
在填入**第五位数据 4** 的时候，发现已在缓存表中有 4，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][c1d2438cb2f648cc9f18f06b0ea84b1f.png_pic_center]  
同理填入**第六位数据 4**，发现已在缓存表中有 4，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][84f8c45ee22d473d84cfe773969a9f9e.png_pic_center]  
填入**第七位数据 3** 时，缓存表中依然存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][4438f1b5f4ef4afc82063c5fe097fcaf.png_pic_center]  
填入**第八位数据 2** 时，缓存表中依然存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][a0061e3dcc7a423bb09624ebdc63aa54.png_pic_center]  
填入**第九位数据 1** 时，缓存表中查不到 1，所以发生缺页现象，将最先进入的数据 2 淘汰，如下图所示。

![在这里插入图片描述][c7d361dc010c4bd4aa4c8d50d79c6b90.png_pic_center]  
填入**第十位数据 4** 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][b2655c0e65c442dea41905d092d8f0dd.png_pic_center]  
填入**第十一位数据 5** 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 3 淘汰，如下图所示。

![在这里插入图片描述][f09c3f07f9134f2e9724850a23a678a4.png_pic_center]  
填入**第十二位数据 3** 时，缓存表中不存在，非常可惜刚刚被上轮淘汰，所以发生缺页现象，将最先进来的数据 4 淘汰，如下图所示。

![在这里插入图片描述][d3691e017bdc459dadf43f4d90e8d0fe.png_pic_center]  
填入**第十三位数据 2** 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 1 淘汰，如下图所示。

![在这里插入图片描述][1bddfb43b001442591cc722be666749c.png_pic_center]  
填入**第十四位数据 2** 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][e83b498a506d4e028ea3ba92d73c1cb3.png_pic_center]  
填入**第十五位数据 5** 时，缓存表中存在，所以没有发生缺页现象，缓存中的数据不变，如下图所示。

![在这里插入图片描述][2f6b9cd305cf4a1182ecd336f0dcb517.png_pic_center]  
填入**第十六位数据 1** 时，缓存表中不存在，所以发生缺页现象，将最先进来的数据 5 淘汰，如下图所示。

![在这里插入图片描述][77b254dd2bf344af99d376b7b24115a3.png_pic_center]  
最终模拟计算可得，**发生缺页次数 9 次**。

--------------------

### 三、 最近最少使用算法 ###

最近最少使用算法是每次淘汰最低频使用的数据。

这种算法不会出现倒挂现象（抖动现象）。  
![在这里插入图片描述][9a77d6372e24496ba554a3822f05e3dd.png_pic_center_pic_center]

> 还是对于 1 2 3 4 4 4 3 2 1 4 5 3 2 2 5 1 序列，进程内存空间为 3 位，开始内存为空，使用最近最少使用算法，计算缺页次数。

首先**对于第 1 - 3 个数据 ，因为缓存为空，所以会触发缺页**，如下图所示。

![在这里插入图片描述][e667257084eb4a63ad7ebde6be7a384b.png_pic_center]

对于**第四个数据 4**，无法在现有缓存中查询到，所以触发了缺页，需要页面淘汰。

根据最近最少使用算法，1 2 3 三个数据最近最常使用的是 3，其次是 2，所以淘汰掉数据 1，如下图所示。

![在这里插入图片描述][7396da557b68418597075787d2502af1.png_pic_center]

对于**第五个数据 4**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][79e057e7961746dead7f89e4a5a74557.png_pic_center]  
对于**第六个数据 4**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][fd131232eba047a6a5f6f8018488c987.png_pic_center]  
对于**第七个数据 3**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][cbc4d15711b344cbbc875cd024855269.png_pic_center]  
对于**第八个数据 2**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][fdada3e8108f4ea485f97c31b5aa2ccb.png_pic_center]  
对于**第九个数据 2**，现有缓存中没有数据 2，所以触发缺页，进行页面淘汰。

数据 2 从第二步加入缓存后，使用了 2 次。

数据 3 使用了 2 次。

数据 4 使用了 3 次。

可以肯定的是，**数据 4 不会被淘汰**。在数据 2 和 3 中，虽然都使用了 2 次，但**数据 2 比数据 3 更最近被使用，所以数据 3 淘汰**，这就是\*\*【最近】【最少】使用算法\*\*，结果如下图所示。

![在这里插入图片描述][2b90928bb1bc48f09a733bff8bf8a31c.png_pic_center]  
对于**第十个数据 4**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][eff89d3b41dd47839f3f342090b0df85.png_pic_center]  
对于**第十一个数据 5**，现有缓存中没有数据 2，所以触发缺页，进行页面淘汰。

现有缓存中数据 2 使用了 2 次。

数据 4 使用了 4 次。

数据 1 使用了 1 次，请注意是最后一次加入缓存后的使用次数，不是全局使用次数。

所以数据 1 淘汰，如下图所示。

![在这里插入图片描述][5d00dea691ee484eb4dbe51f2c543d58.png_pic_center]  
对于**第十二个数据 3**，现有缓存中没有数据 3，所以触发缺页，进行页面淘汰。

现有缓存中数据 2 使用了 2 次。

数据 4 使用了 4 次。

数据 5 使用了 1 次。

所以数据 5 淘汰，如下图所示。

![在这里插入图片描述][29c575fc8cf74ccc856cbc17deab52e6.png_pic_center]

对于**第十三个数据 2**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][b8909ad06e5d4063bd4969bbec4ef9ea.png_pic_center]  
对于**第十四个数据 2**，可以在现有缓存中查询到，所以没有触发缺页，无需页面淘汰，如下图所示。

![在这里插入图片描述][99fa62a1f19a4c609b07ee7ab82a802b.png_pic_center]

对于**第十五个数据 5**，现有缓存中没有数据 5，所以触发缺页，进行页面淘汰。

现有缓存中数据 2 使用了 4 次。

数据 4 使用了 4 次。

数据 3 使用了 1 次。

所以数据 3 淘汰，如下图所示。

![在这里插入图片描述][b5c48a866fa7413e917e995779902d83.png_pic_center]

对于**第十六个数据 1**，现有缓存中没有数据 1，所以触发缺页，进行页面淘汰。

现有缓存中数据 2 使用了 4 次。

数据 4 使用了 4 次。

数据 5 使用了 1 次。

所以数据 5 淘汰，如下图所示。

![在这里插入图片描述][a1fa2a7b499c4cad8ecaad490a1d3e47.png_pic_center]

所以使用**最近最少使用算法**，最终**缺页次数为 9 次**。

--------------------

### 四、总结 ###

本文讲解了操作系统中进程读内存时，维护高速缓存的**页面淘汰算法**，其中重点讲解了**先进先出算法**和**最近最少使用算法**，学习高速缓存 Cache 提高程序执行效率的原理。

[e977674a08b5462d93350135b762c510.png]: https://img-blog.csdnimg.cn/e977674a08b5462d93350135b762c510.png
[6_Cache]: https://blog.csdn.net/qq_41464123/article/details/126596446
[36b214095b534a6984b81de8401aaab7.png_pic_center_pic_center]: https://img-blog.csdnimg.cn/36b214095b534a6984b81de8401aaab7.png#pic_center#pic_center
[d7d1743d9dc14f659ea6448936549a08.png_pic_center]: https://img-blog.csdnimg.cn/d7d1743d9dc14f659ea6448936549a08.png#pic_center
[9a77d6372e24496ba554a3822f05e3dd.png_pic_center_pic_center]: https://img-blog.csdnimg.cn/9a77d6372e24496ba554a3822f05e3dd.png#pic_center#pic_center
[d6675756eef14de6ac2972396b23d59b.png_pic_center]: https://img-blog.csdnimg.cn/d6675756eef14de6ac2972396b23d59b.png#pic_center
[27fabdf2b4674cc3b7044c010154df81.png_pic_center]: https://img-blog.csdnimg.cn/27fabdf2b4674cc3b7044c010154df81.png#pic_center
[a654d6767cdb447da280d23b069bc543.png_pic_center]: https://img-blog.csdnimg.cn/a654d6767cdb447da280d23b069bc543.png#pic_center
[c1d2438cb2f648cc9f18f06b0ea84b1f.png_pic_center]: https://img-blog.csdnimg.cn/c1d2438cb2f648cc9f18f06b0ea84b1f.png#pic_center
[84f8c45ee22d473d84cfe773969a9f9e.png_pic_center]: https://img-blog.csdnimg.cn/84f8c45ee22d473d84cfe773969a9f9e.png#pic_center
[4438f1b5f4ef4afc82063c5fe097fcaf.png_pic_center]: https://img-blog.csdnimg.cn/4438f1b5f4ef4afc82063c5fe097fcaf.png#pic_center
[a0061e3dcc7a423bb09624ebdc63aa54.png_pic_center]: https://img-blog.csdnimg.cn/a0061e3dcc7a423bb09624ebdc63aa54.png#pic_center
[c7d361dc010c4bd4aa4c8d50d79c6b90.png_pic_center]: https://img-blog.csdnimg.cn/c7d361dc010c4bd4aa4c8d50d79c6b90.png#pic_center
[b2655c0e65c442dea41905d092d8f0dd.png_pic_center]: https://img-blog.csdnimg.cn/b2655c0e65c442dea41905d092d8f0dd.png#pic_center
[f09c3f07f9134f2e9724850a23a678a4.png_pic_center]: https://img-blog.csdnimg.cn/f09c3f07f9134f2e9724850a23a678a4.png#pic_center
[d3691e017bdc459dadf43f4d90e8d0fe.png_pic_center]: https://img-blog.csdnimg.cn/d3691e017bdc459dadf43f4d90e8d0fe.png#pic_center
[1bddfb43b001442591cc722be666749c.png_pic_center]: https://img-blog.csdnimg.cn/1bddfb43b001442591cc722be666749c.png#pic_center
[e83b498a506d4e028ea3ba92d73c1cb3.png_pic_center]: https://img-blog.csdnimg.cn/e83b498a506d4e028ea3ba92d73c1cb3.png#pic_center
[2f6b9cd305cf4a1182ecd336f0dcb517.png_pic_center]: https://img-blog.csdnimg.cn/2f6b9cd305cf4a1182ecd336f0dcb517.png#pic_center
[77b254dd2bf344af99d376b7b24115a3.png_pic_center]: https://img-blog.csdnimg.cn/77b254dd2bf344af99d376b7b24115a3.png#pic_center
[e667257084eb4a63ad7ebde6be7a384b.png_pic_center]: https://img-blog.csdnimg.cn/e667257084eb4a63ad7ebde6be7a384b.png#pic_center
[7396da557b68418597075787d2502af1.png_pic_center]: https://img-blog.csdnimg.cn/7396da557b68418597075787d2502af1.png#pic_center
[79e057e7961746dead7f89e4a5a74557.png_pic_center]: https://img-blog.csdnimg.cn/79e057e7961746dead7f89e4a5a74557.png#pic_center
[fd131232eba047a6a5f6f8018488c987.png_pic_center]: https://img-blog.csdnimg.cn/fd131232eba047a6a5f6f8018488c987.png#pic_center
[cbc4d15711b344cbbc875cd024855269.png_pic_center]: https://img-blog.csdnimg.cn/cbc4d15711b344cbbc875cd024855269.png#pic_center
[fdada3e8108f4ea485f97c31b5aa2ccb.png_pic_center]: https://img-blog.csdnimg.cn/fdada3e8108f4ea485f97c31b5aa2ccb.png#pic_center
[2b90928bb1bc48f09a733bff8bf8a31c.png_pic_center]: https://img-blog.csdnimg.cn/2b90928bb1bc48f09a733bff8bf8a31c.png#pic_center
[eff89d3b41dd47839f3f342090b0df85.png_pic_center]: https://img-blog.csdnimg.cn/eff89d3b41dd47839f3f342090b0df85.png#pic_center
[5d00dea691ee484eb4dbe51f2c543d58.png_pic_center]: https://img-blog.csdnimg.cn/5d00dea691ee484eb4dbe51f2c543d58.png#pic_center
[29c575fc8cf74ccc856cbc17deab52e6.png_pic_center]: https://img-blog.csdnimg.cn/29c575fc8cf74ccc856cbc17deab52e6.png#pic_center
[b8909ad06e5d4063bd4969bbec4ef9ea.png_pic_center]: https://img-blog.csdnimg.cn/b8909ad06e5d4063bd4969bbec4ef9ea.png#pic_center
[99fa62a1f19a4c609b07ee7ab82a802b.png_pic_center]: https://img-blog.csdnimg.cn/99fa62a1f19a4c609b07ee7ab82a802b.png#pic_center
[b5c48a866fa7413e917e995779902d83.png_pic_center]: https://img-blog.csdnimg.cn/b5c48a866fa7413e917e995779902d83.png#pic_center
[a1fa2a7b499c4cad8ecaad490a1d3e47.png_pic_center]: https://img-blog.csdnimg.cn/a1fa2a7b499c4cad8ecaad490a1d3e47.png#pic_center