你的位置:首页 > Java教程

[Java教程]缓存算法之belady现象


前言

  在使用FIFO算法作为缺页置换算法时,分配的缺页增多,但缺页率反而提高,这样的异常现象称为belady Anomaly

  虽然这种现象说明的场景是缺页置换,但在运用FIFO算法作为缓存算法时,同样也是会遇到,增加缓存容量,但缓存命中率也会下降的情况。这也是我在学习缓存算法时遇到的概念,虽总结归纳之。

 

一、举例

  假设我们有字符串"dcbadcedcbae",页面置换算法采用FIFO算法,现在有两个内存,一个是3页,一个是4页。结果如下

  

  由图可以清楚的看到,前者缺页数是9,而增加后的缺页数反而是10.

 

二、分析

  让我们仔细看看在每个时刻在内存的页数。比如在时刻3,3页内存的页数是 a、c、b, 4页内存的页数是d、c、b、a,3页内存是4页内存的子集,所以此时如果3不缺页,4肯定不缺页。

  但是,比如在时刻6,3页内存为e、d、c,4页内存为e、c、b、a,3页内存不是4页内存的子集,那就意味着,4出现缺页时,3反而不一定出现缺页。时刻7和时刻10是同样的道理。

 

三、结论

  如果内存中页数更小的集合是内存页数更大的集合的子集,这个算法被称为stack algorithm。可以证明stack algorithm(如LRU)不会出现belady现象,FIFO会出现。

 

四、参考文献

1、Belady’s Anomaly