The staircase scheduler [LWN.net]

The staircase scheduler

Posted Jun 3, 2004 15:30 UTC (Thu) by gallir (guest, #5735)
In reply to: The staircase scheduler by error27
Parent article: The staircase scheduler

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.

(Log in to post comments)

The staircase scheduler

Posted Jun 4, 2004 2:40 UTC (Fri) by error27 (subscriber, #8346) [Link]

> 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. ;)