PARC: A novel OS cache manager. (31st August 2018)

• Record Type: Journal Article
• Authors: Chang, Hsung‐Pin; Chiang, Cheng‐Pang
• Is Part Of: Software, practice & experience. Volume 48:Number 12(2018)
• Page Start: 2193
• Page End: 2222
• Publication Date: 2018-08-31
• Subjects: buffer cache -- cache manager -- operating systems -- page cache -- replacement algorithms; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2633
• Languages: English
• ISSNs: 0038-0644

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.