Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

ARC

ARC stands for ‘adaptive replacement cache’, and is built upon the LRU (least recently used) page replacement scheme. You can read the Wikipedia page Wikipedia page here.

Colors

Each square in the visualization represents a page. The color of the squares represent the state of the page in ARC.

T1
T2
B1
B2
  • A red square is a page in the T1 list
  • A blue square is a page in the T2 list
  • A light red square is a page in the B1 ghost page list
  • A light blue square is a page in the B2 ghost page list
  • A gray square is a page not in any list

Pages in a ghost page list have the content evicted, and only the address of page is retained in the ghost page list.

Layouts

ARC has five layouts.

  • Flat arranges the pages linearly. Pages are inserted in the middle at the MRU positions. The MRU positions are indicated by a downwards-pointing triangle. Pages flow towards the LRU positions on either ends of the list.
    • shows visually how ARC limits the pages it keeps track of to 2c.
    • most similar to the view presented in the original paper.
  • Blocks groups the pages into three blocks. B1 occupies the left block, B2 occupies the right block. The center block is combination of T1 and T2
    • optimized for displaying a large amount of pages.
    • emphasizes |T1| + |T2| = c and movements of pages between T-lists and ghost B-lists.
    • long arrows that appear hint at the flow of pages
  • Two List (T-B) groups T1 and T2 together in one line at the top. B1 and B2 are grouped together in a line at the bottom. The pages flow in from the middle top, then to the ends of the list, and finally come back together to be evicted around the middle of the bottom line.
    • shows visually the property |T1| + |T2| = |B1| + |B2|
  • Two List (1-2) groups B1 and T1 together in one line at the top. B2 and T2 are grouped together in a line at the bottom. Pages flow in from the right and are evicted to the left.
    • emphasizes that ARC uses two queues, and the ghost B-lists are an extension of T-lists.
  • Four List shows the four lists that needs to be tracked to implement ARC.
    • resembles the view of the lists that programmers will likely see when debugging an implementation of ARC.

Implementation

This website implements ARC as described in Megiddo and Modha, 2003. See the paper for the algorithm logic.

Cases

PageRVis differentiates between 9 main cases and 2 replacement cases in the “last event” section.

Main cases

  1. Case 1 (hit) in T1
  2. Case 1 (hit) in T2
  3. Case 2 (B1 hit)1
  4. Case 3 (B2 hit)1
  5. Case 4a (miss with L1 full & |T1| < c)
  6. Case 4a (miss with L1 full & |T1| = c)
  7. Case 4b (miss with L1 < |c| & |all lists| = 2c)
  8. Case 4b (miss with L1 < |c| & c ≤ |all lists| < 2c)
  9. Case 4b (miss with L1 < |c| & |all lists| < c)

Replacement cases

  1. Replace: move T1 to B1
  2. Replace: move T2 to B2

Cases not differentiated

  • p increases and decreases in case 2 and 3, but the “last event” section does not indicate how much p changes by (Case: 1 / more than 1)
  • The replace function has a complex boolean expression to determine whether it should replace from T1 or T2, but the visualizer does not differentiate between which combination of booleans caused the decision to replace from each list.

  1. A hit in a ghost list counts as a miss, since the contents of ghost pages are not loaded. ↩ ↩2