[PATCH 0/7] CART - an advanced page replacement policy

From: Peter Zijlstra (a.p.zijlstra_at_chello.nl)
Date: 09/29/05

  • Next message: Peter Zijlstra: "[PATCH 1/7] CART - an advanced page replacement policy" 
    Date:	Thu, 29 Sep 2005 20:08:45 +0200
To: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>

    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/

  • Next message: Peter Zijlstra: "[PATCH 1/7] CART - an advanced page replacement policy"

    Relevant Pages

    • Re: Sorted: Mains hum on budget turntable...
      ... shorts don't induce hum - they make the signal stop. ... Nothing to do with Lordy's symptoms, ... Pretty obvous it's the cart and/or the wires to the cart, ...
      (uk.rec.audio)
    • [PATCH 32/34] mm: cart-cart.patch
      ... This patch contains a Page Replacement Algorithm based on CART ... * B lists, keeping T lists per zone while having global B lists. ...
      (Linux-Kernel)