Implement Multi-Level Feedback Queue Scheduler

Feedback Queues

A Multi-Level Feedback Queue (MLFQ) places processes on different priority bands and demotes CPU hogs while promoting interactive tasks that yield quickly. The goal is to approximate shortest-job-first without knowing job lengths in advance. Windows and many teaching kernels use variants of this idea.

Rules That Matter

Typical MLFQ behavior:

• Multiple queues: high index = lower priority, longer quantum
• New jobs: start at the highest queue
• On full quantum: demote one level
• On I/O block: stay or boost depending on policy

For example, a compute-bound loop burning 100 quanta cascades from queue 0 to queue 2, while a shell that blocks on keyboard input every 2 ms never leaves the top band.

Why This Matters in Production

MLFQ is the scheduling family that ran production Unix and Windows NT for decades before Linux replaced it with CFS in 2007 (and CFS itself was replaced by EEVDF in kernel 6.6), precisely because naive MLFQ starves CPU-bound batch jobs without a periodic priority boost. The I/O-bound-versus-CPU-bound classification you build here is the same heuristic real schedulers use to decide whether a process is 'interactive' and deserves lower latency.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement queue arrays, demotion on timer expiry, and optional boosting after I/O. You need to log per-process queue levels so you can verify interactive favoritism against batch workloads.