nice handling in ULE (was: Re: SCHEDULE and high load situations)

[Matthew Dillon]

:The best idea that I can come up with is for sched_add(),
:sched_add_internal(), kseq_runq_add(), and runq_add() to grow another
:parameter that would tell them whether to prepend to the beginning of
:the run queue or append to the end.  If setrunqueue() detects that
:TD_IS_RUNNING(td) is true, it would pass the flag to sched_add() that
:would cause the thread to be added to the beginning of the queue.
:
:I don't know if this is appropriate in the PRI_ITHD and PRI_REALTIME
:cases, or if we want to continue to to round-robin.
:
:Comments?

    I've written and played with schedulers for a very long time, and
    pretty much every time I've tried a insert-at-beginning-or-insert-at-end
    hack it's always introduced more problems then it has solved.

    This isn't to say that one is better then the other, just that having
    a conditional that tries to figure out whether to add at
    the beginning or add to the end is bad in general.  

    The scheduler should be designed either for front-loading or for
    rear-loading.  Typically speaking, a fair-share scheduler (which I
    think ULE is) should be front-loaded.  That is, for any particular 
    priority a thread should be added to the beginning of the run queue (but
    not preempt the currently running thread, just be the next runnable
    thread).  The reason for this is because the thread's fair-share quantum
    calculation is expected to be correct and when it *IS* correct front
    loading almost always yields the best performance.

    A good example of this is a heavily loaded system running, say, a 
    thousand simultanious ssh'd logins.  Whenever a user types over their
    ssh connection you get this sort of pattern:

	sshd reads from socket, writes to pty, blocks
	csh on pty reads from pty, echos char, blocks
	sshd unblocks, reads the echo, and writes it back to the socket.

    Now imagine that situation in an extreme loading situation for both the
    front loading and the rear loading case.

    In the front loading case sshd will get the cpu quickly for both the
    initial read and for the echo response.

    In the rear loading case sshd will have to wait for the entire round 
    robin before it can pass the character to the pty, the csh will have
    to wait before it can read the character and echo it, and sshd will
    have to wait before it can read the echo and return the response.

    Again, that's for a fair-share scheduler, i.e. ULE.

    For something like 4BSD you do NOT usually want to front-load because
    the priority mechanism is expected to reflect the interactivity of the
    process and so the process should get the cpu quickly in the above
    case with rear loading.  Front loading 4BSD could potentially lead
    to starvtion due to the fairly long period of time it takes for a
    process's priority to be reduced (at least 4 ticks).

    A fair share scheduler, on the otherhand, is theoretically capable of
    much finer-grained quantums but also tends to have much longer run 
    queues because it depends on the fair share algorithm to figure out 
    the dynamic quantum more then it depends on multi-queuing priorities.

    I hope that all made sense.  The jist is that if you find yourself 
    trying to optimize a scheduler by guessing whether to add to the front
    or the rear of the queue, it usually means that you've already lost
    the game and are now resorting to hacks to try to fix things.  I
    don't mean that in a bad way, just that it is my own experience that
    that is the case.

						-Matt