CPU Scheduling

There are usually more runnable processes than CPUs, so someone has to decide who runs next and for how long. That decision is the scheduler's policy; actually switching is the mechanism (next lesson). In this lesson your program runs a round-robin scheduler over processes that arrive at different times, prints the exact timeline, and reports the three numbers every scheduler is judged by.

What a scheduler is judged on

For a process that arrives at time a, first runs at time s, finishes at f and needs b ms of CPU:

Interactive systems care most about response, batch systems about turnaround and throughput. No policy wins on all of them.

First come, first served, and the convoy

The simplest policy runs each job to completion in arrival order. One long job at the head of the queue makes every short job behind it wait: the convoy effect. Waiting times explode even though the total work is the same.

Round robin

Round robin fixes the convoy by preemption. Each process runs for at most one quantum q; if it still has work left, a timer interrupt (a later lesson) takes the CPU away and it goes to the back of the ready queue. Everyone gets a turn within (n - 1) * q, so response is bounded.

The choice of q is a trade-off. Each switch costs real time (saving and restoring registers, a possible TLB flush, cache misses). If q is 1 ms and a switch costs 0.1 ms, 10% of the machine is overhead. If q is huge, round robin degenerates into first-come first-served. Classic systems used 10 to 100 ms.

The simulation, precisely

State: the clock t, a FIFO ready queue, and the remaining time of each process. One step:

1. Admit every process with arrival <= t to the back of the queue (input order breaks ties).
2. If the queue is empty, the CPU is idle until the next arrival: advance the clock to it.
3. Pop the head, run it for min(q, remaining) ms and advance the clock.
4. Admit every process that arrived while it ran, including one that arrives exactly at the end of the slice.
5. If the process still has work left, append it to the queue. Otherwise it finishes at the current time.

Step 4 happens before step 5. That is a convention, and the one most textbooks use: a newcomer arriving at the same instant as a quantum expiry is queued ahead of the process that was just preempted.

A worked trace

q = 2; A arrives at 0 needing 5, B at 1 needing 3, C at 2 needing 1.

Process A: turnaround 9, waiting 4, response 0. Process C: turnaround 3, waiting 2, response 2.

Common mistakes

• Requeueing the preempted process before admitting arrivals that came during its slice.
• Ignoring the clock when the queue is empty: the CPU idles and time must jump to the next arrival.
• Running a process for a full quantum when it needs less.
• Computing waiting time as finish - burst instead of finish - arrival - burst.

Your exercise

The starter parses the processes and prints your timeline and statistics. You write simulate.