From: wissner@perlis.mcs.gvsu.edu (Jim Wissner)
Subject: Linux Scheduling (Was Re: Die Die Die) (long)
Organization: Grand Valley State University, Allendale MI
Date: Mon, 21 Dec 1992 15:55:44 GMT

In article <BzM129.Lp@brunel.ac.uk> cs89rdb@brunel.ac.uk (Roger D Binns) writes:
>Is it possible to improve the console driver to accept a few more
>keystrokes?  Try the following line, and see if you can get control
>of your machine back.  I can't do anything except press the reset
>button on the box.
>
>while true ; do (ping 127.0.0.1 &) ; done
>
>It doesn't run out of processes, but does run out of swap.  It would
>be nice if there was a magical keystroke that could deal with this,
>and kill the process with the highest pid for instance.  I suggest 
>ctrl+alt+ins.
>
>I have had similar 'lockups' while using X, for instance while running
>xv, and a C compiler.  It swaps so much, there is nothing I can do.
>Init doesn't even get scheduled so that it can handle the soft
>ctrl+alt+delete.

The Linux scheduler follows (in general) a round-robin scheduling model,
in that each process initially gets a fixed time quantum.  Of course, if
a process uses up its quantum it is preempted, and if it needs to sleep
while doing some sort of IO, it releases the CPU voluntarily.

It does not, however, pick the next process to schedule in the traditional
manner.  Normally, new processes are put in at the tail of the queue,
and the scheduler picks processes from the head of the queue.
When it's time, the current process is thrown to the tail of the queue
and the scheduler picks the next process.  There is a sense of ordering.

Linux does not follow this order so strictly.  Specifically, new 
processes will get picked right away (the opposite of the above) and
any processes that are woken up and found to have a higher 'priority'
than the current process will preempt the current process (as opposed
to the above, where they wait until their turn comes around again,
regardless of their priority.).  Usually this works quite well:
interactive jobs get a good response time as you would want.

And theoretically, the scheme Linux uses shouldn't allow for starvation
(what you are experiencing) - processes that use their quantum will
'wait' until all other processes have had their chance.  There is,
however, no mechanism to /prevent/ starvation.  This is what I suspect
is happening: you are flooding the system with new processes, and even
if you aren't running out of them, you are still preventing anything
else from getting scheduled.  (Remember, incoming jobs will get an
advantage over existing ones?)  So in effect, you are in an unbreakable
loop.  I suspect also that the same thing is happening (to a lesser
extent) with the xv & gcc.  Particularly if you are 'making' something -
which is continually spawning off new processes.  While this isn't as
bad as your first problem, you can still really hurt some processes.

As part of an independant study, I have re-written the Linux scheduler.
I performed a lot of testing on the current one, and found that for
most things it works extremely well.  However, once you have X going
and start a couple gcc's and some other things (ie, a multi-user
environment) - things can get pretty nasty.  What I have implemented
is a multi-level feedback queue, which currently using only two queues:
a high and a low priority.  (I'm experimenting with three levels).
I've been running it for quite a while now and it [seems to be] quite
stable.  For the most part you don't notice a difference, but when a
bunch of CPU intensive jobs are submitted, there is a noticable
improvement in the response time to incoming interactive jobs.  There
is still quite a bit of tweaking to be done before it is optimal,
I'm sure.  But if you wish to take a look at it and try it out I'd
be happy to give it to you.

>Roger

Jim.