Multilevel Feedback Queue Scheduling
Chapter Fifty-Three
Syllabus topic Module 1, "CPU Scheduling - Scheduling Algorithms (... Multilevel Feedback Queue Scheduling ...)"
Pages 206 to 209 of 452
In one line
Several queues as in the last chapter, but a process that uses up its whole quantum is moved down to a queue with a longer one, so the scheduler discovers what kind of process it is instead of being told.
Why moving matters
The last chapter's fault was that the classification was permanent and had to be got right in advance. Nobody can get it right in advance: a program may be interactive for an hour and then spend ten minutes computing.
A feedback queue measures rather than classifies. A process that gives the processor up before its quantum expires is behaving like an interactive process and stays high. A process that uses its whole quantum is behaving like a processor bound one and is moved down. Nobody declares anything and the scheduler is never wrong for long.
This is also shortest job first without knowing the burst lengths, which is the deepest thing to say about it: a process with short bursts naturally ends up in the high queue with the short quantum, so short bursts are served first, which is what Chapter forty eight wanted and could not implement.
The rule
| Queues | several, numbered 0 at the top |
| Each queue has | its own quantum, getting longer further down, and its own algorithm |
| A new process enters | the highest queue |
| Uses its whole quantum | it is demoted one queue |
| Gives the processor up early | it stays where it is, or is promoted |
| The bottom queue | usually first come first served, with no demotion below it |
| Scheduling between queues | the highest non empty queue is served |
The parameters a designer must choose
An examination question often asks what defines a multilevel feedback queue, and the answer is this list of six.
- The number of queues.
- The scheduling algorithm for each queue.
- The method used to decide when to promote a process.
- The method used to decide when to demote a process.
- The method used to decide which queue a process enters when it needs service.
- Whether and how the processor is shared between the queues.
It is the most general of the algorithms because it has the most parameters, and it is the hardest to tune for the same reason.
Worked in full
Three queues. Queue 0 has a quantum of 4, queue 1 a quantum of 8, and queue 2 is first come first served. Every process enters queue 0 and drops one queue each time it uses its whole quantum.
Schedule: multilevel feedback queue, quanta 4 8, then first come first served
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 17 |
| P2 | 0 | 5 |
| P3 | 3 | 3 |
| Slice | Process | From | To |
|---|---|---|---|
| 1 | P1 | 0 | 4 |
| 2 | P2 | 4 | 8 |
| 3 | P3 | 8 | 11 |
| 4 | P1 | 11 | 19 |
| 5 | P2 | 19 | 20 |
| 6 | P1 | 20 | 25 |
Multilevel Feedback Queue Scheduling
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 25 | 25 | 8 |
| P2 | 20 | 20 | 15 |
| P3 | 11 | 8 | 5 |
Average turnaround time: 53 / 3, about 17.67
Average waiting time: 28 / 3, about 9.33
Context switches: 5
The demotions, traced
This is the table to be able to produce, because it is where the marks are.
| Time | Process | Queue it ran in | Quantum | Used | What happened next |
|---|---|---|---|---|---|
| 0 to 4 | P1 | 0 | 4 | all 4 | demoted to queue 1, with 13 left |
| 4 to 8 | P2 | 0 | 4 | all 4 | demoted to queue 1, with 1 left |
| 8 to 11 | P3 | 0 | 4 | 3 of 4 | finished inside its quantum, so it never dropped |
| 11 to 19 | P1 | 1 | 8 | all 8 | demoted to queue 2, with 5 left |
| 19 to 20 | P2 | 1 | 8 | 1 of 8 | finished |
| 20 to 25 | P1 | 2 | none | 5 | finished at the bottom |
Read P3's row. It arrived at 3, ran at 8, needed only 3 units and finished inside its quantum, so it was never demoted and never waited behind the long process's later slices. A short process is served quickly without anybody declaring it short, which is the whole purpose of the algorithm.
And read P1's three rows. It was demoted twice, so it ran in all three queues, and in the bottom one it got a long uninterrupted stretch. A processor bound process ends up where switching costs least, which is Chapter fifty one's complaint about round robin, fixed.
Starvation, and the promotion that prevents it
A long process sinks to the bottom queue. If short processes keep arriving, the top queue is never empty and the bottom one is never served. Demotion alone starves long processes.
Two standard remedies:
| Remedy | What it does |
|---|---|
| Promotion by ageing | a process that has waited too long in a low queue is moved up |
| Periodic boost | every so often, every process is put back into the top queue |
The second is what several real systems do, because it is simple and it cannot be got wrong: no process can be forgotten for longer than the boost interval, which is bounded waiting with a number again.
There is a cheat to know about: a process that deliberately gives the processor up just before its quantum expires stays in the top queue for ever and gets more than its share. Real schedulers count the processor time a process has used rather than only whether it finished its quantum, exactly to close that hole.
Distinctions that carry marks
| Multilevel queue | Multilevel feedback queue | |
|---|---|---|
| Processes move | never | yes, by demotion and promotion |
| Classification | given in advance | measured while running |
| Quantum per queue | may be the same | longer further down |
| Approximates | nothing | shortest job first, without knowing the bursts |
| Starvation | of the lower queues | of long processes, fixed by promotion or a boost |
Multilevel Feedback Queue Scheduling
| Demotion | Promotion | |
|---|---|---|
| Happens when | a process uses its whole quantum | it has waited too long, or on a periodic boost |
| Means the process is | processor bound | in danger of starving |
| Effect | longer quantum, lower priority | shorter quantum, higher priority |
What it does not mean
The quantum does not get shorter further down. It gets longer, so that a process which needs a lot of processor gets it in fewer, larger pieces and pays less switching.
A demotion is not a punishment. It is the scheduler learning what the process is, and the bottom queue is the right place for a long computation.
It is not the same as ageing in Chapter fifty. Ageing changes a priority number; here the process changes queue, which also changes its quantum and its algorithm.
Quick revision
- A multilevel feedback queue has several queues with increasing quanta, a new process
starting at the top, and demotion when a process uses its whole quantum.
- It measures behaviour instead of accepting a classification, and it
approximates shortest job first without knowing any burst length.
- Six parameters define one: the number of queues, each queue's algorithm, when to promote, when
to demote, which queue a process enters, and how the processor is shared between the queues.
- A process that finishes inside its quantum is never demoted, so short processes stay fast.
- A process that is demoted twice runs in the bottom queue in long uninterrupted stretches, where
switching costs least.
- Demotion alone starves long processes. The remedies are promotion by ageing or a
periodic boost of everybody to the top queue.
- A process can cheat by yielding just before its quantum expires, so real schedulers count
processor time used.
Test yourself
- How does a multilevel feedback queue differ from a multilevel queue? Processes move
between the queues according to how they behave, instead of staying in a queue fixed when they started.
- When is a process demoted, and what does that say about it? When it uses up its whole
quantum, which means it is processor bound rather than interactive.
- Why do the quanta get longer further down? So that a process needing a lot of processor
time gets it in fewer, larger pieces and pays less context switching.
- In what sense does it approximate shortest job first? Processes with short bursts finish
inside the short quantum of the top queue and stay there, so short bursts are served first without any burst length being known.
Multilevel Feedback Queue Scheduling
- Name the six parameters that define one. The number of queues; the algorithm for each
queue; the method for promoting a process; the method for demoting one; the method that decides which queue a process enters; and how the processor is divided between the queues.
- What starves, and what are the two remedies? Long processes, which sink to the bottom
queue and are never reached while higher queues have work. The remedies are promotion by ageing and a periodic boost of every process to the top queue.
- How can a process cheat this scheduler, and how is that closed? By giving the processor up
just before its quantum expires, so it is never demoted. Real schedulers count the processor time a process has actually used rather than only whether it finished its quantum.
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.