|
FAST '04 — Abstract
Pp. 187-200 of the Proceedings
CAR: Clock with Adaptive Replacement
Sorav Bansal, Stanford University; Dharmendra S. Modha, IBM Almaden Research Center
Abstract
CLOCK is a classical cache replacement policy
dating back to 1968 that was proposed as a low-complexity
approximation to LRU. On every cache hit, the policy LRU
needs to move the accessed item to the most recently used
position, at which point, to ensure consistency and correctness,
it serializes cache hits behind a single global lock. CLOCK
eliminates this lock contention, and, hence, can support high
concurrency and high throughput environments such as virtual
memory (for example, Multics, UNIX, BSD, AIX) and
databases (for example, DB2). Unfortunately, CLOCK is still
plagued by disadvantages of LRU such as disregard for
"frequency", susceptibility to scans, and low performance.
As our main contribution, we propose a simple and elegant
new algorithm, namely, CLOCK with Adaptive Replacement
(CAR), that has several advantages over CLOCK: (i) it is
scan-resistant; (ii) it is self-tuning and it adaptively and
dynamically captures the "recency" and "frequency" features
of a workload; (iii) it uses essentially the same primitives
as CLOCK, and, hence, is low-complexity and amenable to
a high-concurrency implementation; and (iv) it outperforms
CLOCK across a wide-range of cache sizes and workloads.
The algorithm CAR is inspired by the Adaptive Replacement
Cache (ARC) algorithm, and inherits virtually all advantages
of ARC including its high performance, but does not serialize
cache hits behind a single global lock. As our second contribution,
we introduce another novel algorithm, namely, CAR
with Temporal filtering (CART), that has all the advantages of
CAR, but, in addition, uses a certain temporal filter to distill
pages with long-term utility from those with only short-term
utility.
- View the full text of this paper in
PDF.
Until March 2005, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2004 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
