Window‐LRFU: a cache replacement policy subsumes the LRU and window‐LFU policies. (1st December 2015)

• Record Type: Journal Article
• Authors: Bai, Sen; Bai, Xin; Che, Xiangjiu
• Is Part Of: Concurrency and computation. Volume 28:Number 9(2016)
• Page Start: 2670
• Page End: 2684
• Publication Date: 2015-12-01
• Subjects: cache -- replacement policy -- Window‐LFU -- LRU; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3730
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Replacement algorithms have been widely used as key technologies for cache management in areas such as file systems or database management. A replacement algorithm determines which page to be evicted when the cache is full and a new page is referenced. Because replacement policies considering only recency or frequency such as LRU (Least Recently Used) and LFU (Least Frequently Used) do not perform well, replacement polices that take both recency and frequency into account have been intensively studied. As a classical replacement policy, LRFU (Least Recently/Frequently Used) policy subsumes the LRU and LFU policy. However, because LFU is not able to adapt to the change of page accessing pattern and it is hard to select a suitable λ for each certain trace, LRFU cannot always guarantee a good performance. In this paper, we propose a Window‐LRFU policy, to subsume the LRU and Window‐LFU policies. Experimental results show that the Window‐LRFU policy outperforms LRFU and has at least competitive performance than other classical algorithms. Copyright © 2015 John Wiley & Sons, Ltd.