页面置换算法LRULFU算法

页面置换算法介绍

评价一个页面替换算法好坏的标准主要有两个&＃xff0c;一是命中率要高&＃xff0c;二是算法要容易实现。要提高一个页面替换算法的命中率&＃xff0c;首先要使这种算法能正确反映程序的局部性&＃xff0c;其次是这种算法要能够充分利用主存中页面调度情况的历史信息&＃xff0c;或者能够预测主存中将要发生的页面调度情况。 
　　页面替换算法主要用于如下几个地方&＃xff1a; 
　　(1) 虚拟存储器中&＃xff0c;主存页面&＃xff08;或程序段&＃xff09;的替换。 
　　(2) Cache中的块替换。 
　　(3) 虚拟存储器的快慢表中&＃xff0c;快表的替换。 
　　(4) 虚拟存储器中&＃xff0c;用户基地址寄存器的替换。 

LFU算法

    近期最少使用算法&＃xff0c;即LFU算法&＃xff08;Least Frequently Used algorithm&＃xff09;。这种算法选择近期最少访问的页面作为被替换的页面。显然&＃xff0c;这是一种非常合理的算法&＃xff0c;因为到目前为止最少使用的页面&＃xff0c;很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息&＃xff0c;又正确反映了程序的局部性。但是&＃xff0c;这种算法实现起来非常困难&＃xff0c;它要为每个页面设置一个很长的计数器&＃xff0c;并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时&＃xff0c;要从所有计数器中找出一个计数值最大的计数器。因此&＃xff0c;通常采用如下一种相对比较简单的方法。

    核心思想&＃xff1a;如果一个数据在最近一段时间内使用次数很少&＃xff0c;那么在将来一段时间内被使用的可能性也很小“

    传统实现:

        1. 新加入数据插入到队列尾部&＃xff08;因为引用计数为1&＃xff09;&＃xff1b;

        2. 队列中的数据被访问后&＃xff0c;引用计数增加&＃xff0c;队列重新排序&＃xff1b;

        3. 当需要淘汰数据时&＃xff0c;将已经排序的列表最后的数据块(访问次    数最少的块)删除。

    实现方式&＃xff1a;

        可用一个小顶堆&＃43;hashmap,来实现&＃xff1b;

       小顶堆对访问次数排序

       hashmap对每个缓存节点访问次数来更新
 

      改良版算法&＃xff1a;Window-LFU&＃xff08;置换指定时间内&＃xff0c;按照LFU规则排序淘汰数量&＃xff09;

        1&＃xff09;记录了过去W个访问记录&＃xff1b;

        2&＃xff09;需要淘汰时&＃xff0c;将W个访问记录按照LFU规则排序淘汰

        举例如下&＃xff1a;

            假设历史访问记录长度设为9&＃xff0c;缓存大小为3&＃xff0c;图中不同颜色代表针对不同数据块的访问&＃xff0c;同一颜色代表            针 对同一数据的多次访问。

            样例1&＃xff1a;黄色访问3次&＃xff0c;蓝色和橘色都是两次&＃xff0c;橘色更新&＃xff0c;因此缓存黄色、橘色、蓝色三个数据块

            样例2&＃xff1a;绿色访问3次&＃xff0c;蓝色两次&＃xff0c;暗红两次&＃xff0c;蓝色更新&＃xff0c;因此缓存绿色、蓝色、暗红三个数据块

         需要维护一个队列&＃xff0c;记录数据的访问流历史&＃xff1b;需要排序。          

          Window-LFU只记录一部分的访问历史记录&＃xff0c;不需要记录所有的数据访问历史&＃xff0c;因此内存消耗和排序消耗都            比LFU要低。

LRU算法

     最久没有使用算法&＃xff0c;即LRU算法&＃xff08;Least Recently Used algorithm&＃xff09;。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"&＃xff0c;因此&＃xff0c;实现起来比较容易。 

     核心思想&＃xff1a;如果在一段时间内长时间不访问的页面将来也不会访问

    传统实现原理&＃xff1a;

        假设 序列为 4 3 4 2 3 1 4 2

        物理块有3个 则

        首轮 4调入内存 4

        次轮 3调入内存 3 4

        之后 4调入内存 4 3

        之后 2调入内存 2 4 3

        之后 3调入内存 3 2 4

        之后 1调入内存 1 3 2&＃xff08;因为最少使用的是4&＃xff0c;所以丢弃4&＃xff09;

        之后 4调入内存 4 1 3&＃xff08;原理同上&＃xff09;

        最后 2调入内存 2 4 1

LRU算法扩展&＃xff0c;可以看我的另一篇博文&＃xff1a;

    http://my.oschina.net/manmao/blog/601698

LRU算法简单实现&＃xff1a;

https://mp.weixin.qq.com/s?__biz&＃61;MzAxNDI5NzEzNg&＃61;&＃61;&mid&＃61;2651157126&idx&＃61;1&sn&＃61;aec050aae2efc427c1397f4a7e2fde6a&chksm&＃61;8064a3d9b7132acff5614b7c9fbcb60770a52970fa4f8b76e1ab06f8ce803040f998e3f42e95&scene&＃61;0&key&＃61;1a6dc58b177dc626a128add5b7c4924b9be81733861d4c335d100d3f533c6dd072c017e31903757829134be3cbf22354&ascene&＃61;14&uin&＃61;NzkwODcyMzQx&devicetype&＃61;android-19&version&＃61;26031732&nettype&＃61;WIFI&pass_ticket&＃61;b1FAKwVG%2FaONUhFzptp9fVyQ%2BjKJN0WTZmJ10%2FqDvgH1E3rS%2BVODI%2F%2F%2FHLW%2BF%2BBc