Staircase Scheduler v6.3 for 2.6.7-rc2

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

Aims:
- Interactive by design rather than have interactivity bolted on.
- Good scalability.
- Simple predictable design.
- Maintain appropriate cpu distribution and fairness.
- Low scheduling latency for normal policy tasks.
- Low overhead.
- Making renicing processes actually matter for CPU distribution (nice 0
gets 20 times what nice +20 gets)
- Resistant to priority inversion
- More forgiving of poor locking
- Tunable for a server workload or computational tasks

Description:
- All tasks start at a dynamic priority based on their nice value. They
run for one RR_INTERVAL (nominally set to 10ms) and then drop one stair (priority). If they sleep before running again they get to run for 2 intervals before being demoted a priority and so on until they get all their intervals at their best priority: 20 intervals for nice 0; 1 interval for nice +19.

- The staircase elevation mechanism can be disabled and all tasks can simply descend stairs using the sysctl:

echo 0 > /proc/sys/kernel/interactive

this has the effect of maintaining cpu distribution much more strictly according to nice whereas the default mechanism allows bursts of cpu by interactive tasks before settling to appropriate cpu distribution.

- The time tasks are cpu bound can be increased by using the sysctl:

echo 1 > /proc/sys/kernel/compute

which extends the RR_INTERVAL to 100ms and disables the staircase elevation improving conditions for pure computational tasks by optimising cache benefits and decreasing context switching (gains another 1.5% on kernbench).

Performance:
- All cpu throughput benchmarks show equivalent or better performance than mainline. Note that disabling the interactive setting actually _worsens_ some benchmarks because of their dependence on yield() so I don't recommend disabling it unless you do a comparison first.
- Interactivity is approximately equivalent to mainline 2.6 but with faster application startup and no known behavioural quirks.

Comments and testing welcome.

 fs/proc/array.c        |    2
 include/linux/sched.h  |    8
 include/linux/sysctl.h |    2
 kernel/sched.c         |  676
+++++++++++++------------------------------------
 kernel/sysctl.c        |   16 +
 5 files changed, 212 insertions(+), 492 deletions(-)

Can be downloaded here:
http://ck.kolivas.org/patches/2.6/2.6.7-rc2/patch-2.6.7-rc2-s6.3

and below
Con

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

Quoted 9 lines · Con Kolivas

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

I'm impressed... I'm currently playing with linux-2.6.7-rc2-bk7 plus staircase plus autoswappiness and my system behaves exceptionally. It seems pretty responsive even when under heavy load (while true; do a=2; done). Nice work.

Hi,

it is the first time I tried this scheduler with 2.6.7-rc2-mm2. A k.o criteria for me: Playing ut2004 it generated a lot of statics (sound wise). I consider this a regression in contrast to O(1). Nick's scheduler plays nice as well. For Nick's I have X reniced to -10. Your scheduler doesn't like this, as well: When plaing some tune via xmms and then switching to another (virtual) desktop, I get pops in the sound for fractions of a second. Putting X back to 0 fixes this. But I don't know how to "fix" ut2004 with staircase. :-(

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

Quoted 9 lines · Con Kolivas

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

It seems this staircase scheduler has some strange interactions with networking and PM suspend. I can't suspend my laptop when any program is using the network and, what's more, after the suspend mechanism fails, the program that was using the network stays stuck at D state and can't be killed.

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description.

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

There is only one "array" per runqueue; the removed code should be at most a BUG_ON() or WARN_ON(); I opted to delete it altogether.

JIFFIES_TO_NS() is unused.

array->nr_active only ever modified, never examined.

Quoted 1 line

array->nr_active only ever modified, never examined.

cpu_to_node_mask() is dead.

Quoted 1 line

cpu_to_node_mask() is dead.

task->array is nothing more than a boolean flag. Shove it into task->thread_info->flags, saving sizeof(prio_array_t *) from sizeof(task_t). Compiletested only on sparc64 only.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is an update of the scheduler policy mechanism rewrite using the
infrastructure of the current O(1) scheduler. Slight changes from the
original design require a detailed description. The change to the original
design has enabled all known corner cases to be abolished and cpu
distribution to be much better maintained. It has proven to be stable in my
testing and is ready for more widespread public testing now.

Aims:
- Interactive by design rather than have
interactivity bolted on.
- Good scalability.
- Simple predictable design.
- Maintain appropriate cpu distribution and
fairness.
- Low scheduling latency for normal policy tasks.
- Low overhead.
- Making renicing processes actually matter for CPU
distribution (nice 0 gets
20 times what nice +20 gets)
- Resistant to priority inversion
- More forgiving of poor locking
- Tunable for a server workload or computational
tasks

Description:
- All tasks start at a dynamic priority based on
their nice value. They run
for one RR_INTERVAL (nominally set to 10ms) and then drop one stair
(priority). If they sleep before running again they get to run for 2
intervals before being demoted a priority and so on until they get all their
intervals at their best priority: 20 intervals for nice 0; 1 interval for
nice +19.

- - The staircase elevation mechanism can be
disabled and all tasks can simply
descend stairs using the sysctl:

echo 0 > /proc/sys/kernel/interactive

this has the effect of maintaining cpu distribution much more strictly
according to nice whereas the default mechanism allows bursts of cpu by
interactive tasks before settling to appropriate cpu distribution.

- - The time tasks are cpu bound can be increased by using the sysctl:

echo 1 > /proc/sys/kernel/compute

which extends the RR_INTERVAL to 100ms and disables the staircase elevation
improving conditions for pure computational tasks by optimising cache
benefits and decreasing context switching (gains another 1.5% on kernbench).

Performance:
- - All cpu throughput benchmarks show equivalent or better performance than
mainline. Note that disabling the interactive setting actually _worsens_ some
benchmarks because of their dependence on yield() so I don't recommend
disabling it unless you do a comparison first.
- - Interactivity is approximately equivalent to mainline 2.6 but with faster
application startup and no known behavioural quirks.

Comments and testing welcome.

 fs/proc/array.c        |    2
 include/linux/sched.h  |    8
 include/linux/sysctl.h |    2
 kernel/sched.c         |  676 
+++++++++++++------------------------------------
 kernel/sysctl.c        |   16 +
 5 files changed, 212 insertions(+), 492

deletions(-)

Can be downloaded here:

and below
Con
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

wXhrRsBsfY2BIqbLT1tUWcs=
=g1no
-----END PGP SIGNATURE-----

Quoted 1 line

diff -Naurp --exclude-from=dontdiff

linux-2.6.7-rc2-base/fs/proc/array.c
linux-2.6.7-rc2-s6.3/fs/proc/array.c
--- linux-2.6.7-rc2-base/fs/proc/array.c 2004-05-31
21:29:15.000000000 +1000
+++ linux-2.6.7-rc2-s6.3/fs/proc/array.c 2004-06-07
00:03:56.959133536 +1000

(quoted diff) +0 -0

@@ -155,7 +155,6 @@ static inline char *

task_state(struct t

fs/proc/array.c +0 -1

 	read_lock(&tasklist_lock);
 	buffer += sprintf(buffer,
 		"State:\t%s\n"
-		"SleepAVG:\t%lu%%\n"
 		"Tgid:\t%d\n"
 		"Pid:\t%d\n"
 		"PPid:\t%d\n"

@@ -163,7 +162,6 @@ static inline char *

task_state(struct t

fs/proc/array.c +0 -1

 		"Uid:\t%d\t%d\t%d\t%d\n"
 		"Gid:\t%d\t%d\t%d\t%d\n",
 		get_task_state(p),
-		(p->sleep_avg/1024)*100/(1020000000/1024),
 	       	p->tgid,
 		p->pid, p->pid ? p->real_parent->pid : 0,
 		p->pid && p->ptrace ? p->parent->pid : 0,

diff -Naurp --exclude-from=dontdiff
linux-2.6.7-rc2-base/include/linux/sched.h
linux-2.6.7-rc2-s6.3/include/linux/sched.h
--- linux-2.6.7-rc2-base/include/linux/sched.h

2004-05-31 21:29:21.000000000 +1000
+++ linux-2.6.7-rc2-s6.3/include/linux/sched.h
2004-06-07 00:10:37.450576503 +1000

(quoted diff) +0 -0

@@ -164,6 +164,7 @@ extern void show_stack(struct

task_struc

void io_schedule(void);
long io_schedule_timeout(long timeout);

include/linux/sched.h +4 -4

+extern int interactive, compute;
 
 extern void cpu_init (void);
 extern void trap_init(void);

@@ -394,14 +395,13 @@ struct task_struct {
 	struct list_head run_list;
 	prio_array_t *array;
 
-	unsigned long sleep_avg;
-	long interactive_credit;
 	unsigned long long timestamp;
-	int activated;
+	unsigned long runtime, totalrun;
+	unsigned int deadline;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
-	unsigned int time_slice, first_time_slice;
+	unsigned int slice, time_slice, first_time_slice;
 
 	struct list_head tasks;
 	struct list_head ptrace_children;

diff -Naurp --exclude-from=dontdiff
linux-2.6.7-rc2-base/include/linux/sysctl.h
linux-2.6.7-rc2-s6.3/include/linux/sysctl.h
--- linux-2.6.7-rc2-base/include/linux/sysctl.h

2004-05-31 21:29:21.000000000 +1000
+++ linux-2.6.7-rc2-s6.3/include/linux/sysctl.h
2004-06-07 00:06:13.007895851 +1000

(quoted diff) +0 -0

@@ -133,6 +133,8 @@ enum
 	KERN_NGROUPS_MAX=63,	/* int: NGROUPS_MAX */
 	KERN_SPARC_SCONS_PWROFF=64, /* int: serial console

power-off halt */

(quoted diff) +1 -0

 	KERN_HZ_TIMER=65,	/* int: hz timer on or off */
+	KERN_INTERACTIVE=66,	/* interactive tasks to have

cpu bursts */

(quoted diff) +1 -0

+	KERN_COMPUTE=67,	/* adjust timeslices for a

compute server */
};

diff -Naurp --exclude-from=dontdiff
linux-2.6.7-rc2-base/kernel/sched.c
linux-2.6.7-rc2-s6.3/kernel/sched.c
--- linux-2.6.7-rc2-base/kernel/sched.c 2004-05-31
21:29:24.000000000 +1000
+++ linux-2.6.7-rc2-s6.3/kernel/sched.c 2004-06-07
00:36:43.382396246 +1000

(quoted diff) +0 -0

@@ -16,7 +16,10 @@
  *		by Davide Libenzi, preemptible kernel bits by

Robert Love.
* 2003-09-03 Interactivity tuning by Con Kolivas.
* 2004-04-02 Scheduler domains code by Nick
Piggin
- */
+ * 2004-03-19. New staircase scheduling policy by
Con Kolivas with help
+ * from Zwane Mwaikambo and useful suggestions by
+ * William Lee Irwin III.

kernel/sched.c +1 -2

+*/
 
 #include <linux/mm.h>
 #include <linux/module.h>

@@ -66,8 +69,6 @@
 #define USER_PRIO(p)		((p)-MAX_RT_PRIO)
 #define TASK_USER_PRIO(p)
 USER_PRIO((p)->static_prio)
 #define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
-#define AVG_TIMESLICE	(MIN_TIMESLICE +
 ((MAX_TIMESLICE - MIN_TIMESLICE) *\
-			(MAX_PRIO-1-NICE_TO_PRIO(0))/(MAX_USER_PRIO -
 1)))

/*
* Some helpers for converting nanosecond timing to
jiffy resolution

(quoted diff) +0 -5

@@ -75,110 +76,18 @@
 #define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 /
 HZ))
 #define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 /
 HZ))
 
-/*
- * These are the 'tuning knobs' of the scheduler:
- *
- * Minimum timeslice is 10 msecs, default timeslice
 is 100 msecs,
- * maximum timeslice is 200 msecs. Timeslices get

refilled after
- * they expire.
- */

kernel/sched.c +0 -8

-#define MIN_TIMESLICE		( 10 * HZ / 1000)
-#define MAX_TIMESLICE		(200 * HZ / 1000)
-#define ON_RUNQUEUE_WEIGHT	 30
-#define CHILD_PENALTY		 95
-#define PARENT_PENALTY		100
-#define EXIT_WEIGHT		  3
-#define PRIO_BONUS_RATIO	 25
-#define MAX_BONUS		(MAX_USER_PRIO *

PRIO_BONUS_RATIO / 100)

kernel/sched.c +0 -4

-#define INTERACTIVE_DELTA	  2
-#define MAX_SLEEP_AVG		(AVG_TIMESLICE * MAX_BONUS)
-#define STARVATION_LIMIT	(MAX_SLEEP_AVG)
-#define NS_MAX_SLEEP_AVG

(JIFFIES_TO_NS(MAX_SLEEP_AVG))

kernel/sched.c +0 -4

-#define CREDIT_LIMIT		100
-
-/*
- * If a task is 'interactive' then we reinsert it

in the active
- * array after it has expired its current
timeslice. (it will not
- * continue to run immediately, it will still
roundrobin with
- * other interactive tasks.)
- *
- * This part scales the interactivity limit
depending on niceness.
- *
- * We scale it linearly, offset by the
INTERACTIVE_DELTA delta.
- * Here are a few examples of different nice
levels:
- *

- *  TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
- *  TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
- *  TASK_INTERACTIVE(  0): [1,1,1,1,0,0,0,0,0,0,0]
- *  TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
- *  TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]

- *
- * (the X axis represents the possible -5 ... 0 ... +5 dynamic
- * priority range a task can explore, a value of '1' means the
- * task is rated interactive.)
- *
- * Ie. nice +19 tasks can never get 'interactive' enough to be
- * reinserted into the active array. And only heavily CPU-hog nice -20
- * tasks will be expired. Default nice 0 tasks are somewhere between,
- * it takes some effort for them to get interactive, but it's not
- * too hard.
- */

kernel/sched.c +0 -8

-
-#define CURRENT_BONUS(p) \
-	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
-		MAX_SLEEP_AVG)
-
-#ifdef CONFIG_SMP
-#define TIMESLICE_GRANULARITY(p)	(MIN_TIMESLICE * \
-		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) -

1)) * \

kernel/sched.c +0 -4

-			num_online_cpus())
-#else
-#define TIMESLICE_GRANULARITY(p)	(MIN_TIMESLICE * \
-		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) -

1)))

I have had a chance to test this patch.

I have a make
system that has presented 2.6 kernels with problems, so I am using this as the test. Observations show that turning off interactive is much more deterministic:

2.6.7-rc2-bk8-s63:
echo 0 > /proc/sys/kernel/interactive

A:  35.57user 38.18system 1:20.28elapsed 91%CPU
B:  35.54user 38.40system 1:19.48elapsed 93%CPU
C:  35.48user 38.28system 1:20.94elapsed 91%CPU

2.6.7-rc2-bk8-s63:

A:  35.32user 38.51system 1:26.47elapsed 85%CPU
B:  35.43user 38.35system 1:20.79elapsed 91%CPU
C:  35.61user 38.23system 1:25.00elapsed 86%CPU

However, something is still slower than the 2.4.x kernels:

2.4.23:

A:  28.32user 29.51system 1:01.17elapsed 93%CPU
B:  28.54user 29.40system 1:01.48elapsed 92%CPU
B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Nice work, as I can now turn off some functionality within the kernel that is causing me some slow down.

Quoted 1 line · Phy Prabab

I have had a chance to test this patch.

Thanks

Quoted 2 lines

I have a make
system that has presented 2.6 kernels with

problems,

Quoted 1 line

so I am using this as the test. Observations

show

Quoted 18 lines

that turning off interactive is much more deterministic:

2.6.7-rc2-bk8-s63:
echo 0 > /proc/sys/kernel/interactive

A:  35.57user 38.18system 1:20.28elapsed 91%CPU
B:  35.54user 38.40system 1:19.48elapsed 93%CPU
C:  35.48user 38.28system 1:20.94elapsed 91%CPU

2.6.7-rc2-bk8-s63:

A:  35.32user 38.51system 1:26.47elapsed 85%CPU
B:  35.43user 38.35system 1:20.79elapsed 91%CPU
C:  35.61user 38.23system 1:25.00elapsed 86%CPU

However, something is still slower than the 2.4.x kernels:

Quoted 6 lines

2.4.23:

A:  28.32user 29.51system 1:01.17elapsed 93%CPU
B:  28.54user 29.40system 1:01.48elapsed 92%CPU
B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Nice work, as I can now turn off some

functionality

Quoted 1 line

within the kernel that is causing me some slow

down.

Glad to see it does what you require. Turning off "interactive" should still
provide moderately good interactive performance at low to moderate loads, but
is much stricter about cpu usage distribution as you can see.

Cheers,
Con

OOOPPPSSSS....

I need to make a correction on my previous data. I had inadvertantly turned off interactivity and also increased the compute time to 100. I confirmed that just setting interactivity off, does not solve my problem:

2.6.7-rc3-s63 (0 @ /proc/sys/kernel/interactive):

A:  37.30user 40.56system 1:42.01elapsed 76%CPU
B:  37.29user 40.35system 1:23.87elapsed 92%CPU
C:  37.30user 40.56system 1:36.01elapsed 81%CPU

2.6.7-rc3-s63 (0 @ /proc/sys/kernel/interactive & 1 /proc/sys/kernel/compute):

A:  37.28user 40.36system 1:25.60elapsed 90%CPU
B:  37.22user 40.35system 1:22.17elapsed 94%CPU
C:  37.27user 40.35system 1:24.71elapsed 91%CPU

The question here, noticing that user and kernel time are the same, where is the dead time coming from and why is it sooooo much more deterministic with compute time at 100 vs 10? Maybe I am misinterpreting the data, but this suggests to me that something is going awry (ping-pong, no settle, ???) within the kernl?

Also please note the degredation between
2.6.7-rc2-bk8-s63:

A:  35.57user 38.18system 1:20.28elapsed 91%CPU
B:  35.54user 38.40system 1:19.48elapsed 93%CPU
C:  35.48user 38.28system 1:20.94elapsed 91%CPU

Interesting how much more time is spent in both user and kernel space between the two kernels. Also note that 2.4.x exhibits even greater delta:

A:  28.32user 29.51system 1:01.17elapsed 93%CPU
B:  28.54user 29.40system 1:01.48elapsed 92%CPU
B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Could anyone suggest a way to understand why the difference between the 2.6 kernels and the 2.4 kernels?

Thank you for your time.
Phy

Quoted 1 line

Hi.

How repeatable are the numbers normally? Some idea of what it is you're
benchmarking may also help in understanding the problem; locking may be an
issue with what you're benchmarking and out-of-order scheduling is not as
forgiving of poor locking. Extending the RR_INTERVAL and turning off
interactivity makes it more in-order and more forgiving of poor locking or
yield().

Compute==1 setting inactivates interactivity anyway, but that's not really
relevant to your figures since you had set interactive 0 when you set compute
1.

Con

Just to clarify, setting compute 1 implys interactive 0?

These numbers are very reproducable nad have done them (in a continuous loop) for two hours.

The test is a make of headers for a propritary exec. Making headers is rather simple is all it does it link a bunch of h files (traversing dirs) and some dependance generation (3 files, yacc and lex). I have moved the source code base to local disk to dicount nfs issues (though the difference is neglibible and nfs performance on 2.6 is generally faster than 2.4).

I have tried to get a good test case that can be submitted. Still trying.

Any suggestions to try to diagnose this?

Thanks!
Phy

Also please note the degredation between
2.6.7-rc2-bk8-s63:

 A:  35.57user 38.18system 1:20.28elapsed 91%CPU
 B:  35.54user 38.40system 1:19.48elapsed 93%CPU
 C:  35.48user 38.28system 1:20.94elapsed 91%CPU

Interesting how much more time is spent in both user and kernel space between the two kernels. Also note that 2.4.x exhibits even greater delta:

 A:  28.32user 29.51system 1:01.17elapsed 93%CPU
 B:  28.54user 29.40system 1:01.48elapsed 92%CPU
 B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Could anyone suggest a way to understand why the
difference between the 2.6 kernels and the 2.4
kernels?

At a guess I'd say either a) you're hitting some path in the kernel which is going for a giant and bogus romp through memory, trashing CPU caches or
b) your workload really dislikes run-child-first-after-fork or c) the page allocator is serving up pages which your access pattern dislikes or d) something else.

Quoted 6 lines · Andrew Morton

At a guess I'd say either a) you're hitting some path in the kernel which is going for a giant and bogus romp through memory, trashing CPU caches or
b) your workload really dislikes run-child-first-after-fork or c) the page allocator is serving up pages which your access pattern dislikes or d) something else.

e) it's the staircase scheduler patch?

Could anyone suggest a way to understand why the
difference between the 2.6 kernels and the 2.4
kernels

Quoted 1 line · Andrew Morton

At a guess I'd say either a) you're hitting some

path in the kernel which

Quoted 1 line

is going for a giant and bogus romp through

memory, trashing CPU caches or

Quoted 1 line

b) your workload really dislikes

run-child-first-after-fork or c) the page

Quoted 1 line

allocator is serving up pages which your access

pattern dislikes or d)

Quoted 2 lines

something else.

e) it's the staircase scheduler patch?

Quoted 12 lines · Phy Prabab

Also please note the degredation between
2.6.7-rc2-bk8-s63:

 A:  35.57user 38.18system 1:20.28elapsed 91%CPU
 B:  35.54user 38.40system 1:19.48elapsed 93%CPU
 C:  35.48user 38.28system 1:20.94elapsed 91%CPU

Interesting how much more time is spent in both user and kernel space between the two kernels. Also note that 2.4.x exhibits even greater delta:

Quoted 7 lines

 A:  28.32user 29.51system 1:01.17elapsed 93%CPU
 B:  28.54user 29.40system 1:01.48elapsed 92%CPU
 B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Could anyone suggest a way to understand why the
difference between the 2.6 kernels and the 2.4
kernels?

This is very very bad.

It's a uniprocessor machine, yes?

Could you describe the workload a bit more? Is it something which others can get their hands on?

It spends a lot of time in the kernel for a build system. I wonder why.

At a guess I'd say either a) you're hitting some path in the kernel which is going for a giant and bogus romp through memory, trashing CPU caches or
b) your workload really dislikes run-child-first-after-fork or c) the page allocator is serving up pages which your access pattern dislikes or d) something else.

It's certainly interesting.

Quoted 9 lines · Phy Prabab

Also please note the degredation between
2.6.7-rc2-bk8-s63:

 A:  35.57user 38.18system 1:20.28elapsed 91%CPU
 B:  35.54user 38.40system 1:19.48elapsed 93%CPU
 C:  35.48user 38.28system 1:20.94elapsed 91%CPU

Interesting how much more time is spent in both

user

Quoted 1 line

and kernel space between the two kernels. Also

note

Quoted 9 lines

that 2.4.x exhibits even greater delta:

 A:  28.32user 29.51system 1:01.17elapsed 93%CPU
 B:  28.54user 29.40system 1:01.48elapsed 92%CPU
 B:  28.23user 28.80system 1:00.21elapsed 94%CPU

Could anyone suggest a way to understand why the
difference between the 2.6 kernels and the 2.4
kernels?

This is very very bad.

It's a uniprocessor machine, yes?

Could you describe the workload a bit more? Is it something which others
can get their hands on?

It spends a lot of time in the kernel for a build system. I wonder why.

At a guess I'd say either a) you're hitting some path in the kernel which
is going for a giant and bogus romp through memory, trashing CPU caches or
b) your workload really dislikes run-child-first-after-fork or c) the page allocator is serving up pages which your access pattern dislikes or d)
something else.

It's certainly interesting.

The test case is a build system that links headers (ln -s) and runs bison and flex on a couple of files. strace shows no difference between running on 2.4.23 compared to running on 2.6.7-rc2bk8s63.

Unfortuneately, I can not send this out, but I am trying to get a tet case that will demostrate this.

In the mean time, what can I do to try understand this slowdown?

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

Aims:
- Interactive by design rather than have interactivity bolted on.
- Good scalability.
- Simple predictable design.
- Maintain appropriate cpu distribution and fairness.
- Low scheduling latency for normal policy tasks.
- Low overhead.
- Making renicing processes actually matter for CPU distribution (nice 0 gets
20 times what nice +20 gets)
- Resistant to priority inversion

Hi!

Quoted 8 lines

This is an update of the scheduler policy mechanism rewrite using the infrastructure of the current O(1) scheduler. Slight changes from the original design require a detailed description. The change to the original design has enabled all known corner cases to be abolished and cpu distribution to be much better maintained. It has proven to be stable in my testing and is ready for more widespread public testing now.

Quoted 10 lines

Aims:
- Interactive by design rather than have interactivity bolted on.
- Good scalability.
- Simple predictable design.
- Maintain appropriate cpu distribution and fairness.
- Low scheduling latency for normal policy tasks.
- Low overhead.
- Making renicing processes actually matter for CPU distribution (nice 0 gets
20 times what nice +20 gets)
- Resistant to priority inversion

How do you solve priority inversion?

Can you do "true idle threads" now? (I.e. nice +infinity?)