bonus inheritance

bonus inheritance

[Kurt Garloff]

[-- Attachment #1.1: Type: text/plain, Size: 2008 bytes --]

Hi Nick, Con,

in 2.4, the interactivity bonus in the O(1) scheduler was not inherited 
well.

Imagine an idle shell with max bonus (say 200), then forking twice
would lead to the follwing situation:
bash(200) -> script.py(100) -> ls( 50)

In 2.6, this is partially fixed, as the penalty is set to 95.

I believe however, that the mistake of the penalty concept is drawing
the value to 0 instead of the average (100 on HZ=100 systems).

The fix is obvious: Draw to the center and have some inheritance.
This is what the first part of the 2.4 patch does, with inheritance
set to 50.
bash(200) -> script.py(150) -> ls(125)

The second hunk of the 2.4 patch makes the bonus non-linear.
The problem is that with the old behaviour processes tend to be stuck
at either the minimum or the maximum, as those are the only stable
values. With the non-linear formula, you give a higher penalty if
the bonus is higher. The algorithm has several stable points, depending
on CPU consumption.

The patch was written with the goal to improve interactive behaviour.
It did achieve this. Processes freshly started had a higher bonus thatn
the background kernel compile processes and thus get woken up.

The amazing thing is that the patch gave a few percent in SpecJBB and
Volanomark on a 8 way box.

I believe we need something similar in 2.6.
The first part is attached: The bonus inheritance is implemented as
inheritance, daring the value to the center instead of the minimum.
I put inheritance to 80 to more closely resemble current 2.6.

For the second part, I'm unsure. The current tweaks in the scheduler
may already have the non-linear property that I believe we need.
I'll need to reread the code to fully understand it though.

Ideas, comments?
-- 
Kurt Garloff                   <kurt@garloff.de>             [Koeln, DE]
Physics:Plasma modeling <garloff@plasimo.phys.tue.nl> [TU Eindhoven, NL]
Linux: SUSE Labs (Head)        <garloff@suse.de>    [SUSE Nuernberg, DE]

[-- Attachment #1.2: fork-interactive-balance-26.diff --]
[-- Type: text/plain, Size: 1026 bytes --]

diff -uNrp linux-2.6.4.sched/kernel/sched.c linux-2.6.4.sched2/kernel/sched.c
--- linux-2.6.4.sched/kernel/sched.c	2004-03-11 21:22:55.475136648 +0100
+++ linux-2.6.4.sched2/kernel/sched.c	2004-03-11 21:58:57.992384056 +0100
@@ -93,7 +93,7 @@ int max_timeslice = __MAX_TIMESLICE, min
 #define MIN_TIMESLICE ((min_timeslice * HZ + 999999) / 1000000)
 
 #define ON_RUNQUEUE_WEIGHT	 30
-#define CHILD_PENALTY		 95
+#define CHILD_INHERITANCE	 80
 #define PARENT_PENALTY		100
 #define EXIT_WEIGHT		  3
 #define PRIO_BONUS_RATIO	 25
@@ -761,8 +761,9 @@ void fastcall wake_up_forked_process(tas
 	current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) *
 		PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
 
-	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
-		CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
+	p->sleep_avg = JIFFIES_TO_NS((CURRENT_BONUS(p)
+		* MAX_SLEEP_AVG / MAX_BONUS * CHILD_INHERITANCE / 100
+		+ (100-CHILD_INHERITANCE) * MAX_SLEEP_AVG / 200));
 
 	p->interactive_credit = 0;
 

[-- Attachment #1.3: fork-interactive-balance-24.diff --]
[-- Type: text/plain, Size: 1555 bytes --]

--- linux-2.4.21/kernel/sched.c	2003-08-27 17:06:44.000000000 +0200
+++ linux-2.4.21.x86_64/kernel/sched.c	2003-08-27 21:47:39.000000000 +0200
@@ -60,7 +60,7 @@
 #define MAX_TIMESLICE (max_timeslice * HZ / 1000000)
 #define MIN_TIMESLICE (min_timeslice * HZ / 1000000)
 
-#define CHILD_PENALTY		50
+#define CHILD_INHERITANCE	50
 #define PARENT_PENALTY		100
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
@@ -393,7 +393,7 @@
 		 * We decrease the sleep average of forked
 		 * children, to keep max-interactive tasks
 		 * from forking tasks that are max-interactive.
-		 * CHILD_PENALTY is set to 50% since we have
+		 * CHILD_INHERITANCE is set to 50% since we have
 		 * no clue if this is still an interactive
 		 * task like the parent or if this will be a
 		 * cpu bound task. The parent isn't touched
@@ -401,7 +401,8 @@
 		 * changing behaviour after the child is forked.
 		 */
 		parent->sleep_avg = parent->sleep_avg * PARENT_PENALTY / 100;
-		p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+		p->sleep_avg = p->sleep_avg * CHILD_INHERITANCE / 100
+				+ (100-CHILD_INHERITANCE) * MAX_SLEEP_AVG / 200;
 
 		/*
 		 * For its first schedule keep the child at the same
@@ -850,8 +851,7 @@
 	 * it possible for interactive tasks to use up their
 	 * timeslices at their highest priority levels.
 	 */
-	if (p->sleep_avg)
-		p->sleep_avg--;
+	p->sleep_avg = p->sleep_avg * (MAX_SLEEP_AVG-3) / MAX_SLEEP_AVG;
 	if (!--p->time_slice) {
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);

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

Re: bonus inheritance

[Con Kolivas]

Quoting Kurt Garloff <garloff@suse.de>:

> Hi Nick, Con,

Hi Kurt.

> I believe we need something similar in 2.6.
> The first part is attached: The bonus inheritance is implemented as
> inheritance, daring the value to the center instead of the minimum.
> I put inheritance to 80 to more closely resemble current 2.6.

> For the second part, I'm unsure. The current tweaks in the scheduler
> may already have the non-linear property that I believe we need.
> I'll need to reread the code to fully understand it though.

The estimator in 2.6 mainline is nothing like the 2.4 one. Most freshly forked
processes get rapidly elevated to just below fully interactive state in a non
linear fashion and thus are usually much better priority than any running cpu
bound process. Watch top during a kernel compile and starting new apps. You'll
see cpu bound tasks hover between PRI 20 and 25, fully interactive tasks hover
at 15-16 and newly forked processes start around 17. This is intentional as
allowing them to elevate fully to interactive means that disk activity would
fool the cpu scheduler into thinking a cpu bound task is fully interactive, so
they are better than fully cpu bound, but slightly worse than already running
interactive tasks until they declare themselves clearly.

Con

Re: bonus inheritance

[Nick Piggin]

Kurt Garloff wrote:

>
>The patch was written with the goal to improve interactive behaviour.
>It did achieve this. Processes freshly started had a higher bonus thatn
>the background kernel compile processes and thus get woken up.
>
>

Hi Kurt,
I'm sorry I can't comment too much on your patch, as I am not
too familiar with 2.6's scheduler policy. Never hurts to have
another pair of eyes looking at it though.

Does it help any actual interactivity problem? Unfortunately
practically any you make to the scheduler is bound to make
things worse for at least one person, so it is difficult to
just test things out.

Maybe we could include a compile (or even boot) time selectable
schedulers to test improvements. Or wait for 2.7 and backport
good bits. These two options still have the problem that most
of the users that matter still won't test them...

That said, if you have any real, reproducable problems that it
solves, you far improve your chances of it being picked up (in
one form or another).

Nick

Re: bonus inheritance

[Kurt Garloff]

[-- Attachment #1: Type: text/plain, Size: 1659 bytes --]

Hi Nick,

On Tue, Mar 16, 2004 at 04:54:49PM +1100, Nick Piggin wrote:
> Does it help any actual interactivity problem? Unfortunately
> practically any you make to the scheduler is bound to make
> things worse for at least one person, so it is difficult to
> just test things out.

Well, the interactivity problems existed with O(1) in 2.4.
The 50% penalty hurt freshly started processes a lot.

To fix this, the penalty has been set to 95 (5% penalty)
in 2.6.
I believe it's cleaner to draw the bonus towards the average 
and inherit a percentage, and thus I set a inheritance percentage 
of 50 in 2.4.

It was successful in 2.4. In a measurable way.

In 2.6, it likely will not make a big difference as with giving 
95% of the bonus, you don't change much ...

So it's more a question of have the concept in there which is
clearer. More a theoretical thing. Assuming that with 95% chance
your child has the same character w.r.t. to interactiveness is
rather high.

It will be very hard to measure 80% inheritance to 95% penalty 
as for the most important case (starting a process from a shell), 
the results are almost the same.

The fact that we are more likely to start new processes towards 
the center in our bonus scale certainly makes it faster for the
scheduler to put them in the right category, so there should be
some benefit w.r.t. interactiveness. However, those are not easy 
to measure :-(

I'll see whether we can get some benchmarks anyway.

Regards,
-- 
Kurt Garloff  <garloff@suse.de>                            Cologne, DE 
SUSE LINUX AG, Nuernberg, DE                          SUSE Labs (Head)

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

Re: bonus inheritance

[Con Kolivas]

On Tue, 16 Mar 2004 10:48 pm, Kurt Garloff wrote:
> Hi Nick,
>
> On Tue, Mar 16, 2004 at 04:54:49PM +1100, Nick Piggin wrote:
> > Does it help any actual interactivity problem? Unfortunately
> > practically any you make to the scheduler is bound to make
> > things worse for at least one person, so it is difficult to
> > just test things out.
>
> Well, the interactivity problems existed with O(1) in 2.4.
> The 50% penalty hurt freshly started processes a lot.

There are at least 4 different O(1) schedulers in different 2.4 trees still in 
existence and the value of the penalty only started changing when 2.5 
development began. Therefore, no one value is what was in "2.4 O(1)" since 
there was no "standard" O(1). 2.6 is a completely different beast in 
estimating interactivity than the 2.4 O(1) kernels so changes do not work as 
expected upstream.

> To fix this, the penalty has been set to 95 (5% penalty)
> in 2.6.

Actually that's what it used to be on the first O(1) patches for 2.4

> I believe it's cleaner to draw the bonus towards the average
> and inherit a percentage, and thus I set a inheritance percentage
> of 50 in 2.4.
>
> It was successful in 2.4. In a measurable way.
>
> In 2.6, it likely will not make a big difference as with giving
> 95% of the bonus, you don't change much ...

Even less than that logic would reveal because this particular part of the 
estimator is far less important with the heuristics examining process 
behaviour very rapidly in 2.6. This value is more important in the estimator 
in preventing a fork bomb more than anything else.

> So it's more a question of have the concept in there which is
> clearer. More a theoretical thing. Assuming that with 95% chance
> your child has the same character w.r.t. to interactiveness is
> rather high.

See above; it is a penalty the way the estimator currently works.

> It will be very hard to measure 80% inheritance to 95% penalty
> as for the most important case (starting a process from a shell),
> the results are almost the same.
>
> The fact that we are more likely to start new processes towards
> the center in our bonus scale certainly makes it faster for the
> scheduler to put them in the right category, so there should be
> some benefit w.r.t. interactiveness. However, those are not easy
> to measure :-(

As I said; the 2.6 estimator does much in determining interactive tasks 
shortly after forking than just this simple knob affects.

> I'll see whether we can get some benchmarks anyway.

Please don't use contest as this does _not_ measure interactivity; it measures 
responsiveness which is quite different. Interactivity is avoiding scheduling 
latency and scheduling jitter in tasks where that latency and jitter would be 
palpable. I have ideas for coding a benchmark to measure such a thing but not 
the time to do it.

Please I encourage you to try whatever testing and modifications you want; but 
this is nowhere near as simple as it appears on the surface.

Con