缺页中断处理算法

本文主要是介绍缺页中断处理算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

缺页中断：在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存是，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

1、保护CPU现场

2、分析中断原因

3、转入缺页中断处理程序进行处理

4、恢复CPU现场，继续执行

但是缺页中断是由于所要访问的页面不存在于内存时，由硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

1、在指令执行期间产生和处理缺页中断信号

2、一条指令在执行期间，可能产生多次缺页中断

3、缺页中断返回是，执行产生中断的一条指令，而一般的中断返回是，执行下一条指令。

最佳（Optimal）置换算法是指其所选择的淘汰页面，将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其他算法。

先进先出（FIFO）置换算法是最简单的页面置换算法。这种算法的基本思想：当需要淘汰一个页面是，总是选择主流驻村时间最长的页面进行淘汰，~~即先进入主存的页面先淘汰~~。其理由是最早调入主存的页面不在被使用的可能性最大。该算法会淘汰经常访问的页面，不直营进程实际运行的规律，目前已很少使用。

个人认为第二张表比较好理解。

Belady异常：一般来说，分配给进程的物理块越多，运行时的缺页次数应该越少，使用FIFO是，存在相反情况，分配4个物理块的缺页竟然比3个物理块的缺页次数还多。不过LRU和OPT算法永远不会出现Belady异常。

最近最久未使用（LRU）置换算法：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是当需要淘汰一个页面时，总选择在最近一段时间内最久不用的页面予以淘汰。LRU算法普遍地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件支持。

个人认为第二张表比较好理解。

时钟（CLOCK）置换算法

LRU算法的新能接近于OPT，但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。