An idea for prefetching swapped memory...

An idea for prefetching swapped memory...

[Thomas Schlichter]

[-- Attachment #1: signed data --]
[-- Type: text/plain, Size: 1535 bytes --]

Hello,

some days ago some friends and me argued about a feature which seems not to be 
included in current OSs but could improve useability mainly for desktop 
computers.

The idea was about prefetching swapped out pages when some memory is free, the 
CPU is idle and the I/O load is low.

So this should not 'cost' much but behave better on following situation:
(I think there are even more such situations, this one should just be an 
example)

One is surfing the internet and having some browser windows opened. Now, 
without closing the browser windows, he is playing some game which needs 
pretty much memory so the browsers memory is getting swapped out. After 
finishing gaming he's going to make some coffee and then surfing the internet 
again.
But even if the computer was IDLE for a time and, as the game was closed 
again, some memory is really FREE, the pages for the browser are swapped in 
just when they are needed and not in advance.

With this feature there should be no performance decrease because only free 
resources would be used, and if pages were swapped in but not be used, they 
stay not dirty and so have not to be written to disk when they are swapped 
out again. But the improvements should be obvious if simply the last swaped 
out pages are swapped in again...

If somebody could give me a hint how to implement this I would try it. I hope 
it will not be very difficult... ;-)

Thank you for reading and perhaps thinking about it...

Best regards
   Thomas Schlichter

[-- Attachment #2: signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: An idea for prefetching swapped memory...

[Con Kolivas]

On Mon, 7 Apr 2003 18:26, Thomas Schlichter wrote:
> Hello,
>
> some days ago some friends and me argued about a feature which seems not to
> be included in current OSs but could improve useability mainly for desktop
> computers.
>
> The idea was about prefetching swapped out pages when some memory is free,
> the CPU is idle and the I/O load is low.
>
> So this should not 'cost' much but behave better on following situation:
> (I think there are even more such situations, this one should just be an
> example)
>
> One is surfing the internet and having some browser windows opened. Now,
> without closing the browser windows, he is playing some game which needs
> pretty much memory so the browsers memory is getting swapped out. After
> finishing gaming he's going to make some coffee and then surfing the
> internet again.
> But even if the computer was IDLE for a time and, as the game was closed
> again, some memory is really FREE, the pages for the browser are swapped in
> just when they are needed and not in advance.
>
> With this feature there should be no performance decrease because only free
> resources would be used, and if pages were swapped in but not be used, they
> stay not dirty and so have not to be written to disk when they are swapped
> out again. But the improvements should be obvious if simply the last swaped
> out pages are swapped in again...

This has been argued before. Why would the last swapped out pages be the best 
to swap in? The vm subsystem has (somehow) decided they're the least likely 
to be used again so why swap them in? Alternatively how would it know which 
to swap in instead?

Con

Re: An idea for prefetching swapped memory...

[Thomas Schlichter]

Quoting Con Kolivas <kernel@kolivas.org>:

> On Mon, 7 Apr 2003 18:26, Thomas Schlichter wrote:
> > Hello,
> >
> > some days ago some friends and me argued about a feature which seems not
> to
> > be included in current OSs but could improve useability mainly for
> desktop
> > computers.
> >
> > The idea was about prefetching swapped out pages when some memory is
> free,
> > the CPU is idle and the I/O load is low.
> >
> > So this should not 'cost' much but behave better on following situation:
> > (I think there are even more such situations, this one should just be an
> > example)
> >
> > One is surfing the internet and having some browser windows opened. Now,
> > without closing the browser windows, he is playing some game which needs
> > pretty much memory so the browsers memory is getting swapped out. After
> > finishing gaming he's going to make some coffee and then surfing the
> > internet again.
> > But even if the computer was IDLE for a time and, as the game was closed
> > again, some memory is really FREE, the pages for the browser are swapped
> in
> > just when they are needed and not in advance.
> >
> > With this feature there should be no performance decrease because only
> free
> > resources would be used, and if pages were swapped in but not be used,
> they
> > stay not dirty and so have not to be written to disk when they are
> swapped
> > out again. But the improvements should be obvious if simply the last
> swaped
> > out pages are swapped in again...
> 
> This has been argued before. Why would the last swapped out pages be the best
> 
> to swap in? The vm subsystem has (somehow) decided they're the least likely
> 
> to be used again so why swap them in? Alternatively how would it know which
> 
> to swap in instead?
> 
> Con
> 

What I wanted to say is that if there is free memory it should be filled with
the pages that were in use before the memory got rare. And these are the pages
swapped out last. The other swapped out pages are swapped out even longer and so
will likely not be used in the near future... (That's what the LRU algorithm
says...)

  Thomas

Re: An idea for prefetching swapped memory...

[Måns Rullgård]

Thomas Schlichter <schlicht@rumms.uni-mannheim.de> writes:

> > This has been argued before. Why would the last swapped out pages
> > be the best to swap in? The vm subsystem has (somehow) decided
> > they're the least likely to be used again so why swap them in?
> > Alternatively how would it know which to swap in instead?  Con
> 
> What I wanted to say is that if there is free memory it should be
> filled with the pages that were in use before the memory got
> rare. And these are the pages swapped out last. The other swapped
> out pages are swapped out even longer and so will likely not be used
> in the near future... (That's what the LRU algorithm says...)

Would it be possible to track the most recently used swapped out page?
This would possibly be a good candidate for speculative loading.

-- 
Måns Rullgård
mru@users.sf.net

Re: An idea for prefetching swapped memory...

[Christophe Saout]

Am Mon, 2003-04-07 um 12.21 schrieb Con Kolivas:

> > With this feature there should be no performance decrease because only free
> > resources would be used, and if pages were swapped in but not be used, they
> > stay not dirty and so have not to be written to disk when they are swapped
> > out again. But the improvements should be obvious if simply the last swaped
> > out pages are swapped in again...
> 
> This has been argued before. Why would the last swapped out pages be the best 
> to swap in? The vm subsystem has (somehow) decided they're the least likely 
> to be used again so why swap them in?

Are you sure this is working? When I'm watching a video ofer NFS on my
machine which is idle (just X and mplayer, gnome in background, 256 MB
of memory, 512 swap), after 30 minutes or so, the playback starts to
jump. The cpu usage is below 10%, and it even does this when both X and
mplayer are renice to -19 (!). So the VM swapped everything out and
after 30 minutes it starts to swap out X oder mplayer itself, which is
immediately swapped back in but the video jumps... :-(

-- 
Christophe Saout <christophe@saout.de>

Re: An idea for prefetching swapped memory...

[Måns Rullgård]

Christophe Saout <christophe@saout.de> writes:

> > > With this feature there should be no performance decrease
> > > because only free resources would be used, and if pages were
> > > swapped in but not be used, they stay not dirty and so have not
> > > to be written to disk when they are swapped out again. But the
> > > improvements should be obvious if simply the last swaped out
> > > pages are swapped in again...
> > 
> > This has been argued before. Why would the last swapped out pages
> > be the best to swap in? The vm subsystem has (somehow) decided
> > they're the least likely to be used again so why swap them in?
> 
> Are you sure this is working? When I'm watching a video ofer NFS on
> my machine which is idle (just X and mplayer, gnome in background,
> 256 MB of memory, 512 swap), after 30 minutes or so, the playback
> starts to jump. The cpu usage is below 10%, and it even does this
> when both X and mplayer are renice to -19 (!). So the VM swapped
> everything out and after 30 minutes it starts to swap out X oder
> mplayer itself, which is immediately swapped back in but the video
> jumps... :-(

How much of your memory is in use?  Are you sure there isn't a memory
leak somewhere in mplayer?

-- 
Måns Rullgård
mru@users.sf.net

Re: An idea for prefetching swapped memory...

[Jörn Engel]

On Mon, 7 April 2003 13:48:17 +0200, Måns Rullgård wrote:
> Christophe Saout <christophe@saout.de> writes:
> 
> > Are you sure this is working? When I'm watching a video ofer NFS on
> > my machine which is idle (just X and mplayer, gnome in background,
> > 256 MB of memory, 512 swap), after 30 minutes or so, the playback
> > starts to jump. The cpu usage is below 10%, and it even does this
> > when both X and mplayer are renice to -19 (!). So the VM swapped
> > everything out and after 30 minutes it starts to swap out X oder
> > mplayer itself, which is immediately swapped back in but the video
> > jumps... :-(
> 
> How much of your memory is in use?  Are you sure there isn't a memory
> leak somewhere in mplayer?

s/mplayer/X11/

The behaviour on my noteboot (512MB, no swap) is that X keeps grabbing
more memory until either I or OOM take measures.
The interesting part about it is that Mozilla and gcfclient seem to
cause the memory leak - X frees up to 400MB when one of those is
closed - but according to top, X owns that memory.

Anyway, I am quite sure that this is not a kernel problem, so please
take lkml out of any replies. :)

Jörn

-- 
"Translations are and will always be problematic. They inflict violence 
upon two languages." (translation from German)

Re: An idea for prefetching swapped memory...

[David Zaffiro]

> The idea was about prefetching swapped out pages when some memory is free, the 
> CPU is idle and the I/O load is low.
> 
> So this should not 'cost' much but behave better on following situation:
> (I think there are even more such situations, this one should just be an 
> example)

Wouldn't it cost almost twice as much when the user requests a different task, instead of the just 
swaped-in "last swaped-out task(s)"?!

Instead of loading this directly into a free portion of phys. memory, the 
just-swapped-in-ex-swapped-out task(s) would need to be swapped-out *again* in favour of the 
to-be-swaped-in task...

Or am I wrong here?

Re: An idea for prefetching swapped memory...

[Jörn Engel]

On Mon, 7 April 2003 14:32:26 +0200, David Zaffiro wrote:
> 
> >The idea was about prefetching swapped out pages when some memory is free, 
> >the CPU is idle and the I/O load is low.
> >
> >So this should not 'cost' much but behave better on following situation:
> >(I think there are even more such situations, this one should just be an 
> >example)
> 
> Wouldn't it cost almost twice as much when the user requests a different 
> task, instead of the just swaped-in "last swaped-out task(s)"?!
> 
> Instead of loading this directly into a free portion of phys. memory, the 
> just-swapped-in-ex-swapped-out task(s) would need to be swapped-out *again* 
> in favour of the to-be-swaped-in task...
> 
> Or am I wrong here?

Partially. If done right, the swapout would simply free those pages.
The information is already on the disk and unchanged, after all.

Jörn

-- 
If you're willing to restrict the flexibility of your approach,
you can almost always do something better.
-- John Carmack

Re: An idea for prefetching swapped memory...

[Christophe Saout]

Am Mon, 2003-04-07 um 14.19 schrieb Jörn Engel:

> On Mon, 7 April 2003 13:48:17 +0200, Måns Rullgård wrote:
> > Christophe Saout <christophe@saout.de> writes:
> > 
> > > Are you sure this is working? When I'm watching a video ofer NFS on
> > > my machine which is idle (just X and mplayer, gnome in background,
> > > 256 MB of memory, 512 swap), after 30 minutes or so, the playback
> > > starts to jump. The cpu usage is below 10%, and it even does this
> > > when both X and mplayer are renice to -19 (!). So the VM swapped
> > > everything out and after 30 minutes it starts to swap out X oder
> > > mplayer itself, which is immediately swapped back in but the video
> > > jumps... :-(
> > 
> > How much of your memory is in use?  Are you sure there isn't a memory
> > leak somewhere in mplayer?
>
> Anyway, I am quite sure that this is not a kernel problem, so please
> take lkml out of any replies. :)

I'm sorry, I think Måns is right, when the video started to jump,
mplayer took about 60 percent of the memory... in this case I can't
blame the VM. I'm not seeing any reports of memory leaks on its user
list, but my mileage may vary. ;-)

-- 
Christophe Saout <christophe@saout.de>

Re: An idea for prefetching swapped memory...

[Thomas Schlichter]

Quoting Måns Rullgård <mru@users.sourceforge.net>:

> Thomas Schlichter <schlicht@rumms.uni-mannheim.de> writes:
> > What I wanted to say is that if there is free memory it should be
> > filled with the pages that were in use before the memory got
> > rare. And these are the pages swapped out last. The other swapped
> > out pages are swapped out even longer and so will likely not be used
> > in the near future... (That's what the LRU algorithm says...)
> 
> Would it be possible to track the most recently used swapped out page?
> This would possibly be a good candidate for speculative loading.

Well, I think the 'more recently used swapped out' order relation is equivalent
to the 'later swapped out' order relation if the kswapd uses the LRU algorithm.
(if it does not, it has its reasons and we should respect them by simply using
the 'later swapped out' order...)

But I am not familiar with the linux swapping management so I don't know if it
tracks this order in any structure. Perhaps there is a kind of 'last used
timestamp' for each page and so for the swapped pages, too, wich could be used
for my purpose. But as I sayed, I don't know...

I hope there is anybody out there who can help me with this question...

Thanks 
   Thomas

Re: An idea for prefetching swapped memory...

[Helge Hafting]

Thomas Schlichter wrote:

> What I wanted to say is that if there is free memory it should be filled with
> the pages that were in use before the memory got rare. And these are the pages
> swapped out last. 

Not necessarily.  Memory isn't merely used to hold swappable stuff, it also
caches files.  Consider a small but io-intensive program.  The stuff
you want isn't necessarily the last swap (perhaps there
even isn't anything swapped out) , it might be the last thing
dropped from cache instead.

And we can often predict better than "the last thing swapped/flushed"
A bunch of free memory appearing could usually be better used for
extra read-ahead, wether it is read-ahead of files/directories/bitmaps
being accessed, or executable code faulted in from executables or
swap devices.

> The other swapped out pages are swapped out even longer and so
> will likely not be used in the near future... (That's what the LRU algorithm
> says...)


"What we're going to need soon" is the best.  It isn't always predictable,
but sometimes.  "The block following the last we read from some 
file/fs-structure"
is often a good one though.

Helge Hafting

Re: An idea for prefetching swapped memory...

[Chris Friesen]

Helge Hafting wrote:
> Thomas Schlichter wrote:
> 
>> What I wanted to say is that if there is free memory it should be 
>> filled with
>> the pages that were in use before the memory got rare. And these are 
>> the pages
>> swapped out last. 

> "What we're going to need soon" is the best.  It isn't always predictable,
> but sometimes.  "The block following the last we read from some 
> file/fs-structure"
> is often a good one though.

With the current setup though, the memory is wasted.  It makes sense that we 
should fill the memory up with *something* that is likely to be useful.

If I have mozilla open, start a kernel compile, and then come back half an hour 
later, I would like to see the mozilla pages speculatively loaded back into memory.

Since the system is otherwise idle, it doesn't cost anything to do this.  I 
think its obvious that it is beneficial to swap in something, the only trick is 
getting a decent heuristic as to what it should be.

Chris



-- 
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: An idea for prefetching swapped memory...

[Jörn Engel]

On Mon, 7 April 2003 10:19:25 -0400, Chris Friesen wrote:
> 
> With the current setup though, the memory is wasted.  It makes sense that 
> we should fill the memory up with *something* that is likely to be useful.
> 
> If I have mozilla open, start a kernel compile, and then come back half an 
> hour later, I would like to see the mozilla pages speculatively loaded back 
> into memory.
> 
> Since the system is otherwise idle, it doesn't cost anything to do this.

In the scenario above, it costs you a lot. The memory is completely
used, else mozilla wouldn't get swapped out. If you swap it back in
and get rid of fs cache, the next kernel (compile|grep|whatever) will
be slower.

And even in the original scenario, it will be expensive, depending on
your machine. On a notebook, it costs you battery power, which is a
limited resource, *for sure*. You *may* save user time, which *may* be
a limited resource, but not always.

But sure, it is a fun project to hack on, just go ahead and show the
numbers. :)

> I think its obvious that it is beneficial to swap in something, the only 
> trick is getting a decent heuristic as to what it should be.

And when it should be done. ;)

Jörn

-- 
There's nothing better for promoting creativity in a medium than
making an audience feel "Hmm ­ I could do better than that!"
-- Douglas Adams in a slashdot interview

Re: An idea for prefetching swapped memory...

[Magnus Danielson]

From: Con Kolivas <kernel@kolivas.org>
Subject: Re: An idea for prefetching swapped memory...
Date: Mon, 7 Apr 2003 20:21:16 +1000

> This has been argued before. Why would the last swapped out pages be the best 
> to swap in? The vm subsystem has (somehow) decided they're the least likely 
> to be used again so why swap them in? Alternatively how would it know which 
> to swap in instead?

I have been fooling around with similar thoughts, i.e. prefetching of swapped
out pages, but under a different condition.

Consider that you have a system plauged by a set of fat (i.e. having a large
memory footprint) batch-running processes such that when they are running they
get swapped in (traditional deferred swapp-in on page-misses) and other
processes gets swapped out for each run. The idea is to separate out fat batch
processes so that they get scheduled in a separate queue but in a slower pace
than normal batch processes such that when a fat batch is scheduled to run it
gets to run longer, but it is also out of schedule longer. The effect would be
to cause fewer swappings. The topping of this cake would be to prefetch pages
for the next fat-process in the scheduling queue. A "fat" process requires
effectively much more than average number of pages swapped in for each time it
runs.

However, the benefit of deferred swapp-in is that only pages actually needed is
tossed into the tight memory. This benefit can be missed with some processes
in a inferred system, since a process which is constantly shifting its set of
pages would only use part of the pages that got swapped in again. Other
processes might have a large core of pages which is used throughout its
processing. Some statistical analysis could aid (by keeping track of which
pages where not actually used the last time(s) and not swapp it in again) but
this naturally takes additional overheads (you need to trapp the page as if it
where not available and then just page it in, since it was prefetched into
physical memory and naturally also attend to the statistics).

After that I became more doubtfull that prefetching pages would be of interest,
but somebody might convince me otherwise. The scheduling idea might be enought,
but I'm sure it's gonna bit chopped into pieces by scheduling experts.

The idea really started with the question if the scheduler could make a better
scheduling if it where aware of the additional processing cost caused by
swapping in the VM. It might be that this is still a good question to ask.

Before you ask or requests it:
There is no code or numbers to show, this is armwaving around an idea.

Cheers,
Magnus

Re: An idea for prefetching swapped memory...

[Mark Mielke]

On Mon, Apr 07, 2003 at 01:24:41PM +0200, M?ns Rullg?rd wrote:
> Thomas Schlichter <schlicht@rumms.uni-mannheim.de> writes:
> > > This has been argued before. Why would the last swapped out pages
> > > be the best to swap in? The vm subsystem has (somehow) decided
> > > they're the least likely to be used again so why swap them in?
> > > Alternatively how would it know which to swap in instead?  Con

> > What I wanted to say is that if there is free memory it should be
> > filled with the pages that were in use before the memory got
> > rare. And these are the pages swapped out last. The other swapped
> > out pages are swapped out even longer and so will likely not be used
> > in the near future... (That's what the LRU algorithm says...)

> Would it be possible to track the most recently used swapped out page?
> This would possibly be a good candidate for speculative loading.

Personally, I'm not sure that this idea sounds very effective. I
_like_ the fact that after pages get swapped out, my RAM gets filled
up with file pages with use. It means that although bringing a window
that I haven't used in a while takes some time to load, my apache
server, or my xterm, can serve files or requests like 'ls' much
faster. If swap was automatically pulled in to replace my file pages,
I suspect I would be trading one evil for another.

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Re: An idea for prefetching swapped memory...

[Mark Mielke]

On Mon, Apr 07, 2003 at 10:19:25AM -0400, Chris Friesen wrote:
> Helge Hafting wrote:
> >"What we're going to need soon" is the best.  It isn't always predictable,
> >but sometimes.  "The block following the last we read from some 
> >file/fs-structure"
> >is often a good one though.

> With the current setup though, the memory is wasted.  It makes sense that 
> we should fill the memory up with *something* that is likely to be useful.
> 
> If I have mozilla open, start a kernel compile, and then come back half an 
> hour later, I would like to see the mozilla pages speculatively loaded back 
> into memory.
> 
> Since the system is otherwise idle, it doesn't cost anything to do this.  I 
> think its obvious that it is beneficial to swap in something, the only 
> trick is getting a decent heuristic as to what it should be.

Chris: Based on your usage patterns, how would Linux know that you were
going to be opening up Mozilla, and not that you were going to tweak the
kernel source and compile it again?

The only time memory is wasted is when you don't have enough of it, and it
gets trampled for common operations that you perform. All other times, the
memory is loaded, because it was used, which means it might be used again.

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Re: An idea for prefetching swapped memory...

[Chris Friesen]

Mark Mielke wrote:
> On Mon, Apr 07, 2003 at 10:19:25AM -0400, Chris Friesen wrote:

> Chris: Based on your usage patterns, how would Linux know that you were
> going to be opening up Mozilla, and not that you were going to tweak the
> kernel source and compile it again?

Because it would read my mind and figure out what I wanted!   ;-)

Maybe it would be possible to have some way to tell the kernel, "I would prefer 
this process to be in memory, unless you're running short, at which point you 
can swap it out."

This would be very similar to the niceness value, except it would control what 
memory gets swapped out.  You could tie it in to what processes have been 
running, such that if the system goes idle you could start preferentially 
swapping back in the processes with the memory niceness set.  If you left it at 
zero you get the current behaviour (not swapped in until needed) while positive 
(or negative, to align with niceness) values would swap that process in 
preferentially when the system goes idle.

This would give similar benefits as mlock without actually robbing the kernel of 
the ability to swap out under memory pressure.

Does this sound at all useful, or am I blowing smoke?

Chris



-- 
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: An idea for prefetching swapped memory...

[Mark Mielke]

On Mon, Apr 07, 2003 at 02:49:10PM -0400, Chris Friesen wrote:
> Mark Mielke wrote:
> >On Mon, Apr 07, 2003 at 10:19:25AM -0400, Chris Friesen wrote:
> >Chris: Based on your usage patterns, how would Linux know that you were
> >going to be opening up Mozilla, and not that you were going to tweak the
> >kernel source and compile it again?
> Because it would read my mind and figure out what I wanted!   ;-)

Oooo... I want this OS! :-)

> Maybe it would be possible to have some way to tell the kernel, "I would 
> prefer this process to be in memory, unless you're running short, at which 
> point you can swap it out."

> This would be very similar to the niceness value, except it would control 
> what memory gets swapped out.  You could tie it in to what processes have 
> been running, such that if the system goes idle you could start 
> preferentially swapping back in the processes with the memory niceness set. 
> If you left it at zero you get the current behaviour (not swapped in until 
> needed) while positive (or negative, to align with niceness) values would 
> swap that process in preferentially when the system goes idle.

> This would give similar benefits as mlock without actually robbing the 
> kernel of the ability to swap out under memory pressure.

> Does this sound at all useful, or am I blowing smoke?

I think it could be useful, but is probably much more complicated in the
details... Like, for example, how would you know whether a file page in
memory had been used by only one process, or many, and what priority it
should have? What happens if the scheme conflicts with the LRU scheme?
What happens if the memory page is really a shared memory segment used
by both the application and X to double-buffer display the window?

Implementation of this is beyond my imagination today... I only see perils.

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

RE: An idea for prefetching swapped memory...

[Robert White]

DISCLAIMER: Without having actually looked at the code...

I would say that being able to mark a process or executable as a "should be
speculatively  reloaded" is... wait for it... a "very bad" idea.  It would
become far too easy for someone to configure a hugely anti-optimal system by
just flagging some giant pig-dog program as "favorable for residency" and
then have the system end up aggressively reloading parts of that program's
data set that aren't even being used.

Consider:  you flag Mozilla and the system starts aggressively loading the
composer and mail client (etc.) code while all you are doing is looking at a
help file.

Degenerate cases abound.

[These issues are, BTW, why the use of the "text sticky bit" pretty much
deprecated itself.]

On the other hand, presuming for the moment that the VM system works
something vaguely like the one in a Sun SVR4 system (because, remember, I
haven't read the code 8-).  That is, let's say there is a pointer traversing
along through memory that looks at each page and considers it for writing
out to swap.  And there is another pointer that cycles through memory behind
it and, if it hasn't been modified since the first pointer passed, it does
the write-to-swap and then puts the page on the reclaim-or-overwrite list.
When a process accesses a page, if it is normal then it is normal, if it is
on the reclaim-or-overwrite list it reclaims its page, if it isn't on the
list, the system takes the first page off the list and fills it with the
swapped-in contents.

Now lets change that list from a list to a priority queue....

It would be interesting to have the system keep track of page faults for
each process and then make a ratio of Page_Faults/Program_Size (or maybe
RSS?).  The smaller this number is the higher its pages are on the priority
queue.

Now, programs that are experiencing a large amount of paging (because they
are large and they are actively getting hit) will tend to have their pages
preserved on the reclaim/overwrite list.  That is, they are more likely to
be able to reclaim their pages instead of having to swap them in.

The nice parts:

- Small programs that are being intensely used tend to stay in memory
because of that use.  (e.g. actively grep(ing) a file, not a large data set
but the continuous use keeps its pages off the queue naturally.

- Large, inactive programs tend to leave memory quickly.

- Small, moderately inactive programs tend to profile competitively with
larger active more-active programs (so the large active programs don't
completely trample over their smaller kin.)

- New (just initiated) programs will tend to profile themselves quickly,
which will tend to let initialization time code and data subside gracefully.

- As system run state evolves (people and processes come and go) the
heuristic can keep up because the processes are only judged against one
another.

[ASIDE: The tracking might actually be better by "memory image" instead of
"process" so that multi-threaded code will compete based on the sum of their
threads activities...?]

Rob.

-----Original Message-----
From: linux-kernel-owner@vger.kernel.org
[mailto:linux-kernel-owner@vger.kernel.org]On Behalf Of Chris Friesen
Sent: Monday, April 07, 2003 11:49 AM
To: Mark Mielke
Cc: Helge Hafting; Thomas Schlichter; linux-kernel@vger.kernel.org
Subject: Re: An idea for prefetching swapped memory...


Mark Mielke wrote:
> On Mon, Apr 07, 2003 at 10:19:25AM -0400, Chris Friesen wrote:

> Chris: Based on your usage patterns, how would Linux know that you were
> going to be opening up Mozilla, and not that you were going to tweak the
> kernel source and compile it again?

Because it would read my mind and figure out what I wanted!   ;-)

Maybe it would be possible to have some way to tell the kernel, "I would
prefer
this process to be in memory, unless you're running short, at which point
you
can swap it out."

This would be very similar to the niceness value, except it would control
what
memory gets swapped out.  You could tie it in to what processes have been
running, such that if the system goes idle you could start preferentially
swapping back in the processes with the memory niceness set.  If you left it
at
zero you get the current behaviour (not swapped in until needed) while
positive
(or negative, to align with niceness) values would swap that process in
preferentially when the system goes idle.

This would give similar benefits as mlock without actually robbing the
kernel of
the ability to swap out under memory pressure.

Does this sound at all useful, or am I blowing smoke?

Chris



--
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

-
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/

Re: An idea for prefetching swapped memory...

[Chris Friesen]

Robert White wrote:

> It would be interesting to have the system keep track of page faults for
> each process and then make a ratio of Page_Faults/Program_Size (or maybe
> RSS?).  The smaller this number is the higher its pages are on the priority
> queue.

This sounds quite interesting, and might actually be implementable.

> [ASIDE: The tracking might actually be better by "memory image" instead of
> "process" so that multi-threaded code will compete based on the sum of their
> threads activities...?]

Works for me.  We're dealing with memory here, it might make sense to 
differentiate based on memory.

Chris


-- 
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com