LWN: Comments on "The staircase scheduler"

The staircase scheduler

sitaram — Sun, 06 Jun 2004 06:32:47 +0000

> Thus interactive tasks, which normally sleep quite a bit, should stay near
> the top of the staircase and be responsive, while CPU hogs spend much of
> their time on the lower steps.

sounds very much like delay pools in squid, which provide a neat way of penalising bulk downloads while keeping normal "interactive" sufing response good!

[I *have* seen the other posts with extracts from OS books; just want to give a different analogy is all...]

The staircase scheduler

error27 — Fri, 04 Jun 2004 02:40:23 +0000

> Multilevel feedback queues, however, allow a process to move between
queues.

Right. With both the regular scheduler and the stair case scheduler you have 140 queues that represent 140 different priorities. You execute the top priorities first in a round robin format. The trick with the stair case scheduler is the logic behind how the processes move from one queue to the other.

> There are a number of variations on this scheme.

Exactly. In some ways, you could say that this was "just" a new variation. But in other ways, it's a pretty inovative variation. ;)

The staircase scheduler

farnz — Fri, 04 Jun 2004 00:08:33 +0000

The only time a process falls down is if it consumes all its timeslices. Thus, a process that has been placed on the lowest step has consumed n timeslices at each of the priorities Base through Base-n. It can only fall off again if it runs for n timeslices, thus your scenario cannot occur.

The staircase scheduler

gallir — Thu, 03 Jun 2004 15:30:35 +0000

If you read any OS book, it's comprehensively explained. I suppose you
don't expect to give a full description in a "title" :-).

For example, taking an old Peterson/Silberschatz book:

"... Multilevel feedback queues, however, allow a process to move between
queues. The idea is to separate out processes with a different cpu-burts
characteristics. If a process uses too much cpu time, it will be moved to
a lower priority queue. This scheme leaves I/O-bound and interactive
processes in the higher priority queues. Similarly, a process which waits
too long in a lower-priority queue may be moved to a higher priority
queue. This is a form of aging that would pevent starvation. ..."

Or from a Stalling's book:

"... This approach is known as multilevel feedback, meaning that the
operating system allocates the processor to a process, and when the
process blocks or is preempted, feeds it back into one of several queues.
There are a numbre of variations on this scheme. A simple version is to
perform preemption inthe same fashions for round-robin: at periodic
intervals..."

What I mean, a lot of "new methods", for example those applied to CPU and
I/O schedulers are already described, discussed, and compared in the
literature since the '70 or '80s.

The staircase scheduler

mmarsh — Thu, 03 Jun 2004 15:08:41 +0000

It's not obvious in the description, and I haven't looked through the code or any detailed technical docs, but what happens in the following case? Say you have a process that has, through grave misfortune, fallen off of the lowest step and been placed back *on* the lowest step. If there are n steps it'll wait there for n time slices, and if it still hasn't been run it'll fall off again. Does it get placed back on the lowest step as a default? Does it get elevated in priority as compensation for its patience? Can this just not occur (though I'd bet a contrived example could be constructed)? The nightmare scenario is that the scheduler tries to place it below the lowest step, resulting in an array bounds error and a kernel panic.

The staircase scheduler

marduk — Thu, 03 Jun 2004 13:58:04 +0000

This sounds too elegant. And even I can understand it. It can't possibly work! ;-)

The staircase scheduler

error27 — Thu, 03 Jun 2004 05:08:41 +0000

To be honest, the definition of "multilevel feedback queues" is too vague to be worthwhile. The old scheduler fits the definition, and the new scheduler doesn't change that at all. What the new scheduler changes is how the processes move from one queue to the other. The stair case scheduler is pretty inovative actually.

If you want to learn more about the difficult issues for schedulers read Con's write up here.

It's pretty weird to not have an expired array. It seems like a reasonable scheduler design because it obviously gives priority to interactive processes and it doesn't starve any processes. I can see how this would be simpler to code. It's a nice design. I guess the real proof is in testing. :)

The staircase scheduler

gallir — Thu, 03 Jun 2004 01:44:56 +0000

Again... isn't it the same as the old-well-known "multilevel feedback
queues" that appears in every OS book since MULTICS?