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 $|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",
}