Messages in this thread | | | Date | Sat, 03 Oct 1998 11:47:09 -0700 (PDT) | From | Jeremy Fitzhardinge <> | Subject | Re: 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/
| |