Advanced System Software and Security: Question 2

Worked solution

Part (a): What happens when a quantum expires

Round robin gives every ready process a turn on the CPU lasting at most one time quantum. If a process has not finished executing by the time its quantum runs out, the kernel’s timer interrupt fires; the scheduler removes the process from the CPU. Moving it from the running state back to the ready state, not blocked, since it is still perfectly able to run, just not right now, and places it at the back of the ready queue. The process at the front of the ready queue is then given the CPU.

Both P1 and P2 arrive at time = 0 ms, and P1 is always chosen ahead of P2 when both are ready, so P1 is given the CPU first, for 3 ms. The full quantum, since P1’s 7 ms burst time is greater than the 3 ms quantum, so it will be interrupted before it finishes. [2 marks]

Part (b): Completing the trace

Each time a process is given the CPU, it runs for whichever is smaller: the 3 ms quantum, or its own remaining burst time. If it still has time left afterwards, it goes to the back of the ready queue; if its remaining burst time reaches 0, it is finished and is not re-queued.

Working through the queue at each step:

• 0–3 ms: P1 runs. It has 7 ms remaining before this slice; it runs for min(3, 7) = 3 ms, leaving 4 ms remaining. P1 still has time left, so it re-joins the back of the queue: [P2, P1].
• 3–6 ms: P2 runs (front of the queue). It has 4 ms remaining; it runs for min(3, 4) = 3 ms, leaving 1 ms remaining. P2 re-joins the back of the queue: [P1, P2].
• 6–9 ms: P1 runs. It has 4 ms remaining; it runs for min(3, 4) = 3 ms, leaving 1 ms remaining. P1 re-joins the back of the queue: [P2, P1].
• 9–10 ms: P2 runs. It only has 1 ms remaining, so it runs for min(3, 1) = 1 ms and finishes (0 ms remaining). It is not re-queued.
• 10–11 ms: P1 runs. It only has 1 ms remaining, so it runs for min(3, 1) = 1 ms and finishes (0 ms remaining).

[4 marks]: [1] for each of the four time slices from 3–6 ms onwards being correctly scheduled and timed (the first slice is effectively given away by the question), allowing for one mark to also credit correctly showing the remaining burst time reducing at each step.

Part (c): Completion times

Reading directly from the completed trace: P2’s remaining burst time reaches 0 at the end of the 9–10 ms slice, and P1’s remaining burst time reaches 0 at the end of the 10–11 ms slice.

• P2 completes at time = 10 ms.
• P1 completes at time = 11 ms.

[2 marks]: [1] for each correct completion time.

Final answers

• (a) The process is moved from running to ready and placed at the back of the ready queue; P1 runs first, for 3 ms.
• (b) Trace: P1 (0–3), P2 (3–6), P1 (6–9), P2 (9–10, completes), P1 (10–11, completes).
• (c) P2 completes at 10 ms; P1 completes at 11 ms.