COMP30023 · Computer Systems
CPU Scheduling
Week 3 covers how the scheduler picks which ready process runs — First-Come First-Served, Shortest-Job-First, Round-Robin with a quantum, priority and multi-level feedback queues — and how to compute waiting, turnaround and response times from a Gantt chart. Tracing execution order and computing average turnaround/response for several policies on a given burst/arrival table is a flagship Part C exam question.
What this chapter covers
- 01Why scheduling is needed; context switch (thread vs process, including flushing the TLB) and its overhead
- 02CPU-bound vs I/O-bound processes; preemptive (quantum + clock interrupt) vs non-preemptive scheduling
- 03Metrics: turnaround = completion − arrival, response = first-run − arrival, and their averages; fairness and throughput
- 04First-Come First-Served (FCFS): FIFO order, simplicity, and the convoy effect
- 05Shortest-Job-First (SJF): optimal average turnaround when all jobs are ready together; risk of starving long jobs
- 06Round-Robin (RR): one quantum per turn, good response time, no starvation, and the quantum trade-off
- 07Priority scheduling and dynamic priority (e.g. priority = 1/fraction-of-quantum-used) to favour I/O-bound jobs
- 08Multi-Level Feedback Queue (MLFQ): longer quanta at lower levels, no a-priori knowledge, priority boosting
Round-Robin turnaround and response times
- +1Build the Gantt chart, giving each ready process one quantum (3 ms) per turn and re-queuing it at the tail if work remains. A runs 0-3 (3 ms left), B runs 3-6 (done), C runs 6-9 (1 ms left), A runs 9-12 (done), C runs 12-13 (done). Strip: A[0-3] B[3-6] C[6-9] A[9-12] C[12-13].
- +1Read completion times off the chart: B finishes at 6, A finishes at 12, C finishes at 13.
- +1Turnaround = completion − arrival, and all arrive at 0: A = 12, B = 6, C = 13. Average turnaround = (12 + 6 + 13) ÷ 3 = 31 ÷ 3 ≈ 10.33 ms.
- +1Response = first-run start − arrival: A first runs at 0, B first runs at 3, C first runs at 6. Average response = (0 + 3 + 6) ÷ 3 = 9 ÷ 3 = 3 ms. Round-Robin gives a low response time (every process runs within one cycle) but a poorer average turnaround, and it never starves any process.
Key terms
- Turnaround time
- Completion time − arrival time for a process; the total time from submission to finish. Average turnaround is the mean over all processes and is the headline metric for batch scheduling.
- Response time
- Time of first run − arrival time; how long a process waits before it first gets the CPU. Interactive scheduling aims to minimise it, which is why Round-Robin is favoured there.
- First-Come First-Served (FCFS)
- Non-preemptive scheduling that runs ready processes in arrival order (FIFO). Simple with low overhead, but suffers the convoy effect: short jobs stuck behind a long CPU-bound job get large turnaround times.
- Shortest-Job-First (SJF)
- Run the ready process with the shortest next CPU burst. It gives the optimal average turnaround when all jobs are available together, but needs burst-length estimates and can starve long jobs.
- Round-Robin (RR)
- Preemptive scheduling that gives each ready process one time quantum in turn, re-queuing it if unfinished. Good response time and no starvation; the quantum trades responsiveness (short) against context-switch overhead (long).
- Multi-Level Feedback Queue (MLFQ)
- Several priority queues where lower-priority queues get longer quanta; processes start high and sink a level when they use up their quanta. It favours short/interactive jobs, needs no a-priori burst knowledge, and uses priority boosting to avoid starvation.
CPU Scheduling FAQ
How do I compute average turnaround and response time?
Draw the Gantt chart for the policy first. Turnaround for each process is its completion time minus its arrival time; response time is when it first starts running minus its arrival time. Average each over all processes. The commonest slips are forgetting to subtract a non-zero arrival time, and reading completion times wrong from the chart — so always build the strip and read the numbers off it rather than doing arithmetic in your head.
Which scheduling policies can cause starvation?
Shortest-Job-First (and strict priority) can starve long/low-priority jobs, because a steady stream of shorter or higher-priority jobs keeps jumping ahead. FCFS and Round-Robin do not starve: FCFS runs everyone in arrival order, and RR gives every process a turn each cycle. This yes/no pattern (FCFS no, SJF yes, RR no) is a frequent MCQ.
Why is SJF optimal for average turnaround?
When all jobs are ready at time 0, running the shortest burst first means each short job's time is added into fewer of the running completion totals, so the total (and hence average) waiting is minimised. Intuitively, making a long job wait behind several short ones costs less total waiting than making the short ones wait behind the long one. The catch is that it needs to know or estimate burst lengths and can starve long jobs.
How should I choose the Round-Robin quantum?
Long enough to amortise the context-switch cost but short enough to stay responsive. If the quantum is much larger than typical bursts, RR degrades into FCFS (poor response); if it is tiny, context-switch overhead dominates and throughput drops. A common design picks a quantum so that most interactive bursts complete within one or two quanta.
Can AI help me with CPU scheduling problems in COMP30023?
Yes. Sia can generate practice burst/arrival tables, check your Gantt charts for FCFS/SJF/RR, and explain the turnaround-vs-response trade-offs and starvation behaviour step by step. It is a study aid to help you master the method and rehearse for the exam; it does not do your graded MST, exam, quizzes or projects, and University of Melbourne academic-integrity rules apply.
Exam move
Scheduling is one of the most reliably examined quantitative topics — a Part C Gantt question is very likely — and it also sits in the mid-semester test, so drill it until the mechanics are automatic. Practise building Gantt charts for FCFS, SJF and Round-Robin from the same burst/arrival table, then reading completion, turnaround and response times off the chart; do a set with staggered arrivals so you handle 'only ready jobs compete' correctly for SJF and RR. Memorise the qualitative summary (FCFS: convoy effect; SJF: optimal average turnaround but starvation; RR: good response, no starvation; MLFQ: no a-priori knowledge, longer quanta lower down) and the starvation yes/no table. There is no calculator in the exam, so keep the arithmetic to clean small sums. Confirm the MST and exam dates on Canvas; mastering this topic protects your WAM because it recurs in tutorials and the projects' concurrency reasoning.
Working through CPU Scheduling in COMP30023? Sia is AskSia’s AI Computer Science tutor — ask any COMP30023 CPU Scheduling question and get a clear, step-by-step explanation grounded in how COMP30023 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
