MLFQ: Basic Rules

To build such a scheduler, in this chapter we will describe the basic algorithms behind a multi-level feedback queue; although the specifics of many implemented MLFQs differ, most approaches are similar“An Analysis of Decay-Usage Scheduling in Multiprocessors” by D.H.J. Epema. SIG- METRICS ’95. A nice paper on the state of the art of scheduling back in the mid-1990s, including a good overview of the basic approach behind decay-usage schedulers..

Priority-based rules

In our treatment, the MLFQ has a number of distinct queues, each assigned a different priority level. At any given time, a job that is ready to run is in a single queue. MLFQ uses priorities to decide which job should run at a given time: a job with higher priority (i.e., a job on a higher queue) is chosen to run. Of course, more than one job may be in a given queue and thus have the same priority. In this case, we will just use round-robin scheduling among those jobs.

Thus, we arrive at the first two basic rules for MLFQ:

• Rule 1: If $Priority(A) > Priority(B)$, $A$ runs ($B$ doesn’t).

• Rule 2: If $Priority(A) = Priority(B)$, $A$ & $B$ run in RR.

The key to MLFQ scheduling, therefore, lies in how the scheduler sets priorities. Rather than giving a fixed priority to each job, MLFQ varies the priority of a job based on its observed behavior. If, for example, a job repeatedly relinquishes the CPU while waiting for input from the keyboard, MLFQ will keep its priority high, as this is how an interactive process might behave. If instead, a job uses the CPU intensively for long periods of time, MLFQ will reduce its priority. In this way, MLFQ will try to learn about processes as they run, and thus use the history of the job to predict its future behavior.

Example

If we were to put forth a picture of what the queues might look like at a given instant, we might see something like the following figure: