CPU 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)

In the mock exam we did in class before the midterm I got a Round Robin with quantum 2. I drew the Gantt chart, worked out the means and felt very pleased with myself. When it was marked, my mean response time was 3 and the right one was 1.75. The mistake was in a single instant: at t = 2 one process used up its quantum just as another arrived, and I put the one leaving the CPU first in the queue. With that one change, everything after it shifted. Since then, every time a quantum ends at the same instant someone arrives, I stop and write down the whole queue before carrying on.

This is the guided practice for CPU scheduling. In the CPU scheduling theory you saw the metrics and the four algorithms that come up in the exam (FCFS, SJF, SRTF and Round Robin), always with the processes from the night before the deadline. Here we solve four problems step by step, the way they are done in the written part of the exam: the Gantt chart is not enough, you need to know why each process runs when it does and get the sums right. For each one you will see the method, the reason for each decision, how to check it and the mistakes that come up most. Afterwards, in the CPU scheduling exercises, it is your turn with five Gantt charts that mark themselves.

Before you start

It helps to be clear about:

• What a process’s arrival, burst and finish instant are.
• The three formulas: turnaround = finish − arrival, waiting = turnaround − burst and response = first instant on the CPU − arrival.
• Which algorithms preempt (SRTF and Round Robin) and which do not (FCFS and SJF).
• The tie-breaking criteria from the theory: by arrival order and, if they arrive together, by table order; SRTF only preempts if the newcomer is strictly shorter; in Round Robin, the newcomer joins the queue before the process that has just used up its quantum.

If any of them sounds shaky, go over the theory before carrying on.

How to solve a scheduling exercise

The four problems follow the same four-step method. I give it here once so as not to repeat it:

1. Write down the data (process, arrival and burst) and the algorithm, with its quantum if it is Round Robin. Write the tie-breaking criterion before you start.
2. Decide at the instants that matter: in non-preemptive algorithms, every time the CPU becomes free; in SRTF, also at every arrival; in Round Robin, every time a quantum runs out. Nothing happens between those instants.
3. Draw the Gantt chart and write down the finish of each process (the last slice of each one).
4. Subtract and check: turnaround, waiting and response with the formulas, the means and two quick checks (that the last finish is the sum of the bursts if the CPU never idles, and that each waiting time is the time the process is «outside» the chart since it arrived).

Problem 1: FCFS versus SJF

Statement. On the morning of the deadline you have four processes on your laptop (times in milliseconds). Draw the Gantt chart with FCFS and with non-preemptive SJF and work out the mean waiting time and the mean turnaround in both. Which one is better?

Process	What it is	Arrival	Burst
zoom	the group video call	0	7
git	the git push of the assignment	2	3
gcc	compiling the latest version	3	5
latex	the report as a PDF	5	1

The idea

Both algorithms are non-preemptive: the process that gets the CPU leaves when it finishes. So you only need to decide every time the CPU becomes free. FCFS picks the one that arrived first; SJF, the one with the shortest burst among those that have already arrived. That last bit is the key: SJF cannot pick a process that has not arrived yet, even if it is shorter.

Step by step

FCFS. The arrival order is zoom, git, gcc, latex, and each one starts when the previous one finishes:

Instant	CPU free, waiting…	Runs	Until
0	zoom	zoom	7
7	git, gcc, latex	git (arrived first)	10
10	gcc, latex	gcc	15
15	latex	latex	16

SJF. At t = 0 only zoom is there; it runs and does not leave until t = 7. At t = 7 git (3), gcc (5) and latex (1) are waiting: the shortest is latex, even though it arrived last. Then git (3) and finally gcc (5).

Instant	CPU free, waiting… (burst)	Runs	Until
0	zoom (7)	zoom	7
7	git (3), gcc (5), latex (1)	latex	8
8	git (3), gcc (5)	git	11
11	gcc (5)	gcc	16

Now the sums, with turnaround = finish − arrival and waiting = turnaround − burst:

Process	Arrival	Burst	FCFS finish	Turnaround	Waiting	SJF finish	Turnaround	Waiting
zoom	0	7	7	7	0	7	7	0
git	2	3	10	8	5	11	9	6
gcc	3	5	15	12	7	16	13	8
latex	5	1	16	11	10	8	3	2
Mean				9.5	5.5		8	4

Means: FCFS, turnaround $(7 + 8 + 12 + 11) / 4 = 38 / 4 = 9.5$ ms and waiting $(0 + 5 + 7 + 10) / 4 = 22 / 4 = 5.5$ ms. SJF, turnaround $32 / 4 = 8$ ms and waiting $16 / 4 = 4$ ms. SJF is better in both.

Check

• The CPU never idles (someone is always waiting), so both charts must end at $7 + 3 + 5 + 1 = 16$: they do.
• Each waiting time is the time the process spends without the CPU since it arrived. latex in FCFS arrives at 5 and starts at 15: 10 ms, as the table says.
• In non-preemptive algorithms, waiting equals response (each process runs only once).

Questions you might ask

Why does SJF not pick latex at t = 0 if it is the shortest? Because at t = 0 latex has not arrived. SJF only compares the processes in the ready queue at the moment of deciding.

Why does SJF win on mean waiting? Because by putting the short one first, its few milliseconds are added to the waiting time of few processes, and the long ones only wait a little more. It is the optimal algorithm for mean waiting when all processes are available at once, which is why it is used as a reference.

Does any process lose out with SJF? Yes: git waits 6 instead of 5 and gcc 8 instead of 7. The mean improves because latex gains a lot (from 10 to 2). If short processes kept arriving, gcc could wait forever: that is SJF’s starvation.

What if two processes had the same burst at t = 7? You apply the tie-breaking criterion: the one that arrived first (and, if they arrived together, the one earlier in the table). In the exam, write it in one line: that way it is clear it was not chance.

Try it yourself

• Change latex’s arrival to t = 8. Does anything change in SJF? Why?
• Work out the mean turnaround of FCFS if the arrival order were latex, git, gcc, zoom, all at t = 0. How much does it improve?

Problem 2: SRTF with one preemption

Statement. Now a big download is running and other processes keep arriving. Draw the Gantt chart with SRTF (preemptive SJF) and work out the turnaround, waiting and response of each process and their means.

Process	Arrival	Burst
download	0	6
gcc	1	3
antivirus	2	7
spotify	4	1

The idea

SRTF always runs the process with the least time left. That is why you have to decide at two kinds of instant: every time someone arrives (it may preempt the running process if it needs less than what that one has left) and every time someone finishes. So as not to get lost, keep a column with what each process has left at each decision instant.

Step by step

Instant	What happens	Left for…	Decision
0	download arrives	download 6	download runs
1	gcc arrives	download 5, gcc 3	3 < 5: gcc preempts download
2	antivirus arrives	gcc 2, download 5, antivirus 7	7 is not less than 2: gcc goes on
4	gcc finishes; spotify arrives	download 5, antivirus 7, spotify 1	spotify runs
5	spotify finishes	download 5, antivirus 7	download runs
10	download finishes	antivirus 7	antivirus runs
17	antivirus finishes	—	end

Process	Arrival	Burst	First instant on CPU	Finish	Turnaround	Waiting	Response
download	0	6	0	10	10	4	0
gcc	1	3	1	4	3	0	0
antivirus	2	7	10	17	15	8	8
spotify	4	1	4	5	1	0	0
Mean					7.25	3	2

Mean turnaround $29 / 4 = 7.25$ ms, mean waiting $12 / 4 = 3$ ms and mean response $8 / 4 = 2$ ms.

Check

• The sum of bursts is $6 + 3 + 7 + 1 = 17$ and the chart ends at 17, with no gaps.
• download appears in two slices (0-1 and 5-10): $1 + 5 = 6$ ms, its whole burst. Its waiting time, 4, is exactly the gap between the two slices (from 1 to 5).
• In a preemptive algorithm, waiting and response can differ: download has response 0 (it ran as soon as it arrived) but waits 4.

Questions you might ask

Why does antivirus not preempt gcc at t = 2? Because gcc has 2 ms left and antivirus needs 7. SRTF always compares with what the running process has left, not with its initial burst.

What if at t = 4 download had 1 left, the same as spotify? It would be a tie between two waiting processes (the CPU has just become free): with the theory’s criterion arrival breaks the tie and download would run, since it arrived first. The «strictly shorter» rule is for something else: deciding whether a newcomer preempts the process already on the CPU. If your lecturer uses another criterion, write it down and apply it the same way throughout the exercise.

Why does antivirus wait so long? Because it is the longest and every short process that arrives jumps ahead of it. It is the same starvation as in SJF, but more marked, because SRTF also reacts to arrivals.

How many context switches are there? Each change of process in the chart is one: download → gcc → spotify → download → antivirus, four. In the theory they were assumed to be free; in a real system each one costs a bit of CPU, which is why preempting too much is not free either.

Try it yourself

• Repeat the problem with non-preemptive SJF. How much worse does the mean waiting time get?
• Change gcc’s burst to 5. Does it now preempt download at t = 1? Why?

Problem 3: the Round Robin queue

Statement. With Round Robin and quantum q = 2, draw the Gantt chart of these processes, write the ready queue at each change and work out the mean turnaround, waiting and response.

Process	Arrival	Burst
zoom	0	5
gcc	1	3
spotify	2	1
latex	3	4

The idea

Round Robin is FCFS with turns: the first in the queue uses the CPU for at most one quantum. If it finishes earlier, it leaves; if not, it goes back to the end of the queue. The whole problem is keeping the queue right. And the only tricky moment is when a quantum runs out at the same instant another process arrives: with the theory’s criterion, the newcomer joins the queue before the one leaving the CPU.

Step by step

Instant	On CPU (slice)	Arrive	Queue after the slice
0	zoom (0-2), 3 left	gcc (1), spotify (2)	gcc, spotify, zoom
2	gcc (2-4), 1 left	latex (3)	spotify, zoom, latex, gcc
4	spotify (4-5), finishes	—	zoom, latex, gcc
5	zoom (5-7), 1 left	—	latex, gcc, zoom
7	latex (7-9), 2 left	—	gcc, zoom, latex
9	gcc (9-10), finishes	—	zoom, latex
10	zoom (10-11), finishes	—	latex
11	latex (11-13), finishes	—	—

The row for t = 0 is the one from the story at the start: zoom uses up its quantum at t = 2, which is exactly when spotify arrives. spotify joins the queue before zoom.

Process	Arrival	Burst	First instant on CPU	Finish	Turnaround	Waiting	Response
zoom	0	5	0	11	11	6	0
gcc	1	3	2	10	9	6	1
spotify	2	1	4	5	3	2	2
latex	3	4	7	13	10	6	4
Mean					8.25	5	1.75

Mean turnaround $33 / 4 = 8.25$ ms, mean waiting $20 / 4 = 5$ ms and mean response $7 / 4 = 1.75$ ms.

Check

• Sum of bursts $5 + 3 + 1 + 4 = 13$ and the chart ends at 13.
• No slice lasts more than q = 2, and the 1 ms ones are always the end of a process (spotify, gcc and zoom).
• zoom has three slices (0-2, 5-7 and 10-11) adding up to 5, its burst. Its waiting time, 6, is the gaps: from 2 to 5 (3) and from 7 to 10 (3).

Questions you might ask

Why does Round Robin win on response and not on waiting? Because it shares the CPU among everyone straight away: nobody waits more than a few quanta to start (mean response 1.75). But by slicing, long processes finish later, and total waiting goes up.

What happens if the quantum is very large? If q is larger than every burst, nobody uses up the quantum and Round Robin becomes FCFS. If it is very small, there are so many context switches that the system spends more time switching than working.

What if the quantum runs out and the queue is empty? The process goes back on the CPU straight away. The chart shows two consecutive slices of the same process, which you can draw as one.

Why does the queue order change the response and not always the waiting? Because response depends on when each process starts for the first time, and that is decided by the queue order in the first instants. In the story at the start, with the queue in the wrong order, the mean waiting came out the same, 5, but the mean response went from 1.75 to 3.

Try it yourself

• Repeat the problem with q = 3. How many slices does the chart have now?
• With which quantum would you get the same chart as with FCFS?

Problem 4: an exercise in the exam format

The written part of the IC2 exam usually includes a quick process exercise: some processes with their arrival and burst, one or two algorithms (FCFS, SJF, SRTF or Round Robin) and the mean times. What is marked is the Gantt chart, the table with the sums and that the result is consistent. This exercise is original and written in that format, so you can practice answering quickly and well.

Exercise. Given the processes in the table (times in ms), a) draw the Gantt chart with non-preemptive SJF and with Round Robin with q = 3; b) work out in both the mean turnaround, waiting and response times; c) say which one is better on mean waiting and which on mean response.

Process	Arrival	Burst
P1	0	6
P2	1	4
P3	2	2
P4	4	5
P5	6	1

Result	SJF	RR (q = 3)
Mean turnaround	___	___
Mean waiting	___	___
Mean response	___	___

The idea

Two algorithms with the same data: the trick is not to mix them up. Do one completely (chart, table and means) and then the other. In SJF, the first decision with candidates is at t = 6, when P1 finishes and everyone has arrived. In Round Robin, the tricky instant is t = 6: P2 uses up its quantum just as P5 arrives.

Step by step

SJF. P1 runs at t = 0 and does not leave until t = 6. At t = 6, P2 (4), P3 (2), P4 (5) and P5 (1, just arrived) are waiting: by burst, P5, P3, P2 and P4.

Round Robin, q = 3.

Instant	On CPU (slice)	Arrive	Queue after the slice
0	P1 (0-3), 3 left	P2 (1), P3 (2)	P2, P3, P1
3	P2 (3-6), 1 left	P4 (4), P5 (6)	P3, P1, P4, P5, P2
6	P3 (6-8), finishes	—	P1, P4, P5, P2
8	P1 (8-11), finishes	—	P4, P5, P2
11	P4 (11-14), 2 left	—	P5, P2, P4
14	P5 (14-15), finishes	—	P2, P4
15	P2 (15-16), finishes	—	P4
16	P4 (16-18), finishes	—	—

Process	Arrival	Burst	SJF: finish	Turnaround	Waiting	Resp.	RR: finish	Turnaround	Waiting	Resp.
P1	0	6	6	6	0	0	11	11	5	0
P2	1	4	13	12	8	8	16	15	11	2
P3	2	2	9	7	5	5	8	6	4	4
P4	4	5	18	14	9	9	18	14	9	7
P5	6	1	7	1	0	0	15	9	8	8
Mean				8	4.4	4.4		11	7.4	4.2

Result	SJF	RR (q = 3)
Mean turnaround	40 / 5 = 8	55 / 5 = 11
Mean waiting	22 / 5 = 4.4	37 / 5 = 7.4
Mean response	22 / 5 = 4.4	21 / 5 = 4.2

c) SJF is better on mean waiting (4.4 versus 7.4) and Round Robin, narrowly, on mean response (4.2 versus 4.4).

Check and how it is marked

• Both charts end at $6 + 4 + 2 + 5 + 1 = 18$, and each process adds up its burst across all its slices.
• In SJF, waiting = response for every process (it is non-preemptive): if yours differed, something would be wrong.
• A check on the means: the sum of waiting times is the sum of turnarounds minus the sum of bursts, $40 – 18 = 22$ in SJF and $55 – 18 = 37$ in RR. If it does not add up, check the finishes.

In marking, what counts is the chart (with the instants written on the axis), the table with each subtraction and the means. A mistake at the start of the chart drags into all the sums, so it pays to go over the first two decision instants before carrying on. And the answer to part c) must come from your numbers, not from what «usually happens»: here Round Robin wins on response, but only just.

Try it yourself

• Solve the same exercise with SRTF. Does it improve on SJF’s mean waiting?
• With Round Robin, what is the smallest quantum that gives the same chart as FCFS?

Common mistakes in this practice

• Forgetting to subtract the arrival. Waiting = finish − arrival − burst; without the arrival it only works for those arriving at t = 0.
• Picking a process that has not arrived yet. SJF and SRTF only compare the processes in the queue at that instant.
• In SRTF, comparing with the original burst. You compare with what the running process has left.
• In Round Robin, getting the queue out of order in ties between a used-up quantum and an arrival.
• Not writing down the tie-breaking criterion. If the exercise does not give one, write yours and always apply it the same way.
• Not checking. The last finish, the sum of waiting times and each process’s slices catch almost every mistake.

Check it with Python

This paper scheduler solves the four problems with the same criteria as the theory and prints the chart and the table of each one. Run it after doing the problems by hand, not before.

# Paper CPU scheduler: FCFS, SJF, SRTF and Round Robin with the processes of the practice.
# Criteria (those of the theory): ties by arrival and, failing that, by table order; SRTF only preempts
# if the newcomer is STRICTLY shorter; in Round Robin the newcomer joins the queue before
# the process that has just used up its quantum.
def schedule(procs, alg, q=None):
    left = {p: r for p, _, r in procs}; arr = {p: l for p, l, _ in procs}
    order = [p for p, _, _ in procs]; t, gantt, end, queue, seen = 0, [], {}, [], set()
    def arrive(until):   # put in the queue, in order, those that have arrived by that instant
        for p in order:
            if p not in seen and arr[p] <= until: queue.append(p); seen.add(p)
    arrive(0)
    while len(end) < len(procs):
        if not queue: t = min(arr[p] for p in order if p not in seen); arrive(t); continue
        if alg in ("SJF", "SRTF"):
            p = min(queue, key=lambda x: (left[x], arr[x], order.index(x)))
        else:
            p = queue[0]                      # FCFS and RR: the first one in the queue
        queue.remove(p)
        if alg == "RR": dur = min(q, left[p])
        elif alg == "SRTF":                   # runs until it finishes or until someone shorter arrives
            dur = left[p]
            for o in order:
                if o not in seen and t < arr[o] < t + dur and left[o] < left[p] - (arr[o] - t):
                    dur = arr[o] - t; break
        else: dur = left[p]
        gantt.append((p, t, t + dur)); t += dur; left[p] -= dur
        arrive(t)                             # first the newcomers...
        if left[p]: queue.append(p)           # ...and then the one that has not finished
        else: end[p] = t
    return gantt, end

def report(name, procs, alg, q=None):
    g, end = schedule(procs, alg, q)
    merged = []                               # merge consecutive slices of the same process
    for p, a, b in g:
        if merged and merged[-1][0] == p and merged[-1][2] == a: merged[-1] = (p, merged[-1][1], b)
        else: merged.append((p, a, b))
    print(f"== {name}: {alg}" + (f" q={q}" if q else ""))
    print("   Gantt:", " | ".join(f"{p} {a}-{b}" for p, a, b in merged))
    tot = {"ret": 0, "wait": 0, "resp": 0}
    for p, l, r in procs:
        ret = end[p] - l; wait = ret - r; resp = min(a for x, a, _ in g if x == p) - l
        tot["ret"] += ret; tot["wait"] += wait; tot["resp"] += resp
        print(f"   {p:<9} arrives {l:>2}  burst {r:>2}  end {end[p]:>2}  turnaround {ret:>2}  waiting {wait:>2}  response {resp:>2}")
    n = len(procs)
    print(f"   means: turnaround {tot['ret']}/{n} = {tot['ret']/n:.2f}  waiting {tot['wait']}/{n} = {tot['wait']/n:.2f}  response {tot['resp']}/{n} = {tot['resp']/n:.2f}")

A = [("zoom", 0, 7), ("git", 2, 3), ("gcc", 3, 5), ("latex", 5, 1)]
B = [("download", 0, 6), ("gcc", 1, 3), ("antivirus", 2, 7), ("spotify", 4, 1)]
C = [("zoom", 0, 5), ("gcc", 1, 3), ("spotify", 2, 1), ("latex", 3, 4)]
D = [("P1", 0, 6), ("P2", 1, 4), ("P3", 2, 2), ("P4", 4, 5), ("P5", 6, 1)]
report("Problem 1", A, "FCFS"); report("Problem 1", A, "SJF")
report("Problem 2", B, "SRTF")
report("Problem 3", C, "RR", 2)
report("Problem 4", D, "SJF"); report("Problem 4", D, "RR", 3)

Output (run once):

== Problem 1: FCFS
   Gantt: zoom 0-7 | git 7-10 | gcc 10-15 | latex 15-16
   zoom      arrives  0  burst  7  end  7  turnaround  7  waiting  0  response  0
   git       arrives  2  burst  3  end 10  turnaround  8  waiting  5  response  5
   gcc       arrives  3  burst  5  end 15  turnaround 12  waiting  7  response  7
   latex     arrives  5  burst  1  end 16  turnaround 11  waiting 10  response 10
   means: turnaround 38/4 = 9.50  waiting 22/4 = 5.50  response 22/4 = 5.50
== Problem 1: SJF
   Gantt: zoom 0-7 | latex 7-8 | git 8-11 | gcc 11-16
   zoom      arrives  0  burst  7  end  7  turnaround  7  waiting  0  response  0
   git       arrives  2  burst  3  end 11  turnaround  9  waiting  6  response  6
   gcc       arrives  3  burst  5  end 16  turnaround 13  waiting  8  response  8
   latex     arrives  5  burst  1  end  8  turnaround  3  waiting  2  response  2
   means: turnaround 32/4 = 8.00  waiting 16/4 = 4.00  response 16/4 = 4.00
== Problem 2: SRTF
   Gantt: download 0-1 | gcc 1-4 | spotify 4-5 | download 5-10 | antivirus 10-17
   download  arrives  0  burst  6  end 10  turnaround 10  waiting  4  response  0
   gcc       arrives  1  burst  3  end  4  turnaround  3  waiting  0  response  0
   antivirus arrives  2  burst  7  end 17  turnaround 15  waiting  8  response  8
   spotify   arrives  4  burst  1  end  5  turnaround  1  waiting  0  response  0
   means: turnaround 29/4 = 7.25  waiting 12/4 = 3.00  response 8/4 = 2.00
== Problem 3: RR q=2
   Gantt: zoom 0-2 | gcc 2-4 | spotify 4-5 | zoom 5-7 | latex 7-9 | gcc 9-10 | zoom 10-11 | latex 11-13
   zoom      arrives  0  burst  5  end 11  turnaround 11  waiting  6  response  0
   gcc       arrives  1  burst  3  end 10  turnaround  9  waiting  6  response  1
   spotify   arrives  2  burst  1  end  5  turnaround  3  waiting  2  response  2
   latex     arrives  3  burst  4  end 13  turnaround 10  waiting  6  response  4
   means: turnaround 33/4 = 8.25  waiting 20/4 = 5.00  response 7/4 = 1.75
== Problem 4: SJF
   Gantt: P1 0-6 | P5 6-7 | P3 7-9 | P2 9-13 | P4 13-18
   P1        arrives  0  burst  6  end  6  turnaround  6  waiting  0  response  0
   P2        arrives  1  burst  4  end 13  turnaround 12  waiting  8  response  8
   P3        arrives  2  burst  2  end  9  turnaround  7  waiting  5  response  5
   P4        arrives  4  burst  5  end 18  turnaround 14  waiting  9  response  9
   P5        arrives  6  burst  1  end  7  turnaround  1  waiting  0  response  0
   means: turnaround 40/5 = 8.00  waiting 22/5 = 4.40  response 22/5 = 4.40
== Problem 4: RR q=3
   Gantt: P1 0-3 | P2 3-6 | P3 6-8 | P1 8-11 | P4 11-14 | P5 14-15 | P2 15-16 | P4 16-18
   P1        arrives  0  burst  6  end 11  turnaround 11  waiting  5  response  0
   P2        arrives  1  burst  4  end 16  turnaround 15  waiting 11  response  2
   P3        arrives  2  burst  2  end  8  turnaround  6  waiting  4  response  4
   P4        arrives  4  burst  5  end 18  turnaround 14  waiting  9  response  7
   P5        arrives  6  burst  1  end 15  turnaround  9  waiting  8  response  8
   means: turnaround 55/5 = 11.00  waiting 37/5 = 7.40  response 21/5 = 4.20

Things to notice:

1. In Problem 2, the chart has two download slices (0-1 and 5-10): the preemption at t = 1 comes straight out of the condition left[o] < left[p] - (arr[o] - t), which compares with what is left at the instant of arrival.
2. In Problem 3, the order of the two lines arrive(t) and queue.append(p) is the theory’s criterion: newcomers first. If you swap them, the mean response goes from 1.75 to 3, as in the story.
3. In SJF and SRTF, min(queue, key=…) breaks ties by arrival and table order; with other criteria, only that key would need changing.
4. report() merges consecutive slices of the same process to draw the chart as on paper, but computes the response from each process’s first slice.

If you want to see it animated, step by step and with your own data, there is the CPU scheduling simulator in the Lab: it uses the same tie-breaking criteria.

Summary

• Decide only at the instants that matter: CPU free (all), arrivals (SRTF) and used-up quanta (Round Robin).
• SJF and SRTF choose among those that have already arrived; SRTF compares with what the running process has left.
• In Round Robin, keep the queue written down; the newcomer goes before the one that used up its quantum.
• Turnaround = finish − arrival; waiting = turnaround − burst; response = first instant on the CPU − arrival.
• SJF and SRTF usually win on mean waiting; Round Robin on response. But the conclusion comes from your numbers.
• Always check: the last finish, each process’s slices and that the sum of waiting times is the sum of turnarounds minus the sum of bursts.

Checklist: have you practised it?

• Have you done the four problems on paper before reading the step by step?
• Do you know at which instants each algorithm decides?
• Can you write the Round Robin queue at each change without getting the ties wrong?
• Do you know how to compute the response and why it equals the waiting time in non-preemptive algorithms?
• Have you checked the four problems with the Python program or the simulator?
• Have you tried the «Try it yourself» tasks without looking at the theory?

If you answered yes to almost everything, you are ready for the CPU scheduling exercises, with a test on the whole topic and five Gantt charts with boxes that mark themselves. See you there!

Next step: exercisesCPU scheduling — exam-style exercises with a test, five Gantt charts that mark themselves and open questions (and the arrival I no longer forget to subtract)

Did this article help you? Here is how you can support SergioLearns →