GATE CS 2011 Q.35 (CS Q.35): Process Synchronization and Concurrency

Consider the following table of arrival time and burst time for three processes P0, P1 and P2.

Process	Arrival time	Burst Time
P0	0 ms	9 ms
P1	1 ms	4 ms
P2	2 ms	9 ms

The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?

5.0 ms

4.33 ms

6.33 ms

7.33 ms

Official answer and solution

Official answer: A
From: Official GATE 2011 answer key

Solution

Construct the Gantt chart for Shortest Remaining Time First (SRTF) scheduling and compute the waiting times.

At time $t = 0$ : Only process P0 is available (burst 9). P0 executes from $t = 0$ to $t = 1$ .

At time $t = 1$ : P1 arrives with burst 4 ms. P0 has remaining burst $9 - 1 = 8\text{ ms}$ . Because $4 < 8$ , P1 preempts P0. P1 executes.

At time $t = 2$ : P2 arrives with burst 9 ms. P1 has remaining burst 3 ms. Because $3 < 9$ , P1 continues executing until completion at $t = 1 + 4 = 5\text{ ms}$ .

At time $t = 5$ : Ready queue contains P0 (remaining 8 ms) and P2 (remaining 9 ms). P0 has the shorter remaining time and executes from $t = 5$ to $t = 13\text{ ms}$ , completing at $t = 13$ .

At time $t = 13$ : P2 executes from $t = 13$ to $t = 22\text{ ms}$ , completing at $t = 22$ .

Waiting time for each process (Completion Time - Arrival Time - Burst Time):

P0: $13 - 0 - 9 = 4\text{ ms}$
P1: $5 - 1 - 4 = 0\text{ ms}$
P2: $22 - 2 - 9 = 11\text{ ms}$

Average waiting time:

\text{Average Waiting Time} = \frac{4 + 0 + 11}{3} = \frac{15}{3} = 5.0\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 2011 Computer Science and Information Technology (CS)
Question: 35 of 65, printed as CS Q.35
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