Re: Linux gets O(1) scheduler

On Sun, Jan 04, 2004 at 05:39:27PM +0000, David Laight wrote:
> It might be nice stopping the scheduler looking at every LWP every timer
> tick though.

Yes, agreed. We knew our scheduler needs a major rewrite for SMP/threading.

I've looked at the ULE paper and it has several interesting points,
of which the "we got rid of some simple data structures from the stone
age that do not scale well today" [i.e. the part O(1) refers to in the Linux
stuff] is only a minor one.

The per physical CPU (ignoring virtual/hyper threaded ones) queues and their
balancing are interesting. I fail to see how the very simple scheme should do
well with scheduling multiple FPU using threads + some non-CPU using ones on
a multi-hyper-threaded-CPU machine though.

Martin
P.S.: I found it funny that the whole paper does not explain the name. I've
never used FreeBSD, so how should I know that options SCHED_4BSD selects the
old scheduler in FreeBSD, while options SCHED_ULE selects the new one.