Scheduling: The Multi-Level Feedback Queue

The Dual Goals MLFQ Tries to Achieve

A scheduler wants low response time for interactive users while also finishing short jobs quickly to optimize turnaround. The system however rarely knows job durations in advance. MLFQ starts every job at high priority and lowers it only if the job keeps consuming the CPU, thereby inferring future needs from past behavior.

Queues, Rules and Priority Adjustment

Several priority queues are maintained; a newly arriving job is placed in the top queue. Jobs sharing a queue run round-robin. Exhausting the current-level allotment causes demotion; yielding the processor early (for instance to wait for I/O) keeps the present priority. Interactive jobs therefore tend to stay high while CPU-bound jobs sink.

Approximating Shortest Job First and Its Limits

An unknown job is optimistically treated as short and given high priority; if it truly finishes quickly it receives SJF-like service, otherwise it gradually drops. The technique works when jobs exhibit phases, yet too many interactive jobs starve long ones, and a malicious program can game the scheduler by repeatedly running only briefly.

Pitfalls

• A flood of short interactive jobs can starve long-running jobs of any CPU time
• A user can keep high priority unfairly by yielding just before the time slice expires
• Without a periodic boost, jobs that have dropped to the bottom queue may never run again

Minimum C11 · complete program · Download .c

#include <stdio.h>
#define SLICE 4
#define MAXT 25
int main(void) {
    char names[2] = {'A', 'B'};
    int rem[2] = {20, 5};
    int prio[2] = {2, 2};
    int used[2] = {0, 0};
    int arr[2] = {0, 12};
    printf("MLFQ sim: 3 levels, slice=%d\n", SLICE);
    printf("Gantt (A=long CPU, B=short arr@12):\n");
    for(int t=0; t<MAXT; t++) {
        int best=-1, bp=-1;
        for(int i=0; i<2; i++) {
            if(arr[i]<=t && rem[i]>0 && prio[i]>bp) {
                bp=prio[i];
                best=i;
            }
        }
        if(best<0) {
            putchar('.');
            continue;
        }
        putchar(names[best]);
        rem[best]--;
        used[best]++;
        if(used[best]>=SLICE) {
            if(prio[best]>0) prio[best]--;
            used[best]=0;
        }
    }
    printf("\n");
    printf("Final remaining A=%d B=%d\n", rem[0], rem[1]);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-08-mlfq.c -o example && ./example

Expected result

MLFQ sim: 3 levels, slice=4
Gantt (A=long CPU, B=short arr@12):
AAAAAAAAAAAABBBBBAAAAAAAA
Final remaining A=0 B=0

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A CPU-bound job has already fallen to the lowest-priority queue. An interactive job that needs only a little CPU then arrives. Explain how MLFQ schedules them and why this behavior benefits interactive users.

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.