MLFQ: a scheduler that learns from the past and predicts the future.

MLFQ has a number of queues, each of which has different priorities. A ready process is on one of the queues. A job with higher priority is run, and use Round Robin for processes with the same priority (Rule 1 & 2).

When a process enters, it’s at highest priority (Rule 3). if a process doesn’t use up the time slice, scheduler keeps its priority; otherwise it’s downgraded (cos it’s likely to use CPU for too long) (Rule 4a & 4b). In this way, MLFQ approx. SJF.

Problems:

1. Starvation: too many short processes chokes long-running jobs
2. Cheat scheduler: run 99% of slice and then perform IO (gives up CPU).
3. Change behavior: a CPU bound process may become IO bound, and thus the behavior would change.

CPU-intensive (CPU bound): tend to use CPU more and longer.

So here it comes Rule 5: after some time period S, move all jobs to top of the queue. Given an appropriate S, the starvation is solved.

To prevent cheating, rewrite Rule 4: Once a job uses up its time allotment at a given level, its priority is reduced (see P73).

Tuning

Higher priority, shorter slices (~10ms); lower priority, longer slices (~100ms).

Solaris has 60 queues, and elevates priority every 1s

https://www.notion.so/cyp0633/8-Scheduling-The-Multi-Level-Feedback-Queue-cd5a09f4495e4315b814c0da3fdf7351