chapter 8 - Scheduling: The Multi-Level Feedback Queue Flashcards
what is MLFQ designed to do
- prioritize interactive jobs
- de-prioritize CPU-bound jobs
- adjust priorities dynamically based on behavior
How does MLFQ structure its queues?
As multiple priority levels — higher queues run first
What happens to jobs that use the CPU for a full time slice?
They are demoted to a lower priority queue
What is Rule 3 in MLFQ?
New jobs start at the highest priority
rule 4a
If a job uses its full time slice, it gets demoted
rule 4b
If a job gives up the CPU early, it stays at the same level
new rule 4
A job is demoted after it has used its total CPU time allowance at a level, even if it gives up the CPU early many times
what is the convoy effect avoided by MLFQ
MLFQ prevents short jobs from being stuck behind long ones
problems with basic MLFQ
- Starvation: Long-running jobs might never run
- Gaming: Jobs can exploit the rules to stay at high priority
- Changing behavior: Jobs never get promoted again even if they become interactive
What is Rule 5
Every S ms, move all jobs to the top queue
Why use a priority boost?
- Prevent starvation
- Give CPU-bound jobs another chance
- Handle behavior changes
What happens during a priority boost?
Every job is temporarily treated like a new high-priority job
How does better accounting (Rule 4) improve fairness?
It tracks total time used, not just per-slice behavior, to detect abuse
What is “gaming the system” in MLFQ?
When a program avoids demotion by giving up the CPU just before the time slice ends
How does MLFQ prevent gaming?
By tracking total CPU time at a level — even early exits count toward the quota
What happens if a job gives up the CPU early many times?
It will still be demoted once it exceeds the total time threshold
Why give longer time slices to lower-priority queues?
To reduce context switch overhead for CPU-heavy jobs
