LRU算法理解（转）

问题：某虚拟存储系统采用页式内存管理，使用LRU页面替换算法， 考虑下面的页面访问地址流，
1 8 1 7 8 2 7 1 8 3 8 2 1 3 1 7 1 3 7
假如内存容量为4个页面，开始是空的，则失效率为?

• LRU是LeastRecently Used 近期最少使用算法，也就是说，近期最少使用的那个页面，将被置换出去（可以理解为这个页面将被废弃）

• 对于本题。内存容量为4个页面，这是要清楚的。具体看下面的表格：

• 缺页率 = 6 / 20 =3/ 10 = 30%
  从上到下是4个页面。

• 最开始，1 需要被调用，将1放入内存中，由于1一开始没有，所以一次缺页

• 然后，8 要被调用，，将1放入内存中，由于8一开始没有，所以又产生一次缺页

• 以此往后，直到4块内存都满了，最新使用过的放在最下面（页4），则置换出最上面（页1）。

• 通俗地说，就是总共空间只有4块。只能放4个页面。那么当页面满的时候，就把你很久很久没有使用过的那个页面（也就是近期最少使用的页面）置换出去，然后补充新的页面进来。