On optimising the scheduler for large run queues

[Jamie Lokier]

I will summarise.

  Heavyweight kernel developers (no that doesn't mean >40 years old :-)
  believe that, for all well designed real applications, scheduler
  overhead is dominated by cache overhead.  Therefore optimising cache
  overhead takes priority.

I agree.  Though I personally do not have figures to support it, I have
the impression that others do.

  Adding code to the scheduler is not worthwhile unless there is a
  demonstrable benefit in a real application.

It is difficult to demonstrate.  Everyone is designing their
applications around the assumption that scheduler overhead is
significant and should be avoided.  Some even use user-space scheduling.

  Multi-threaded I/O can be reduced to select() I/O.

This isn't true for Java at the application level.  You might call it a
flaw in Java itself, and it probably is for now[1].  But there isn't a
better alternative yet.  Rewriting Java "business objects" in C is not
plausible.  User space threading is often a better idea in Java.  If
they worked perfectly run queues would not be an issue, but user space
threads introduce their own overheads.[2]  Maybe dynamic compilers
should try dynamically optimising thread switches outside the kernel.

  Real applications that are fully optimised for performance do not have
  large run queues.

Apparently this is true.

  Therefore optimising the scheduler for large run queues, at a cost for
  small run queues (in maintenance, footprint and overhead) is
  counterproductive for the most critical cases.

Here is a logical reasoning error.[3]  By the kernel heavyweights.

The overhead of a scheduler changes is *only* relevant to high switching
rate applications.  And that doesn't include purely select() based
single-threaded monolithic servers.

No-one has shown any real, well designed, well tuned, short run queue
applications that have a high switching rate!

They certainly haven't used such examples in their arguments!  They've
used other examples.  That's why it's a reasoning error: Those examples
aren't relevant!

Now, I expect there are examples of real, well designed, well tuned
applications that switch very often.

Until someone demonstrates that *those* applications have small run
queues, and only those, then we have to consider the large run queue
patches seriously.  Remember the other applications, including
single-threaded, SIGIO-optimised, mmapping hyper-tuned servers, are
unaffected by scheduler changes.

This is because loaded hyper-tuned servers don't schedule at all.
And under partial load, the schedule to and from idle isn't important.
It is absorbed.

All the above means that the argument over whether to handle large run
queues properly has not been properly settled.  The answers have not
answered the questions.

    ----

  The Java folks have hypothesised that Java servers need good large run
  queue performance.

I hypothesise that good user space scheduling support would be just as
effective.[1]  This means there is alternative approach to improving Java
performance which should be looked at.

But as for the scheduler optimisation, that's an indicator in favour of
it.  Attempting to counter that:

  The kernel developers have noted that run queues are usually small,
  and always small for performance-tuned application.

Dear experienced kernel developers, please give examples of real world
application, properly written for performance (as you like), that would
be adversely affected by the proposed scheduler changes.

and have a radiant day,
-- Jamie


[1] I think it would be good if the kernel included a few nice and
general things to aid user space threads, but... another time.  Or
search the archives.

[2] Such as the CPU having nothing to do when a thread swaps, and
complicated schemes for doing all I/O in a scalable way.

[3] In corporate serfdom this is widely thought to be the natural result
of an "entrenched attitude".

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo en vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/