CPU Scheduling: make the queue explain the timeline

A task can be ready without running. When several tasks share one CPU, the scheduler decides which ready task gets the next interval. The hard part of the exercise is keeping arrivals, remaining work, and time consistent at every boundary.

Before starting, distinguish READY from BLOCKED in the process-model module and be comfortable with a FIFO queue. By the end, you should be able to predict completion times, explain a queue's order at a quantum boundary, and account for every unit of elapsed time.

Define the teaching model

Each task has an arrival time and one CPU burst. Tasks do not block for I/O; there is one CPU, no priority, and no startup cost. IDs are unique, arrival times and context costs are nonnegative, and the quantum is positive. Ignore nonpositive bursts. These assumptions describe this simulator, not every operating-system scheduler.

Round robin runs the head of the ready queue for min(quantum, remaining). An unfinished task goes to the tail. A new arrival joins the queue; it does not interrupt a running slice. With a finite workload and positive quantum, each selected task makes progress, and an already queued task cannot be overtaken by later arrivals.

Establish event order before writing the loop

Keep current time, a FIFO ready queue, the next arrival index, remaining burst per task, and a completion map. Stably sort tasks by arrival, preserving input order for ties. At each slice boundary:

1. Advance time by the work just performed and decrease the running task's remaining burst.
2. Append every new arrival with Arrival <= time, in stable arrival order. An arrival exactly at the boundary is included.
3. If the running task finished, record completion now. Otherwise append it after those arrivals.
4. Charge context time only if another task was ready at this boundary. Append arrivals during that context interval after the existing queue.

If the task is unfinished and alone, it continues without a context charge. If it finished and the queue is empty, jump to the next arrival without a charge. Do not charge after the final completion. Check whether another task is ready before putting the current task back; its own queue entry is not a competitor.

Arrivals during a context interval do not restart or lengthen it. This rule deliberately models one fixed overhead per handoff.

Work a complete trace

Use quantum 2, context cost 1, and these tasks:

Task	Arrival	Burst
A	0	5
B	1	2
C	3	1

Interval	CPU activity	State at the end
0–2	A runs	A has 3 left; B arrived, so queue becomes [B,A]
2–3	Context switch	C arrives; queue is [B,A,C]
3–5	B runs	B completes at 5; queue is [A,C]
5–6	Context switch	Queue remains [A,C]
6–8	A runs	A has 1 left; queue becomes [C,A]
8–9	Context switch	Queue remains [C,A]
9–10	C runs	C completes at 10; queue is [A]
10–11	Context switch	Queue remains [A]
11–12	A runs	A completes at 12; queue is empty

The CPU performs 8 units of useful work and 4 units of switching: total time is 12. C does not jump ahead of A when it arrives during the first switch. B's completion is 5, not 6: the following switch is not part of B's lifetime.

Derive the metrics from that trace

Turnaround is completion - arrival; response is first run - arrival. In this single-burst model, waiting time is turnaround - burst: all time after arrival is either useful execution or waiting, including dispatch overhead.

Task	Turnaround	Waiting	Response
A	12	7	0
B	4	2	2
C	7	6	6

Useful CPU utilization over this run is 8/12, about 66.7%. For a long saturated workload of full quantum-sized slices, the approximate useful fraction is q/(q+c). That approximation omits startup, final completion, shorter bursts, and idle periods. A smaller quantum offers more frequent turns but pays the fixed handoff cost more often; it does not guarantee lower turnaround for every task.

Invariants and diagnostic cases

Every arrived, unfinished task appears exactly once across the running task and ready queue. A completed task never reenters the queue. Remaining bursts stay nonnegative. Time never moves backward. At termination, elapsed time from zero equals useful burst time plus charged switches plus idle time.

Try a single task arriving at 4 with burst 5, quantum 2, and context 3. It runs 4–6, 6–8, 8–9 and finishes at 9. The quantum boundaries do not manufacture competitors or overhead. With no positive bursts, return an empty completion map and total time zero.

Predict, then explain

1. A arrives at 0 with burst 4; B arrives at 2 with burst 1. Quantum is 2 and context is 0. Which task finishes first, and when?
2. A finishes at 2 with no ready task. B arrives at 7 with burst 1, and context cost is 4. When does B finish?
3. In the full trace, what would go wrong if arrivals during a switch were inserted at the front?

Model answers

1. B finishes at 3. Its boundary arrival enters before unfinished A is requeued. A then finishes at 5.
2. At 8. Idle time advances directly to 7; this model does not charge a dispatch from idle.
3. C would overtake B and A, violating FIFO arrival/requeue order and changing both response and completion times.

Implement Round Robin Scheduler, then use the checkpoint to diagnose different schedules. The next synchronization module introduces blocked tasks; those are deliberately absent from this workload.

For the policy and metric background, see OSTEP: Scheduling. The event ordering and cost exceptions above are the exercise's explicit contract.