8 - Multi-Level Feedback Queue

Question 1

Where was MLFQ first described and by who?

Answer 1

In 1962, by Corbato in a Compatible Time-Sharing System, CTSS

Question 2

What two problems does MLFQ address?

Answer 2

Optimize turnaround time & minimize response time by making a system feel responsive to interactive users.

Question 3

In what situations does MLFQ work?

Answer 3

where jobs have behavioral phases and are predictable

Question 4

Is MLFQ 100% trustworhy?

Answer 4

No, it can easily be wrong and drive a system to make worse decisions than they would’ve with no knowledge at all.

Question 5

MLFQ has a number of what type of queues?

Answer 5

distinct queues

Question 6

What is each queue assigned?

Answer 6

a different priority level

Question 7

How does MLFQ decide which job to run at a given time?

Answer 7

uses priorities

Question 8

What if more than one job is on a given queue, meaning they have the same priority?

Answer 8

Use round-robin scheduling.

Question 9

How does the MLFQ scheduler set priorities?

first word is a verb

Answer 9

Varies the priority of a job based on its observed behavior.

Question 10

How does the MLFQ predict a process’s future behavior?

Answer 10

Learns about the process as it runs and uses the history of the job to predict the future behavior.

Question 11

What is allotment?

Answer 11

the amount of time a job can spend at a given priority level before the scheduler reduces its priority

Question 12

How does MLFQ try to approximate SJF?

Answer 12

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.

Question 13

What are the three problems with ‘current’ MLFQ?

Answer 13

Starvation, Possibility of gaming the scheduler, A program may change its behavior over time.

Question 14

Explain ‘Starvation’.

Answer 14

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.

Question 15

Explain ‘The Possibility of Gaming the Scheduler’.

Answer 15

Something sneaky can trick the scheduler into giving you more than your fair share of the resource.

Question 16

An example of a GTS attack.

Answer 16

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.

Question 17

Explain ‘A program may have change its behavior over time.’

Answer 17

what was CPU bound may transition to a phase of interactivity.

Question 18

What is rule 5?

Answer 18

After some time period S, move all the jobs in the system to the topmost queue.

Question 19

What problems does Rule 5 solve?

Answer 19

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

Question 20

How are processes guaranteed to not starve?

job/jobs/service

Answer 20

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

Question 21

What happens if time period S is set too high or too low?

Answer 21

If too high, long-running jobs could starve. If too low, interactive jobs may not get a proper share of the CPU.

Question 22

What is Ousterhout’s Law?

Answer 22

S values are often left unmodified, and thus we are left to hope that the defaults work well in the field.

Question 23

What should we do if we let a job retain its priority by relinquishing the CPU before its allotment expires?

Answer 23

Perform better accounting of the CPU time at each level of the MLFQ

Question 24

What happens once a process has used its allotment?

continuation…

Answer 24

Whether in one burst, or many small bursts, it is demoted to the next priority queue.

Question 25

What are things to consider when parameterizing such a scheduler?

Answer 25

how many queues should there be?
how big should the time-slice be per queue?
the allotment?
how often should priority be boosted in order to avoid starvation and account for changes in behavior?

Question 26

High-priority queues are usually given what?

Answer 26

short time slices, comprised of interactive short jobs

Question 27

What do low-priority queues contain?

mention time slices @ end

Answer 27

long-running jobs that are CPU-bound so longer time slices work well.

Question 28

Solaris MLFQ is also known as?

Answer 28

Time-sharing scheduling class or TS

Question 29

What does Solaris MLFQ provide?

Answer 29

a set of tables that determine exactly how the priority of a process is altered throughout its lifetime, how long each time slice is, how often to boost the priority of a job.

Question 30

What are the default values for Solaris MLFQ?

Answer 30

60 queues with slowly increasing time-slice lengths from 20 milliseconds to a few hundred milliseconds and priorities boosted around every second or so.

Question 31

What are the size of the time slices for high-priority queues in Solaris MLFQ?

Answer 31

20 milliseconds

Question 32

What are the size of the time slices for low-priority queues in Solaris MLFQ?

Answer 32

few hundred milliseconds

Question 33

How does FreeBSD work?

Answer 33

Adjusts priorities using mathematical formulae to calculate current priority level of a job, basing it on how much CPU the process has used.

Question 34

In FreeBSD, what does decayed usage provide?

Answer 34

the desired priority boost in a different manner

Question 35

What about other Schedulers?

Answer 35

Some reserve h-p levels for OS work. Others allow some user advice to help set priorities.

Question 36

What help can user or administrators provide the OS so the OS can make a better decision?

Answer 36

hints/advice

Question 37

What do BSD Unix derivatives, Solaris, Windows NT, and subsequent Windows OS use as their base scheduler?

Answer 37

a form of MLFQ

Question 38

MLFQ can deliver excellent overall performance for what?

Answer 38

short-running interactive jobs

Question 39

MLFQ is fair and makes progress for what?

Answer 39

long-running CPU-intensive workloads

Question 40

What is rule 1?

Answer 40

If Priority(A) > Priority(B), A runs and B doesn’t.

Question 41

What is rule 2?

Answer 41

If Priority(A) = Priority(B), A & B run in R-R fashion, using the time-slice/quantum length of the given queue.

Question 42

What is rule 3?

Answer 42

When a job enters the system, it is placed at the highest priority/topmost queue.

Question 43

What is rule 4?

Answer 43

Once a job uses up its time allotment at a given level, its priority level is reduced