Summary

We have described a scheduling approach known as the Multi-Level Feedback Queue (MLFQ). Hopefully, you can now see why it is called that: it has multiple levels of queues, and uses feedback to determine the priority of a given job. History is its guide: pay attention to how jobs behave over time and treat them accordingly.

The refined set of MLFQ rules, spread throughout the chapter, are reproduced here for your viewing pleasure:

• 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.

MLFQ is interesting for the following reason: instead of demanding a priori knowledge of the nature of a job, it observes the execution of a job and prioritizes it accordingly. In this way, it manages to achieve the best of both worlds: it can deliver excellent overall performance (similar to SJF/STCF) for short-running interactive jobs, and is fair and makes progress for long-running CPU-intensive workloads. For this reason, many systems, including BSD UNIX derivatives1. “The Design and Implementation of the 4.3BSD UNIX Operating System” by S.J. Leffler, M.K. McKusick, M.J. Karels, J.S. Quarterman. Addison-Wesley, 1989. Another OS classic, written by four of the main people behind BSD. The later versions of this book, while more up to date, don’t quite match the beauty of this one. 2. “The Design of the UNIX Operating System” by M.J. Bach. Prentice-Hall, 1986. One of the classic old books on how a real UNIX operating system is built; a definite must-read for kernel hackers., Solaris“Solaris Internals: Solaris 10 and OpenSolaris Kernel Architecture” by Richard McDougall. Prentice-Hall, 2006. A good book about Solaris and how it works., and Windows NT and subsequent Windows operating systems“Inside Windows NT” by Helen Custer and David A. Solomon. Microsoft Press, 1997. The NT book, if you want to learn about something other than UNIX. Of course, why would you? OK, we’re kidding; you might actually work for Microsoft someday you know. use a form of MLFQ as their base scheduler.