GATE CS 2020 Q.60 (CS Q.50): CPU Scheduling

Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order $P_1, P_2, P_3, P_4$ .

Process burst times
Processes	P1	P2	P3	P4
Burst time (in ms)	8	7	2	4

If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _______.

Your answer

Official answer and solution

Official answer: 5.25
From: Official GATE 2020 answer key

Solution

Construct Gantt charts for SJF and Round Robin (quantum 4) and calculate average turnaround times.

Given processes arriving at time 0:

$P_1$ : burst time = 8 ms
$P_2$ : burst time = 7 ms
$P_3$ : burst time = 2 ms
$P_4$ : burst time = 4 ms

Shortest Job First (SJF) scheduling:

Order of execution by shortest burst time: $P_3 (2) \to P_4 (4) \to P_2 (7) \to P_1 (8)$ .
Gantt chart: [P3: 0-2] [P4: 2-6] [P2: 6-13] [P1: 13-21].
Completion times: $C_3 = 2, C_4 = 6, C_2 = 13, C_1 = 21$ .
Turnaround times ( $TAT = C - 0$ ): $TAT_3 = 2, TAT_4 = 6, TAT_2 = 13, TAT_1 = 21$ .
Average TAT for SJF: $\text{Avg } TAT_{\text{SJF}} = \frac{2 + 6 + 13 + 21}{4} = \frac{42}{4} = 10.5\text{ ms}$

Round Robin (RR) scheduling with time quantum 4 ms:

Ready queue initially: $P_1, P_2, P_3, P_4$ .

$P_1$ runs from 0 to 4 ms (remaining: 4 ms). Ready queue: $P_2, P_3, P_4, P_1$ .
$P_2$ runs from 4 to 8 ms (remaining: 3 ms). Ready queue: $P_3, P_4, P_1, P_2$ .
$P_3$ runs from 8 to 10 ms (remaining: 0 ms, completes at $t = 10$ ). Ready queue: $P_4, P_1, P_2$ .
$P_4$ runs from 10 to 14 ms (remaining: 0 ms, completes at $t = 14$ ). Ready queue: $P_1, P_2$ .
$P_1$ runs from 14 to 18 ms (remaining: 0 ms, completes at $t = 18$ ). Ready queue: $P_2$ .
$P_2$ runs from 18 to 21 ms (remaining: 0 ms, completes at $t = 21$ ).

Completion times: $C_1 = 18, C_2 = 21, C_3 = 10, C_4 = 14$ .
Average TAT for RR: $\text{Avg } TAT_{\text{RR}} = \frac{18 + 21 + 10 + 14}{4} = \frac{63}{4} = 15.75\text{ ms}$

Absolute difference:

|\text{Avg } TAT_{\text{RR}} - \text{Avg } TAT_{\text{SJF}}| = |15.75 - 10.5| = 5.25\text{ ms}

Final answer

5.25

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

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 60 of 65, printed as CS Q.50
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