目录

一、LRU是什么？

二、LRU算法的规则

三、缺页，换页

四、计算页面置换次数、缺页数

LRU，全称是Least Recently Used，即最近最少使用页面置换算法。从字面意思上可以看出，选择最近最久未使用的页面予以淘汰。

LRU算法是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是，发生缺页中断时，选择未使用时间最长的页面置换出去。

最近被使用或访问的数据放置在最前面;

当缓存命中(即缓存数据被访问)则将数据移到头部;

当缓存数量达到最大值时，将最近最少访问的数据剔除。

缺页：当内存中不存在该页时，将该页调入内存中。

换页：当发生缺页时，内存已满，需要将内存中的某页调换成需要的页。

即换页一定缺页，缺页不一定换页。

题目：一进程刚获得三个主存块的使用权，若该进程访问页面的次序是｛1，3，2，1，2，1，5，1，2，3｝，采用LRU算法时，缺页数是______次。  假设把三主存块想象成长度为3的数组。开始演示：

1 进入 —> 1（缺1） 3 进入 —> 3 1 （刚使用的放在前面(左边)，未使用的依次后移(右移))（缺3） 2 进入 —> 2 3 1（缺2） 1 进入 —> 1 2 3（把原本的1移出） 2 进入 —> 2 1 3 1 进入 —> 1 2 3 5 进入 —> 5 1 2 （进行页面置换，3是最少使用的所以换出） 1 进入 —> 1 5 2 2 进入 —> 2 1 5 3 进入 —> 3 2 1（进行页面置换，5是最少使用的所以换出）

总共进行了两次页面置换，所以缺页数=3+2=5，这个3代表前三个缺的，2代表置换的次数，缺页率为5/10=0.5。（页面置换算一次缺页数）