数据结构-页面常用置换算法

做应用做了两年多了，发现自己曾经认为最重要的是各种各样的api，各种各样的效果图，这些都算法编出来的。再后来就发现编程到最后就是属于算法的扩充。听起来好牛气的样子，不过的确是这样，后悔在大学里没有好好地学习数据结构这门课程，后来凭记忆从网上搜集了几种页面置换算法，整理记录一下。

缓存算法（页面置换算法）-FIFO、LFU、LRU

　　在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路，下面继续来探讨一下另外两种常见的Cache算法：FIFO、LFU

1. FIFO算法

　　FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。

　　在FIFO Cache设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在FIFO Cache中应该支持以下操作;

　　get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；

　　set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最早进入Cache的数据。

　　举个例子：假如Cache大小为3，访问数据序列为set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)

　　则Cache中的数据变化为：

　　(1,1)                           set(1,1)

　　(1,1) (2,2)                     set(2,2)

　　(1,1) (2,2) (3,3)               set(3,3)

　　(2,2) (3,3) (4,4)               set(4,4)

　　(2,2) (3,3) (4,4)               get(2)

　　(3,3) (4,4) (5,5)               set(5,5)

　　那么利用什么数据结构来实现呢？

　　下面提供一种实现思路：

　　利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。

2. LFU算法

　　LFU（Least Frequently Used）最近最少使用算法。它是基于 如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小的思路。

　　注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子：

　　假设缓存大小为3，数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，

　　则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1)。

　　那么LFU Cache应该支持的操作为：

　　get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；

　　set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最少访问的数据。

　　为了能够淘汰最少使用的数据，因此LFU算法最简单的一种设计思路就是利用一个数组存储数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。

　　另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。

3. LRU算法最近最少使用页面置换算法

最近最不常用调度算法总是根据一段时间内页面的访问次数开选择淘汰页面，没次淘汰访问次数最少的页面。算法实现是需要为每个页面设置计数器，记录访问次数。计数器有硬件或操作系统自动定时清零。

4.LRU和LFU的区别

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面

LFU是最近最不常用页面置换算法(Least Frequently Used),也就是首先淘汰一定时期内被访问次数最少

比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4

注意,当调页面4时会发生缺页中断

若按LRU算法,应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内,页面3只使用了一次)

可见LRU关键是看页面最后一次被使用到发生调度的时间长短,

而LFU关键是看一定时间段内页面被使用的频率!

5. 先进先出调度算法(FIFO)

先进先出调度算法根据页面进入内存的时间先后选择滔滔页面，本算法实现时需要将页面按照进入的时间先后组成一个队列，每次调度队首页面予以淘汰。他的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，他没有反映程序的局部性，因为最先调入主存的页面，很可能也是经常要使用的页面。

6. 最优替换算法 OPT

前面几种页面调度算法主要是以主存出奇中页面调度情况的历史信息为依据的，他假设将来主存出器中页面调度情况的历史信息为依据的，他假设将来主存储器中的页面调度情况与过去一段时间内主存储器的页面调度情况是相同的。显然，这种假设不总是真确的，最好的算法应该是选择将来最久不被方位的页面最为被替换的页面，这种算法命中率一定是最高的。就是最优替换算法，也实现opt算法，唯一的方法就是让程序先执行一边，记录下实际的页地址流情况，根据这个页地址流才能找出当前要被替换的页面，显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法 ，然而，这也是一种很有用的算法。实际上，经常把这种算法用来作为评价其他页面调度算法好坏的标准，在其他条件相同的情况下，哪中页面调度算法的命中率与opt相近，那么，他就是一种比较好的页面置换算法。

缺页调度次数和缺页中断率，缺页置换率计算：

缺页中断次数是缺页是发出缺页中的次数
缺页中断率=缺页中断次数/中的页面引用次数
缺页调度次数是调入新页是需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数

总结

判断一个页面调度算法好坏

一是命中率要高，二是效率高，三是算法要容易实现。

应用

虚拟存储器中，贮存页面的替换
Cache中的块替换
虚拟存储器中的快慢表中，块表的替换
虚拟存储其中，用户基地址寄存器的替换