MLFQ: Basic Rules

This lesson outlines the basic rules employed by the MLFQ in running processes and assigning priorities.

We'll cover the following

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)Priority(A) > Priority(B), AA runs (BB doesn’t).

  • Rule 2: If Priority(A)=Priority(B)Priority(A) = Priority(B), AA & BB 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:

In the figure, two jobs (A and B) are at the highest priority level, while job C is in the middle,​ and Job D is at the lowest priority. Given our current knowledge of how MLFQ works, the scheduler would just alternate time slices between A and B because they are the highest priority jobs in the system; poor jobs C and D would never even get to run — an outrage!

Of course, just showing a static snapshot of some queues does not really give you an idea of how MLFQ works. What we need is to understand how job priority changes over time. And that, in a surprise only to those who are reading a chapter from this course for the first time, is exactly what we will do next.

Get hands-on with 1400+ tech skills courses.