linux-kernel-digest V1 #71

[Stephen Satchell]

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 en vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/