lkml.org 
[lkml]   [2004]   [Mar]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patches in this message
/
Date
From
Subjectbonus inheritance
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]
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;
--- 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);[unhandled content-type:application/pgp-signature]
\
 
 \ /
  Last update: 2005-03-22 14:01    [W:1.378 / U:0.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site