Messages in this thread | | | Date | Thu, 29 Sep 2005 20:08:45 +0200 | From | Peter Zijlstra <> | Subject | [PATCH 0/7] CART - an advanced page replacement policy |
| |
Multiple memory zone CART implementation for Linux. An advanced page replacement policy.
http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf (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: B1_j, B2_j.
and global values: |B1|, |B2|
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/7] cart-nonresident.patch [3/7] cart-cart.patch [6/7] cart-use-once.patch [7/7] cart-use-cart.patch
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:
[5/7] cart-cart-r.patch
And some debugging /proc stats for both the nonresident and cart code:
[2/7] cart-nonresident-stats.patch [4/7] cart-cart-stats.patch
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.
Kind regards,
Peter Zijlstra - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |