The Gateway to Computer Science Excellence
+6 votes
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
$$\begin{array}{|c|c|c|c|c|} \hline \text{Process} & P1 & P2 & P3 & P4  \\ \hline \text{Arrival Time} & 0 & 1 & 3 & 4 \\ \hline \text{CPU burst time} & 3 & 1 & 3 & Z \\ \hline \end{array}$$
These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is $1$ millisecond, then the value of $Z$ is _____
in Operating System by Veteran (431k points)
edited by | 3.3k views
ans is 2
At, 4ms p1 and p2 are finished, and waiting time of p1 and p2 is 1 and 0. In order to have avg wait time as 1 sum of wait time of p3 and p4 should be 3. If p4 starts at 4 with BT as "2" then its wait time is 0, and at 6 ms it will be over and p3 will start at 6. So wait time of p3 is 6-3=3 and hence it satisfies the condition that sum of wait times of p3 and p4 should be 3. Hence, Z=2
Should be 2 !
I could not do this in exam, but solved it easily when came home. That's why we need to keep calm during GATE exam
Very easy question.

3 Answers

+19 votes
Best answer

Till $t = 4$, the waiting time of $P1 = 1$ and $P2 = 0$ and $P3=1$ but $P3$ has not started yet.

Case 1:

Note that if $P4$ burst time is less than $P3$ then $P4$ will complete  and after that $P3$ will complete. Therefore Waiting time of $P4$ should be $0$. And total waiting time of $P3 = 1 +$ ( Burst time of $P4$) because until $P4$ completes $P3$ does not get a chance.

Then average waiting time $= \frac{1+0+(1+x)+0}{4} = 1$

$\frac{2+x}{4} = 1 \Rightarrow x = 2.$

Case 2:

Note that if $P4$ burst time is greater than $P3$ then $P4$ will complete after $P3$ will complete. Therefore, Waiting time of $P3$ remains the same. And total waiting time of $P4 =$ ( Burst time of $P3$) because until $P3$ completes $P4$ does not get a chance.

Then average waiting time $= \frac{1+0+1+3}{4} = 1$

$\frac{5}{4} \neq 1 \Rightarrow$ This case is invalid.

Correct Answer: 2

by Veteran (65.6k points)
edited by
+10 votes
In SRTF we use criteria on the basis of burst time . A process have lowest burst time go first  for execution  if two process have same burst time priority should be given to that process which have lowest arrival time . Still two process have same arrival time choose lower  process id.


by Loyal (5.3k points)
+1 vote
The burst time of process P4=2


Since,waiting time of process P1 and P2 are 1 and 0 respectively and finishes in time 4ms and given the average=1 therefore the sum of waiting time of P3 and P4 must be 3 and for this,Z should be equal to 2 so that the waiting time of P4 could be 0 and waiting time of P3 will be 6-3=3ms
by (303 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,295 answers
104,971 users