CPU scheduling — theory with FCFS, SJF, SRTF and Round Robin drawn as Gantt charts (and the midterm where I forgot to subtract the arrival)
The night before the second IC2 midterm I revised scheduling with whatever was open on my laptop: OneDrive uploading a backup of my assignment, gcc compiling, the university’s virtual campus in the browser and Spotify in the background. I made up arrival times and bursts, drew the SRTF Gantt chart and it looked beautiful. Then I worked out the waiting times as end − burst, got a mean of 6.5 ms and went to bed happy. The next day, in the exam, I did exactly the same. The right mean was 5 ms: I had forgotten to subtract the arrival time. The drawing was right; the sums were not.
This article comes out of that mistake. In the previous topic you saw that ready processes wait in a queue while only one of them uses the CPU. Today’s question is the obvious one: who decides whose turn it is, and by what rule? We will look at the metrics used to judge a scheduler, the four algorithms that come up in the exam (FCFS, SJF, SRTF and Round Robin) drawn step by step with the same four processes, and the other methods that appear in the multiple-choice test: priorities, lottery, multilevel queues and multiprocessors. When you are done, the CPU scheduling exercises have five Gantt charts to solve with boxes that mark themselves.
Table of Contents
What scheduling the CPU means
Your laptop has more processes than cores. With one core, only one of them can execute instructions at any instant; the rest wait in the ready queue (their PCBs, really). Every time the CPU becomes free, someone has to choose the next one.
Scheduling means deciding which process (or thread) gets access to a resource, and in this topic the resource is the CPU. The processor scheduler (the short-term scheduler from the previous topic) decides which process gets the processor when it becomes free and, if the algorithm allows it, when the running one must give it up. The algorithm it uses to decide is the scheduling policy.
Look at the picture: with one core, gcc, spotify, campus and onedrive take turns in slices so small that they seem to run together. That is concurrency: several tasks making progress interleaved in time. With two cores, two of them really do run at the same time: that is parallelism. This topic deals with the single-core case, where the decision matters most.
To study the algorithms, the problem is simplified: one program per user, one thread per program and programs independent of each other. It is not realistic, but without these assumptions you could not compare anything with pen and paper.
CPU bursts and I/O bursts
A process does not ask for the CPU once for all its work. It computes for a while, asks the disk or the network for something and blocks, computes again… A process’s active life is a sequence of CPU bursts and I/O bursts.
At the top there is a process alternating CPU bursts of 3, 4, 2 and 5 ms with I/O waits. Below, the typical shape of the distribution: most CPU bursts are short, under 8 ms, and a few are very long (those of CPU-bound processes). That is why each scheduling decision does not hand out “a program”, but the next CPU burst. And that is why, with time sharing, a process sometimes has to give up the CPU before finishing its burst.
What would a process want if it could choose? To be served straight away when it needs the CPU, to be left alone to finish its burst once inside, and to be done as soon as possible. The trouble is that the four processes on your laptop all want the same thing at once.
The metrics: how a scheduler is judged
To say an algorithm is “better” you have to measure something. These are the definitions that come up in the exam:
- Waiting time: total time a process spends in the ready queue (adding up every time it goes back to it).
- Turnaround time: time from when the process arrives (is created) until it finishes.
- Response time: time a CPU burst takes from joining the ready queue until it starts running.
- CPU utilisation: percentage of time the CPU does productive work.
And the relationship that ties it all together: turnaround time = waiting time + CPU time. With numbers from the Gantt chart they are worked out like this:
| Metric | Formula | Read it on the Gantt chart… |
|---|---|---|
| Turnaround | end − arrival | from the arrival arrow to the last block |
| Waiting | turnaround − burst | everything hatched: time in the queue |
| Response | first run − arrival | only up to the first block |
Look at gcc under Round Robin (you will see the whole chart further down): it arrives at t = 1, first gets the CPU at t = 3, leaves, goes back to the queue and finishes at t = 15. Its response is 3 − 1 = 2 ms, its turnaround 15 − 1 = 14 ms and its waiting time 14 − 4 = 10 ms. Checked by hand from the hatched pieces: (3 − 1) + (14 − 6) = 2 + 8 = 10. Both sums agree, as they should.
Working out waiting time as end − burst. It only works if the process arrived at t = 0. If it arrived later, subtract the arrival first: turnaround = end − arrival, then waiting = turnaround − burst. That was my midterm mistake.
What are we trying to optimise? It depends on the system, and no policy is optimal for every criterion, so there is always a compromise:
| Type of system | What the scheduler is after |
|---|---|
| Batch | Getting the most out of the CPU (utilisation) |
| Interactive | Short response times for the user |
| Real time | Meeting the set execution deadlines |
Besides the means, extreme values (nobody waits more than X) or the variance (the system is predictable) sometimes matter too.
Preemptive and non-preemptive
Before the algorithms, the classification that is asked about most:
- Non-preemptive: the process on the CPU gives it up only when it asks to (it finishes its burst or blocks requesting I/O). Risk: a process may hog the CPU unfairly. That is how Windows 3.11 and the first versions of iOS worked.
- Preemptive: the scheduler can evict the process on the CPU. Time sharing and real time require preemptive scheduling: it is what Unix, Windows and macOS use.
The picture sums it up in four situations. The top two (the burst ends, the process blocks for I/O) happen in every algorithm. The bottom two (someone better arrives, the quantum runs out) only exist in preemptive ones, and the quantum one needs the timer you saw in the hardware topic: without its interrupt, the OS would never find out that the time is up.
Saying time sharing needs non-preemptive scheduling. It is the other way round: if the OS cannot take anyone out, a process that computes non-stop leaves every interactive one hanging.
The example: the night before the deadline
We will try every algorithm with the same four processes, with times in milliseconds:
| Process | What it is | Arrival | CPU burst |
|---|---|---|---|
| onedrive | backing up the assignment to the cloud | 0 | 8 |
| gcc | compiling the assignment | 1 | 4 |
| campus | the browser with the virtual campus | 2 | 9 |
| spotify | background music | 3 | 2 |
In total they need 8 + 4 + 9 + 2 = 23 ms of CPU. With one core, the last one will finish at t = 23 whatever the algorithm; what changes is who waits, and for how long.
FCFS: first come, first served
FCFS (First-Come, First-Served) is the simplest policy: the ready queue is a FIFO ordered by arrival, and whoever gets the CPU keeps it until its burst ends. It is non-preemptive.
How to read this picture (and the following ones): the top bar is the CPU’s Gantt chart; underneath, each process has its own “lane”, with a triangle where it arrives, hatching while it waits in the queue and coloured blocks when it is on the CPU. On the right, its waiting time and turnaround.
Checked by hand: onedrive arrives at 0 and leaves at 8 (waits 0). gcc arrives at 1 and gets in at 8: waits 7, turnaround 12 − 1 = 11. campus arrives at 2 and gets in at 12: waits 10, turnaround 19. spotify arrives at 3, gets in at 21: waits 18, turnaround 20. Mean waiting time: (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75 ms.
Look at spotify: it needs 2 ms and waits 18. That is FCFS’s big flaw, the convoy effect: short processes get stuck behind long ones, like cars behind a lorry on a single-lane road.
The picture shows it with all four arriving together at t = 0. If the long one goes first, the mean waiting time is (0 + 8 + 12 + 21) / 4 = 10.25 ms; if the short ones go first, (0 + 2 + 6 + 14) / 4 = 5.5 ms. Same work, almost half the waiting. That is why FCFS is said to be very sensitive to the order of arrival.
| FCFS | |
|---|---|
| Advantages | Simple to implement: a FIFO queue is all it takes |
| Drawbacks | Very sensitive to the order of arrival; convoy effect; penalises I/O-bound processes (their short bursts wait behind long ones) |
SJF: shortest job first
What if, instead of serving in order of arrival, we serve first whoever will take the least time? That is SJF (Shortest Job First): when the CPU becomes free, the process with the shortest CPU burst among those in the queue gets in. In a tie, the earlier arrival. In its basic form it is non-preemptive: whoever gets in does not leave until it is done.
Step by step: at t = 0 only onedrive is there, so it gets in, and since SJF does not preempt, it stays until t = 8 even though shorter ones arrive. At t = 8, gcc (4), campus (9) and spotify (2) are waiting: spotify, the shortest, gets in, even though it was the last to arrive. At t = 10, gcc (4) and campus (9) are left: gcc gets in. At t = 14, campus.
Waiting: onedrive 0, spotify 8 − 3 = 5, gcc 10 − 1 = 9 and campus 14 − 2 = 12. Mean: (0 + 5 + 9 + 12) / 4 = 26 / 4 = 6.5 ms, better than FCFS’s 8.75.
In non-preemptive SJF, the question “who is the shortest?” is only asked when the CPU becomes free. Never while someone is running.
| SJF | |
|---|---|
| Advantage | Minimises the mean waiting time (it is optimal on that metric) |
| Drawback | Risk of starvation for processes with long bursts if short ones keep arriving |
| Practical problem | Nobody knows how long the next burst will be: it has to be estimated |
If every process lasts the same, SJF and FCFS do exactly the same thing. The difference appears when lengths differ: with SJF short jobs no longer get stuck behind long ones. The flip side: if you have the month’s shopping at the supermarket and everyone with just a loaf of bread goes first, you never get out.
Estimating the next burst
A real OS does not know the next burst, so it would have to estimate it. One possible way is the exponential average of previous bursts:
τ(n+1) = α · t(n) + (1 − α) · τ(n), with 0 < α < 1
where t(n) is how long the current burst lasted and τ(n) was the previous estimate. With α = 0.5, if 10 ms were expected and the burst lasted 6, the new estimate is 0.5 · 6 + 0.5 · 10 = 3 + 5 = 8 ms: halfway between what was expected and what happened.
SJF is not used in practice, not even with estimates. There are algorithms with a better balance between performance and response time. It is studied because it sets the minimum mean waiting time to compare the others against.
SRTF: the SJF that does preempt
The preemptive version of SJF is called SRTF (Shortest Remaining Time First): every time a process arrives, its burst is compared with what the running process has LEFT. If the newcomer is shorter, it preempts the running one, which goes back to the queue with its remaining time.
This is the full trace. At each event, write down what each one has left:
| t | What happens | Remaining at that instant | Decision |
|---|---|---|---|
| 0 | onedrive arrives (8) | onedrive 8 | onedrive runs |
| 1 | gcc arrives (4) | onedrive 7, gcc 4 | 4 < 7: gcc preempts onedrive |
| 2 | campus arrives (9) | gcc 3, onedrive 7, campus 9 | 9 > 3: gcc carries on |
| 3 | spotify arrives (2) | gcc 2, spotify 2, … | 2 = 2: no preemption, gcc carries on |
| 5 | gcc finishes | spotify 2, onedrive 7, campus 9 | spotify runs |
| 7 | spotify finishes | onedrive 7, campus 9 | onedrive runs |
| 14 | onedrive finishes | campus 9 | campus runs until 23 |
The t = 3 row is the trap: gcc has 2 ms left and spotify brings 2 ms. To preempt, the newcomer has to be strictly shorter; with a tie, paying for a context switch is not worth it. (If you use another criterion in the exam, write it in one line.)
Now the sums, subtracting the arrival (my midterm mistake): onedrive finishes at 14, turnaround 14 − 0 = 14, waiting 14 − 8 = 6. gcc: turnaround 5 − 1 = 4, waiting 4 − 4 = 0. campus: turnaround 23 − 2 = 21, waiting 21 − 9 = 12. spotify: turnaround 7 − 3 = 4, waiting 4 − 2 = 2. Mean waiting time: (6 + 0 + 12 + 2) / 4 = 20 / 4 = 5 ms. And if you had done end − burst: (6 + 1 + 14 + 5) / 4 = 6.5 ms. Exactly what happened to me.
Comparing the newcomer’s burst with the total burst of the running process. It must be compared with what it has left: at t = 1, gcc (4) is not compared with onedrive’s 8, but with its 7 remaining.
SRTF lowers the mean waiting time even further (5 ms against SJF’s 6.5) because short jobs no longer wait behind a long one that got in earlier. But it inherits SJF’s problem, made worse: a long process can be preempted again and again and starve.
Round Robin: taking turns with a quantum
Round Robin (RR) is like FCFS, but each process gets a time quantum Q on the CPU. If Q passes and the process is still running, the scheduler evicts it and puts it at the end of the ready queue, which works as a circular FIFO. It is preemptive and it is the typical time-sharing algorithm. In practice, Q is usually between 1 and 200 ms.
With Q = 3: onedrive gets in at t = 0 and at t = 3 uses up its quantum. At that very instant spotify arrives. Who goes first in the queue? The usual criterion puts the newcomer first, then the one returning after using up its quantum. This is what the queue looks like at every decision:
Read the picture from top to bottom. At t = 3 gcc (the head of the queue) gets in and onedrive goes to the end, behind spotify. At t = 6 gcc uses up its quantum (1 left) and joins the queue. At t = 9 spotify gets in and finishes at t = 11 without using up the quantum (it only needed 2). And so on until campus finishes at t = 23.
The sums: onedrive finishes at 20 (waiting 20 − 8 = 12), gcc at 15 (turnaround 14, waiting 10), campus at 23 (turnaround 21, waiting 12) and spotify at 11 (turnaround 8, waiting 6). Mean waiting time: (12 + 10 + 12 + 6) / 4 = 10 ms, the worst of the four. But look at the response: onedrive gets in at 0, gcc at 3 − 1 = 2, campus at 6 − 2 = 4 and spotify at 9 − 3 = 6. Mean (0 + 2 + 4 + 6) / 4 = 3 ms, the best. That is what Round Robin buys: everyone starts early.
A guarantee that is asked about a lot: if there are N processes in the queue, a process’s response time is at most Q · (N − 1). Here, 3 · (4 − 1) = 9 ms: nobody waits more than 9 ms to get in for the first time.
In a tie between a process arriving and another using up its quantum, putting the one leaving first. The usual criterion is the opposite (the newcomer first). What matters in the exam is writing which criterion you follow.
How the quantum matters
Q is not a detail: it decides how the whole algorithm behaves.
- Very large Q (longer than the bursts): everyone finishes before using up the quantum and Round Robin behaves like FCFS.
- Very small Q: the CPU is shared very evenly, as if each of the N processes had a processor N times slower (processor sharing)…
- …but if Q is too small, there are loads of context switches and performance drops. Q should be much longer than a context switch.
The chart comes from the second simulator in “Check it with Python” (further down), with the same four processes and assuming each context switch costs 0.5 ms. With Q = 1 the mean response is 0.75 ms, but there are 20 switches and only 69.7% of the CPU does useful work. With Q = 9 (longer than the longest burst) you get exactly FCFS: mean waiting time 8.75 ms. And look at the waiting line: it goes up and down. A smaller Q is not always better.
Q can be made variable, depending on the load or on the priority of the process. Linux (with its CFS scheduler) gives each process that gets the CPU a slice that depends on how long it has waited and on how many processes there are in the system.
All four, side by side
With the same processes, each algorithm wins at something different:
| Algorithm | Preemptive? | Who it picks | Mean waiting | Mean response | Its problem |
|---|---|---|---|---|---|
| FCFS | No | The first to arrive | 8.75 | 8.75 | Convoy effect |
| SJF | No | The shortest burst | 6.5 | 6.5 | Long jobs starve; needs estimates |
| SRTF | Yes | The least remaining time | 5 | 3.5 | Starvation; more switches |
| Round Robin | Yes | The next in the FIFO, with quantum Q | 10 | 3 | Choosing Q well |
When should you use each one?
| If what matters is… | Best… | Because… |
|---|---|---|
| Simplicity (batch jobs, no rush) | FCFS | A FIFO queue is enough |
| The lowest mean waiting (in theory) | SJF / SRTF | They serve short jobs first |
| The user feeling a quick response | Round Robin | Nobody waits more than Q · (N − 1) |
| No starvation | FCFS or Round Robin | They respect the order of the queue |
The supermarket queue sums it up well: FCFS is bad for people with little shopping (if you end up behind five full trolleys…) and SJF is bad for people with a lot (if you have the month’s shopping and everyone with just bread goes first).
Priority scheduling
Each process has a priority and the one with the highest priority gets the CPU. It can be preemptive or not (in the preemptive version, if a higher-priority one arrives, it evicts the running one). Priorities can be internal (computed by the OS, for example from memory or I/O usage) or external (set by the user). SJF is a special case: the priority is the estimated burst length.
The risk is the usual one: starvation of lower-priority processes. If gcc, spotify and campus keep arriving with higher priority, the onedrive backup never gets in. The fix is aging: gradually raising the priority of waiting processes, until the forgotten one becomes the highest priority and gets in. (The numbers in the picture are illustrative.)
Lottery
A curious approach: each process is given tickets and, in every time slice, a winning ticket is drawn. In the long run, CPU time is proportional to the number of tickets each process holds.
| Process | Tickets | CPU in the long run |
|---|---|---|
| gcc | 3 | 3 / 4 = 75% |
| onedrive | 1 | 1 / 4 = 25% |
How many tickets should each get? To behave like SRTF, more tickets for short jobs and fewer for long ones. So that nobody is left without CPU, everyone gets at least one (so there is no starvation). And if processes come or go, the tickets are shared out again proportionally.
Multilevel queues
Instead of one ready queue, several queues, each managed with a different policy. For example, interactive processes in a queue with Round Robin and batch processes in another with FCFS. The queues share the CPU by absolute priority (a queue is not served until the ones above it are empty) or with a percentage of time for each one.
The picture follows the classic example of four queues from higher to lower priority: system processes (FCFS), interactive (RR), student interactive (RR) and batch (FCFS). The dashed arrow is feedback: in multilevel feedback queues, a process can move from one queue to another, for example if its behaviour changes or, as in classic UNIX, if it has been waiting a long time (it moves up to a higher-priority queue, which is another way of avoiding starvation).
Multiprocessor scheduling
Several processors bring new problems:
- Asymmetric processing: one processor schedules the work of all the others. It is an obsolete technique.
- Symmetric processing (SMP): each processor does its own scheduling. There can be a single ready queue in shared memory or one queue per processor.
And two policies that pull in opposite directions:
- Processor affinity: keeping a process on the same processor, so it benefits from the data already in that CPU’s cache.
- Load balancing: avoiding very busy processors while others sit idle. With push migration, a supervisor task checks the load and moves processes; with pull migration, an idle processor “steals” processes from a busier one.
Saying that in symmetric processing “every processor schedules every other”. No: each one schedules its own work. The one that schedules the others is asymmetric processing.
Common mistakes
Forgetting to subtract the arrival. Turnaround = end − arrival; waiting = turnaround − burst. With arrivals other than 0, end − burst gives a number that looks reasonable and is wrong.
In non-preemptive SJF, taking the running process off the CPU because a shorter one arrived. Only SRTF does that.
In Round Robin, sending the preempted process to the front of the queue. It goes to the end, and keeps what it has left (it does not restart its burst).
Saying SJF minimises the mean response time. What it minimises is the mean waiting time. Round Robin wins on response.
With two of the three quantities (turnaround, waiting, burst) you get the third. If all three agree (turnaround = waiting + burst), your sums are right.
Check it with Python
The Gantt charts in this article are not drawn by hand: they come from a 40-line simulator you can run yourself. You need nothing installed beyond Python 3 (or paste it into pythontutor.com, choosing Python 3, to watch the queue and the left dictionary change millisecond by millisecond).
# The night before the deadline: four processes want the CPU (times in ms)
PROCESSES = [('onedrive', 0, 8), ('gcc', 1, 4), ('campus', 2, 9), ('spotify', 3, 2)]
Q = 3 # Round Robin time quantum
def schedule(alg):
arrival = {n: l for n, l, r in PROCESSES}
left = {n: r for n, l, r in PROCESSES} # what each one has LEFT
queue, gantt, current, used, t = [], [], None, 0, 0
while any(left.values()):
queue += [n for n, l, r in PROCESSES if l == t] # arrivals go to the back
if alg == 'RR' and current and used == Q: # quantum used up: behind
queue.append(current); current = None # the newcomers
if alg == 'SRTF' and current and queue and min(left[n] for n in queue) < left[current]:
queue.append(current); current = None # a shorter one arrives: preemption
if current is None: # CPU free: whose turn is it?
if alg in ('SJF', 'SRTF'): # the shortest (tie: the earlier arrival)
current = min(queue, key=lambda n: (left[n], arrival[n]))
else: # FCFS and RR: the head of the queue
current = queue[0]
queue.remove(current); used = 0
if gantt and gantt[-1][0] == current:
gantt[-1][2] = t + 1 # same process: the block grows
else:
gantt.append([current, t, t + 1]) # context switch: new block
left[current] -= 1; used += 1; t += 1
if left[current] == 0:
current = None # finishes and frees the CPU
return gantt
print('process arrival burst end turnaround waiting response')
for alg in ('FCFS', 'SJF', 'SRTF', 'RR'):
gantt = schedule(alg)
print(f'== {alg}' + (f' (Q = {Q})' if alg == 'RR' else '') + ': ' + ' '.join(f'{n}[{a}-{b}]' for n, a, b in gantt))
means = [0, 0, 0]
for n, l, r in PROCESSES:
end = max(b for m, a, b in gantt if m == n) # last instant on the CPU
first = min(a for m, a, b in gantt if m == n) # first time it runs
turnaround, waiting, response = end - l, end - l - r, first - l
means = [x + y / len(PROCESSES) for x, y in zip(means, (turnaround, waiting, response))]
print(f'{n:<9}{l:>8}{r:>8}{end:>5}{turnaround:>11}{waiting:>8}{response:>11}')
print(f'{"mean":<9}{"":>21}{means[0]:>11.2f}{means[1]:>8.2f}{means[2]:>11.2f}')
The idea is to simulate the CPU one millisecond at a time: at each t, arrivals join the queue, the code decides whether someone leaves (quantum used up or preemption), picks who gets in if the CPU is free and runs for 1 ms. This is its real output:
process arrival burst end turnaround waiting response == FCFS: onedrive[0-8] gcc[8-12] campus[12-21] spotify[21-23] onedrive 0 8 8 8 0 0 gcc 1 4 12 11 7 7 campus 2 9 21 19 10 10 spotify 3 2 23 20 18 18 mean 14.50 8.75 8.75 == SJF: onedrive[0-8] spotify[8-10] gcc[10-14] campus[14-23] onedrive 0 8 8 8 0 0 gcc 1 4 14 13 9 9 campus 2 9 23 21 12 12 spotify 3 2 10 7 5 5 mean 12.25 6.50 6.50 == SRTF: onedrive[0-1] gcc[1-5] spotify[5-7] onedrive[7-14] campus[14-23] onedrive 0 8 14 14 6 0 gcc 1 4 5 4 0 0 campus 2 9 23 21 12 12 spotify 3 2 7 4 2 2 mean 10.75 5.00 3.50 == RR (Q = 3): onedrive[0-3] gcc[3-6] campus[6-9] spotify[9-11] onedrive[11-14] gcc[14-15] campus[15-18] onedrive[18-20] campus[20-23] onedrive 0 8 20 20 12 0 gcc 1 4 15 14 10 2 campus 2 9 23 21 12 4 spotify 3 2 11 8 6 6 mean 15.75 10.00 3.00
The four tables are the ones in the pictures: same end times, same waiting times and same means (8.75, 6.5, 5 and 10 ms of waiting). The heart of the simulator is these lines:
queue += [n for n, l, r in PROCESSES if l == t] # arrivals go to the back
if alg == 'RR' and current and used == Q: # quantum used up: behind
queue.append(current); current = None # the newcomers
if alg == 'SRTF' and current and queue and min(left[n] for n in queue) < left[current]:
queue.append(current); current = None # a shorter one arrives: preemption
if current is None: # CPU free: whose turn is it?
if alg in ('SJF', 'SRTF'): # the shortest (tie: the earlier arrival)
current = min(queue, key=lambda n: (left[n], arrival[n]))
else: # FCFS and RR: the head of the queue
current = queue[0]
queue.remove(current); used = 0
The order of the if statements is the tie-break rule. First the arrivals at t join the queue (the queue += line), and only then does the process that used up its quantum join it: that is why, at t = 3, spotify ends up ahead of onedrive. In SRTF, the strict < is the “only preempt if shorter” rule: at t = 3, since 2 is not less than 2, gcc stays. And the key (left[n], arrival[n]) in the min says “the one with the least left and, in a tie, the earlier arrival”.
Things to look at:
- In the SRTF line, onedrive appears twice (
onedrive[0-1]andonedrive[7-14]): that is the preemption at t = 1. Its response is 0 even though its waiting time is 6. - In the RR table, the response column (0, 2, 4, 6) is the best of all, even though the waiting column is the worst.
- In FCFS and SJF, response and waiting always match: since they do not preempt, a process only waits once, before getting in.
- In all four tables the last process finishes at t = 23 (8 + 4 + 9 + 2): the total work does not change, only who waits.
The second simulator answers the quantum question: it repeats Round Robin with several values of Q and counts context switches, assuming each one costs 0.5 ms.
# Which quantum? Round Robin with the same four processes and several Q
PROCESSES = [('onedrive', 0, 8), ('gcc', 1, 4), ('campus', 2, 9), ('spotify', 3, 2)]
SWITCH = 0.5 # cost of each context switch (ms): save one PCB and load another
def round_robin(Q):
left = {n: r for n, l, r in PROCESSES}
queue, gantt, current, used, t = [], [], None, 0, 0
while any(left.values()):
queue += [n for n, l, r in PROCESSES if l == t] # arrivals go to the back
if current and used == Q: # quantum used up: to the back,
queue.append(current); current = None # behind the newcomers
if current is None:
current = queue.pop(0); used = 0 # FIFO circular
if gantt and gantt[-1][0] == current:
gantt[-1][2] = t + 1
else:
gantt.append([current, t, t + 1])
left[current] -= 1; used += 1; t += 1
if left[current] == 0:
current = None
return gantt
print(' Q avg waiting avg turnaround avg response switches useful CPU')
for Q in (1, 2, 3, 4, 6, 9):
gantt = round_robin(Q)
waiting = turnaround = response = 0
for n, l, r in PROCESSES:
end = max(b for m, a, b in gantt if m == n)
turnaround += (end - l) / len(PROCESSES)
waiting += (end - l - r) / len(PROCESSES)
response += (min(a for m, a, b in gantt if m == n) - l) / len(PROCESSES)
switches = len(gantt) - 1 # each new block = one switch
cpu = gantt[-1][2] # ms of useful work (23)
useful = 100 * cpu / (cpu + switches * SWITCH) # % not lost to switches
print(f'{Q:>3}{waiting:>14.2f}{turnaround:>16.2f}{response:>17.2f}{switches:>10}{useful:>10.1f} %')
Its output, which is what the quantum chart draws:
Q avg waiting avg turnaround avg response switches useful CPU 1 9.25 15.00 0.75 20 69.7 % 2 9.00 14.75 2.00 10 82.1 % 3 10.00 15.75 3.00 8 85.2 % 4 8.50 14.25 4.50 5 90.2 % 6 10.50 16.25 6.50 5 90.2 % 9 8.75 14.50 8.75 3 93.9 %
- The mean response grows with Q (0.75 → 8.75 ms): with small quanta everyone gets in straight away.
- Context switches drop from 20 to 3, and useful CPU rises from 69.7% to 93.9%: with Q = 1 almost a third of the CPU is thrown away saving and loading PCBs.
- With Q = 9, the mean waiting and turnaround (8.75 and 14.5) are FCFS’s: the quantum no longer preempts anyone.
- The mean waiting time does not fall steadily (9.25, 9, 10, 8.5, 10.5, 8.75): it depends on when the quanta coincide with the arrivals. There is no “magic Q” for everything.
And if you want to try your own processes without writing code, the Lab’s CPU scheduling simulator draws the FCFS, SJF, SRTF and Round Robin Gantt chart step by step and gives you the averages.
Summary
| Concept | What you need to remember |
|---|---|
| Scheduler | Decides which ready process gets the CPU and, if preemptive, when the running one leaves |
| Bursts | A process’s life alternates CPU and I/O; most CPU bursts last under 8 ms |
| Metrics | Turnaround = end − arrival = waiting + CPU; response = first run − arrival |
| Non-preemptive / preemptive | The process lets go of the CPU itself / the OS can take it out (needed for time sharing and real time) |
| FCFS | FIFO, non-preemptive, simple; convoy effect and very sensitive to order |
| SJF / SRTF | The shortest / the least remaining time; minimum mean waiting; starvation |
| Round Robin | Circular FIFO with quantum Q; response ≤ Q · (N − 1); large Q = FCFS, small Q = many switches |
| Priorities | The highest priority runs; starvation → aging |
| Lottery | CPU proportional to tickets; everyone gets at least one |
| Multilevel queues | One policy per queue; with feedback, processes change queue |
| Multiprocessor | Asymmetric (obsolete) or symmetric; affinity vs load balancing (push / pull) |
Three ideas to take away:
- Everything comes from the Gantt chart. Draw first, write down the end times, then subtract: turnaround = end − arrival, waiting = turnaround − burst. And never forget the arrival.
- There is no perfect algorithm. SJF and SRTF win on mean waiting, Round Robin on response, FCFS on simplicity. Each system chooses which metric to sacrifice.
- Ties are settled with a rule, and you write it down. SRTF only preempts if the newcomer is strictly shorter; in Round Robin, the newcomer goes before the one that used up its quantum.
Now it is your turn. First, in the CPU scheduling guided practice we solve exam problems together, step by step, with their Gantt charts and sums; then the CPU scheduling exercises have a test with every exam format, five Gantt charts with boxes that mark themselves (FCFS, SJF, SRTF and Round Robin with two quanta) and the open questions. And in the next topic we will see what happens when these processes that take turns on the CPU share data: concurrency and critical sections.
Next step: practiceCPU scheduling — practice with guided problems step by step: FCFS versus SJF, a preemption in SRTF, the Round Robin queue and an exercise in the exam format (and the quantum I gave to the wrong process)Did this article help you? Here is how you can support SergioLearns →
