设某进程有一访问列：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
网友评论