readahead/behind algorithm

readahead/behind algorithm

[Rik van Riel]

Hi,

I've thought a bit about what the 'ideal' readahead/behind
algorithm would be and reached the following conclusion.

1. we test the presence of pages in the proximity of the
   faulting page (31 behind, 32 ahead) building a map of
   64 pages.
2. we see how many pages are already present and mapped
   in these locations:
   - 31-15 pages behind
   - 14-01 pages behind
   - 01-15 pages ahead
   - 16-32 pages ahead
3. if there are a lot of (20? 25?) pages behind and less
   than 8 pages ahead (from a previous readahead?) we read
   possibly up to the 32-page mark
4. same for read-behind (so a program can walk through it's
   address space the other way around at full speed :)
5. if there are only a very few pages present around us (only
   using the 'near' indexes) we read 7 behind and 8 ahead
6. if there are quite a lot of pages present in our vincinity,
   chances are that we've already had situation 5 so we can
   establish a sense of direction and read in 16 pages in that
   direction

Of course, we use the physical location of all these pages in
swap and ignore pages that are far away physically and cannot
efficiently be clustered with other I/O requests.

Ideally we'd also keep track of those pages (using 2 lists,
which we alternately zero to forget old requests) and test
the physical vincinity of our swap requests in order to
read in the ones that were too 'remote' previously...

This is not the most clear explanation of what I meant,
but my mind is too foggy now to make a complete explanation :)

cheers,

Rik -- the flu hits, the flu hits, the flu hits -- MORE
+-------------------------------------------------------------------+
| Linux memory management tour guide.        H.H.vanRiel@phys.uu.nl |
| Scouting Vries cubscout leader.      http://www.phys.uu.nl/~riel/ |
+-------------------------------------------------------------------+


--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: readahead/behind algorithm

[Stephen C. Tweedie]

Hi,

On Mon, 7 Dec 1998 21:17:56 +0100 (CET), Rik van Riel
<H.H.vanRiel@phys.uu.nl> said:

> Hi,
> I've thought a bit about what the 'ideal' readahead/behind
> algorithm would be and reached the following conclusion.

> 1. we test the presence of pages in the proximity of the
>    faulting page (31 behind, 32 ahead) building a map of
>    64 pages.

It will only be useful to start getting complex here if we take more
care about maintaining the logical contiguity of pages when we swap
them.  If swap gets fragmented, then doing this sort of readahead will
just use up bandwidth without giving any measurable performance gains.
It would be better thinking along those lines right now, I suspect.

--Stephen
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: readahead/behind algorithm

[Rik van Riel]

On Mon, 7 Dec 1998, Stephen C. Tweedie wrote:
> On Mon, 7 Dec 1998 21:17:56 +0100 (CET), Rik van Riel
> <H.H.vanRiel@phys.uu.nl> said:
> 
> > I've thought a bit about what the 'ideal' readahead/behind
> > algorithm would be and reached the following conclusion.
> 
> > 1. we test the presence of pages in the proximity of the
> >    faulting page (31 behind, 32 ahead) building a map of
> >    64 pages.
> 
> It will only be useful to start getting complex here if we take more
> care about maintaining the logical contiguity of pages when we swap
> them.

We will need to test 2 proximities, the one in the process'
address space (of which I was talking here) and the one in
swap space. We only read those virtual addresses that can
be scooped off of swap in one sweep and those that can be
properly clustered.

The rest we put in a new swap bitmap (actually two bitmaps,
which get cleaned&written alternately so we can forget old
requests without forgetting new ones) and we read those pages
only when they become clusterable due to other I/O requests
happening near them or when the process faults on them.

> If swap gets fragmented, then doing this sort of readahead will just
> use up bandwidth without giving any measurable performance gains. 
> It would be better thinking along those lines right now, I suspect. 

At the moment, yes. To do the stuff I wrote about we'd need to
clone about half the code from vmscan.c and pass the faulting
address to swap_in() as an extra parameter.

We probably only want this (expensive!) swapin code on machines
than run multiple large simulations and have loads of memory
but even more swap. It will be a lot of fun to write though :)

cheers,

Rik -- the flu hits, the flu hits, the flu hits -- MORE
+-------------------------------------------------------------------+
| Linux memory management tour guide.        H.H.vanRiel@phys.uu.nl |
| Scouting Vries cubscout leader.      http://www.phys.uu.nl/~riel/ |
+-------------------------------------------------------------------+

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org