LRU（最近最久未使用）淘汰算法出入图

设某进程有一访问列：3 2 1 4 4 5 3 4 3 2 1 5，共访问12次，为了求其缺页率，必须要写出其置换出入图，采用LRU（最近最久未使用）淘汰算法，内存分配3页帧

刚开始时，由于内存并没有缓存该进程的任何页，所以前三次由于分别访问第3,2,1页，也就发生了3次缺页，并分别缓存进来

接下里要访问第4页，此时发生缺页中断，因此要替换掉一页。用LRU替换算法的判别方式如下：

访问第四页之前，因为第3,2,1页已经缓存了，所以它们三个就是最近使用的页，此时查看之前的访问列，找出离4最远的那一页，它就是最久未使用的页，由于在这里是3，所以第三页要被替换：

第三页被替换为第四页，接下来又访问第四页，此时不发生缺页中断

接下来要访问第5页，继续选出一个牺牲页：

因为访问第5页之前，已经缓存了第4,2,1页，查看访问列，发现第2页最远，从而第二页是最近最久未使用的页，它就会被替换

对于接下来的第3页也是同理：

这样，我们就能构造出这一访问列的出入图了：

可见缺页9次，所以LRU替换算法对于该访问列的缺页率是 9/12=0.75