lkml.org 
[lkml]   [1998]   [Oct]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: a different approach to scheduling issues

On 02-Oct-98 Mark H. Wood wrote:
> 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.

Not really. Ignoring the problem that priority numbers are the wrong way of
expressing the relative right to CPU time a process has, scanning 40 run-queue
heads to find a process is much more work than finding the most likely out of a
single short list of processes (and much *much* harder than picking off the
list head if its already sorted). You'll only really start seeing wins when
the number of runnable processes gets very large AND distributed over a wide
range of priorities.

The problem is that interactive tasks tend to have higher priorities than
CPU-bound ones. If you've got a machine with one or more CPU-bound processes,
they spend all their time at relatively low priorities, which means your scan
of the per-priority run-queues will tend to find them last. This is exactly
the wrong behaviour: if you're CPU-bound, you want to spend as much time as
possible running in the process. Interactive processes (= mostly sleeping,
higher priority), on the other hand, get the best response because they're near
the top of the list of run-queues to scan. This is good, but there are better
ways of dealing with it (like Linux now, for example).

If I remember my history right, the multiple run-queue scheduler design
appeared in BSD so they could use a particular Vax instruction to find the next
useful run-queue. As it turned out, as with so many other Vax instructions, it
wasn't such a performance win there, and it hasn't been that great since.

J

-
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.055 / U:1.380 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site