== 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 ---- CategoryAdvancedPageReplacement