lkml.org 
[lkml]   [1998]   [Oct]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: a different approach to scheduling issues
On Thu, 1 Oct 1998, Rik van Riel wrote:

> 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/

\
 
 \ /
  Last update: 2005-03-22 13:44    [W:0.062 / U:1.152 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site