Multi-level Feedback Queues

2026-11-18 · virtualisation

notes / Operating Systems / 01_vir

OS

Priority Scheduling1

a good scheduler now needs to do 2 things

  1. minimise response time when necessary
  2. minimise turnaround time, i.e. get the most processes done in a unit time and its got to do this without any of the assumptions we made previously

Most importantly we don't have knowledge of the job length. So what we have to do is estimate the runtime using knowledge of previous runtimes.

Learning From History

The MLFQ is an example of a system that learns from the past to predict the future. Other examples of such systems are hardware branch predictors2 and caching algorithms

Basic Rules

different queues each assigned a different priority level. if multiple jobs are on the same queue i.e. same priority, then round robin (or potentially some other alg) is used. higher priority is run first. i.e.

RULE 1: if Priority(A)>Priority(B) A runs (B doesn't)

RULE 2: If Priority(A)=Priority(B), A and B run in RR (or potentially some other alg)

∴ managing priority is key for mlfq.

it may want to analyse the processes and pass judgement

Consider the trivial example below (no RR)

Job List:
  Job  0: startTime   0 - runTime  10 - priority   2
  Job  1: startTime   0 - runTime   1 - priority   4
  Job  2: startTime   0 - runTime   2 - priority   1
  Job  3: startTime   0 - runTime   1 - priority   0
  Job  4: startTime   0 - runTime   5 - priority   3

Q4: 1
Q3:  44444
Q2:       0000000000
Q1:                 22
Q0:                   3

Final statistics:
  Job  0: startTime   0 - response   6 - turnaround  16
  Job  1: startTime   0 - response   0 - turnaround   1
  Job  2: startTime   0 - response  16 - turnaround  18
  Job  3: startTime   0 - response  18 - turnaround  19
  Job  4: startTime   0 - response   1 - turnaround   6

  Avg  4: startTime n/a - response 8.20 - turnaround 12.00

Attempt #1: Allotted Runtime

create something called allotment -> time allotted to a process at a certain priority before it is shifted down3

RULE 3: When a job enters the system, it is placed at the highest priority

RULE 4: If a job uses up its allotment at a given level, its priority is reduced (regardless of how many times it gives up the CPU)

our mlfq is still incomplete though, and leaves potential for developers to game the system into giving them more resources

Starvation

Starvation occurs when there are "too many" high priority tasks running, this causese them to consume all the CPU time and lower priority processes end up never running Rumor has it when they shut down the IBM7094 at MIT in 1973, they found a process submitted in 1967 that had still not been run

Secure Scheduling

a scheduling policy is also a security concern, if a process is allowed to increase its priority it can cause a denial of service attack and not let anything else run. Linux only allows a non-root process to decrease it's priority. Suppose we said interactive processes stay at the same level in our policy: if an attacker simply made their process more interactive they could theoretically stay at the highest priority indefinitely and starve your other processes

Attempt #2: Aging (The Priority Boost)

to avoid starvation what we can do to help CPU-bound jobs make progress?

RULE 5: The priority boost. After some time period S, move all the jobs in the system to the topmost queue

guarantees that processes won't starve, they will eventually run to completion. This also ensures that if a process becomes interactive later on, once boosted it will be treated with the priority it deserves

Warning

What should the value of S be? this is a difficult question with no simple method to determine a correct answer

Tuning MLFQ and Other Issues

some enhancements/variations can be added

puserpriority=50+pcpu4+2pnice

Where `p_cpu` is incremented every time the system clock ticks while the process is running. However, we also introduce a *decay filter*[^8] to essentially give less weight to older cpu runtimes and focus more on the recent cpu utilisations

pcpu=2load2load+1pcpu+pnice

where load is the average length of the run queue in the last minute. However interactive processes can not accumulate CPU time as above, so the scheduler recomputes their priority when they are awoken

pcpu=[(2load)(2load+1)]psleeptimepcpu

where `p_sleeptime` is the time the process slept in seconds

Summary

Consider this example (same jobs as in the beginning) on an MLFQ with 3 queues, the first with a quantum length of 1, the second with 5, and the third being a standard FIFO queue with aging disabled (i am also ignoring i/o)

❯ python mlfq.py -M 0 -c -Q 1,5,999 -l 0,10:0,1:0,4:0,5:0,2 -n 3
Job List:
  Job  0: startTime   0 - runTime  10 - ioFreq   0
  Job  1: startTime   0 - runTime   1 - ioFreq   0
  Job  2: startTime   0 - runTime   4 - ioFreq   0
  Job  3: startTime   0 - runTime   5 - ioFreq   0
  Job  4: startTime   0 - runTime   2 - ioFreq   0

Q2: 01234
Q1:      0000022233334
Q0:                   0000

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround  22
  Job  1: startTime   0 - response   1 - turnaround   2
  Job  2: startTime   0 - response   2 - turnaround  13
  Job  3: startTime   0 - response   3 - turnaround  17
  Job  4: startTime   0 - response   4 - turnaround  18

  Avg  4: startTime n/a - response 2.00 - turnaround 14.40

Here's another example with a priority boost enabled to demonstrate aging. There is a priority boost every 10 units

❯ python mlfq.py -M 0 -c -Q 1,5,999 -l 0,15:0,1:0,6:0,5:0,12 -n 3 -B 10
Job List:
  Job  0: startTime   0 - runTime  15 - ioFreq   0
  Job  1: startTime   0 - runTime   1 - ioFreq   0
  Job  2: startTime   0 - runTime   6 - ioFreq   0
  Job  3: startTime   0 - runTime   5 - ioFreq   0
  Job  4: startTime   0 - runTime  12 - ioFreq   0

Q2: 01234     0234      0234      4
Q1:      00000    000002    002233 44444
Q0:                                     444

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround  26 # notice the improvement in this process
  Job  1: startTime   0 - response   1 - turnaround   2
  Job  2: startTime   0 - response   2 - turnaround  28 # at the cost of this
  Job  3: startTime   0 - response   3 - turnaround  30 # and this
  Job  4: startTime   0 - response   4 - turnaround  39

  Avg  4: startTime n/a - response 2.00 - turnaround 25.00

Compared to a priority boost every 25 units

Q2: 01234                    04
Q1:      0000022222333344444   0000044444
Q0:                         0            00

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround  39
  Job  1: startTime   0 - response   1 - turnaround   2
  Job  2: startTime   0 - response   2 - turnaround  15
  Job  3: startTime   0 - response   3 - turnaround  19
  Job  4: startTime   0 - response   4 - turnaround  37

  Avg  4: startTime n/a - response 2.00 - turnaround 22.40

Versus the non priority boosted version

Q2: 01234
Q1:      0000022222333344444
Q0:                         000000000444444

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround  33
  Job  1: startTime   0 - response   1 - turnaround   2
  Job  2: startTime   0 - response   2 - turnaround  15
  Job  3: startTime   0 - response   3 - turnaround  19
  Job  4: startTime   0 - response   4 - turnaround  39

  Avg  4: startTime n/a - response 2.00 - turnaround 21.60

Our processes are not very particularly interactive so they don't benefit from being in the highest queue with a small quantum, leading to higher turnaround times



  1. https://www.youtube.com/watch?v=57r9OCN1EfA -> video for everything discussed here↩︎

  2. https://medium.com/@s.ruban2000/branch-prediction-the-silent-clairvoyant-living-inside-the-processor-959557b0fbf5↩︎

  3. different queues/priority levels can have their own different allotted times↩︎

  4. https://pages.cs.wisc.edu/~remzi/solaris-notes.pdf -> Solaris scheduling implementation↩︎

  5. https://pages.cs.wisc.edu/~dusseau/Classes/CS537-F04/Questions/q7.html some questions↩︎

  6. https://www.crystallabs.io/unix-books-papers-videos/The-Design-and-Implementation-of-the-4.3BSD-Unix-OS.pdf pg 87↩︎

  7. https://www.cs.columbia.edu/~nieh/teaching/e6118_s00/papers/p79-patterson.pdf -> an argument for making the os listen to the user more. "informed prefetching and caching"↩︎