PARC: A novel OS cache manager
Authors:
- 31 August 2018
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 48 (12) , 2193-2222
Abstract
Summary: To boost input‐output performance, operating systems employ a kernel‐managed caching space called the buffer cache or page cache. Given the limited size of a buffer cache, an effective cache manager is required to decide which blocks should be evicted from the cache. Previous cache managers use historical information to make replacement decisions. However, existing approaches are unable to maximize performance since they rely on limited historical information. Motivated by the limitations of existing solutions, this paper proposes a novel manager called the Pattern‐assisted Adaptive Recency Caching (PARC) manager. PARC simultaneously uses the historical information of recency, frequency, and access patterns to estimate the locality strengths of blocks and, upon a cache miss, evicts the block with the least strength. Specifically, PARC exploits the reference regularities exhibited in past input‐output behaviors to actively and rapidly adapt the recency and frequency information of blocks so as to precisely distinguish blocks with long‐ and short‐term utility. Through comprehensive simulations on a variety of traces of different access patterns, we show that PARC is robust since, except for random workloads where the performance of each cache manager is similar, PARC always outperforms existing solutions.Keywords
Funding Information
- Ministry of Science and Technology (MOST 104-2221-E-005-003-)
This publication has 27 references indexed in Scilit:
- RACE: A Robust Adaptive Caching Strategy for Buffer CacheIEEE Transactions on Computers, 2007
- Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache PerformanceIEEE Transactions on Computers, 2005
- Design, implementation, and performance evaluation of a detection-based adaptive block replacement schemeIEEE Transactions on Computers, 2002
- LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policiesIEEE Transactions on Computers, 2001
- Compiler-based I/O prefetching for out-of-core applicationsACM Transactions on Computer Systems, 2001
- Adaptive page replacement based on memory reference behavior1997
- Hipec: A System for Application-customized Virtual-memory Caching ManagementSoftware: Practice and Experience, 1997
- Implementation and performance of integrated application-controlled file caching, prefetching, and disk schedulingACM Transactions on Computer Systems, 1996
- Informed prefetching and caching1995
- Cache operations by MRU changeIEEE Transactions on Computers, 1988