8 - Multi-Level Feedback Queue Flashcards
(43 cards)
Where was MLFQ first described and by who?
In 1962, by Corbato in a Compatible Time-Sharing System, CTSS
What two problems does MLFQ address?
Optimize turnaround time & minimize response time by making a system feel responsive to interactive users.
In what situations does MLFQ work?
where jobs have behavioral phases and are predictable
Is MLFQ 100% trustworhy?
No, it can easily be wrong and drive a system to make worse decisions than they would’ve with no knowledge at all.
MLFQ has a number of what type of queues?
distinct queues
What is each queue assigned?
a different priority level
How does MLFQ decide which job to run at a given time?
uses priorities
What if more than one job is on a given queue, meaning they have the same priority?
Use round-robin scheduling.
How does the MLFQ scheduler set priorities?
first word is a verb
Varies the priority of a job based on its observed behavior.
How does the MLFQ predict a process’s future behavior?
Learns about the process as it runs and uses the history of the job to predict the future behavior.
What is allotment?
the amount of time a job can spend at a given priority level before the scheduler reduces its priority
How does MLFQ try to approximate SJF?
It first assumes the job is short, giving it high priority. If the assumption is right, it runs and completes quickly. If the assumption is wrong, it will slowly move down the queues, proving to be a long-running process.
What are the three problems with ‘current’ MLFQ?
Starvation, Possibility of gaming the scheduler, A program may change its behavior over time.
Explain ‘Starvation’.
If there are “too many” interactive jobs in the system, they will consume ALL cpu time and long-running jobs will never receive any CPU time.
Explain ‘The Possibility of Gaming the Scheduler’.
Something sneaky can trick the scheduler into giving you more than your fair share of the resource.
An example of a GTS attack.
Before the allotment is issued, issue an I/O operation and relinquish the CPU. This allows us to remain in the same queue and gain a higher percentage of CPU time. If done right, a job could nearly monopolize the CPU.
Explain ‘A program may have change its behavior over time.’
what was CPU bound may transition to a phase of interactivity.
What is rule 5?
After some time period S, move all the jobs in the system to the topmost queue.
What problems does Rule 5 solve?
Processes are guaranteed to not starve;
If a CPU-bound job becomes interactive, the scheduler treats it properly once it has received the priority boost
How are processes guaranteed to not starve?
job/jobs/service
By sitting in the top queue, a job will share the CPU with other H-P jobs in a R-R fashion, and thus eventually receive service
What happens if time period S is set too high or too low?
If too high, long-running jobs could starve. If too low, interactive jobs may not get a proper share of the CPU.
What is Ousterhout’s Law?
S values are often left unmodified, and thus we are left to hope that the defaults work well in the field.
What should we do if we let a job retain its priority by relinquishing the CPU before its allotment expires?
Perform better accounting of the CPU time at each level of the MLFQ
What happens once a process has used its allotment?
continuation…
Whether in one burst, or many small bursts, it is demoted to the next priority queue.
