Attempt #1: How To Change Priority
Understand how the Multi-Level Feedback Queue (MLFQ) scheduling algorithm adapts job priorities based on runtime behavior. Explore examples showing how MLFQ balances short interactive jobs with longer CPU-bound processes. Learn about challenges like starvation and gaming the scheduler, and why secure scheduling policies are critical to system fairness and performance.
We'll cover the following...
We now must decide how MLFQ is going to change the priority level of a job (and thus which queue it is on) over the lifetime of a job. To do this, we must keep in mind our workload: a mix of interactive jobs that are short-running (and may frequently relinquish the CPU), and some longer-running “CPU-bound” jobs that need a lot of CPU time but where response time isn’t important.
Here is our first attempt at a priority-adjustment algorithm:
-
Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
-
Rule 4a: If a job uses up an entire time slice while running, its priority is reduced (i.e., it moves down one queue).
-
Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same priority level.
Example 1: a single long-running job
Let’s look at some examples. First, we’ll look at what happens when there has been a long-running job in the system. The figure below shows what happens to this job over time in a three-queue scheduler.
As you can see in the example, the job enters at the highest priority (Q2). After a single time-slice of 10 ms, the scheduler reduces the job’s priority by one, and thus ...