load control demotion/promotion policy

load control demotion/promotion policy

[Rik van Riel]

Hi,

I've got an idea for a load control / memory scheduling
policy that is inspired by the following requirements
and data points:

1) wli pointed out that one of the better performing load
   control mechanisms is one that swaps out the SMALLEST
   process (easy to swap out, removes one process worth of
   IO load from the system)

2) small processes, like root shells, should not be
   swapped out for a long time, but should be swapped
   back in relatively quickly

3) because swapping big processes in or out is a lot of
   work, we should do that infrequently

4) however, once a big process is swapped out, it should
   stay out for a long time because it greatly reduces
   the amount of memory the system needs

The swapout selection loop would be as follows:
- calculate (rss / resident time) for every process
- swap out the process where this value is lowest
- remember the rss and swapout time in the task struct

At swapin time we can do the opposite, looking at
every process in the swapped out queue and waking up
the process where (swap_rss / now - swap_time) is
the smallest.

What do you think ?

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[William Lee Irwin III]

On Sat, Dec 20, 2003 at 09:33:34PM -0500, Rik van Riel wrote:
> I've got an idea for a load control / memory scheduling
> policy that is inspired by the following requirements
> and data points:
> 1) wli pointed out that one of the better performing load
>    control mechanisms is one that swaps out the SMALLEST
>    process (easy to swap out, removes one process worth of
>    IO load from the system)
> 2) small processes, like root shells, should not be
>    swapped out for a long time, but should be swapped
>    back in relatively quickly
> 3) because swapping big processes in or out is a lot of
>    work, we should do that infrequently
> 4) however, once a big process is swapped out, it should
>    stay out for a long time because it greatly reduces
>    the amount of memory the system needs

I like this as it gives us a starting point for tuning and algorithmic
adjustments with a precedent. Some synthesis appears to be required for
queueing due to the fact it's not possible to integrate this with the
cpu scheduler (because threads create an essential distinction between
user execution contexts and process address spaces not present in older
kernels).

One case I would be very careful about is that of a single userspace
process meeting the demotion criteria remaining in-core. We might need
init=foo mem=bar to get into a situation of that kind with any certainty.
I've not seen this discussed anywhere. Maybe it's irrelevant.


On Sat, Dec 20, 2003 at 09:33:34PM -0500, Rik van Riel wrote:
> The swapout selection loop would be as follows:
> - calculate (rss / resident time) for every process
> - swap out the process where this value is lowest
> - remember the rss and swapout time in the task struct
> At swapin time we can do the opposite, looking at
> every process in the swapped out queue and waking up
> the process where (swap_rss / now - swap_time) is
> the smallest.
> What do you think ?

Tracking the integral of the RSS may be useful if you're after the
mean RSS over a time interval.

Also, a threshold (called K_0 in my sources) for minimum RSS before
a process becomes a candidate for eviction (or its mappings candidates
for page replacement) again was typical of policies I've seen described.
Processes with RSS's less than K_0 were called "loading tasks" there.
This seemed to be used mostly in conjunction with process-local
replacement policies.


-- wli
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Roger Luethi]

On Sat, 20 Dec 2003 21:33:34 -0500, Rik van Riel wrote:
> I've got an idea for a load control / memory scheduling
> policy that is inspired by the following requirements
> and data points:

It is my understanding that wli is interested in load control because
he knows this Russian guy who puts an insane load on his box. Do you
have friends in Russia as well? Isn't there _anybody_ interested in
the fact that 2.6 performance completely breaks down under a light
overload where 2.4 doesn't and where load control would be more of a
problem than a solution? Heck, I even showed that you don't have to give
up physical scanning to get most of the pageout performance back! Oh,
and btw: Did I overlook this problem on akpm's should/must fix lists,
or is it missing for a reason?

I can't help but think of the man who looks for his keys not where he
lost them but near the lamp post, where the light is. While I agree
that working on load control is a lot more fun, it is _pageout_ that
has been completely borked in 2.6 and there is no way in hell load
control can fix that. Load control trades latency for throughput and
makes sense for some situations after pageout tuning has been exhausted,
which is not true at all for Linux 2.6.

I hate to be a pest but I am still entirely unconvinced that load control
is what 2.6 needs at this point. Maybe I should make that ceterum censeo
a sig.

That said, here's my take:

> 1) wli pointed out that one of the better performing load
>    control mechanisms is one that swaps out the SMALLEST
>    process (easy to swap out, removes one process worth of
>    IO load from the system)

According to wli this strategy was 15% better than random selection in
terms of throughput / CPU usage. Those 15% may well be quite solid for
transaction based systems, but typical Linux systems and workloads are
different animals and it doesn't seem safe to rely on those numbers here.
Also, on modern servers/workstations with load control, latency will
become a much bigger problem than +/- 15% throughput could ever be.

Bottom line: We would have to benchmark various criteria anyway and
chosing the smallest process is arguably quite arbitrary. The best I
could say about it is that for all we know it's as good as any other
policy.

> 2) small processes, like root shells, should not be
>    swapped out for a long time, but should be swapped
>    back in relatively quickly
> 
> 3) because swapping big processes in or out is a lot of
>    work, we should do that infrequently
> 
> 4) however, once a big process is swapped out, it should
>    stay out for a long time because it greatly reduces
>    the amount of memory the system needs
> 
> The swapout selection loop would be as follows:
> - calculate (rss / resident time) for every process
> - swap out the process where this value is lowest
> - remember the rss and swapout time in the task struct
> 
> At swapin time we can do the opposite, looking at
> every process in the swapped out queue and waking up
> the process where (swap_rss / now - swap_time) is
> the smallest.

If I understand your description correctly, you'll probably stun sshd
early on, because it will have accrued an impressive resident time.
If the user starts a fat GUI administration tool to study/fix the load
problem, it will likely hit the sack as well and stay there for a long
time. IOW, you will help some users and quite possibly make things worse
for others.

Of course I don't claim your selection algorithm is any worse than mine,
but I doubt it is much better. It is hard to get right -- looks like
the OOM killer all over again.

As for the implementation: An overload situation that is grave enough
to make load control worthwhile should be a rare event. I didn't think
I could justify growing the task struct even further for that. So when
I wanted to save some state (like RSS at stunning time), I kept it in
local variables where the processes hit the wait queue. I didn't use
it for global comparisons like what you are suggesting, but even that
is possible with some extra effort. And at the time load control is
kicking in, we've got plenty of CPU cycles to spend on extra efforts.

Roger
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[William Lee Irwin III]

On Sat, 20 Dec 2003 21:33:34 -0500, Rik van Riel wrote:
>> I've got an idea for a load control / memory scheduling
>> policy that is inspired by the following requirements
>> and data points:

On Mon, Dec 22, 2003 at 12:55:42AM +0100, Roger Luethi wrote:
> It is my understanding that wli is interested in load control because
> he knows this Russian guy who puts an insane load on his box. Do you
> have friends in Russia as well? Isn't there _anybody_ interested in
> the fact that 2.6 performance completely breaks down under a light
> overload where 2.4 doesn't and where load control would be more of a
> problem than a solution? Heck, I even showed that you don't have to give
> up physical scanning to get most of the pageout performance back! Oh,
> and btw: Did I overlook this problem on akpm's should/must fix lists,
> or is it missing for a reason?

Obviously, the simple regressions should be corrected first. We're not
interested in programming them ourselves because as far as we know,
you've already written the fixes. It would be premature to do
measurements before your fixes are in place.


-- wli
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Roger Luethi]

On Sun, 21 Dec 2003 17:21:26 -0800, William Lee Irwin III wrote:
> Obviously, the simple regressions should be corrected first. We're not
> interested in programming them ourselves because as far as we know,
> you've already written the fixes. It would be premature to do

Sorry about the delay. Buried in work.

I wonder how I managed to make that impression. I created one patch as
a proof of concept. It demonstrates that the data I collected can be
used to identify regressions and -- sometimes -- roll them back.

I repeated the benchmarks just to be sure. Numbers are not accurate
(2.6.0 performance has a huge variance), but quite reliable
nevertheless. I should do more runs, but 10 is about as many as I can
get done in time.  Median run time (in seconds) for each benchmark are
as follows (priority, kswapd_throttling refer to the two hunks in the
patch below):

	efax	kbuild	qsbench
2.6.0 vanilla
	865	500	275
priority
	860	491	299
kswapd_throttling
	659	500	362
priority + kswapd_throttling
	560	433	327

The numbers look pretty good, but the patch is lame. It does not even
properly revert the distress changes let alone deal with the issue the
changes in 2.6.0-test3 were supposed to address.

That's the only patch I have reasonably solid data for.

Roger


diff -uNp -X /home/rl/data/doc/kernel/dontdiff-2.6 /data/exp/tmp/18_binsearch/linux-2.6.0/mm/vmscan.c ./mm/vmscan.c
--- /data/exp/tmp/18_binsearch/linux-2.6.0/mm/vmscan.c	Wed Oct 15 15:03:46 2003
+++ ./mm/vmscan.c	Tue Dec 23 08:25:42 2003
@@ -632,7 +632,7 @@ refill_inactive_zone(struct zone *zone, 
 	 * `distress' is a measure of how much trouble we're having reclaiming
 	 * pages.  0 -> no problems.  100 -> great trouble.
 	 */
-	distress = 100 >> zone->prev_priority;
+	distress = 100 >> priority;
 
 	/*
 	 * The point of this algorithm is to decide when to start reclaiming
@@ -981,8 +981,7 @@ static int balance_pgdat(pg_data_t *pgda
 		}
 		if (all_zones_ok)
 			break;
-		if (to_free > 0)
-			blk_congestion_wait(WRITE, HZ/10);
+		blk_congestion_wait(WRITE, HZ/10);
 	}
 
 	for (i = 0; i < pgdat->nr_zones; i++) {
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Rik van Riel]

On Mon, 22 Dec 2003, Roger Luethi wrote:

> that working on load control is a lot more fun, it is _pageout_ that has
> been completely borked in 2.6 and there is no way in hell load control
> can fix that. Load control trades latency for throughput and makes sense
> for some situations after pageout tuning has been exhausted, which is
> not true at all for Linux 2.6.

I agree, pageout in 2.6 needs to be finetuned a bit more
to get that extra factor of 2 performance that's hiding
in a dark corner.

However, I don't think that obviates the need for load
control.  You have convinced me, though, that load
control is an emergency thing and shouldn't be meant
for regular use. 

Then again, I've wanted to work on load control for
years and would like to use this opportunity to have
some fun.

If you'd rather work on tuning the pageout code to make
that faster, I'd be happy to play around a bit with the
load control code ;))

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Roger Luethi]

On Sun, 21 Dec 2003 20:34:30 -0500, Rik van Riel wrote:
> I agree, pageout in 2.6 needs to be finetuned a bit more
> to get that extra factor of 2 performance that's hiding
> in a dark corner.
> 
> However, I don't think that obviates the need for load
> control.  You have convinced me, though, that load
> control is an emergency thing and shouldn't be meant
> for regular use. 

We are in violent agreement then.

> Then again, I've wanted to work on load control for
> years and would like to use this opportunity to have
> some fun.
> 
> If you'd rather work on tuning the pageout code to make
> that faster, I'd be happy to play around a bit with the
> load control code ;))

I bet :-). I meant to save the load control stuff as a dessert, for later
(i.e. after the regressions are fixed where possible). Bad thinking I
reckon.

Roger
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Andrew Morton]

Roger Luethi <rl@hellgate.ch> wrote:
>
> Isn't there _anybody_ interested in
>  the fact that 2.6 performance completely breaks down under a light
>  overload where 2.4 doesn't and where load control would be more of a
>  problem than a solution?

I am!

But I have vague memories of being dazed and confused when last you tried
to describe the causes.  I was hoping that things would firm up a bit.


Please, take the time to describe it to us again, exhaustively.

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Roger Luethi]

On Sun, 21 Dec 2003 22:56:11 -0800, Andrew Morton wrote:
> But I have vague memories of being dazed and confused when last you tried
> to describe the causes.  I was hoping that things would firm up a bit.
> 
> Please, take the time to describe it to us again, exhaustively.

Sorry, I wouldn't do anyone a favor if I added more speculation. I'm
progressing slowly due to other tasks, but the benchmark data is
rather solid and can serve as a map for others to determine the cause
of regressions.

Here's one thing that might be interesting, though:

I explained recently on LKML that the kswap throttling patch of
2.6.0-test3 I reverted makes kswapd do virtually all the paging,
while previous (faster) kernels relied heavily on the path through the
page allocator to free memory. Remember the tiny patch I circulated in
early October, before I started systematically benchmarking the whole
devel series?

It looked like this (against test6):

+++ ./mm/vmscan.c	2003-10-02 23:30:59.423106182 +0200
@@ -1037,7 +1037,7 @@ int kswapd(void *p)
 		if (current->flags & PF_FREEZE)
 			refrigerator(PF_IOTHREAD);
 		prepare_to_wait(&pgdat->kswapd_wait, &wait, TASK_INTERRUPTIBLE);
-		schedule();
+		sys_sched_yield();
 		finish_wait(&pgdat->kswapd_wait, &wait);
 		get_page_state(&ps);
 		balance_pgdat(pgdat, 0, &ps);

This patch did pretty well with kbuild, but not with qsbench. Back then
I dropped the patch because of that. In the meantime I realized that
qsbench and the compile benchmarks are separate and rarely agree on
what's good. In fact, usually the best you can get is an improvement
for one type of benchmarks and no regression with the other. Check the
graph I posted, you'll see what I mean.

The kswapd/priority patch I posted (and the one above IIRC, I'd have
to repeat those benchmarks as well to be sure) accomplishes that
pretty much.

The reason I mention this old patch: If you compare the old patch above
with the kswapd/priority reversal patches I posted and discussed on
LKML, you'll notice that they have something in common: Slow down kswapd
freeing in favor of freeing by allocator. Seems to be a common theme.
I could speculate about the reasons, but I didn't have the time to test
any theories.

Roger
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[William Lee Irwin III]

On Sat, 20 Dec 2003 21:33:34 -0500, Rik van Riel wrote:
>> I've got an idea for a load control / memory scheduling
>> policy that is inspired by the following requirements
>> and data points:

On Mon, Dec 22, 2003 at 12:55:42AM +0100, Roger Luethi wrote:
> It is my understanding that wli is interested in load control because
> he knows this Russian guy who puts an insane load on his box. Do you
> have friends in Russia as well? Isn't there _anybody_ interested in
> the fact that 2.6 performance completely breaks down under a light
> overload where 2.4 doesn't and where load control would be more of a
> problem than a solution? Heck, I even showed that you don't have to give
> up physical scanning to get most of the pageout performance back! Oh,
> and btw: Did I overlook this problem on akpm's should/must fix lists,
> or is it missing for a reason?

I have posted to this thread several times and I've not gotten the
replies back from the mailing list, but I have received several
subsequent replies. What's going on here?


-- wli
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Benjamin LaHaise]

On Sun, Dec 21, 2003 at 11:00:18PM -0800, William Lee Irwin III wrote:
> I have posted to this thread several times and I've not gotten the
> replies back from the mailing list, but I have received several
> subsequent replies. What's going on here?

I've seen two messages from you on this thread.  The first two of the 
thread were delayed as they tripped up one of the spam regexps.  If 
you have copies of the sent messages which are missing, I can certainly 
check the logs here.

		-ben
-- 
"The software industry today survives only through an unstated agreement 
not to stir things up too much.  We must hope this lawsuit [by SCO] isn't 
the big stirring spoon." -- Ian Lance Taylor, Linux Journal, June 2003
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[William Lee Irwin III]

On Sun, Dec 21, 2003 at 11:00:18PM -0800, William Lee Irwin III wrote:
>> I have posted to this thread several times and I've not gotten the
>> replies back from the mailing list, but I have received several
>> subsequent replies. What's going on here?

On Mon, Dec 22, 2003 at 10:12:45AM -0500, Benjamin LaHaise wrote:
> I've seen two messages from you on this thread.  The first two of the 
> thread were delayed as they tripped up one of the spam regexps.  If 
> you have copies of the sent messages which are missing, I can certainly 
> check the logs here.

There were only two sent out; it's been suggested that the list is
configured not to send messages back to their original sender.


-- wli
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: load control demotion/promotion policy

[Benjamin LaHaise]

On Mon, Dec 22, 2003 at 07:18:52AM -0800, William Lee Irwin III wrote:
> There were only two sent out; it's been suggested that the list is
> configured not to send messages back to their original sender.

Nope, you were unsubscribed for bounces a while back.

		-ben
-- 
"The software industry today survives only through an unstated agreement 
not to stir things up too much.  We must hope this lawsuit [by SCO] isn't 
the big stirring spoon." -- Ian Lance Taylor, Linux Journal, June 2003
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>