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 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:
mdb-2.6.15-rc2-stock: 3:29:27 mdb-2.6.15-rc2-mlock: 3:12:26 mdb-2.6.15-rc2-clockpro: 3:07:55
times listed are walltime, 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;
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?
fix the SwapTokenTuning; enabling somehow makes the kernel go round 'n round