nice handling in ULE (was: Re: SCHEDULE and high load
dillon at apollo.backplane.com
Sat Aug 14 01:14:23 PDT 2004
: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.
Yes, that's how it ought to work. It's precisely the algorithm I used
in several embedded projects in the past, the only difference being
that the fair share scheduling queues in those projects were actually
headless circular queues (the current task always being the 'head' of
the circular queue). When the current task's quantum is lost it is
simply left on the queue and skipped, making the next task the head
which if you think about it magically places the task that ran its
quantum to 0 at the end.
If you do it this way then you can focus all your attention in picking
proper quantums for the tasks on the queue.
In the block/wakeup case the task being woken up is always placed just
after the currently running task, effectively the 'front' of the queue.
This is absolutely essential for any IPC oriented system (with
synchronous messages flying back and forth), which is what those embedded
projects used. I even went so far as to optimizing the blocking case
by letting the thread slide (not removing it from the queue) until the
scheduler saw it again and that it was still blocked. The wakeup case
would check if the thread was already the 'next' thread on the queue
(which was most of the time in an even oriented IPC based system), thus
completely optimizing out both the block/dequeue and the wakeup/requeue
code for the critical path. Those were the days :-)
<dillon at backplane.com>
More information about the freebsd-current