Clock-Pro
As read in the [http://www.cs.wm.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 now 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.
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;
validate the logic around zone->nr_r, the target for the number of cold pages, currently it's rather volatile under a cyclic access pattern, while the paper states it should handle it;
- did I mention benchmark already?