详细分解十大替换算法及置换算法

作者：课课家教育来源： http://www.kokojia.com点击数：3589发布时间： 2017-04-03 08:29:19

　　缓存中容量是有限的，当要查找的数据库不在缓存中时，我们要用新数据替换掉，部分原有得数据，有很多种替换策略，lru就是最近最少使用的被替换，我们想要将来被使用的数据保留下来，但我们不知道将来会使用那些数据，就按照最近使用数据近似将来也会使用的数据。现在有很多的算法，今天呢，就让课课家带领你一起来了解常用的算法算法”。认真看文章哦

详细分解十大替换算法及置换算法_操作系统_网络工程师_替换算法_置换算法_课课家

1.SIZE

替换size最大的对象。这一策略通过淘汰一个大对象而不是多个小对象来提高命中率。不过，可能有些进入缓存的小对象永远不会再被访问。SIZE策略没有提供淘汰这类对象的机制，也会导致“缓存污染”。

2.LRU-Threshold

不缓存超过某一size的对象，其它与LRU相同。

3.Log(Size) + LRU

替换size最大的对象，当size相同时，按LRU进行替换

4.Hyper-G

LFU的改进版，同时考虑上次访问时间和对象size

5.Lowest-Latency-First

替换下载时间最少的文档。显然它的目标是最小化平均延迟。

6.Hybrid

Hybrid有另外一个目标，减少平均延迟。对缓存中的每个文档都会计算一个保留效用（utility of retaining）。保留效用最低的对象会被替换掉。位于服务器s的文档f的效用函数定义如下：

　Cs: 与服务器s的连接时间

bs: 服务器s的带宽

frf: f的使用频率

sizef: f的size，单位字节

　　K1和K2是常量，Cs和bs是根据最近从服务器s获取文档的时间进行估计的。
　　7.Lowest Relative Value(LRV)

LRV也是基于计算缓存中文档的保留效用。然后替换保留效用最低的文档。有点复杂，实际应用价值不大。

　　[ASAWF95, WASAF96]所做的性能研究表明在命中率方面，SIZE优于LFU， LRU-Threshold, Log(Size) + LRU, Hyper-G以及Pitkow/Recker。
　　[WASAF96]还显示大多数情况下，SIZE要优于LRU。然而，[LRV97]的研究表明在字节命中率方面LRU要优于SIZE。
　　大多数情况下，LRU都要比LFU好[Cao-Irani97]。在极少情况下，LFU表现比LRU好。
　　在最小化延迟方面，[WA97]表明Hybrid表现优于Lowest-Latency-First。
　　[LRV97]的性能研究表明，无论在命中率还是字节命中率方面，LRV表现都比LRU和SIZE好。
　　这缩小了我们的选择范围，似乎我们只需要考虑这些策略：LRU, SIZE, Hybrid, LRV。Hybrid和LRV涉及到大量的参数，理论价值大于实际应用。
　　[Cao-Irani97]所做的性能研究表明，Greedy-Dual-Size算法是目前最好的，在不同的维度都优于LRU, SIZE, Hybrid和LRV。
　　8.Pitkow/Recker
　　替换最近最少使用的对象，除非所有对象都是今天访问过的。如果是这样，则替换掉最大的对象。这一策略试图符合每日访问web网页的特定模式。这一策略也被建议在每天结束是运行，以释放被“旧的”，最近最少使用的对象占用的空间。
　　9.Least-Recently-Used(LRU) - 最近最少使用
　　替换掉最近被请求最少的文档。这一传统策略在实际中应用最广。在CPU缓存淘汰和虚拟内存系统中效果很好。然而直接应用与代理缓存效果欠佳，因为Web访问的时间局部性常常变化很大。
　　10.Least-Frequently-Used(LFU) - 最不经常使用
　　替换掉访问次数最少的。这一策略意图保留最常用的、最流行的对象，替换掉很少使用的那些。然而，有的文档可能有很高的使用频率，但之后再也不会用到。传统的LFU策略没有提供任何移除这类文件的机制，因此会导致“缓存污染(Cache Pollution)”，即一个先前流行的缓存对象会在缓存中驻留很长时间，这样，就阻碍了新进来可能会流行的对象对它的替代。
　　11.最佳置换算法定义
　　最佳(Optimal)置换算法是指，其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。
　　算法过程
　　现举例说明如下：
　　假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

　　进程运行时，先将7，0，1 三个页面装入内存。以后，当进程要访问页面2 时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7 予以淘汰。这是因为页面0 将作为第5 个被访问的页面，页面1 是第14 个被访问的页面，而页面7 则要在第18 次页面访问时才需调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1 被淘汰；因为，它在现有的1，2，0 三个页面中，将是以后最晚才被访问的。