This is an improvement over ARC by combining ARC with Clock (second-chance) cache replacement algorithm. Like ARC, there are two LRU queues and each queue is separated from cache (\(T\)) and directory (\(T+B\)). But instead of a simple queue, the LRU are now implemented in a circular queue with a “hand” pointing to one of the items. And each item has a R-bit to flag that the item has been accessed recently.
The algorithm is as follows:
- If there is a cache hit (\(T_1+T_2\)), assert the R-bit of the item
- If there is a cache miss (not in \(T_1+T_2\)), make room to load the item into the cache
- If \(|T_1+T_2|=c\), then the cache is full. We loop until a page is moved from \(T_1\) to \(B_1\) or from \(T_2\) to \(B_2\),
as described in the following
- In every loop, if \(|T_1|>p\), and the item pointed by the “hand” in \(T_1\) has R-bit asserted, it is moved to the tail (i.e. the one behind the “hand”) position in \(T_2\) with the R-bit cleared
- Alternatively, if \(|T_1|>p\), but the item pointed by the “hand” in \(T_1\) has R-bit cleared, it is moved to the MRU position of B1 and the loop terminates
- Alternatively, if \(|T_1|\le p\), and the item pointed by the “hand” in \(T_2\) has R-bit asserted, its R-bit will be cleared and the “hand” moves forward by 1
- Alternatively, if \(|T_1|\le p\), but the item pointed by the “hand” in \(T_2\) has R-bit cleared, it is moved to the MRU position of B2 and the loop terminates
- If \(|T_1+T_2|=c\), then the cache is full. We loop until a page is moved from \(T_1\) to \(B_1\) or from \(T_2\) to \(B_2\),
as described in the following
- If \(|L_1|=c\), discard the an object from \(B_1\) or if \(|L_1+L_2|=2c\), discard an object from \(B_2\) according to the second-chance priority
- Now the cache shall have room for the new entry
- If the item is a directory miss, load the object into \(T_1\) (from \(B_1+B_2\)) with R-bit cleared.
- If the item is a directory hit but a cache miss, adjust the parameter \(p\) according to ARC and move the object to the “tail” position of \(T_2\) with its R-bit cleared
Comparing LRU, ARC and CAR:
- LRU captures recency but not frequency. ARC improves over this
- A scan, i.e. a sequence of one-time-use object reference can pollute the LRU. ARC solves the problem by a dual LRU.
- LRU requires items be moved on every access, which is expensive. The Clock algorithm gives a lightweight solution.
And therefore, CAR combines ARC and Clock and it solves all the above problems.
Bibliographic data
@inproceedings{
title = "CAR: Clock with Adaptive Replacement",
author = "Sorav Bansal and Dharmendra S. Modha",
booktitle = "Proc. 3rd USENIX Conference on File and Storage Technologies (FAST)",
pages = "187--200",
year = "2004",
address = "San Francisco CA",
}