process selection

process selection

[Rik van Riel]

Hi,

in mm/vmscan.c::swap_out() we select the process from
which to swap out pages. In my experience, this selection
is done on a somewhat random basis.

The way things are running on my system right now, X
and Netscape are swapped out while a stopped setiathome
(been sleeping for over an hour) remains in memory.

Could it be an idea to take the 'sleeping time' of each
process into account when selecting which process to swap
out?  Due to extreme lack of free time, I'm asking what
you folks think of it before testing it myself...

cheers,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:   http://www.linux.eu.org/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Andrea Arcangeli]

On Sat, 12 Jun 1999, Rik van Riel wrote:

>Could it be an idea to take the 'sleeping time' of each
>process into account when selecting which process to swap
>out?  Due to extreme lack of free time, I'm asking what

The CPUs set the "accessed" bit in hardware, and that should be enough to
do proper aging. If setiathome is all in RAM it means it gets touched more
fast than netscape.

BTW, I suggest you to try out:

	ftp://ftp.suse.com/pub/people/andrea/kernel-patches/2.2.9_andrea-VM4.gz

and see if the swapout behaviour changes.

(I have just ready a VM5 too but since there are not critical issues in
VM5 I am waiting a bit more before releasing it)

Andrea Arcangeli

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Rik van Riel]

On Sun, 13 Jun 1999, Andrea Arcangeli wrote:
> On Sat, 12 Jun 1999, Rik van Riel wrote:
> 
> >Could it be an idea to take the 'sleeping time' of each
> >process into account when selecting which process to swap
> >out?  Due to extreme lack of free time, I'm asking what
> 
> The CPUs set the "accessed" bit in hardware, and that should be
> enough to do proper aging. If setiathome is all in RAM it means it
> gets touched more fast than netscape.

Setiathome had been stopped (by loadwatch) for over an hour.
This means that _everything_ else in the system could have
been touched more often.

Unfortunately, the kernel was still busy shrinking the page
cache and the swapout counter was still with X and later with
Netscape -- it didn't advance fast enough to get to setiathome,
yet writing out my mailbox took so much disk activity in the
limited buffer space that my mp3s began skipping.


Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:   http://www.linux.eu.org/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Kanoj Sarcar]

> 
> Could it be an idea to take the 'sleeping time' of each
> process into account when selecting which process to swap
> out?  Due to extreme lack of free time, I'm asking what
> you folks think of it before testing it myself...
>

You are right, sleep time is a good heuristic to determine 
the "swappability" of a process. 

Hmm, I wonder if this is what happended in your case: setiathome
probably had a big rss, but netscape and X probably had 
larger rss and got selected for stealing. 

These are just a couple of things probably worth trying out:
1. The stealing algorithm can be upgraded to steal more than just
SWAP_CLUSTER_MAX, for all the work it does.
2. Also, in swap_out, it might make sense to steal more than a
single page from a victim process, to balance the overhead of
scanning all the processes.

Kanoj
--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Benjamin C.R. LaHaise]

Sometime earlier, Rik wrote:

> > Could it be an idea to take the 'sleeping time' of each
> > process into account when selecting which process to swap
> > out?  Due to extreme lack of free time, I'm asking what
> > you folks think of it before testing it myself...

On Mon, 14 Jun 1999, Kanoj Sarcar wrote:

> You are right, sleep time is a good heuristic to determine 
> the "swappability" of a process. 

I'm starting to think that going back and benchmarking my vm patches
against 2.1.47 or 66 might prove useful as they used a physical page
scanning with the old LFU technique, but proved remarkably faster than
scanning the virtual addresses space of processes.  Gee, I guess it's time
for forward port the beast again and see what results it gets against
current things.

		-ben (who now has another project for tonight)


--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Rik van Riel]

On Mon, 14 Jun 1999, Benjamin C.R. LaHaise wrote:

> I'm starting to think that going back and benchmarking my vm
> patches against 2.1.47 or 66 might prove useful as they used a
> physical page scanning with the old LFU technique,

I don't think this will be worth the effort. Firstly, physical
scanning is disastrous for effective I/O clustering (once we
hit swap, disk seek is _far_ more important than CPU time) and
LFU just isn't as good as LRU.

If you want a real improvement, you should port over some of
the (very nice) FreeBSD algorithms for I/O clustering and
assorted stuff.

As for including the sleep time in VMA selection. I think we
should just give an added 'bonus' if the process to which the
VMA belongs has been sleeping for a long time. If it's been
sleeping for a very long time (> 15 minutes) and the VMA is
not shared, we might even consider swapping the whole thing
out in one (physically contiguous for easy reading) swoop.


regards,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:   http://www.linux.eu.org/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Benjamin C.R. LaHaise]

On Mon, 14 Jun 1999, Rik van Riel wrote:

> On Mon, 14 Jun 1999, Benjamin C.R. LaHaise wrote:
> 
> > I'm starting to think that going back and benchmarking my vm
> > patches against 2.1.47 or 66 might prove useful as they used a
> > physical page scanning with the old LFU technique,
> 
> I don't think this will be worth the effort. Firstly, physical
> scanning is disastrous for effective I/O clustering (once we
> hit swap, disk seek is _far_ more important than CPU time) and
> LFU just isn't as good as LRU.

Physical scanning might be bad for IO clustering as we're doing it right
now, but it provides significantly more graceful performance degredation
under high load because we're not blowing the cache away for every single
attempt to find a page to release.  The old patch I was referring to
cached the vma the page was last mapped into, which meant that the
overhead as compared to what we're doing for the normal privately mapped
case was negligable.  I suppose that once a region is found that's
inactive, one could deal with neighbours to achive reasonable clustering.

> If you want a real improvement, you should port over some of
> the (very nice) FreeBSD algorithms for I/O clustering and
> assorted stuff.

I've started looking at FreeBSD, and boy is it... different.  (Still on a
really steep learning curve, looking for a guide to the internals as it
doesn't feel nearly as readable as Linux code.)  There are a couple of
ideas bouncing about my head in the last little while that might be worth
sharing now: vm_store -- I like the idea of having an object that manages
a cache for an object.  Something like vm_store could be generic enough to
replace both the page cache and buffer cache code which suffers from a
good deal of duplication of hashing code, locking, updating and waiting... 
Towards this end I wrote a light hash template that deals with SMP (it's
made mostly lockless by using a singly linked list for the hash along with
an atomic generation counter).  I stopped fiddling with the page cache
since Ingo's stuff was coming, but now that I can see what it looks like,
it'll be worth poking at again.

One of the things I thought about doing when starting this was to make a
hash bucket for each object, rather than the overall system as is
currently done: it would allow the bucket size to be tuned to the size of
the object, and get rid of the need for having a doubly linked inode list
(as all pages for an inode could now be found by walking the inode's hash
queues).  Another thought was to also have a second bucket for a dirty
object hash to make fsync/fdatasync fast.  Basically, the idea is making a
beast that's just as light as the page-cache, but used for everything
(fs metadata would be a separate store so readahead on the damn indirect
blocks would happen automatically, as would the inode tables and so on).
With that in place, making the buffer_head an io placeholder becomes easy,
and clustering the bh's would be much more effective.

> As for including the sleep time in VMA selection. I think we
> should just give an added 'bonus' if the process to which the
> VMA belongs has been sleeping for a long time. If it's been
> sleeping for a very long time (> 15 minutes) and the VMA is
> not shared, we might even consider swapping the whole thing
> out in one (physically contiguous for easy reading) swoop.

That sounds like a very good idea, and in fact would give us the ability
to truely swap out a process for free. =)  And it's only one extra flag to
the swap code! 

		-ben

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Antonino Sabetta]

>2. Also, in swap_out, it might make sense to steal more than a
>single page from a victim process, to balance the overhead of
>scanning all the processes.
Or at least, steal more that a single page if the process owns a "big"
number of pages.
--

+---------------------------------+
| A n t o n i n o   S a b e t t a |
|  sabetta@ieee.ing.uniroma1.it   |
|        ICQ:    39918730         |
+---------------------------------+
--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: process selection

[Stephen C. Tweedie]

On Tue, 15 Jun 1999 12:28:06 +0200, Antonino Sabetta <copernico@tin.it> said:

>> 2. Also, in swap_out, it might make sense to steal more than a
>> single page from a victim process, to balance the overhead of
>> scanning all the processes.

> Or at least, steal more that a single page if the process owns a "big"
> number of pages.

This is something we really, really need to do eventually, to reduce the
overhead of the swapper.  Optimisations such as unmapping large chunks
at once for sequentially accessed mmap()s are an example of obvious
performance improvements, but by swapping multiple pages we also have
opportunities for reducing swap fragmentation.

--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/