Multi Level Feedback Queue

• Key Question: How can struct the scheduling that minimizes response time and turnaround time without having any prior information of the job.

MLFQ Basic Rules

MLFQ is consist of multiple queues which has its own priority level.

1. If priority(A) > priority (B) then execute A
2. If prior(A) == prior(B) then do RR for A and B.

• MLFQ assigns the priority depends on the characteristics of the job; keyboard input waiting…
• If one job maintains the high priority for a long time, lower the level.

3. When a job enters the system, it has the highest priority.
4. 1. a: After use all of its time slice, priority goes lower.
   2. b: Maintain the priority level if it gives up the CPU before the end of its time slice.

Key Points:
* Scheduler do not know if the job is short or not
* So assume it is the short one at first (assign high prior level).
* Therefore, if the job is the short one, it will be finished fast.
* If not, it will slowly move down to the lower prior queue which proves it is a time consuming job.
* By doing so, MLFQ approximates SJF without having prior info.

Problems:

1. Starvation: if there are too many conversational job (which gives up the time slice earlier), lower prior queue tasks will not have a chance to use CPU.
2. Can trick the scheduler: Can program the code intentionally to trick the scheduler, and seize the CPU for a longer time.
3. The job may alter its characteristics later; but not able to have the higher priority disregard to its change.

1. After certain time, system moves all the tasks to the highest queue.
   1. Non starvation is guaranteed.
   2. Altered Jobs (characteristics into interactive) can be treated as intended.

Redefine 4a 4b into one rule to prevent the second problem; gaming of the scheduler.
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).

Other problems/concerns

1. How many queues should there be?
2. How big should the time slice be per queue?
3. How often priority must be reset to avoid starvation?
   There are no definite answer to these concerns.
   There could be different implementation such as alloting different time slice per each priority queue (longer for lower level…).