CPU Scheduling: A Visual Notebook
CPU scheduling decides which ready process uses the CPU next. A policy can favor arrival order, short work, regular turns, or priority classes. These choices change how long processes wait, how quickly they first receive CPU time, and when they finish.
Start with FCFSThis notebook explains each policy with a small workload and a trace you can read from left to right. Start with the terms below, then follow the worked examples. The simulator is available whenever you want to try a different workload.
The terms used in every example
| Term | Meaning |
|---|---|
| Arrival time | The time a process becomes eligible for CPU service. |
| CPU burst | The amount of CPU execution that the process needs in this example. |
| Ready | A process has arrived and can run, but is waiting for the CPU. |
| Remaining work | The original burst minus the CPU service already received. |
| First start | The first time a process receives CPU service. |
| Completion time | The time its entire burst has finished. |
| Preemption | The running process is interrupted before its burst finishes, so it can resume later. |
| Quantum | The maximum CPU time allowed in a Round Robin turn. A process can finish earlier. |
| Dispatch cost | Time spent changing the active process instead of executing its work. It is zero in these examples. |
One CPU executes one process at a time. A future arrival is not ready yet, and the currently running process is separate from the waiting Ready queue.
Three metrics that answer different questions
Let A be arrival time, B the burst, S the first start, and C completion.
- Turnaround time = C - A. How long did the whole job take from arrival to completion?
- Waiting time = C - A - B. How much of that time was spent without CPU service?
- Response time = S - A. How long did it take to receive CPU service for the first time?
These waiting-time calculations use the notebook's single-burst model without I/O blocking. The mean of a metric is the sum of its process values divided by the number of processes.
A process can have a response time of zero and still wait later after preemption. The SRTF example makes that distinction visible.
How to read the figures
Read each CPU timeline from left to right. A segment identifies the running process and its start and end times. Arrival markers show when new work becomes eligible; a new marker does not necessarily cause a process change.
A boundary at t = 7 means the preceding segment ends there and the following one starts there. Idle time or dispatch overhead, when present in the simulator, needs its own labeled span. None is present in the worked examples below.
Choose a policy to study
| Policy | The selection rule in this notebook | What to look for |
|---|---|---|
| FCFS | Earliest ready arrival first | A long first job makes later short jobs wait. |
| SJF | Shortest ready burst when the CPU becomes free | A new short arrival does not interrupt the running job. |
| SRTF | Least remaining CPU work | A strictly shorter arrival can interrupt current work. |
| SRTF checkpoints | Least remaining work at execution checkpoints or completion | An app-specific variant that delays some decisions. |
| Round Robin | FIFO turns, each bounded by a quantum | Work shares access without needing burst length to choose a turn. |
| HRRN | Largest (waiting + burst) / burst ratio | Waiting can make an older, longer job win. |
| MLQ | Highest nonempty fixed queue, then that queue's policy | Class priority can outweigh job length. |
| MLFQ | Highest current queue, with feedback from consumed CPU allotments | A process's level can change as it runs. |
A useful reading order is FCFS, SJF, SRTF, the checkpoint variant, Round Robin, HRRN, MLQ, then MLFQ. The checkpoint lesson explores a teaching variant specific to this application.
One workload, five schedules
The first five examples use the same input:
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 1 | 3 |
| P3 | 2 | 1 |
One CPU · One burst per process · No I/O · Dispatch cost 0. Times are abstract units.
With zero dispatch cost, RR quantum 2, and checkpoint interval 3:
| Policy | Mean waiting | Mean turnaround | Mean response | Process changes |
|---|---|---|---|---|
| FCFS | ≈ 4.667 | ≈ 8.333 | ≈ 4.667 | 2 |
| SJF | 4 | ≈ 7.667 | 4 | 2 |
| SRTF | ≈ 1.667 | ≈ 5.333 | 0 | 4 |
| SRTF checkpoints | ≈ 2.667 | ≈ 6.333 | ≈ 1.333 | 3 |
| Round Robin | ≈ 3.333 | 7 | 1 | 5 |
In this comparison, process changes count transitions between different CPU owners. The initial dispatch is not a change, and a new turn or queue level for the same process adds no change.
Means are rounded to three decimal places. Every schedule finishes at time 11: there are 11 units of work, no idle interval, and no dispatch cost. The individual waits and first responses still differ.
For this workload, continuous SRTF gives every process an immediate first start, while RR gives shorter waits for a first turn than FCFS. SRTF and RR also change processes more often than FCFS. A different workload or nonzero dispatch cost can change the tradeoffs.
The HRRN, MLQ, and MLFQ articles use different inputs to expose their particular rules. Their result tables therefore are not directly comparable with the figures in this table.