面试常问内容——缺页错误与页面置换
当我们使用分页方式进行内存管理时，缺页错误是一种常见的错误。当遇到缺页错误时，我们应当设置合理的算法去解决该问题。
首先让我们了解一下缺页错误的基本概念。
缺页错误
访问页表中有效位为“无效”的页（通常通过页表中的有效位进行判断）时，产生缺页错误（第一次访问某页肯定会产生缺页错误）。
处理缺页错误的做法：
1）检查进程的对应的内部表，查看该引用是有效的还是无效的内存访问；
2）如果是无效的内存访问，则终止进程；否则在物理内存中寻找一个空闲帧；
3）将该页面从磁盘中读到刚分配的帧上；
4）修改内部表和页表；
5）从发生缺页错误处重新启动进程；
我们可以看到，当物理内存中还存在空闲帧时，缺页错误是比较容易处理的，只需要将页面从磁盘中读到新分配的空闲帧上并修改内部表和页表即可。但如果物理内存已经满了，没有空闲帧了呢？这时我们就必须选择一个牺牲帧，用该页面来替换牺牲帧上的内容，这个过程也称为页面置换。如何选择牺牲帧是我们需要考虑的主要问题。下面我会给大家介绍三种常见的页面置换算法：FIFO页面置换算法、最优页面置换算法、LRU页面置换（最近最少使用）。
首先我们来了解一下页面置换的基本过程。
页面置换
当发生了缺页错误，且主存中没有了空闲帧时，需要利用页面置换从主存中选择一个帧作为牺牲帧来替换。（页面置换需要两次页面传输，牺牲帧的页面调入磁盘，所需页面调出磁盘）
基本的页面置换过程：
1）找到所需页面的磁盘；
2）寻找主存中的一个空闲帧：如果有，则使用该帧；否则选择一个牺牲帧，将牺牲帧的内容写入磁盘，修改牺牲帧对应的页表和帧表；
3）从磁盘中将所需页面加载到选择的帧上，修改该所需页面对应的页表和帧表；
4）从发生缺页错误处重启进程；
有时候牺牲帧的页面无需再写入磁盘上，因此我们引入“脏位”，从而进一步提高页面置换的速度。脏位（修改位）
当需要页面置换时，并非所有情况下牺牲帧的页面都要写入磁盘，当该页面的脏位为True，即该页面被修改时，才需要重新写入磁盘，否则不需要重新写入磁盘（因为磁盘中本就有该页面的内容，如果没修改，那么再次写入和不写入没区别）。
页面置换常见算法
1. FIFO页面置换
为每个页面记录了调到内存的时间（实际上用链表来表示时间的前后顺序），当需要页面置换时，选择最旧（即最早调入内存）的页面来进行置换。
- 该算法存在Belady异常，当分配的帧的数量增加时，缺页错误率可能上升。
2. 最优页面置换（OPT）
置换接下来最长时间不会使用的页面（预测未来最长时间不使用）。
- 该算法的缺页错误最少，但很难实现，因为要用到未来知识。
3. LRU页面置换（最近最少使用算法）
选择最近最少使用的页面进行置换。（用到历史的知识）
- 该算法的缺页错误比较少，也比较容易实现，一般使用该算法。
一般而言，随着可用帧数量的增多，缺页错误的数量会越来越少。（FIFO页面置换算法有例外）
实际上，页面置换算法可分为两大类：全局分配和局部分配（全局和局部针对于置换帧的选取范围而言）。
全局分配
允许一个进程从所有帧的集合中选取一个置换帧，该帧可以是其他进程所拥有的。
局部分配
只允许进程从它自己所拥有的帧中选取置换帧。
以上便是本文关于缺页错误和页面置换的全部内容。后面我会继续谈谈缺页错误所引起的系统抖动问题，感兴趣的伙伴可以多加关注
~
#操作系统##面试题目#~ 
