CPU Scheduling

You have one CPU core and thirty ready tasks. The scheduler's job is to decide, every time the decision comes up, who runs next and for how long — and to make thirty programs each believe they own the machine. This lesson builds the policy that started it all, and the one your exercise simulates: round-robin.

Where the decision points come from

A scheduler only gets to act when control passes through the kernel:

1. The running task blocks (reads from a socket with no data) — voluntary.
2. The running task exits — very voluntary.
3. The timer interrupt fires and the task's time is up — involuntary, and the load-bearing one.

Number 3 is what makes scheduling preemptive. The kernel programs a hardware timer to interrupt, say, every millisecond; each tick is a chance to take the CPU away. Without it, one while(true) loop owns the machine forever — this is exactly how pre-1995 Mac and Windows systems could be frozen solid by a single misbehaving app ("cooperative" multitasking: multitasking, cooperation permitting).

Round-robin: fairness by rotation

The policy is one sentence: keep ready tasks in a FIFO queue; run the head for at most one quantum; if it's still running when the quantum expires, put it at the tail and run the next one.

QUANTUM = 3ms, jobs: A needs 5ms, B needs 2ms, C needs 4ms

time  0    3     5      8     10     11
      | A:3 | B:2✓ | C:3 | A:2✓ | C:1✓ |
queue A,B,C→B,C,A →C,A  →A,C  →C     →done

Walk that trace by hand until it's mechanical: A uses its full quantum and goes to the tail; B finishes inside its quantum, so it just leaves; nobody waits longer than (n−1) × quantum for a turn. That last property is round-robin's whole personality: no starvation, bounded response time, zero knowledge of the future required. Your exercise implements precisely this simulation — quantum, arrival order, completion times — and the trace above is your first mental test case.

Judging a scheduler

Three numbers capture most arguments:

• Turnaround time = completion − arrival. What batch jobs care about ("when is my compile done?").
• Response time = first-run − arrival. What humans care about ("did the keypress echo?").
• Waiting time = turnaround − actual CPU time. Pure overhead from the task's perspective.

Round-robin optimizes response time and is mediocre at turnaround: by design it stretches every long job out across the whole workload. Compare FCFS (first-come-first-served, run to completion): great throughput, but one 10-second job in front of three 10-millisecond jobs wrecks everyone — the convoy effect. SJF (shortest-job-first) provably minimizes average turnaround… and requires knowing job lengths in advance, which nobody does. Hold that thought; MLFQ (two lessons ahead) is the industry's answer to "SJF without a crystal ball."

The quantum knob

The quantum is a real engineering tradeoff, not a free parameter:

• Too small (say, 0.1ms): the machine spends its life context-switching. If a switch costs ~2µs of direct work plus cache damage (next lesson puts numbers on this), a 100µs quantum burns a measurable percent of the CPU on pure overhead.
• Too big (say, 500ms): response time dies; typing feels like postal mail. As quantum → ∞, round-robin degenerates into FCFS.

Linux's answer lands in the handful-of-milliseconds range, scaled by load. When your simulator works, re-run the same job set with quantum 1 and quantum 100 and watch turnaround and response time trade places — that's the tradeoff, measured by code you wrote.