Multilevel Queue Scheduling
Chapter Fifty-Two
Syllabus topic Module 1, "CPU Scheduling - Scheduling Algorithms (... Multilevel Queue Scheduling ...)"
Pages 203 to 205 of 452
In one line
Divide the processes into classes, give each class a queue of its own with its own algorithm, and always serve the most important queue that is not empty.
Why one queue is not enough
Chapter forty three said that input and output bound and processor bound processes want opposite treatment. One queue and one algorithm must treat them the same, and whichever algorithm is chosen is wrong for one of them.
A multilevel queue keeps them apart and treats each properly. That is the whole idea, and it is the answer to the question of why a system would have more than one ready queue.
The rule
| Processes are divided into | classes, by a property that does not change |
| Each class has | its own queue and its own scheduling algorithm |
| Between queues | a fixed priority: the highest non-empty queue is served |
| A process | stays in its queue for life |
| Preemptive between queues | yes, usually: a process arriving in a higher queue throws the running one off |
A process never moves between queues, and that is what distinguishes this from the next chapter. If the classification was wrong, it stays wrong. That single sentence answers the commonest examination question on the pair.
A typical arrangement
The classic five queue example, highest priority first.
| Queue | Holds | Algorithm | Why |
|---|---|---|---|
| 0 | system processes | round robin, short quantum | must respond, and are trusted |
| 1 | interactive processes | round robin, short quantum | a person is waiting |
| 2 | interactive editing | round robin | a person is waiting, less urgently |
| 3 | batch processes | first come first served | nobody is waiting |
| 4 | student processes | first come first served | they can wait |
Each queue's algorithm is chosen for what is in it: round robin where response matters, first come first served where it does not and the switching would be waste.
Two ways to share between queues
The choice is examined and both answers are legitimate.
Fixed priority, or absolute priority. The highest non-empty queue is served, always. Simple, and it starves the lower queues: while any interactive process is ready, a batch process never runs.
Time slice between queues. Each queue is given a percentage of the processor: for example 80 per cent to the foreground queue and 20 per cent to the background one. Nothing starves, and the guarantee is weaker: a foreground process may wait while the background queue takes its share.
Worked in full
Four processes. P1 and P3 are interactive and belong in queue 0, run round robin with a quantum of
- P2 and P4 are batch and belong in queue 1, run first come first served. Queue 0 has absolute
priority.
Schedule: multilevel queue, queue 0 round robin quantum 3, queue 1 first come first served
Multilevel Queue Scheduling
| Process | Arrival | Burst | Queue |
|---|---|---|---|
| P1 | 0 | 6 | 0 |
| P2 | 0 | 8 | 1 |
| P3 | 1 | 4 | 0 |
| P4 | 2 | 5 | 1 |
| Slice | Process | From | To |
|---|---|---|---|
| 1 | P1 | 0 | 3 |
| 2 | P3 | 3 | 6 |
| 3 | P1 | 6 | 9 |
| 4 | P3 | 9 | 10 |
| 5 | P2 | 10 | 18 |
| 6 | P4 | 18 | 23 |
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 9 | 9 | 3 |
| P2 | 18 | 18 | 10 |
| P3 | 10 | 9 | 5 |
| P4 | 23 | 21 | 16 |
Average turnaround time: 57 / 4 = 14.25
Average waiting time: 34 / 4 = 8.50
Context switches: 5
Read the chart in two halves.
- From 0 to 10, only queue 0 runs. P1 and P3 take turns of three units. P2 and P4 are ready
the whole time and are never chosen, because queue 1 is only served when queue 0 is empty.
- From 10 onwards, queue 0 is empty, so queue 1 runs, first come first served: P2 then P4.
P4 arrived at 2 and started at 18. Sixteen units of waiting for five units of work, because of a classification it cannot change.
Starvation, and what fixes it
Absolute priority between queues starves the lower queues, and it is not a subtle failure: if interactive processes keep arriving, a batch process never runs at all. Three answers, and a question may want any of them.
| Answer | What it does | Cost |
|---|---|---|
| Time slice between queues | each queue gets a percentage | a high priority process may wait |
| Ageing | a waiting process's priority improves | needs the priority to be able to change |
| Let processes move between queues | this is the next chapter | more bookkeeping |
Ageing does not fit comfortably here, because a process's queue is supposed to be fixed. That tension is exactly why the multilevel feedback queue was invented.
Distinctions that carry marks
| Priority scheduling | Multilevel queue | |
|---|---|---|
| Structure | one queue, ordered by priority | several queues, each with its own algorithm |
| Within a priority level | first come first served | whatever that queue's algorithm is |
| Chosen for | urgency | the kind of process |
| Multilevel queue | Multilevel feedback queue | |
|---|---|---|
| A process moves between queues | never | yes, on its behaviour |
| Classification | permanent, and set when the process starts | discovered while it runs |
| If the classification is wrong | it stays wrong | it corrects itself |
What it does not mean
The queues are not priority levels of one queue. Each has its own algorithm, which a priority level does not.
A multilevel queue does not measure processes. It classifies them once, by what they are, not by what they do. Measuring is the next chapter.
Absolute priority is not always wrong. For a real time queue above everything else it is exactly right: a brake controller must not wait behind an editor.
Multilevel Queue Scheduling
Quick revision
- A multilevel queue divides processes into classes, gives each class its own queue
and its own algorithm, and serves the highest non empty queue.
- A process never leaves its queue.
- The classic arrangement: system, interactive, interactive editing, batch, student, with round
robin above and first come first served below.
- Sharing between queues is either absolute priority, which starves the lower queues, or a
time slice per queue, for example 80 per cent to the foreground and 20 to the background.
- Measured here: with absolute priority, the batch process P4 waited sixteen units for five units
of work and the two interactive processes finished first.
- The fix for the starvation is a time slice per queue, ageing, or letting processes move, which
is the next chapter.
Test yourself
- What is a multilevel queue? Several ready queues, one per class of process, each with its
own scheduling algorithm, with the scheduler serving the highest priority queue that is not empty.
- What does a process's queue depend on, and can it change? The class it belongs to, decided
when it enters the system, and it cannot change.
- Why does each queue have its own algorithm? Because the classes want different things:
round robin for processes a person is waiting on, first come first served for batch work where switching is only overhead.
- Give the two ways of sharing the processor between queues, with a fault of each. Absolute
priority, which starves the lower queues; and a time slice per queue, under which a high priority process may wait while a lower queue takes its share.
- Give the classic five queue arrangement. System processes, interactive processes,
interactive editing, batch processes, student processes, in that order of priority.
- What is the essential difference from a multilevel feedback queue? A process never moves
between queues here, so a wrong classification stays wrong; in a feedback queue it moves according to its behaviour.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.