GATE CS 2017 Set 2 Q.51 (CS Q.51): CPU Scheduling

Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.

Process	Arrival Time	Burst Time	Priority
$P_1$	0	11	2
$P_2$	5	28	0
$P_3$	12	2	3
$P_4$	2	10	1
$P_5$	9	16	4

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is

Your answer

Official answer and solution

Official answer: 29
From: Official GATE 2017 answer key

Solution

Simulate preemptive priority CPU scheduling using a Gantt chart to track execution intervals and calculate waiting times.

Scheduling policy: Preemptive, priority 0 is highest, priority 4 is lowest.
Trace CPU execution:

$t = 0$ : $P_1$ arrives (burst 11, priority 2). $P_1$ runs.
$t = 2$ : $P_4$ arrives (burst 10, priority 1). Since priority 1 < 2 (higher priority), $P_4$ preempts $P_1$ . Remaining burst of $P_1 = 11 - 2 = 9$ . $P_4$ runs.
$t = 5$ : $P_2$ arrives (burst 28, priority 0). Since priority 0 is the highest possible, $P_2$ preempts $P_4$ . Remaining burst of $P_4 = 10 - (5 - 2) = 7$ . $P_2$ runs.
During $P_2$ 's execution, $P_5$ arrives at $t=9$ (prio 4) and $P_3$ arrives at $t=12$ (prio 3). Neither can preempt $P_2$ .
$P_2$ completes at $t = 5 + 28 = 33$ .
$t = 33$ : Ready processes are $P_4$ (prio 1, rem 7), $P_1$ (prio 2, rem 9), $P_3$ (prio 3, rem 2), $P_5$ (prio 4, rem 16). Highest priority is $P_4$ . $P_4$ runs from 33 to 40 and finishes.
$t = 40$ : Highest priority is $P_1$ (prio 2). $P_1$ runs from 40 to 49 and finishes.
$t = 49$ : Highest priority is $P_3$ (prio 3). $P_3$ runs from 49 to 51 and finishes.
$t = 51$ : $P_5$ (prio 4) runs from 51 to 67 and finishes.

Calculate turnaround time ( $TAT = CT - AT$ ) and waiting time ( $WT = TAT - BT$ ) for each process:

$P_1$ : $CT = 49, AT = 0, BT = 11 \implies TAT = 49, WT = 49 - 11 = 38$
$P_2$ : $CT = 33, AT = 5, BT = 28 \implies TAT = 28, WT = 28 - 28 = 0$
$P_3$ : $CT = 51, AT = 12, BT = 2 \implies TAT = 39, WT = 39 - 2 = 37$
$P_4$ : $CT = 40, AT = 2, BT = 10 \implies TAT = 38, WT = 38 - 10 = 28$
$P_5$ : $CT = 67, AT = 9, BT = 16 \implies TAT = 58, WT = 58 - 16 = 42$

Sum of waiting times:

\sum WT = 38 + 0 + 37 + 28 + 42 = 145 \text{ ms}

Average waiting time:

\text{Average WT} = \frac{145}{5} = 29 \text{ ms}

Final answer

Common trap

Treating larger numeric values as higher priority instead of 0 being the highest priority.

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 51 of 65, printed as CS Q.51
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