I'm trying to implement the Adaptative Replacement Cache algorithm but, i'm reading in the literature, and i can't understand the algorithm. Anyone can explain me that algorithm? I see that it use two lists L1 to the frequency and L2 to the recency. But the T1, B1 and T2, B2 for the L1 and L2 lists, i can't understand.
ftp://paranoidbits.com/ebooks/Outperforming%20LRU%20with%20an%20Adaptive%20Replacement%20Cache.pdf in this paper i saw this information.
T1 and T2 hold the actual data that is being cached. T1 holds all the data (pages) that has been referenced exactly once. T2 holds pages that have been referenced 2 or more times. B1 is a ghost list which is used to remember which pages once were in the T1 cache. B2 is the same, only for the T2 cache. When you add T1 and B1 together, you get a set (called L1) of references to pages that were or currently are cached because they were referenced once. The same goes for L2, only it contains references to which pages have been referenced at least twice.
T1 and T2 share a fixed sized set of slots (each slot can hold one page), and we use B1 and B2 to decide how to share these slots among T1 and T2. This is what makes ARC adaptive - the automatic adjustment of who gets the most slots. If B1 holds multiple references to the same page, it means that we don't allow T1 to hold on to its pages long enough, and that it should be allowed more slots to counter this. The same goes for B2.
I won't try and explain the entire algorithm here, but this is at least my understanding of the ARC lists.