Round Robin, SRT and Feedback Queues

Round robin takes the next ready job and gives it up to a fixed quantum. If it has unfinished work after that slice, it joins the back of the ready queue. A task that finishes early releases the CPU immediately. Timer interrupts can trigger the scheduler; switching also requires saving and restoring execution context.

Using A(0,5), B(1,2), C(2,1) with quantum 2, put arrivals at a slice boundary into the queue before requeuing the expired job. The order is A 0–2, B 2–4, C 4–5, A 5–7, A 7–8. A very small quantum increases switching overhead; a very large quantum makes CPU-only behaviour approach FCFS.

SRT is preemptive: a new arrival can replace the current job when its remaining CPU time is smaller. A tie rule is necessary for a reproducible trace. Here ties favour the job that arrived earlier. A starts at 0; B arrives at 1 and preempts because its 2 units are less than A’s remaining 4.

C arrives at 2 with 1 unit while B also has 1 left, so B continues under the stated tie rule. The timeline is A 0–1, B 1–3, C 3–4, A 4–8. This improves mean waiting for this workload, but still relies on estimated remaining lengths and can repeatedly postpone long jobs. It need not optimise interactive fairness.

A multilevel feedback queue uses several priority queues and moves jobs between them according to observed behaviour. A simple teaching model starts new jobs in a high-priority queue with short slices, demotes jobs that consume their allocation, and schedules lower queues only when higher ones have no ready work. Specific systems use different movement and slice rules.

This can give quick service to short or interactive tasks without knowing their complete CPU demand in advance. CPU-bound tasks still need progress; periodic priority boosts or ageing can reduce starvation. State the rules before tracing, including whether a higher-priority arrival interrupts lower-priority work. Feedback queues are not simply several permanent priority classes with no movement.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.