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

Matthew Dillon dillon at
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 :-)

					    Matthew Dillon 
					    <dillon at>

More information about the freebsd-current mailing list