Operating systems

The Multi-Level Feedback Queue

Prashanth L.A.

2023-08-22

Lecture 8 continues here

How to schedule without perfect knowledge?

Multi-Level Feedback Queue (MLFQ)
To optimize turnaround time, run shorter jobs first
to make system feel responsive to interactive users, use time slice scheduling

MLFQ in words

MLFQ has a number of distinct queues, each assigned a different priority level
A job that is ready to run is on a single queue
- A job on a higher queue is chosen to run.
- Use RR among jobs in the same queue

Rule	Description
Rule 1	If Priority(A) \(>\) Priority(B), A runs
Rule 2	If Priority(A) \(=\) Priority(B), A and B run in RR

MLFQ in 1000 words worth

Problems

Alternate between A and B
Ignore C and D

First fix

Vary the priority of a job
Workload has two job types
- Short running: relinquishes the CPU (e.g. for I/O)
- Long running: A job uses the CPU intensively

More on the first fix: How to change priority

Rule	Description
Rule 3	When a job enters the system, it is placed at the highest priority
Rule 4a	If a job uses up an entire time slice while running, its priority is reduced
Rule 4b	If a job gives up the CPU before the time slice is up, it stays at the same priority level

Example 1: A long-running job

Enter at highest priority and then go down

Example 2: Along Came a Short Job

Main idea

assume a new job might be a short one and give it high priority.
- If it indeed short, then no worries
- If not, it will slowly move down the queues
This way MLFQ approximates SJF

Example 3: Jobs with I/O

MLFQ keeps B at the highest priority because B keeps releasing the CPU;
if B is an interactive job, MLFQ further achieves its goal of running interactive jobs quickly

Problems

Starvation

Too many interactive jobs consuming all CPU time. Long running jobs don’t ever run

Games processes play

Before time slice is over, issue an I/O operation
Give up CPU and stay in the same queue

The name of the process is change

If a CPU-intensive process becomes interactive, its schedule won’t change

Lecture 9 starts here

Second fix: Boosting the priority

Rule	Description
Rule 5	After some time period \(S\), move all the jobs to the topmost queue

Does this solve starvation problem?

Does this address process name change?

Does this address gaming?

Example 4: Jobs with I/O

Left figure: No priority boost, long-running job suffers
Right figure: With priority boost, long-running job gets some CPU

Does new Rule 4 solve some problems?

Does this solve starvation problem?
Yes

Does this address process name change (CPU-bound \(\rightarrow\) I/O bound)?
Yes

Does this prevent gaming by timing I/O?
No

Last fix: Track process usage

Rule	Description
Rule 4	Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced

Left figure: No Rule 4
Right figure: Track process usage and push it downward

Regardless of the I/O behavior of the process, it slowly moves down the queues \(\Rightarrow\) cannot gain an unfair CPU share

Tuning MLFQ

How many queues should there be?
How big should the time slice be per queue?
How often should priority be boosted in order to solve avoid starvation, etc?

No easy answers, try different workloads to tune MLFQ

Varying timeslices

Higher queues \(\rightarrow\) lower timeslices and vice-versa

Summary

Rule	Description
Rule 1	If Priority(A) \(>\) Priority(B), A runs
Rule 2	If Priority(A) \(=\) Priority(B), A and B run in RR.
Rule 3.	When a job enters the system, it is placed at the highest priority
Rule 4	Once a job uses up its time allotment at a given level, its priority is reduced
Rule 5	After some time period \(S\), move all the jobs to the topmost queue