OSNews

Because *that* is how you do an O(1) scheduler for
a UNIX like system. Not a stupid round robin scheduler
like you were trying to suggest for 2.0!

The classic round robin scheduler I am discussing (the one I mentioned being documented in RSX documentation, very early in this discussion) is an N priority queue round-robin-within-queue scheduler.

It is the one in which no compute-bound penalty is charged but threads which block rather than having a quantum expire are switched to the 'highest priority' queue and those which have a quantum expire are switched to their 'oriignal priority' queue. It does not feature 'real time' priorities. It does feature scheduler pools because it wasn't designed for an SMP in which separate processor pools make sense. The only optimization it uses is a head pointer that remembers which is the highest priority pool that is not empty.

It is as simple to understand and implement as the "O(n) scheduler" implemented by Linus in 1991, and there is no workload with more than a few processes on the run queue for which it is slower, or has a larger cache footprint (either i or d) than the O(n) queue.

OK, mr pedant. It uses dual arrays of 140 queues. Per CPU. Happy?

I'm always happy. You're still wrong, but I'm always happy. You really should go read kern/sched.c more carefully.

"Use a round robin scheduler" is utterly naive and
wrong. *That* would have been a bad engineering choice.


On that we agree. Unfortunately, you keep using my shorthand against me, as if you can't deal with elipses. When I first mentioned the scheduler that I would have used rather than Linus' O(n) scheduler, I mentioned where it was documented. Throughout this discussion, I've called it various things, since we are just having a conversation on a web forum, and I thought you were following my context. But, for the entire time, I have meant the scheduler I described in the first paragraph of this post. It is neither a pure/simple round robin scheduler, nor is it the 2.6 scheduler. It is a better engineering choice for the sort of system that Linus proposed in '91 than the scheduler he opted for.


1. tell me why a round robin scheduler would have been
better than the O(n) scheduler in terms of general
purpose performance (not context switching performance)


See above. The scheduler I meant when I said "classic round robin" is better than"Linus O(n)" because it schedules faster and otherwise has similar properties.


2. tell me how you can design a priority queue based
scheduler with at least 40 priorities (ie. a simple
UNIX model) will be faster than an O(n) model in
"most interactive applications"


Using the queue head optimization described above means that a priority queue based scheduler always knows without searching which process to run. It runs the one the head pointer is pointing to. If you put the idle process in a queue, you don't even have to check for an empty runqueue.

The cost of the optimization is a single test whenever a process is inserted onto a run queue. The win is that no searching is ever done at schedule time.

The interactivity is achieved by placing processes that are preempted on the tail of the queue for their priority when they were selected and placing processes that become runable after blocking on the tail of the highest priority queue when they become runable.

Once again, the cost is a single test, this time at queue insertion time. (It's really two tests, but they happen in different places in the state machine, so only one is ever required: the preempter places a process at the tail of its priority queue, an act which unblocks a thread places the thread at the tail of the highest priority queue.)

Scheduling time becomes fixed O(1) with a very small value for K, and independent of both n and C. (C, you will recall, is the number of priority queues.) Similarly, process insertion is O(1) with small K and independent of n and C.

There is one weakness to this design compared to basic Unix process scheduling on a uniprocessor, and I'll leave it to you to identify it and explain what the basic Unix process scheduler does differently.

If you set C to 2, by the way, the problem mentioned above disappears, and it is better than the O(N) scheduler in all respects for the workload Linus expected in 1991.

>The classic round robin scheduler I am discussing (the
>one I mentioned being documented in RSX documentation,
>very early in this discussion) is an N priority queue
>round-robin-within-queue scheduler.

Sorry, that isn't the classic round robin scheduler.

>>OK, mr pedant. It uses dual arrays of 140 queues. Per
>>CPU. Happy?
>
>I'm always happy. You're still wrong, but I'm always
>happy. You really should go read kern/sched.c more
>carefully.

No, you're wrong. What do you think it uses?

>Using the queue head optimization described above
>means that a priority queue based scheduler always
>knows without searching which process to run. It runs
>the one the head pointer is pointing to. If you put
>the idle process in a queue, you don't even have to
>check for an empty runqueue.
>
>The cost of the optimization is a single test whenever
>a process is inserted onto a run queue. The win is
>that no searching is ever done at schedule time.
>
>The interactivity is achieved by placing processes
>that are preempted on the tail of the queue for their
>priority when they were selected and placing processes
>that become runable after blocking on the tail of
>the highest priority queue when they become runable.
>
>Once again, the cost is a single test, this time at
>queue insertion time. (It's really two tests, but they
>happen in different places in the state machine, so
>only one is ever required: the preempter places a
>process at the tail of its priority queue, an act
>which unblocks a thread places the thread at the tail
>of the highest priority queue.)
>
>Scheduling time becomes fixed O(1) with a very small
>value for K, and independent of both n and C. (C,
>you will recall, is the number of priority queues.)
>Similarly, process insertion is O(1) with small K and
>independent of n and C.
>
>There is one weakness to this design compared to basic
>Unix process scheduling on a uniprocessor, and I'll
>leave it to you to identify it and explain what the
>basic Unix process scheduler does differently.

Wait, before you get carried away, you haven't showed
me a working solution yet. This solution has a far
larger cache footprint and will be slower for a small
number of tasks.

The fact that there are a large number of queues means
there will be a large cache footprint. I can't quite
understand exactly what you're describing... but what
happens when you have run the full quantum of your
"queue head" and want to find the next process to run?
You need to search the priority queues, right?

Maybe you have a list of "next to run" processes,
which means you don't have to search. Well then what
happens when you insert a new process into a priority
with no other processes in it? You have to search.

And suppose you have a single process running. OK, so
no searching, right? Maybe so, but with a dynamic
priority it is going to be wandering around the
priority queues. Cache footprint.

You still haven't shown why it is better than the O(n)
scheduler in all ways, because it quite likely would
be slower due to larger cache footprint at n=small.