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

On 13 Aug, Matthew Dillon wrote:

>     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.

This makes a lot of sense.

The problem that I'm trying to solve is that CPU-bound threads don't
get allocated CPU time according to their nice values.  ULE attempts to
do this by allocating smaller time slices to threads with larger nice
values.  This strategy is foiled because whenever a running thread is
preempted, it gets put back at then end of the run queue even though it
has not exhausted its time slice.  This causes CPU-bound threads to get
run in an approximately round-robin fashion, with an effective time
slice equal to the interval between preemption events.

It seems like ULE would work properly if threads were always prepended
to the run queue, except when they exhaust their time slice when they
should be put at the end.