: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 :-) -Matt Matthew Dillon <dillon_at_backplane.com>Received on Sat Aug 14 2004 - 06:14:23 UTC
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:38:06 UTC