nice handling in ULE (was: Re: SCHEDULE and high load
dillon at apollo.backplane.com
Fri Aug 13 23:24:47 PDT 2004
: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.
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.
More information about the freebsd-current