Re: a different approach to scheduling issues

Mathew G Monroe (mmex+@andrew.cmu.edu)
Thu, 1 Oct 1998 19:12:56 -0400 (EDT)

Excerpts from internet.computing.linux-kernel: 1-Oct-98 Re: a different
approach to.. by Ben Kosse@thecreek.com
>
> > It is nice to optimise the scheduler, but maybe
> > having a "run" queue to parse is the main problem.
> > How about having an "ordered" queue, where the
> > next active process is the head of the queue, and
> > deciding to reorder the queue when an event is
> > signaled ?
> While that may be a good thing (I think it is), it
> won't be as much of a pancea as it sounds. You see,
> by using an ordered queue, you simply push the time
> sink to a different location in the stream (from
> "pick the process" time to "where does the process
> go" time). Unfortunately, both those have to be
> done by the kernel.
>
> However, unless your system is heavily CPU bound,
> you typically won't have more than 2-3 processes on
> a run queue (and that might be stretching it, even).
> However, an ordered queue might be interesting.
>

exactly I wrote a new scheduler for of Linux about 4 years ago based on
a heap strcuture for processes. It ended up being significantly slowwer
then a simple list method. Though it was faster then the ancient way
when all processes had only one queue, not a processes and a run queue
like today. You used to have to go throught he 20 or 30 or 100
processes sitting around, but that is history.

As a note the current list based method works great on current UP and
N-way SMP with small N. Because the CPU bound loads we work with on
these machines is so low. But I imagine with large N-way SMP machines
this would change. If you got a 64 processor SMP machine, you most
likely would have at least 64 cpu bound tasks. That makes a list not so
good. But, when those types of machines start to become popular we can
worry about that. :) Right now the current method is very good.

Matt

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/