Analyzing anomalous behavior of least recently frequently used (LRFU) page replacement algorithm

Abstract

In most of the page replacement algorithms, number of page faults decreases as the memory size increases. But in some algorithms it is just opposite i.e. increasing in memory size leads to increase in number of page faults. This unexpected result is known as anomaly. LRFU page replacement algorithm also showed anomalous behavior some times. This study successfully identified reason behind the anomalous behavior of LRFU and adopted the algorithm so that anomalous behavior had avoided.

In this dissertation a sample workload had listed where LRFU shows anomalous behavior. Besides this, experiment is done with LRFU using real memory traces such as cs, 2_pools, sprite and multi to identify anomalous behavior and showed that LRFU shows an anomalous behavior with real memory traces also. And, adaptation is made to existing LRFU so that an anomalous behavior can be avoided. Finally, the dissertation compares LRFU and Adapted LRFU with real memory traces cpp, 2_pools, sprite and multi and showed that LRFU and Adapted LRFU had comparative performance. Further, it is also showed that Adapted LRFU shows better performance with strong locality of workload such as sprite.

Keywords: Cache memory, Virtual memory, Anomalous behavior, LRU, LFU, LRFU, Adapted LRFU.