①LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也很高”,反过来说“如果 数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”,两种理解是一样的;常 用于页面置换算法,为虚拟页式存储管理服务。
②达到这样一种情形的算法是最理想的:每次调换出的页面是所有内存页面中最迟将被使用的;这可以最大限度的推迟页面调换,这种算法,被称为理想页面置换算法。可惜的是,这种算法是无法实现的。 为了尽量减少与理想算法的差距,产生了各种精妙的算法,最近最少使用 页面置换算法便是其中一个。LRU 算法的提出,是基于这样一个事实:在前面几条指令中使用 频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能 在未来较长的一段时间内不会被用到 。这个,就是著名的局部性原理——比内存速度还要快 的cache,也是基于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最少使用 的那个页面调出内存。