Heard about the 2Q algorithm?

Heard about the 2Q algorithm?

[linux]

That's a page-aging algorithm that claims better than LRU performance.

There are two tunable knobs.

You divide memory into two sections: a FIFO section and an LRU section.
Pages first loaded go into the FIFO section.  The size of this section is
one of the knobs.

Somewhere in the middle of the LRU section (exactly where is the second knob),
we start looking for additional accesses to the page.  If we get any, it
goes into the LRU section.  If not, it eventually gets pushed out of the
FIFO section.

A third knob that's available is to extend the FIFO queue "beyond memory"
into backing store.  Pages that have been pushed out but get referenced
can go straight into the LRU pool rather than taking another pass through
the FIFO.


The idea is that the FIFO absorbs sequential scans and filters out the
initial burst of accesses.  Only if access to the page is *prolonged*
do we consider it for longer-term cacheing.


I haven't implemented it, but the idea is fairly straightforward and makes
sense, and has a reasonable but not excessive number of tuning knobs to
play with.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Heard about the 2Q algorithm?

[Stephen C. Tweedie]

Hi,

On Thu, Jun 08, 2000 at 05:56:32PM -0000, linux@horizon.com wrote:
> 
> 
> The idea is that the FIFO absorbs sequential scans and filters out the
> initial burst of accesses.  Only if access to the page is *prolonged*
> do we consider it for longer-term cacheing.

Page aging does that.  The initial age of a page will be fairly low,
relative to pages which are constantly being accessed, and so will 
be evicted from the cache before they can accumulate a high age if we
have a sequential access pattern.

--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/