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

BySergio Alejandro Medina Ospina
ExercisesFrom scratchIC230 min read

In the midterm I drew an SRTF Gantt chart correctly and lost the marks on the sums: I worked out the waiting times without subtracting the arrival. Since then I always do Gantt charts the same way, with a table of end, turnaround and waiting next to them, and it has not happened again. This article is designed so you pick up that same habit before the exam, because CPU scheduling is the star topic of the written part: you will almost certainly get a Gantt chart with FCFS, SJF, SRTF or Round Robin and its mean times.

If you have not read the CPU scheduling theory yet, start there: here it is taken as known. All the questions are original: they cover the same ground as the exam, with different data and wording. And if you first want to see these problems solved step by step, there is the CPU scheduling guided practice.

How to use this article

  1. Do the test without looking at the theory. Each question has its own “Check” button and explanation; multiple-choice questions subtract for every wrong tick, as in the exam.
  2. Solve the five Gantt charts on paper, with the time axis drawn, and only then type the numbers into the boxes. Decimals accept a comma or a point.
  3. Write the open questions as a paragraph, without bullet points, and compare them with the model answer and the list of what the marker looks for.
  4. Go over the cheat sheet the night before: it has the formulas, the tie-break rules and the symptoms of the usual mistakes.

To check a Gantt chart with other data, open it in the CPU scheduling simulator: it shows every scheduler decision and each process’s waiting time.

Test: CPU scheduling

Thirty questions in every exam format: single choice, multiple choice with penalties, true or false, gaps, matching, ordering, short answer and one calculation with boxes. The calculations are short: the long Gantt charts are in the next section.

Question 1Single choice

Your laptop has a single core and four processes in the ready queue. What does the (short-term) CPU scheduler decide?

  1. Which ready process gets the CPU when it becomes free (and, if it is preemptive, when the running one must leave)
  2. Which programs are loaded from disk into memory
  3. How much memory each process gets
  4. In which order disk requests are served
Solution

Answer: Which ready process gets the CPU when it becomes free (and, if it is preemptive, when the running one must leave)

The short-term scheduler looks at the ready queue and decides who uses the CPU. It does this many times per second, so it has to be fast.

Question 2True or false

About CPU and I/O bursts, say whether each statement is true or false:

  1. While it is active, a process alternates CPU bursts with I/O bursts.
  2. Most CPU bursts last more than 100 ms.
  3. An I/O-bound process (like a music player) usually has short CPU bursts.
  4. The scheduler hands out the CPU for whole programs, not for bursts.
Solution
  • T — While it is active, a process alternates CPU bursts with I/O bursts.
  • F — Most CPU bursts last more than 100 ms.
  • T — An I/O-bound process (like a music player) usually has short CPU bursts.
  • F — The scheduler hands out the CPU for whole programs, not for bursts.

A process’s active life is a sequence of bursts: it computes for a while (CPU), waits for the disk or the network (I/O), computes again…

Typical CPU bursts are short, under 8 ms: there are many short ones and few long ones. Each scheduling decision hands out the next burst, not the whole program.

Question 3Match

Match each metric with what it measures:

Waiting time
Turnaround time
Response time
CPU utilisation

Definitions:

  • Total time the process spends in the ready queue
  • Percentage of time the CPU does useful work
  • The time the OS takes to save one PCB and load another
  • From when the process arrives until it finishes
  • From when it joins the queue until it first gets the CPU
Solution
  • Waiting time → Total time the process spends in the ready queue
  • Turnaround time → From when the process arrives until it finishes
  • Response time → From when it joins the queue until it first gets the CPU
  • CPU utilisation → Percentage of time the CPU does useful work

The leftover one defines a context switch, which is not a per-process metric but a system cost. Remember: turnaround = waiting + CPU time.

Question 4Short answer

A process has a turnaround time of 12 ms and a CPU burst of 5 ms. How many milliseconds did it wait in the ready queue? (just the number)

Solution

Answer: 7

Turnaround = waiting + CPU, so waiting = turnaround − burst = 12 − 5 = 7 ms.

Question 5Single choice

A process arrives at t = 4, first gets the CPU at t = 9, leaves, comes back and finishes at t = 15. What is its response time?

  1. 5 ms
  2. 11 ms
  3. 9 ms
  4. 6 ms
Solution

Answer: 5 ms

Response time only looks at the first time it gets the CPU: 9 − 4 = 5 ms. Whatever happens afterwards (leaving and coming back) counts for turnaround and waiting, not for response.

Question 6Match

Match each type of system with what its scheduler cares about most:

Batch
Interactive
Real time

Definitions:

  • The user sees quick responses
  • Always meeting the set deadlines
  • Getting the most out of the CPU
  • Using as few processes as possible
Solution
  • Batch → Getting the most out of the CPU
  • Interactive → The user sees quick responses
  • Real time → Always meeting the set deadlines

Each system pursues a different goal and no policy is optimal for every criterion: you always need a compromise.

Question 7Multiple · wrong ticks subtract

About preemptive and non-preemptive scheduling, tick the correct statements:

  1. In a non-preemptive algorithm, the process only leaves the CPU when it finishes its burst or blocks
  2. Time-sharing systems need preemptive scheduling
  3. In a preemptive algorithm the process decides when to leave the CPU
  4. FCFS is a preemptive algorithm
  5. Round Robin can work without the timer interrupt
Solution

Answer: In a non-preemptive algorithm, the process only leaves the CPU when it finishes its burst or blocks · Time-sharing systems need preemptive scheduling

With non-preemptive schedulers a process can hog the CPU. Preemptive ones (SRTF, Round Robin, preemptive priorities) let the OS evict it, which is why they are the basis of time sharing and real time.

Question 8Fill in the gaps

Complete the description of FCFS:

In FCFS the ready queue is a ____ ordered by ____ time. If a very long process is at the front, the short ones get stuck behind it: this is the ____ effect.

Words:

  • FIFO
  • convoy
  • LIFO
  • domino
  • burst
  • arrival
Solution

In FCFS the ready queue is a FIFO ordered by arrival time. If a very long process is at the front, the short ones get stuck behind it: this is the convoy effect.

FCFS serves in order of arrival (FIFO). Its big problem is the convoy effect: like a slow lorry on a single-lane road.

Question 9Single choice

With FCFS, three processes arrive together in this order: A (10 ms), B (2 ms) and C (3 ms). What is the mean waiting time?

  1. 7.33 ms
  2. 2.33 ms
  3. 5 ms
  4. 12.33 ms
Solution

Answer: 7.33 ms

Gantt chart: A from 0 to 10, B from 10 to 12, C from 12 to 15. Waiting: A = 0, B = 10, C = 12. Mean = (0 + 10 + 12) / 3 = 7.33 ms.

With the short ones first (B, C, A) the waits would be 0, 2 and 5: mean 2.33 ms. Same work, a third of the waiting: that is how sensitive FCFS is to order.

Question 10Multiple · wrong ticks subtract

Which statements about FCFS are correct?

  1. It is very sensitive to the order in which processes arrive
  2. It penalises I/O-bound processes
  3. It is simple to implement
  4. It mainly penalises CPU-bound processes
  5. It evicts a process once it has been on the CPU for a maximum time
Solution

Answer: It is very sensitive to the order in which processes arrive · It penalises I/O-bound processes · It is simple to implement

FCFS is simple, but one long CPU-bound process at the front makes all the interactive and I/O-bound ones wait (convoy effect).

Question 11Single choice

In non-preemptive SJF, when and how is the next process chosen?

  1. When the CPU becomes free, the one with the shortest burst among those in the queue is chosen
  2. Every time a process arrives, it is compared with the running one
  3. The first to arrive is chosen and, in a tie, the shortest
  4. The one with the longest burst is chosen to get it out of the way
Solution

Answer: When the CPU becomes free, the one with the shortest burst among those in the queue is chosen

SJF (Shortest Job First) does not preempt: whoever gets in stays until its burst ends. Only when the CPU becomes free does it look for the shortest in the queue (in a tie, the earlier arrival).

Question 12True or false

About SJF, say whether each statement is true or false:

  1. SJF achieves the lowest possible mean waiting time.
  2. If short processes keep arriving, a long one can wait indefinitely.
  3. What SJF always minimises is the mean response time.
  4. Real operating systems use pure SJF because they know the length of every burst in advance.
Solution
  • T — SJF achieves the lowest possible mean waiting time.
  • T — If short processes keep arriving, a long one can wait indefinitely.
  • F — What SJF always minimises is the mean response time.
  • F — Real operating systems use pure SJF because they know the length of every burst in advance.

SJF minimises the mean waiting time; its risk is the starvation of long processes.

In practice the next burst is unknown: it would have to be estimated (for example, with an exponential average of the previous ones), and even then pure SJF is not used.

Question 13Short answer

What is the preemptive version of SJF called? (acronym)

Solution

Answer: SRTF

SRTF, Shortest Remaining Time First: the running process is evicted if one arrives whose burst is shorter than what the running one has left.

Question 14Single choice

With SRTF, gcc has 4 ms left on the CPU and spotify arrives with a 4 ms burst. With the usual criterion, what happens?

  1. gcc carries on: it is only preempted if the newcomer is strictly shorter
  2. spotify evicts gcc because it arrived last
  3. They share the CPU half and half
  4. gcc goes back to the head of the queue with its full burst
Solution

Answer: gcc carries on: it is only preempted if the newcomer is strictly shorter

In SRTF the newcomer’s burst is compared with the remaining time of the running process. With 4 = 4 there is no preemption (if an exam uses another criterion, state it in one line).

Question 15Short answer

An OS estimates the next burst with τ(n+1) = α·t(n) + (1 − α)·τ(n). If α = 0.5, the previous estimate was τ(n) = 10 ms and the actual burst was t(n) = 6 ms, what is the new estimate in ms?

Solution

Answer: 8

τ(n+1) = 0.5 · 6 + 0.5 · 10 = 3 + 5 = 8 ms. With α = 0.5 the new estimate lands halfway between what happened and what was expected.

Question 16Multiple · wrong ticks subtract

Tick the correct statements about Round Robin:

  1. It is a preemptive algorithm
  2. The ready queue works as a circular FIFO
  3. If a process uses up its quantum without finishing, it goes back to the end of the queue
  4. Each process runs its full burst before giving up the CPU
  5. It is designed for hard real-time systems
Solution

Answer: It is a preemptive algorithm · The ready queue works as a circular FIFO · If a process uses up its quantum without finishing, it goes back to the end of the queue

Round Robin is FCFS with a quantum Q: nobody can stay longer than Q in a row while others are waiting. It is the typical time-sharing algorithm.

Question 17Short answer

In Round Robin with Q = 20 ms there are 6 processes in the ready queue. At most, how many ms does a process take to get the CPU again? (just the number)

Solution

Answer: 100

The other N − 1 = 5 may go before it, each for at most one quantum: Q · (N − 1) = 20 · 5 = 100 ms.

Question 18Match

Match each choice of the quantum Q with its effect:

Q longer than every burst
Q far too small
Q a bit longer than the typical burst

Definitions:

  • Almost everyone finishes in one quantum: a good compromise
  • Round Robin behaves exactly like FCFS
  • Long processes never finish any more
  • Lots of context switches and less useful CPU
Solution
  • Q longer than every burst → Round Robin behaves exactly like FCFS
  • Q far too small → Lots of context switches and less useful CPU
  • Q a bit longer than the typical burst → Almost everyone finishes in one quantum: a good compromise

Q must be much longer than a context switch. With a huge Q nobody is preempted (FCFS); with a tiny Q the CPU spends its day switching processes.

Question 19Single choice

Round Robin with Q = 2. At t = 4 process A uses up its quantum and, at that very instant, D arrives. The queue was [B, C]. With the usual criterion, what does the queue look like?

  1. B, C, D, A
  2. B, C, A, D
  3. D, B, C, A
  4. A, B, C, D
Solution

Answer: B, C, D, A

Arrivals join the end of the queue and, when two things happen at the same instant, the newcomer is usually placed first, then the preempted process. Always write in one line which criterion you follow.

Question 20Order

Put the steps for solving a Gantt chart scheduling exercise in order:

  1. Work out the waiting time: turnaround − burst
  2. Work out the turnaround: end − arrival
  3. Add up and divide by the number of processes for the means
  4. Place the blocks on the time axis according to the algorithm
  5. Write down the end time of each process
Solution

Correct order:

  1. Place the blocks on the time axis according to the algorithm
  2. Write down the end time of each process
  3. Work out the turnaround: end − arrival
  4. Work out the waiting time: turnaround − burst
  5. Add up and divide by the number of processes for the means

Drawing first, sums afterwards. Everything comes from the Gantt chart: the end is read from it, and turnaround and waiting are subtractions.

Question 21Multiple · wrong ticks subtract

About priority scheduling, tick the correct ones:

  1. The ready process with the highest priority gets the CPU
  2. It can be preemptive or non-preemptive
  3. SJF is a special case: the priority is the estimated burst length
  4. Only the user can set priorities
  5. It cannot cause starvation
Solution

Answer: The ready process with the highest priority gets the CPU · It can be preemptive or non-preemptive · SJF is a special case: the priority is the estimated burst length

Priorities can be internal (computed by the OS) or external (set by the user). Their risk is the starvation of low-priority processes.

Question 22Fill in the gaps

Complete the sentence:

If higher-priority processes keep arriving, a low-priority one can suffer ____. The fix is ____, which gradually ____ the priority of the processes that have been waiting a long time.

Words:

  • aging
  • raises
  • deadlock
  • convoy
  • starvation
  • lowers
Solution

If higher-priority processes keep arriving, a low-priority one can suffer starvation. The fix is aging, which gradually raises the priority of the processes that have been waiting a long time.

Aging rewards waiting: sooner or later the forgotten process becomes the highest-priority one.

Question 23Single choice

In lottery scheduling, gcc has 3 tickets and onedrive has 1. In the long run, what share of the CPU does gcc get?

  1. 75%
  2. 50%
  3. 100%
  4. 33%
Solution

Answer: 75%

In each time slice a winning ticket is drawn: CPU time is proportional to the number of tickets. gcc has 3 out of 4 → 75%.

Question 24True or false

About lottery scheduling, say whether each statement is true or false:

  1. Every process gets at least one ticket, so that none is left without CPU.
  2. To imitate SRTF, long jobs get more tickets.
  3. If processes come or go, tickets are shared out again proportionally.
Solution
  • T — Every process gets at least one ticket, so that none is left without CPU.
  • F — To imitate SRTF, long jobs get more tickets.
  • T — If processes come or go, tickets are shared out again proportionally.

To behave like SRTF, short jobs get more tickets. With at least one ticket each, nobody starves.

Question 25Fill in the gaps

Complete the description of multilevel queues:

Multilevel queues use several ____ queues, each with its own ____: for example, ____ for interactive processes and ____ for batch processes. With ____, a process can move from one queue to another.

Words:

  • Round Robin
  • SRTF
  • feedback
  • ready
  • convoy
  • policy
  • blocked
  • FCFS
Solution

Multilevel queues use several ready queues, each with its own policy: for example, Round Robin for interactive processes and FCFS for batch processes. With feedback, a process can move from one queue to another.

The queues share the CPU by absolute priority or with a percentage of time each. Feedback lets a process that has waited a long time move up a queue, or move down if its behaviour changes.

Question 26Multiple · wrong ticks subtract

About multiprocessor scheduling, tick the correct ones:

  1. In asymmetric processing, one processor schedules the work of the others
  2. In symmetric processing there can be one shared queue or one queue per processor
  3. Affinity tries to keep a process on the same processor to make use of its cache
  4. In symmetric processing, one processor schedules all the others
  5. Load balancing means each process spends the same time on each processor
Solution

Answer: In asymmetric processing, one processor schedules the work of the others · In symmetric processing there can be one shared queue or one queue per processor · Affinity tries to keep a process on the same processor to make use of its cache

Symmetric (SMP) = each processor does its own scheduling. Load balancing moves processes so that no CPU is swamped or idle.

Question 27Match

Match each concept with its description:

Push migration
Pull migration
Processor affinity
Asymmetric processing

Definitions:

  • One CPU schedules all the others
  • An idle processor takes processes from a busier one
  • Each process runs one quantum on each CPU in turn
  • A supervisor task checks the load and moves processes
  • Keeping a process on the same CPU because of its cache
Solution
  • Push migration → A supervisor task checks the load and moves processes
  • Pull migration → An idle processor takes processes from a busier one
  • Processor affinity → Keeping a process on the same CPU because of its cache
  • Asymmetric processing → One CPU schedules all the others

Push = someone hands the work out; pull = the idle one takes it. Affinity works against load balancing: moving a process balances the load but loses its cache.

Question 28Single choice

A single-core laptop runs gcc, spotify and the browser, taking turns every few milliseconds. What does it have?

  1. Concurrency, but not parallelism
  2. Parallelism, because they seem to run together
  3. Neither concurrency nor parallelism
  4. Both concurrency and parallelism
Solution

Answer: Concurrency, but not parallelism

Concurrency: several tasks make progress interleaved in time. Parallelism: they run simultaneously on different cores. With one core, the scheduler decides whose turn it is.

Question 29Calculation

FCFS with three processes arriving at t = 0 in the order P1, P2, P3. Work out the end, turnaround and waiting time of each and the means:

ProcessArrivalBurst
P106
P203
P301
ProcessEndTurnaroundWaiting
P1
P2
P3
Mean
SolutionP1P2P306910
ProcessEndTurnaroundWaiting
P1660
P2996
P310109
Mean8.335

Since they all arrive at t = 0, turnaround equals the end time: 6, 9 and 10 (mean 25 / 3 = 8.33 ms). The waits are 0, 6 and 9: mean 15 / 3 = 5 ms.

In SJF order (P3, P2, P1) the waits would be 0, 1 and 4: mean 1.67 ms. That is why SJF minimises the mean waiting time.

Question 30Multiple · wrong ticks subtract

Which policies can leave a process waiting indefinitely (starvation) if no remedy is added?

  1. SJF
  2. SRTF
  3. Priorities without aging
  4. FCFS
  5. Round Robin
Solution

Answer: SJF · SRTF · Priorities without aging

Starvation appears when the selection rule can always skip someone. FCFS and Round Robin respect the order of the queue, so everyone eventually gets in.

If you get the metric questions wrong (t4-38 to t4-40), go back to the “Turnaround / Waiting / Response” table in the theory before moving on to the Gantt charts. Everything else rests on those three subtractions.

Gantt charts step by step

Here is what scores the most. Five exercises: FCFS, non-preemptive SJF, SRTF with the same data as the SJF one (so you can compare) and Round Robin with two different quanta on the same processes. Before you start, the method that always works:

  1. Draw the time axis and place the blocks according to the algorithm. In preemptive ones, at every arrival write down what each process has left (SRTF) or what the queue looks like (Round Robin).
  2. Write down the end time of each process.
  3. Turnaround = end − arrival.
  4. Waiting = turnaround − burst.
  5. Response = first run − arrival (only if asked).
  6. Mean = sum / number of processes.

Forgetting to subtract the arrival when processes do not all arrive at t = 0. It is the most expensive mistake in the exam, because the Gantt chart is right and every sum comes out wrong.

The tie-break rules used here (which you should write down in the exam if you hit a tie): in SJF and SRTF, with equal lengths the earlier arrival goes first, and SRTF only preempts if the newcomer is strictly shorter than what the running process has left; in Round Robin, if someone arrives at the same instant another uses up its quantum, the newcomer joins the queue first.

Question 1Calculation

Gantt 1 · FCFS. Draw the Gantt chart on paper and work out the end, turnaround and waiting time of each process and the means:

ProcessArrivalBurst
P105
P213
P327
P442
ProcessEndTurnaroundWaiting
P1
P2
P3
P4
Mean
SolutionP1P2P3P40581517
ProcessEndTurnaroundWaiting
P1550
P2874
P315136
P4171311
Mean9.55.25

Step 1, the Gantt chart. FCFS serves in order of arrival and nobody preempts: P1 from 0 to 5, P2 from 5 to 8, P3 from 8 to 15 and P4 from 15 to 17.

Step 2, turnaround = end − arrival: P1 = 5 − 0 = 5, P2 = 8 − 1 = 7, P3 = 15 − 2 = 13, P4 = 17 − 4 = 13. Mean = 38 / 4 = 9.5 ms.

Step 3, waiting = turnaround − burst: P1 = 5 − 5 = 0, P2 = 7 − 3 = 4, P3 = 13 − 7 = 6, P4 = 13 − 2 = 11. Mean = 21 / 4 = 5.25 ms.

Look at P4: with only 2 ms of work it waits 11, because it arrived behind P3 (7 ms). That is the convoy effect.

Question 2Calculation

Gantt 2 · Non-preemptive SJF. With these processes, work out the end, turnaround and waiting time of each and the means:

ProcessArrivalBurst
P106
P225
P332
P453
ProcessEndTurnaroundWaiting
P1
P2
P3
P4
Mean
SolutionP1P3P4P20681116
ProcessEndTurnaroundWaiting
P1660
P216149
P3853
P41163
Mean7.753.75

t = 0: only P1 is there. It gets in and, since SJF does not preempt, it stays until t = 6 even though others arrive.

t = 6: waiting in the queue are P2 (5), P3 (2) and P4 (3). The shortest, P3, runs until t = 8.

t = 8: P2 (5) and P4 (3) are left: P4 runs until t = 11. t = 11: only P2 is left, until t = 16.

Turnaround: 6 − 0 = 6, 16 − 2 = 14, 8 − 3 = 5 and 11 − 5 = 6 (mean 31 / 4 = 7.75 ms). Waiting: 0, 14 − 5 = 9, 5 − 2 = 3 and 6 − 3 = 3 (mean 15 / 4 = 3.75 ms).

Question 3Calculation

Gantt 3 · SRTF (preemptive SJF) with the same processes as Gantt 2. Work out end, turnaround, waiting and response, and the means:

ProcessArrivalBurst
P106
P225
P332
P453
ProcessEndTurnaroundWaitingResponse
P1
P2
P3
P4
Mean
SolutionP1P3P1P4P203581116
ProcessEndTurnaroundWaitingResponse
P18820
P2161499
P35200
P411633
Mean7.53.53

At every arrival, the newcomer’s burst is compared with what the running process has left.

t = 2: P2 (5) arrives. P1 has 6 − 2 = 4 left. Since 5 > 4, no preemption. t = 3: P3 (2) arrives. P1 has 3 left. Since 2 < 3, P3 preempts P1.

t = 5: P3 finishes and P4 (3) arrives. Remaining: P1 = 3, P2 = 5, P4 = 3. A tie between P1 and P4: the earlier arrival, P1, runs until t = 8. Then P4 (8-11) and P2 (11-16).

Turnaround: 8, 14, 2 and 6 (mean 30 / 4 = 7.5 ms). Waiting: 8 − 6 = 2, 14 − 5 = 9, 2 − 2 = 0 and 6 − 3 = 3 (mean 14 / 4 = 3.5 ms). Response (first run − arrival): 0, 11 − 2 = 9, 3 − 3 = 0 and 8 − 5 = 3 (mean 12 / 4 = 3 ms).

With the same data, SRTF (3.5 ms mean waiting) beats SJF (3.75 ms).

Question 4Calculation

Gantt 4 · Round Robin with Q = 2. If a process arrives at the same instant another uses up its quantum, the newcomer joins the queue first. Work out end, turnaround, waiting and response, and the means:

ProcessArrivalBurst
P105
P213
P324
P442
ProcessEndTurnaroundWaitingResponse
P1
P2
P3
P4
Mean
SolutionP1P2P3P1P4P2P3P10246810111314
ProcessEndTurnaroundWaitingResponse
P1141490
P2111071
P3131172
P410644
Mean10.256.751.75

Keep the queue written down at every switch:

t = 2: P1 uses up its quantum and P3 arrives → queue [P2, P3, P1]. P2 runs. t = 4: P2 uses up its quantum and P4 arrives → queue [P3, P1, P4, P2]. P3 runs.

t = 6: P3 uses it up → [P1, P4, P2, P3]. P1 runs (6-8; 1 left). t = 8: P4 runs (8-10, finishes). t = 10: P2 (10-11, finishes). t = 11: P3 (11-13, finishes). t = 13: P1 (13-14, finishes).

Turnaround: 14, 10, 11 and 6 (mean 41 / 4 = 10.25 ms). Waiting: 14 − 5 = 9, 10 − 3 = 7, 11 − 4 = 7 and 6 − 2 = 4 (mean 27 / 4 = 6.75 ms). Response: 0, 2 − 1 = 1, 4 − 2 = 2 and 8 − 4 = 4 (mean 7 / 4 = 1.75 ms).

Question 5Calculation

Gantt 5 · Round Robin with Q = 4 and the same processes as Gantt 4. Work out end, turnaround, waiting and response, and the means:

ProcessArrivalBurst
P105
P213
P324
P442
ProcessEndTurnaroundWaitingResponse
P1
P2
P3
P4
Mean
SolutionP1P2P3P4P1047111314
ProcessEndTurnaroundWaitingResponse
P1141490
P27633
P311955
P413977
Mean9.563.75

t = 0-4: P1 uses its whole quantum (1 left). At t = 4 P4 arrives just as P1 uses it up: queue [P2, P3, P4, P1].

P2 (4-7) finishes before the quantum runs out, P3 (7-11) uses exactly 4 and finishes, P4 (11-13) finishes and P1 (13-14) completes its last millisecond.

Turnaround: 14, 6, 9 and 9 (mean 38 / 4 = 9.5 ms). Waiting: 9, 3, 5 and 7 (mean 24 / 4 = 6 ms). Response: 0, 3, 5 and 7 (mean 15 / 4 = 3.75 ms).

Compare with Q = 2: with the bigger quantum there are fewer switches (4 instead of 7) and a better mean waiting time (6 instead of 6.75), but the mean response gets worse (3.75 instead of 1.75).

Check each row with turnaround = waiting + burst before moving to the next. If it does not add up, the mistake is in that row, not in the mean.

Compare Gantt 2 and 3 (same data): SRTF lowers the mean waiting time from 3.75 to 3.5 ms. And Gantt 4 and 5: with Q = 4 there are 4 context switches instead of 7 and the mean waiting time drops from 6.75 to 6 ms, but the mean response rises from 1.75 to 3.75 ms. That is exactly the quantum trade-off you saw in the theory.

Open questions

The written part may also include a question to answer in prose. Write your answer in the box, press “Check” and compare it with the model answer and with the list of what the marker looks for: if you cover every point, you have it.

Question 1Open answer

Explain the difference between preemptive and non-preemptive scheduling, with one algorithm of each kind, and why time-sharing systems need preemptive scheduling.

Solution

Model answer:

In non-preemptive scheduling, the process on the CPU only gives it up when it asks to: when it finishes its CPU burst or blocks waiting for I/O. The scheduler only makes a decision when the CPU becomes free. FCFS and SJF are non-preemptive. Their risk is hogging: a process with a very long burst makes everyone else wait.

In preemptive scheduling, the operating system can evict the running process, for example when another one arrives with a shorter burst (SRTF) or a higher priority, or when its quantum runs out (Round Robin), which it detects thanks to the timer interrupt. Time sharing needs preemption because it has to guarantee every user quick responses even when some processes compute non-stop; real time needs it to serve tasks with deadlines on time.

What the marker looks for:

  • Defines non-preemptive: the process leaves the CPU when its burst ends or it blocks
  • Defines preemptive: the OS can evict the process
  • Gives correct examples (FCFS or SJF versus SRTF or Round Robin)
  • Mentions the risk of hogging and the role of the timer
  • Justifies why time sharing (and real time) needs preemption
Question 2Open answer

Compare FCFS, SJF and Round Robin: how they choose the next process, what advantage each one has and what its main problem is.

Solution

Model answer:

FCFS serves processes in order of arrival with a FIFO queue and does not preempt. It is the simplest, but it is very sensitive to order: if a long process is at the front, the short ones wait a long time behind it (convoy effect), which penalises I/O-bound processes.

SJF chooses, when the CPU becomes free, the process with the shortest CPU burst. It minimises the mean waiting time, but it can starve long processes if short ones keep arriving, and it requires knowing the next burst, which in practice can only be estimated. Its preemptive version is SRTF.

Round Robin is a preemptive FCFS: each process uses the CPU for at most one quantum Q and, if it does not finish, goes back to the end of the queue. It shares the CPU fairly and gives good response times, which is why it is the typical algorithm for interactive systems; its problem is choosing Q well, because with a very large Q it behaves like FCFS and with a very small one a lot of time is lost in context switches.

What the marker looks for:

  • Correct selection criterion for all three
  • Whether each one preempts
  • Advantage: simplicity (FCFS), minimum mean waiting (SJF), response and fairness (RR)
  • Problem: convoy effect (FCFS), starvation and estimating the burst (SJF), choosing Q (RR)
Question 3Open answer

Explain how the size of the quantum Q affects the behaviour of Round Robin.

Solution

Model answer:

In Round Robin each process may use the CPU for at most one quantum Q in a row; if it does not finish, it goes back to the end of the ready queue. With N processes in the queue, a process waits at most Q · (N − 1) to get back in, so Q directly sets the response time.

If Q is very large, longer than the CPU bursts, processes finish their burst before using up the quantum and the algorithm behaves exactly like FCFS, with its convoy-effect problems. If Q is very small, the CPU is shared very evenly, as if each process had a processor N times slower, but context switches increase and CPU time is lost saving and loading PCBs. That is why Q should be much longer than a context switch and, ideally, a bit longer than the typical burst; in practice it is usually between 1 and 200 ms, and systems like Linux adjust it to the load.

What the marker looks for:

  • Links Q with the response time, Q · (N − 1)
  • Very large Q: behaves like FCFS
  • Very small Q: lots of context switches and lower performance
  • Criterion for choosing Q (longer than a context switch, close to the typical burst)
Question 4Open answer

Explain priority scheduling, the problem of starvation and how aging and multilevel feedback queues avoid it.

Solution

Model answer:

In priority scheduling each process has a priority, which can be set by the operating system (internal) or by the user (external), and the ready process with the highest priority gets the CPU. It can be preemptive, if a higher-priority arrival evicts the running process, or non-preemptive. SJF is a special case in which the priority is the estimated burst length.

Its problem is starvation: if there are always higher-priority processes, a low-priority one can wait indefinitely. The classic fix is aging, which gradually raises the priority of processes that have been waiting a long time until they finally get in. Multilevel queues organise ready processes into several queues with different policies (for example, Round Robin for interactive and FCFS for batch) that share the CPU by priority or by percentage of time; with feedback, a process can change queue, so one that has been waiting a long time moves up to a higher-priority queue.

What the marker looks for:

  • Defines priority scheduling (internal or external, preemptive or not)
  • Defines starvation
  • Explains aging
  • Explains multilevel queues and feedback as a way to avoid it

When comparing algorithms, always use the same order for each one: how it chooses, whether it preempts, its advantage and its problem. That way you leave nothing out and the marker sees it at a glance.

The whole topic in one picture

Before the cheat sheet, the whole topic in one image: the three formulas, one card per algorithm and the methods that come up in the test.

The whole topic in one pictureThe metric formulas, the cards for FCFS, SJF, SRTF and Round Robin (whether they preempt, whom they pick, their strength and their problem) and priority, multilevel-queue, lottery and multiprocessor methods.CPU scheduling in one pictureMetrics (always work them out from the Gantt chart)turnaround = end − arrival · waiting = turnaround − burst · response = first run − arrivalFCFSnon-preemptiveFIFO queue by arrival  convoy effectsimpleSJFnon-preemptiveshortest burst  long jobs starveminimum mean waitingSRTFpreemptiveleast remaining time  long jobs starveeven less waitingRRpreemptivecircular FIFO + quantum Q  badly chosen Qgood responsePrioritiesstarvation → agingMultilevel queuesone policy per queueLotteryCPU ∝ number of ticketsMultiprocessoraffinity · push / pullPreemptive = the OS can take the process out (time sharing and real time need it)
If this picture fits in your head, the whole topic does.

Cheat sheet: CPU scheduling

The essentials in 30 seconds

  • The scheduler decides which ready process gets the CPU and, if it is preemptive, when the running one leaves.
  • Turnaround = end − arrival = waiting + CPU. Waiting = turnaround − burst. Response = first run − arrival.
  • Non-preemptive: FCFS and SJF. Preemptive: SRTF, Round Robin and preemptive priorities. Time sharing and real time need preemption.
  • SJF minimises mean waiting; Round Robin gives the best response; FCFS is the simplest.
  • Starvation in SJF, SRTF and priorities; the cure is aging.

What each algorithm does

I want…AlgorithmHow it decides
To serve in order of arrivalFCFSFIFO queue; nobody preempts
To serve the shortest firstSJFWhen the CPU becomes free, the shortest burst
The short one to evict the long oneSRTFAt each arrival, compare with what the running one has left
Fair turns for interactive workRound RobinCircular FIFO; at most Q in a row
Importance to rulePrioritiesThe highest priority; aging against starvation
Proportional CPULotteryTicket draw; everyone gets at least one
To mix policiesMultilevel queuesOne policy per queue; with feedback, they change queue

Formulas and facts that come up

I want to work out…FormulaExample
Turnaroundend − arrivalfinishes at 15, arrived at 1 → 14
Waitingturnaround − burst14 − 4 → 10
Responsefirst run − arrivalruns at 3, arrived at 1 → 2
Maximum response in RRQ · (N − 1)Q = 20, N = 6 → 100 ms
Burst estimateτ(n+1) = α · t(n) + (1 − α) · τ(n)α = 0.5, t = 6, τ = 10 → 8
CPU with lotteryown tickets / total tickets3 out of 4 → 75%

Template for any Gantt chart

ProcessArrivalBurstEndTurnaround = end − arrivalWaiting = turnaround − burst
P1……(from the Gantt)……
Meansum / Nsum / N

Results of the five Gantt charts above, for revision: FCFS 9.5 / 5.25 ms (mean turnaround / waiting); SJF 7.75 / 3.75; SRTF 7.5 / 3.5; Round Robin Q = 2: 10.25 / 6.75; Round Robin Q = 4: 9.5 / 6.

Symptom / likely cause

SymptomLikely cause
A waiting time comes out negativeYou took the end of an intermediate block, not the process’s last one (happens in SRTF and Round Robin)
The waiting times do not add up to what you expectedYou did end − burst with processes that do not arrive at t = 0
In SJF a process appears split into two blocksYou preempted: that is SRTF, not SJF
In SRTF you preempted on a tieIt only preempts if the newcomer is strictly shorter
In RR the chart goes wrong after the second quantumYou put the preempted process ahead of a newcomer, or at the front of the queue
Turnaround ≠ waiting + burst in a rowA subtraction mistake in that row: redo it before working out the mean

Before you hand it in, ask yourself

  1. Have I subtracted the arrival in every turnaround?
  2. Does every row add up: turnaround = waiting + burst?
  3. Have I respected whether the algorithm is preemptive or not?
  4. Have I written in one line the tie-break rule I used?

If you got almost everything right, you are ready for the next topic: concurrency and critical sections, where these processes that take turns on the CPU start sharing data. See you there!

Keep goingAll Operating systems articles

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

Ready for the exam?IC2 theory mock exam — first midterm, second midterm or the full exam, with your real mark and a review of every mistake (as if you were in the exam room)

Data Science and Engineering student at ULPGC. I explain what I learn
at university the way I wish it had been explained to me: with its
doubts, its mistakes and the path to the solution.

Keep learning