中断

    [百度百科，下同]

是指计算机在执行程序的过程中，当出现异常情况或特殊请求时，计算机停止现行程序的运行，转向对这些异常情况或特殊请求的处理，处理结束后再返回现行程序的间断处，继续执行原程序。

缺页中断

缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。

缺页中断的顺序

缺页中断发生时的事件顺序如下：

1) 硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。

2) 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。

3) 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。

4) 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。

5) 如果选择的页框“脏”（修改了）了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。

6) 一旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。

7) 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。

8) 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。

9) 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。

10) 该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

LRU页面置换算法

       LRU是Least Recently Used的缩写，即最少使用页面置换算法，是为虚拟页式存储管理服务的。

关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式—— 在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。

然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。

对于虚拟页式存储，内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时，把它调入内存，同时为了保持原有空间的大小，还要把一个内存中页面调出至外存。自然，这种调动越少，进程执行的效率也就越高。那么，把哪个页面调出去可以达到调动尽量少的目的？我们需要一个算法。

自然，达到这样一种情形的算法是最理想的了——每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。

该算法赋予每一个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当必须淘汰一个页面时，选择现有页面里其中t值最大的，即最近最久未使用的页面予以淘汰。

FIFO页面置换算法

       FIFO（first in first out，先进先出）页面置换算法，这是的最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面给予淘汰。该算法实现简单，只需要把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，还有全局变量，常用函数，例程等页面，先进先出算法并不能保证这些页面不被淘汰。

计算用LRU和FIFO算法计算“缺页中断”

   [http://blog.csdn.net/linping070/article/details/5457130]

       在一个虚拟存储管理系统中，假如系统分配给一个作业的内存物理块数是3，并且此作业的页面使用顺序为2，3，2，1，5，2，4，5，3，2，5，2，若采用FIFO和LRU置换算法，其产生的缺页次数分别为 (5) 和 (6) 。
(5) A．6  6) A．6
   B．7    B．7
   C．8    C．8
   D．9    D．9 
【解析】

2  2  2  2  5  5  5  5  3  3  3  3   [第一个内存物理块]

3  3  3  3  2  2  2  2  2  5  5   [第二个内存物理块]

1  1  1  4  4  4  4  4  2   [第三个内存物理块]

可知缺页次数为9。

采用LRU时，其页面调度过程：

2  2  2  2  2  2  2  2  2  2  2  2

   3  3  3  5  5  5  5  3  3  3  3

         1  1  1  4  4  4  4  5  5

可计算其缺页次数为7。

FIFO置换算法有这样一个奇怪现象：内存空间块数越多，缺页中断率可能相反的越高(缺页中断次数越高)。 
【解答】

FIFO的置换过程：
刚开始内存并没有这个作业，所以发生缺页中断一次。作业的0号页进入内存。(1次缺页中断) 
而页1又不在内存，又发生缺页中断一次。作业页1进入内存。(2次缺页中断) 

页2不在内存，发生缺页中断。页2进入内存。 (3次缺页中断) 
页3不在内存，发生缺页中断。页3进入内存。 (4次缺页中断) 
接下来调入页2，页1，页3，页2。由于都在内存中，并不发生缺页中断。 
页5不在内存，发生缺页中断。页5进入内存，页5置换页0。 (5次缺页中断) 
接下来调入页2，页3。由于都在内存中，并不发生缺页中断。 
页6不在内存，发生缺页中断。页6进入内存。页6置换页1。 (6次缺页中断) 
页2在内存，不发生缺页中断。 
页1不在内存(在发生第6次缺页中断时被置换了)，发生缺页中断。 
页1进入内存，页2被置换。 (7次缺页中断) 
页4置换页3，页4进入内存。 (8次缺页中断) 
现在调入页2，但页2在发生第7次缺页中断时被置换掉了。 
现在页2进入内存，其置换页5。(因为这个时候是页5最先进入内存。)(9次缺页中断)