GATE CS 2021 Set 1 Q.35 (CS Q.25): CPU Scheduling

Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is __________ milliseconds.

Your answer

Official answer and solution

Official answer: 12
From: Official GATE 2021 answer key

Solution

Apply Shortest Job First (SJF) scheduling, which provably minimizes average waiting time when all processes arrive at time zero.

All three processes arrive at time $t = 0$ with burst lengths: $P_1 = 16\text{ ms}, P_2 = 20\text{ ms}, P_3 = 10\text{ ms}$ .
To achieve minimum average waiting time in a non-preemptive scheduler, the scheduler must execute processes in non-decreasing order of their CPU burst lengths (Shortest Job First).

Execution order:

$P_3$ executes from $t = 0$ to $t = 10$ . Waiting time $W(P_3) = 0\text{ ms}$ .
$P_1$ executes from $t = 10$ to $t = 10 + 16 = 26$ . Waiting time $W(P_1) = 10 - 0 = 10\text{ ms}$ .
$P_2$ executes from $t = 26$ to $t = 26 + 20 = 46$ . Waiting time $W(P_2) = 26 - 0 = 26\text{ ms}$ .

Total waiting time $= 0 + 10 + 26 = 36\text{ ms}$ .
Average waiting time $= \frac{36}{3} = 12\text{ ms}$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 35 of 65, printed as CS Q.25
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source