Messages in this thread | | | Date | Fri, 2 Oct 1998 13:52:11 -0500 (EST) | From | "Mark H. Wood" <> | Subject | Re: 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/
| |