CPU Scheduling, Explained

After reading this you can hand-run FCFS, SJF, SRTF, round robin, priority and MLFQ on a set of processes, draw the Gantt chart, and compute completion, turnaround, waiting and response time for each one by hand.

What a CPU scheduler does

A single CPU can run one process at a time. When several processes are ready, something has to decide which one runs next and for how long. That decision rule is the scheduling algorithm. The simulator takes a list of processes, each with an arrival time and a burst time (the amount of CPU time it needs), and plays the rule forward one time unit at a time.

Here is the hook. Suppose three jobs arrive at time 0 with burst times 24, 3 and 3. Run them first-come first-served in that order and the average waiting time is (0 + 24 + 27) / 3 = 17. Run the two short jobs first and the average waiting time drops to (0 + 3 + 6) / 3 = 3. Same work, same CPU, same total busy time of 30 units. The order alone cut average waiting by a factor of nearly six. That gap is the whole subject in one example.

The six algorithms and when each fits

Every algorithm answers one question: given the processes that have arrived and are not finished, which one runs in the next instant?

FCFS (first-come first-served)
Run jobs in arrival order, no interruptions. Simple and fair in a queue sense, but one long job delays everything behind it. This is the convoy effect.
SJF (shortest job first)
Among arrived jobs, run the one with the smallest total burst. Non-preemptive. Gives the lowest possible average waiting time when bursts are known, but it needs those bursts in advance and can starve long jobs.
SRTF (shortest remaining time first)
The preemptive version of SJF. At every instant, run the job with the least time left. A newly arrived short job can evict a running long one.
Round robin
Each ready job gets a fixed time slice called the quantum, then goes to the back of the queue. Fast, fair response. Throughput drops if the quantum is so small that context switches dominate.
Priority
Run the job with the best priority number (lower usually means higher priority). Comes in preemptive and non-preemptive flavours. Low-priority jobs can starve unless you age them.
MLFQ (multilevel feedback queue)
Several queues with different quanta. A job that uses its whole slice drops a level; a job that yields early stays high. This approximates SJF without knowing burst times in advance.

SJF and SRTF assume you already know how long each job will run. Real operating systems do not. That is exactly why MLFQ exists: it guesses future burst length from recent behaviour. Treat SJF as a lower-bound benchmark, not a deployable policy.

The four numbers you compute

Once the Gantt chart is drawn, four timings describe each process. They chain together, so get the first right and the rest follow.

\text{turnaround} = \text{completion} - \text{arrival}

Turnaround is the wall-clock time from when the process arrived to when it finished. If job P1 arrives at 0 and completes at 30, its turnaround is 30.

\text{waiting} = \text{turnaround} - \text{burst}

Waiting is the time spent sitting in the ready queue, not running. It equals turnaround minus the burst the job actually needed. A job that waited not at all has turnaround equal to burst.

\text{response} = \text{first run} - \text{arrival}

Response is the delay from arrival until the job first touches the CPU. Under FCFS, response and waiting are equal because a job runs to completion once started. Under round robin they differ: response is short, waiting can be long.

Two aggregate numbers summarise the whole run. CPU utilization is busy time divided by total time including idle gaps. Throughput is jobs finished divided by total time.

\text{utilization} = \frac{\text{busy time}}{\text{total time}} \times 100\%

A worked example you can reproduce

Four processes under FCFS and SRTF

Take four processes. Arrival and burst in time units:

Workload: arrival and burst times
ProcessArrivalBurst
P107
P224
P341
P454

First run FCFS. Jobs run in arrival order with no preemption.

  1. P1 runs 0 to 7. Completion 7.
  2. P2 runs 7 to 11. Completion 11.
  3. P3 runs 11 to 12. Completion 12.
  4. P4 runs 12 to 16. Completion 16.

Now the timings. Turnaround is completion minus arrival, waiting is turnaround minus burst.

FCFS results
ProcessCompletionTurnaroundWaiting
P1770
P21195
P31287
P416117

Average waiting under FCFS is (0 + 5 + 7 + 7) / 4 = 4.75.

Now SRTF on the same data. At each instant the job with least remaining time runs, and an arrival can preempt.

  1. At 0 only P1 is here, so P1 runs. At 2, P2 arrives needing 4 while P1 has 5 left, so P2 preempts. P1 has 5 remaining.
  2. At 4, P3 arrives needing 1. P2 has 2 left. P3 is shorter, so P3 runs 4 to 5 and finishes.
  3. At 5, P4 arrives needing 4. Remaining times are P1 5, P2 2, P4 4. P2 is shortest, so P2 runs 5 to 7 and finishes.
  4. At 7, remaining are P1 5 and P4 4. P4 runs 7 to 11 and finishes.
  5. P1 runs last, 11 to 16, and finishes.
SRTF results
ProcessCompletionTurnaroundWaiting
P116169
P2751
P3510
P41162

Average waiting under SRTF is (9 + 1 + 0 + 2) / 4 = 3.0. SRTF cut average waiting from 4.75 to 3.0, but notice P1 now waits 9 units instead of 0. The short jobs won; the long job paid for it.

SRTF lowers the average but shifts the cost onto the longest job. Both numbers are computed in the worked example above.

How the quantum reshapes round robin

Round robin has one dial, the time quantum. Make it very large and round robin becomes FCFS, because every job finishes its burst inside one slice. Make it very small and response time drops toward zero, but every switch between jobs costs real time.

Suppose a context switch costs 0.5 time units and you have 4 jobs each needing 10 units, so 40 units of work. With a quantum of 10, each job runs once: 3 switches between them, total overhead 1.5 units, utilization 40 / 41.5 = 96.4\%. Drop the quantum to 1 and you force roughly 39 switches, overhead 19.5 units, utilization 40 / 59.5 = 67.2\%. Same work, a third of the CPU wasted on bookkeeping.

With 4 jobs of 10 units each and a switch cost of 0.5 units, a quantum of 10 gives utilization 96.4% and a quantum of 1 gives 67.2%. Smaller quanta shorten response time but waste more CPU on switching.

Reading the results without fooling yourself

The averages hide the distribution. An algorithm can post a lovely average waiting time while one unlucky job waits ten times the mean. Always scan the per-process column, not just the bottom row.

Three reading habits save you from wrong conclusions:

  • Check that busy time equals the sum of all bursts. If it does not, you dropped or double-counted a slice. In the worked example that sum is 7 + 4 + 1 + 4 = 16, and both runs finish at 16 because there is no idle gap after time 0.
  • Compare response and waiting separately. Round robin and FCFS can share an average waiting time while round robin gives far better response.
  • Watch for idle gaps. If the first arrival is at time 3, the CPU sits idle for 3 units and utilization can never reach 100%.

Common mistakes

When two jobs tie on the deciding key (equal burst in SJF, equal priority, or both reaching the quantum boundary), break the tie by arrival time, then by name. That is the textbook convention and it makes your Gantt chart match the published solution.

The errors that cost the most marks and the most confusion:

  • Forgetting preemption checks happen at every arrival. In SRTF you must re-evaluate the instant a new job arrives, not only when the running job finishes. Miss the arrival at time 2 in the example and your whole chart is wrong.
  • Confusing burst with remaining time. SJF compares total burst; SRTF compares what is left. Using the wrong one quietly turns one algorithm into the other.
  • Counting the final slice as a full quantum. A job with 2 units left under a quantum of 5 runs for 2, not 5, and no switch follows if it finishes and the queue is empty.
  • Ignoring the switch cost in the averages. If you add a context-switch cost, it extends completion times, so turnaround and waiting grow too.

Related tools

Scheduling is one member of a family of step-by-step algorithm visualizers. If you like watching a rule unfold one move at a time, these sit nearby. The Sorting Algorithm Visualizer races comparison sorts on the same array. The Pathfinding Visualizer and the Graph Algorithm Playground show search and shortest-path algorithms exploring a grid or graph, and a priority queue drives Dijkstra much as a ready queue drives a scheduler. For the theory of computation end, the Turing Machine Simulator strips execution down to a tape and a head.

Frequently asked questions

Why does SJF give the lowest average waiting time?

Because placing a short job before a long one reduces the long job's contribution to everyone's wait by less than it adds, as long as the short one's own wait falls. Formally, ordering jobs by increasing burst minimises the sum of waiting times. It is the same argument that sorts items by shortest-processing-time in scheduling theory.

Can a job wait forever?

Under SJF, SRTF and plain priority, yes. A steady stream of short or high-priority jobs can starve a long or low-priority one indefinitely. Round robin cannot starve a job because every ready job gets a turn within one cycle. MLFQ adds aging to prevent starvation at lower levels.

What quantum should round robin use?

Large enough that most jobs finish in a few slices, small enough that response stays snappy. A common rule of thumb is that 80% of bursts should be shorter than one quantum. If a switch costs 0.5 units, a quantum of 4 wastes about 11% of the CPU on switching; a quantum of 1 wastes about 33%.

Why do response and waiting time differ?

Response measures only the first time a job touches the CPU. Waiting sums every idle stretch in the ready queue across the whole run. In FCFS they are equal because a job never pauses once it starts. In round robin a job starts quickly (short response) but gets interrupted many times (longer waiting).

Does idle CPU time count against utilization?

Yes. Utilization is busy time over total elapsed time. If the first process arrives at time 3, those 3 idle units are in the denominator, so even a perfectly packed schedule afterward cannot reach 100%.