← ⏱️ CPU Scheduling
Subtopic 5 of 5

2.5Multilevel queues, feedback queues and real-time

The idea

Real systems combine ideas: multilevel queues, feedback queues that move processes by behaviour, and real-time schedulers with deadlines.

Think of it like this: A post office with separate counters for parcels, letters and urgent mail, where a customer who turns out to have a long job is moved to the slow counter.

Why it exists

One policy cannot serve interactive, batch and real-time work at once, so systems layer them.

How it works

  1. Multilevel queue: fixed queues, strict priority between them.
  2. Feedback queue: new jobs enter at the top with a short quantum; using the whole quantum demotes the job.
  3. Rate monotonic: shorter period = higher static priority.
  4. EDF: nearest deadline first; schedulable up to 100% utilisation.

Worked example: Three periodic tasks with total utilisation 0.75

RM bound for 3 tasks is 3(2^(1/3) − 1) ≈ 0.78, and 0.75 ≤ 0.78 so RM guarantees the deadlines. EDF would also succeed since 0.75 ≤ 1.

Now play with it

  • →Use the calculator: set U = 0.85 for 3 tasks and see RM no longer guaranteed by the test while EDF still works.
  • →Read the table to see why feedback queues favour I/O-bound jobs.
SchemeHow it worksRemember
Multilevel queuefixed queues by type: system, interactive, batch; strict priority between queuesa process stays in its queue
Multilevel feedback queueprocesses move down if they use their whole quantum, up if they wait or do I/Ofavours short and I/O-bound jobs
Rate monotonicstatic priority, shorter period = higher prioritysufficient: U ≤ n(2^(1/n) − 1)
Earliest deadline firstdynamic priority by nearest deadlineschedulable iff U ≤ 1 (deadline = period)
Rate-monotonic bound0.78
RM guaranteed?yes (U ≤ bound)
EDF feasible?yes

The bound tends to ln 2 ≈ 0.693 as n grows. Failing the RM bound does not prove the set is unschedulable, it only means this simple test cannot promise it.

Check yourself

EDF can schedule a set of periodic tasks (deadline = period) whenever total utilisation is

Remember: RM bound n(2^(1/n) − 1) is sufficient only; EDF: U ≤ 1.
Exam notes (the dense version)

Multilevel queue: separate queues (system, interactive, batch), each with its own policy, strict priority between queues. Multilevel feedback queue: processes move between queues based on behaviour: CPU hogs sink to lower queues with longer quanta, I/O-bound ones stay on top. Real-time: rate monotonic (static, shorter period = higher priority; schedulable if utilisation ≤ n(2^(1/n) − 1)) and EDF (dynamic, earliest deadline first; schedulable if utilisation ≤ 1).

Previous year questions: CPU Scheduling (13)

PYQs are grouped by topic, so this is the full set for CPU Scheduling; try the ones that match this subtopic. Open all 13 on the topic page.