|| ||Peter Zijlstra <email@example.com>|
|| ||Linux Kernel Mailing List <firstname.lastname@example.org>|
|| ||[PATCH 0/7] CART - an advanced page replacement policy|
|| ||Thu, 29 Sep 2005 20:08:45 +0200|
Multiple memory zone CART implementation for Linux.
An advanced page replacement policy.
(IBM does hold patent rights to the base algorithm ARC)
My ideas are based on the initial cart patch by Rahul Iyer and the
non-resident code of Rik van Riel.
For a zoned page replacement algorithm we have per zone resident list(s)
and global non-resident list(s). CART specific we would have a T1_i and
T2_i, where 0 <= i <= nr_zones, and global B1 and B2 lists.
Because B1 and B2 are variable size and the B1_i target size q_i is zone
specific we need some tricks. However since |B1| + |B2| = c we could get
away with a single hash_table of c entries if we can manage to balance
the entries within.
Let us denote the buckets with the subscript j: |B1_j| + |B2_j| = c_j.
We need to balance the per zone values:
T1_i, T2_i, |T1_i|, |T2_i|
p_i, Ns_i, Nl_i
|B1_i|, |B2_i|, q_i
against the per bucket values:
and global values:
This can be done with two simple modifications to the algorithm:
- explicitly keep |B1_i| and |B2_i| - needed for the p,q targets;
rebalance with the global |B1|, |B2| before a batch replace.
- merge the history replacement (lines 6-10) in the replace (lines
36-40) code so that: adding the new MRU page and removing the old LRU
page becomes one action.
This will keep:
|B1_j| |B1| |B1_i|
-------- ~ ------ ~ --------
|B2_j| |B2| |B2_i|
I implemented my ideas in the following 4 patches:
1. contains the hashed nonresident page management
3. contains the CART implementation proper
6. removes the current use-once logic
7. replace the current page replacement logic with cart
I also improved upon CART in the following patch:
And some debugging /proc stats for both the nonresident and cart code:
The code seems stable on my SMP box (thanks to the wonderfull lock debugging
found in the -rt tree) hence this first post outside of linux-mm.
All feedback, comments and test results are welcome. I hope for inclusion in
-mm and if blessed in -linus one day.