Multi Level Feedback Queue
a good scheduler now needs to do 2 things
- minimise response time when necessary
- 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
Basic Rules
different queues each assigned different priority level. if multiple jobs are on the same queue i.e. same priority, then round robin is used. higher priority is run first. i.e.
RULE 1: if A runs (B doesn’t)
RULE 2: If , A and B run in RR
managing priority is key for mlfq. if a job has a lot of i/o ⇒ frees up the cpu often, it keeps its high priority if it is an intensive background process its priority is reduced
Attempt #1 at changing priority
create something called allotment → time allotted to a process at a certain priority before it is shifted down
RULE 3: When a job enters the system, it is placed at the highest priority (topmost queue)
RULE 4a: If a job uses up its allotment while running, its priority is reduced
RULE 4b: If a job gives up the CPU before the allotment is up, it stays at the same priority level
our mlfq is still incomplete though, and leaves potential for developers to game the system into giving them more resources
issue 1: starvation, too many interactive processes and the lower level longer jobs never get the CPU issue 2: a developer can just add some nonsense i/o calls to ensure they stay at the top level
TIP
scheduling is apparently a major security concern
Attempt #2 at changing priority
to avoid starvation what we can do to help CPU-bound jobs make progress?
RULE 5: The priority boost. After some time period , move all the jobs in the system to the topmost queue
guarantees that processes won’t starve, they will eventually run to completion.
WARNING
What should the value of be? this is a difficult question with no simple method to determine a correct answer
Attempt #3 at changing priority
how do you prevent gaming the system though? the fault lies in 4a/b, which lets a process keep its priority. we have to be less lenient
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
Tuning MLFQ and Other Issues
some enhancements/variations can be added
VARIANT 1: make your time slices longer at lower priority levels VARIANT 2: FreeBSD uses a formula to calculate the current priority of a job based on how much CPU the process has used VARIANT 3: some reserve the topmost levels only for OS processes VARIANT 4: many allow users to adjust the “niceness” of a process
man niceSummary
- Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
- Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
- Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
- 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 (i.e., it moves down one queue).
- Rule 5: After some time period S, move all the jobs in the system to the topmost queue.
[1] https://pages.cs.wisc.edu/~remzi/solaris-notes.pdf → Solaris scheduling implementation
[2] 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”
[3] https://www.youtube.com/watch?v=57r9OCN1EfA → video for everything discussed above