Clock-Pro

As read in the [http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs05-3.html paper] clock-pro keeps it's non-resident pages on the same clock as it does it's resident pages. This conflicts with the ["PageReplacementRequirements"]. Hence we have to modify the algorithm somewhat in order to get it to work on linux.

What I did was to take the non-resident pages off the clock and put them in a second clock that I superimposed on the first. Since normaly the hot hand removes non-resident pages from the clock I bound the movement of the hot hand to the non-resident hand, so that when the hot hand has made a full circle, the non-resident hand will also have made one. Whereby the non-resident hand removes pages from the non-resident list. The movement of the test hand is replaced by limiting the size of the non-resident clock to the number of resident pages.

1 List, 2 Hands

This implementation creates a two handed clock from two lists. The lists are laid head to tail to form a two handed clock. When one hand gains on the other the lists are simply swapped.

Use-Once

The use once logic is captured by essentially moving the non-resident pages state to the resident page; ie. insert as cold with test bit set depending on the presence of the faulted page in the non-resident list. The next reference check (which we know will come) will then promote them to the normal insertion state (cold with test-period, or hot).

Benchmark results

As of 30-11-2005:

times listed are wall-time, on a p3-500 with mem=128M and a single 7200RPM ata disk.

Code

The code is available [http://programming.kicks-ass.net/kernel-patches/clockpro-2/ here]

TODO

• redo the non-resident code; currently I hacked up the CART non-resident code, which is a bit of overkill for this algorithm, revert back to something closer to Rik's original code;
• benchmark;

CategoryAdvancedPageReplacement