Loading page…
Master the fundamental concepts of process management through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksA 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.
Typical MLFQ behavior:
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.
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.
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.
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.
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.
Simulate a multi-level feedback queue (MLFQ) scheduler, following the rules in OSTEP chapter 8. The scheduler learns from behaviour: tasks that burn through their CPU allotment drift down to low-priority levels with long quanta, while tasks that block for I/O keep their high priority. A periodic boost lifts everything back to the top, so long jobs cannot starve.
cLoading…
Time advances one tick at a time. At every tick boundary, apply these steps in order:
done. Otherwise, if its allotment at this level is used up (CPU ticks at this level = the level's quantum, counted across dispatches), reset the count and demote it one level (at the bottom level it stays, with quantum expired). Then, if it has reached its I/O point, it blocks until now + WAIT. Otherwise, if it was demoted or expired, it goes to the tail of its level's queue.now is a positive multiple of S. The running task is stopped (boosted) and queued at the tail of its level. Then the queues of levels 1, 2… are appended to level 0 in order, and every unfinished task (including blocked ones) gets level 0 and a zero allotment count.preempted and joins the tail of its level. It keeps its allotment count.cLoading…
Each dispatch prints one line when it ends, showing the level it started at and the reason: done, demoted to N, quantum expired, blocked until T (or the demotion and the block together), preempted or boosted. Idle stretches are printed when they end, and a boost during idle splits the idle stretch. The table lists tasks in input order. Invalid tasks print task NAME: rejected.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover the periodic boost interrupting a running task, a boost during idle time, a task that games the scheduler by blocking often, preemption by a newly arrived task, a single-level configuration (plain round robin), and rejected tasks.