Re: linux-kernel-digest V1 #71

From: Stephen Satchell (satch@concentric.net)
Date: Sat Jan 22 2000 - 13:27:20 EST


At 12:54 AM 1/21/00, Peter Rival wrote:
>What kind of scheduling I want? I just want an algorithm that doesn't
>fall apart
>completely when the system is very heavily loaded. And right now, we linearly
>walk the runqueue under a spinlock and re-calculate the goodness of
>everything on
>it every time we call schedule(). While it's not bad on a small system, it's
>horrible on a larger one. I just want something that works well on both my
>workstation and the large servers I work on. Or at the very least, the
>ability to
>switch between them, be it at runtime or compile time. Or someone to show
>me just
>how wrong I am. :)

I'm beginning to think that the people who are asking for proof are
correct. In order to answer the question, though, I believe that we need
to be able to answer the following questions:

1) What is the average and maximum runqueue length for systems running
real applications? It would be good to get numbers for "desktops", "I/O
servers", "computational servers", and portables. You might as well get
numbers for benchmarks, too, because people will be talking about them.

2) How do the elements of goodness change over time? Is there any way to
reduce the number of complete recalculations? (Yes, I'll read the
source. So should everyone else, and then discuss what they find.) Can
the calculations be performed when a task is deselected instead of every
time schedule() is called? Every "n"th schedule in a clock tick or three
or ten?

3) Is there any way to limit the length of the run queue that is
"interesting" to the scheduler?

4) Has the "smash" problem been addressed, where you have a large number
of processes blocked on the same resource, and when that resource becomes
available the number of runnable processes increases dramatically? I
recall how people were working on a change to limit the number of processes
that would actually be made runnable in that situation. In a large-server
environment, I could see how you can easily have several thousand processes
waiting on disk, and the system surges as all of those processes try to
glom onto the disk. (I'm surprised sometimes that some OS schedulers don't
cause the hardware to walk across the floor in that situation.)

(In a real-time system I worked on, the I/O model was to release all
waiting processes, then let the regular scheduler pick which one got to run
and take the resource. Then every process still waiting got its turn to
get back onto the queue. One of the changes we made was to have an I/O
release scheduler, that worked just like the regular scheduler, that would
"pick" the winner and would release that one process and that one
only. The real-time response of the system improved markedly, the
throughput response of the system rose by about 10 percent if I recall, and
several every-other-fortnight bugs stopped completely. Utilization of the
I/O devices went up, too, because when a request would finish early the
system wasn't still trying to sort out the losers.)

Just a pair-o-pennies(tm) to the discussion...

Satch

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



This archive was generated by hypermail 2b29 : Sun Jan 23 2000 - 21:00:28 EST