MLFQ & Priority Scheduling

Round robin treats every job alike, but a real machine runs short interactive jobs (a keystroke handler) beside long computations (a compiler), and the kernel does not know in advance which is which. The multi-level feedback queue (MLFQ) learns it by watching behaviour, with no knowledge of job lengths. Jobs that use their time slices get pushed down; jobs that finish quickly stay near the top. Your program will simulate a complete MLFQ, including the rule that stops it starving long jobs.

The rules

There are n queues; level 0 has the highest priority.

1. Run the job at the head of the highest non-empty queue. Jobs in the same queue take turns round-robin.
2. Each level has its own quantum: high levels have short slices (so interactive jobs are served quickly), low levels long ones (fewer switches for CPU hogs).
3. Every job starts at level 0.
4. Each level also has an allotment: the total CPU time a job may use at that level. When a job has used its allotment it is demoted one level (to the back of the next queue, with its usage counter reset). A job at the lowest level stays there.
5. Boost: every S ms of elapsed time, move all jobs back to the top queue.

Why an allotment and not "demote after one full quantum"?

A job that gives up the CPU just before its quantum ends (say by issuing a cheap I/O every 99% of a slice) would never be demoted, and could monopolise the top queue. Counting the total time used at the level makes that trick useless: yielding early still adds up.

Why a boost?

Without rule 5, a long job sinks to the bottom and can starve forever behind a stream of short jobs at higher levels. Periodic boosting guarantees that every job gets a turn near the top at least every S ms. It also lets a job that changed from CPU-bound to interactive be noticed. Tuning S is voodoo: too large and starvation returns, too small and short jobs lose priority to long ones.

The simulation, precisely

A batch workload: all jobs arrive at time 0 in input order and never block. After each slice:

1. Subtract the time run from the job; add it to its usage counter at this level.
2. If the job is finished, record its finish time. Otherwise: if usage >= allotment and the level is not the lowest, move it to the back of the next level and reset its usage; if not, put it back at the end of the same queue.
3. If a boost interval is set and the clock has crossed a multiple of S during this slice (that is, floor(now / S) > floor(before / S)), move every job to level 0 and reset usage. Keep order: first the jobs of level 0 in their queue order, then those of level 1, and so on.

A worked trace

Three levels, quanta 2/4/8, allotments 4/8/16; jobs A needs 10 ms, B needs 6 ms.

Priority scheduling and its trap

Plain priority scheduling (always run the highest priority) is simple but suffers starvation, and priority inversion: a low-priority job holding a lock needed by a high-priority one can be held up by a medium-priority job. The cure for the second is priority inheritance. MLFQ-style systems appear in BSD, Solaris and Windows.

Common mistakes

• Resetting usage when a job merely stays at its level, or forgetting to reset it on demotion.
• Counting a slice as "one use" instead of adding the milliseconds actually run.
• Demoting a job at the lowest level or letting a finished job be requeued.
• Boosting every S slices instead of when the clock crosses a multiple of S, or losing the queue order during a boost.

Your exercise

The starter reads the configuration and prints the schedule. You write the scheduling loop, including the boost.