页面置换算法

概述

LRU是Least Recently Used近期最少使用算法

内存管理的一种页面置换算法，对于在内存中但又不用的数据块(内存块)叫做LRU，Oracle会根据那些数据属于LRU而将其移出内存腾出空间来加载另外的数据

差距

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被使用到。这个，就是著名的局部性原理

真题

网上搜索了阿里巴巴2014校园招聘真题，这里做一下（ps：我因为北京没试卷没能参加9月14号笔试）

某缓存系统采用LRU淘汰算法，假定缓存容量为4,并且初始为空，那么在顺序访问一下数据项的时候：1,5,1,3,5,2,4,1,2出现缓存直接命中的次数是？，最后缓存中即将准备淘汰的数据项是？

解答：

1. 1调入内存 1
2. 5调入内存 1 5
3. 1调入内存 5 1（命中 1）
4. 3调入内存 5 1 3
5. 5调入内存 1 3 5 （命中5）
6. 2调入内存 1 3 5 2
7. 4调入内存（1最久未使用，淘汰1） 3 5 2 4
8. 1调入内存（3最久未使用，淘汰3） 5 2 4 1
9. 2调入内存 5 4 1 2（命中2）

因此，直接命中次数是3,最后缓存即将准备淘汰的数据项是5