Randy Hron posted some additional O(1) scheduler benchmarks [earlier story], this time illustrating how the scheduler patch seems to decrease pipe bandwidth and increase pipe latency. (neither affect is good)

The thread goes on to talk about Davide Libenzi's Balanced Multi Queue Scheduler patch (BMQS). Andrea Arcangeli says of this scheduler (which he has in his -aa kernel tree), "Davide's patch reduces the complexity of the scheduler from O(N) where N is the number of tasks in the system, to O(N) where N is the number of simultaneous running tasks in the system. It's also a simple optimization and it can make responsiveness even better than the mainline scheduler."

The third scheduler mentioned is the MQ, or Linux MultiQue Scheduler. The Linux Showcase & Conference web site offers an informative comparison of the Default SMP Scheduler (DSS), the MultiQueue Scheduler (MQS), and the Pooled MultiQueue Scheduler (PMQS).

From: Randy Hron
Subject: Re: O(1) scheduler gives big boost to tbench 192
Date: 	Fri, 3 May 2002 09:38:56 -0400

> > > Rumor is that on some workloads MQ it outperforms O(1), but it
> > > may be that the latest (post K3?) O(1) is catching up?

Is MQ based on the Davide Libenzi scheduler? 
(a version of Davide's scheduler is in the -aa tree).

> > I'd be interested to know what workloads ?

> AIM on large CPU count machines was the most significant I had heard
> about.  Haven't measured recently on database load - we made a cut to
> O(1) some time back for simplicity.  Supposedly volanomark was doing
> better for a while but again we haven't cut back to MQ in quite a while;
> trying instead to refine O(1).  Volanomark is something of a scheduling
> anomaly though - sender/receiver timing on loopback affects scheduling
> decisions and overall throughput in ways that may or may not be consistent
> with real workloads.  AIM is probably a better workload for "real life"
> random scheduling testing.

tbench 192 is an anomaly test too.  AIM looks like a nice
"mixed" bench.  Do you have any scripts for it?  I'd like 
to use AIM too.

A side effect of O(1) in ac2 and jam6 on the 4 way box is a decrease 
in pipe bandwidth and an increase in pipe latency measured by lmbench:

kernel                    Pipe bandwidth in MB/s - bigger is better
-----------------------  ------
2.4.16                   383.93
2.4.19-pre3aa2           316.88
2.4.19-pre5              385.56
2.4.19-pre5-aa1          345.93
2.4.19-pre5-aa1-2g-hio   371.87
2.4.19-pre5-aa1-3g-hio   355.97
2.4.19-pre7              462.80
2.4.19-pre7-aa1          382.90
2.4.19-pre7-ac2           85.66
2.4.19-pre7-jam6          66.41
2.4.19-pre7-rl           464.60
2.4.19-pre7-rmap13       453.24

kernel                   Pipe latency in microseconds - smaller is better
-----------------------  -----
2.4.16                   12.73
2.4.19-pre3aa2           13.58
2.4.19-pre5              12.98
2.4.19-pre5-aa1          13.46
2.4.19-pre5-aa1-2g-hio   12.83
2.4.19-pre5-aa1-3g-hio   13.08
2.4.19-pre7              10.71
2.4.19-pre7-aa1          13.32
2.4.19-pre7-ac2          31.95
2.4.19-pre7-jam6         29.51
2.4.19-pre7-rl           10.71
2.4.19-pre7-rmap13       10.75

More at:

http://home.earthlink.net/~rwhron/kernel/bigbox.html
--

Randy Hron
From: Gerrit Huizenga

Subject: Re: O(1) scheduler gives big boost to tbench 192

Date: 	Fri, 03 May 2002 13:29:11 -0700
In message Randy Hron writes:

> Is MQ based on the Davide Libenzi scheduler?

> (a version of Davide's scheduler is in the -aa tree).
No - Davide's is another variant.  All three had similar goals

and similar changes.  MQ was the "first" public one written by

Mike Kravetz and Hubertus Franke with help from a number of others.
> tbench 192 is an anomaly test too.  AIM looks like a nice

> "mixed" bench.  Do you have any scripts for it?  I'd like

> to use AIM too.
The SGI folks may be using more custom scripts.  I think there

is a reasonable set of options in the released package.  OSDL

might also be playing with it (Wookie, are you out here?).  Sequent

used to have a large set of scripts but I don't know where those

are at the moment.  I may check around.
> A side effect of O(1) in ac2 and jam6 on the 4 way box is a decrease

> in pipe bandwidth and an increase in pipe latency measured by lmbench:
Not surprised.  That seems to be one of our problems with

volanomark testing at the moment and we have some hacks to help,

one in TCP which allows the receiver to be scheduled on a "close"

CPU which seems to help latency.  Others are tweaks of the

scheduler itself, with nothing conclusively better yet.
gerrit
From: Andrea Arcangeli

Subject: Re: O(1) scheduler gives big boost to tbench 192

Date: 	Sat, 4 May 2002 10:13:45 +0200
On Fri, May 03, 2002 at 01:29:11PM -0700, Gerrit Huizenga wrote:

> No - Davide's is another variant.  All three had similar goals
Davide's patch reduces the complexity of the scheduler from O(N) where N

is the number of tasks in the system, to O(N) where N is the number of

simultaneous running tasks in the system. It's also a simple

optimization and it can make responsiveness even better than the mainline

scheduler.  I know many people is using 2.4 with some thousand tasks

with only a few of them (let's say a dozen of them) running

simultaneously, so while the O(1) scheduler would be even better, the

dyn-sched patch from Davide looked the most attractive for production

usage given its simplicty. I also refined it a little while merging it

with Davide's overview.
Soon I will also get into merging the O(1) scheduler, but first I want

to inspect the interactivity and pipe bandwith effect, at least to

understand why they are getting affected (one first variable could be

the removal of the sync-wakeup, O(1) scheduler needs to get the wakeup

anyways in order to run the task but still we can teach the O(1)

scheduler that it must not try to reschedule the current task after

queueing the new one). In theory dyn-sched would be almost optimal for

well written applications with only 1 task per-cpu using async-io, but

of course in many benchmark (and in some real life environemtn) there

are an huge number of tasks running simultaneously and so dyn-sched

doesn't help much there compared to mainline.
BTW, Randy, I seen my tree runs slower with tiobench, that's probably

because I made the elevator anti-starvation logic more aggressive than

mainline and the other kernel trees (to help interactive usage), could

you try to run tiobench on -aa after elvtune -r 8192 -w 16384

/dev/hd[abcd] to verify? Thanks for the great benchmarking effort.
And for the reason fork is faster in -aa that's partly thanks to the

reschedule-child-first logic, that can be easily merged in mainline,

it's just in 2.5.