An Adaptive Cache Management Using Dual LRU Stacks to Improve Buffer Cache Performance

摘要

Cache plays an essential role in modern computer systems to smooth the performance gap between memory and CPU. Most existing cache replacement algorithms use three stacks: recency stack, frequency stack and history stack. The balance and design of those stacks is a key to achieve high hit ratio, thus improving the buffer cache efficiency. In this paper we propose a new cache replacement algorithm, Adaptive Dual LRU, or AD-LRU for short, to efficiently utilize the buffer cache pages. Instead of using one LRU stack, we use two LRU stacks: one LRU stack LR to catch the accesses of pages with low recency, and the other LRU stack HR to catch the accesses of pages with high recency. The idea is to adaptively adjust the sizes of the history stack, recency and frequency stacks, an overall buffer cache efficiency in terms of hit ratio will be improved. Simulations results show that AD-LRU demonstrates higher hit ratio compared to existing popular algorithms such as LRU, ARC, and LIRS.