Status of Linux CART implementation by Rahul Iyer
I'd like to say that as of now, CART on Linux works... almost. There is some odd case where some pages get pinned in memory and cannot be freed, because of which we OOM every now and again if we malloc() enough. I presume this is a flags issue.
Also, I need to fix a few other things: 1. I'm kmalloc()'ing the memory for the non resident nodes. This is proving to be painful for speed. I'm thinking of using the slab allocator for these purposes. 2. Currently, there is a non resident node "list". Lookups of this will get painful, so maybe a hash table is in order.
All in all, if i'm not mistaken, on every page fault CART involves an overhead larger than the current system because of the requirement to update the non resident list. So, I guess, this will be faster only if the difference in the number of page faults that a workload generates on CART as opposed to the current scheme can mask the extra overhead. Also, i guess, that lock contention on the nonresident list will also be an issue on multiprocessor machines.
I plan to release the code by Thursday or Friday (worst case by the weekend) without fix #2. I have to fix the "glued" pages issue and do some code cleanup. Hoping for the best
CART Patch v2
I have implemented a second version of a zoned CART with hashtables for speeding up lookup. Also, I have used the short term/long term lists for the active list only. There is a separate inactive list which works in the standard way. Both patches are available at http://www.cs.cmu.edu/~412/projects/CART/
CART Homepage Moves
Unfortunately, due to administrative reasons, the CART homepage had to move. The page is now here. My apologies to those who were inconvenienced by the broken links.
Also see AdvancedPageReplacement and CategoryAdvancedPageReplacement