An operating system uses First Come First Served (FCFS) scheduling, a non-preemptive algorithm, to share a single processor between processes purely in the order they arrive in the ready queue. Three processes arrive as follows, and none of them need to perform any I/O once they…

Answer: ((a)) First Come First Served always gives the CPU next to whichever ready process has been waiting longest in the ready queue (i.e. arrived earliest), regardless of its burst time. It is a non-preemptive algorithm, since a running process is never interrupted and always keeps the CPU… ((b)) P1: start = 0 ms, completion = 5 ms, waiting = 0 ms. P2: start = 5 ms, completion = 6 ms, waiting = 3 ms. P3: start = 6 ms, completion = 14 ms, waiting = 3 ms. ((c)) P2 arrives at 2 ms, while P1 (which started at 0 ms) is still running and does not release the CPU until 5 ms, so P2 must wait even though its own burst time is very short. First Come First Served never reorders the queue by burst time. This general problem, where short processe…. Part (a): How First Come First Served chooses the next process First Come First Served (FCFS) always gives the CPU next to whichever process has been waiting longest in the ready queue, in other words, whichever process arrived earliest. I…

A Level Computer Science 9618: Tracing First Come First Served Scheduling

Process

Arrival time (ms)

Burst time (ms)

Start time (ms)

Completion time (ms)

Waiting time (ms)

Part (a): How First Come First Served chooses the next process

First Come First Served (FCFS) always gives the CPU next to whichever process has been waiting longest in the ready queue, in other words, whichever process arrived earliest. It never looks at how long a process’s burst time is when making this choice. FCFS is a non-preemptive algorithm: once a process has been given the CPU, it keeps the CPU and runs all the way to completion, without ever being interrupted so that another process can run instead. [2 marks]: [1] for correctly describing the arrival-order rule, [1] for correctly stating non-preemptive.

Part (b): Completing the trace

Because FCFS is non-preemptive, once a process starts it always finishes before the next one can begin, so each process’s start time is simply the later of its own arrival time and the previous process’s completion time.

P1 arrives at 0 ms with the CPU free, so it starts immediately at 0 ms. It runs for its full 5 ms burst time, finishing at 0 + 5 = 5 ms. Waiting time = 5 - 0 - 5 = 0 ms.
P2 arrives at 2 ms, but the CPU is still busy with P1 until 5 ms, so P2 must start at 5 ms. It runs for its 1 ms burst time, finishing at 5 + 1 = 6 ms. Waiting time = 6 - 2 - 1 = 3 ms.
P3 arrives at 3 ms, but the CPU is still busy (with P1 until 5 ms, then P2 until 6 ms), so P3 must start at 6 ms. It runs for its 8 ms burst time, finishing at 6 + 8 = 14 ms. Waiting time = 14 - 3 - 8 = 3 ms.

Process	Arrival time (ms)	Burst time (ms)	Start time (ms)	Completion time (ms)	Waiting time (ms)
P1	0	5	0	5	0
P2	2	1	5	6	3
P3	3	8	6	14	3

[4 marks]: [1] for P1’s row, [1] for correctly starting P2 at 5 ms (not its arrival time of 2 ms) with completion 6 ms and waiting 3 ms, [1] for correctly starting P3 at 6 ms (not its arrival time of 3 ms), [1] for P3’s completion time of 14 ms and waiting time of 3 ms.

Part (c): Why P2 still has to wait. The convoy effect

Even though P2’s burst time (1 ms) is far shorter than P1’s (5 ms), P2 arrives at 2 ms while P1, which started running at 0 ms, is still occupying the CPU and will not release it until 5 ms. Because FCFS is non-preemptive and never reorders the ready queue by burst time, P2 simply has to wait for P1 to finish, regardless of how short P2’s own burst time is.

This general problem. Where a short process gets stuck waiting behind an already-running longer process purely because of arrival order, rather than being run first for efficiency, is known as the convoy effect. [2 marks]: [1] for explaining that P1 is still running when P2 arrives and FCFS does not reorder by burst time, [1] for naming the convoy effect.

Final answers

(a) FCFS selects the process that has been waiting longest (arrived earliest); it is non-preemptive.
(b) P1: start 0, completion 5, waiting 0. P2: start 5, completion 6, waiting 3. P3: start 6, completion 14, waiting 3.
(c) P2 must wait because P1 is still running when it arrives, and FCFS never reorders by burst time. This is the convoy effect.