Quick summary of CART
as found in the paper (http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf).
There are four lists: T1, T2, B1 and B2 and two list targets: p and q. The T lists hold resident pages and the B lists hold non-resident pages. The targets are the target sizes of T1 and B2 respectivly. Each page has two bits: the referenced bit and a filter bit. The filter bit distinguishes shortterm vs. longterm usage.
T1 contains both short- and longterm pages and T2 only contains longterm pages. B1 contains shortterm non-resident pages; B2 contains longterm non-resident pages.
On fault a page is checked agains B1 and B2, if present the page becomes a longterm page, otherwise a shortterm page is inserted in T1.
When the need arises to free a page we rotate T2 until it points to an unreferenced longterm page; referenced pages are moved to T1. Then we rotate T1 until it points to an unreferenced shortterm page; longterm pages are moved to T2's head, referenced shortterm pages are moved to T1's head and optinally promoted to longterm pages when T1 exceeds its target size. Then depening on T1's target size p either the T1 or the T2 tail page is reclaimed and placed on B1 or B2 resp. possibly replacing another B page which is determined by B1's size in relation to is target q.
The T1 target size p is a reflection of the number of hits in B1 vs. hits in B2; ie. its incremented on a B1 hit and decremented on a B2 hit.
The T2 target size q is a little more complicated, q almost measures the flux of pages from T2 to T1.
My intuition for the parameter 'q' is as follows. This parameter is the target size for the list B1. It is also varied throughtout the algorithm depending upon movement of pages from T1 -> T2 or T2 -> T1. On a move from T1 -> T2, q is decreased. On a move from T2 -> T1, q is increased. As you point out the trick part is the increment of q. Understanding a croner case will help a lot here. Let us assume that all T2 pages move to T1. At this point the desired size of q is exactly c. Similarly, if T1 is empty and T2 is full, then we would like to keep q again to size c. Observe that it is hits in B1 that generate new T2 pages. --- Dharmendra S Modha
[NOTE: the dynamics of T1 and T2 are such that it is possible to view them as a two-handed clock]
Adaption
- Multiple zones
In order to adapt CART to multiple zones I took advantage of the fact that the resident and non-resident lists are nicely seperated. I keep global B lists with target q and per zone T lists with target p. When B/q values are used in T/p context I scale them.
- Insert Referenced
In order to avoid that new pages are promoted to longterm on their first check I introduced PG_new, it is set when a page enters the T lists and testcleared on T1 rotation. The short- to longterm promotion is skipped when new. (More on PG_new in the CART+ section).
- Expensive Referenced Check
Batching up the reclaim part of CART took a little thought. What I ended up with is this: instead of looking for a single match to the T1 and T2 rotation condition I'd rotate a fixed quanta of pages and isolate those that match the condition; moving the rest off to their resp. places. Then from these two candidate lists I'd p-balance-pick the proper one until I had the required number of reclaimable pages or one or both of the candidate lists dried up, in which case I'd just batch-rotate them again.
- Asynchronous Page-Out
In order to avoid the infinite loop over PG_writeback pages I treat PG_writeback pages as if they were referenced (in order to rotate them as far away as possible) and break the batch-rotate when then number of encountered PG_writeback pages outnumbered the number of candidates.
CART+
CARTs weakness is it's inability to handle cyclic access patterns. I have made an attempt to solve this deficiency. This is done by adding another adaptive parameter: r, which will measure the influx of fresh pages. A fresh page is one that is not on either B1 or B2; ie. r is incremented when the faulted page is not in B otherwise it is decremented.
The reclaim path is then modified to prefer new (PG_new) longterm pages when r drops below the number of longterm pages on the T lists. The idea here is that we want to recognize the situation where we have a saturation of longterm pages and low influx of fresh pages.
This complicates the reclaim path a bit since we now have a possible third candidate list.