> On Thu, 1 Oct 1998, Etienne Lorrain wrote:
>
> > 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 ?
>
> I've thought about it, but it looks as if this
> solution will be more expensive than just scanning
> the queue. The main reasons for this are:
> - processes are often added to the queue for one
> shot of CPU power (eg. your mailreader when you
> read this) and sorting each time is expensive
> - the priorities change quite often (the running
> process' priority is decreased every jiffie)
> - with Richard's RT_queue patch, goodness() has
> become a little more efficient
> - the run queue is very short most of the time,
> walking it is about as expensive as sorting
> each time
This is where multiple run queues shine, with one queue per scheduler
priority level. A change in priority is just being unlinked from one
queue and onto another. Selecting the next process to run means taking
the first process off the highest-priority queue that is not empty. All
the messy decision-making happens "elsewhere". If the "elsewhere" code
maintains a word that points to the highest priority with work to do, you
don't even have to scan for nonempty queues.
-- Mark H. Wood, Lead System Programmer mwood@IUPUI.Edu Some things are not improved when made "graphical". Imagine how crude Kilmer's "Trees" would be if reduced to comic-book form.
- 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/