地址映射过程中,若在页面中发现所要访问的页面不再内存中,则产生缺页中断。发生当缺页中断时操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出(FIFO)法。

 

      优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。

 

 

假定系统为某进程分配了三个物理块,并考虑有以下页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2 ,0,1,7,0,1。釆用FIFO算法进行页面置换,进程访问页面2时,把最早进入内存的页面7换出。然后访问页面3时,再把2,0,1中最先进入内存的页换出。由下图可以看出,利用FIFO算法时进行了12次页面置换。

访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
物理块1 7 7 7 2   2 2 4 4 4 0     0 0     7 7 7
物理块2   0 0 0   3 3 3 2 2 2     1 1     1 0 0
物理块3     1 1   1 0 0 0 3 3     3 2     2 2 1
缺页否