GATE CSE 2011 | Question: 35

Question

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

$$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Burst Time}\\\hline \text{P0} & \text{0 ms} & 9 \\\hline \text{P1} & \text{1 ms} & 4 \\\hline \text{P2} & \text{2 ms} & 9 \\\hline  \end{array}$$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?

• A. $5.0$ ms
• B. $4.33$ ms
• C. $6.33$ ms
• D. $7.33$ ms

Comments

Waiting time = Turn Around Time - Burst Time
Turn Around Time = Completion Time - Arrival Time

---

why not Waiting time =completion time - Burst time

---

Lets suppose a process arrived at 99 sec and runs for 1 sec and completes at 100 so according to you its waiting time will be 99 which is wrong as it did not wait any time.

So thats why waiting time = completion time - arrival time - burst time.

Thats how much time it has to sit idle and wait

Answer 1

Answer is (A). $5$ms

Gantt Chart

$\text{ Average Waiting Time = } \dfrac{(0+4)+(0)+(11)}{3} = \text{ 5ms. }$

Comments

Notice the "or" word in the Quoted Text @Nitish Gate Questions Tricks you

---

@jatin, Doesn’t SRTF schedules both during arrival of process and also at end of process(When a process A was pre-empted due to Process B, after Process B completes , A is considered for scheduling).

 

Can some-one pls explain the Significance of OR in the question, I am confused 

 

---

@Mohank it simply means that scheduling will happen if a process arrives or completes(Observe When P0 had executed for 1ms then at t=1 P1 arrives and since it is mentioned in the question that scheduling can happen if a process arrives, so srtf will now schedule process P1 because it has shorter Burst time) at T=2 again process P3 arrives then scheduling will happen again and so on.

If the question had been “Scheduling is carried out only at arrival AND completion of processes.” then it would have been non-preemptive because at t=1 even if P1 arrives the process P0 has not yet completed its execution, only at T=9 scheduling will happen because at that time a process has completed it execution and other processes have already arrived.

Answer 2

BEST ANSWER

Answer 3

P   AT    BT      CT    TAT   WT

P0    0     9,8,0   13    13    4

P1    1     4,0     5     4     0

P2    2     9,0     22    20    11

P0,P1,P0,P1

Avg, waiting time = 15/3  = 5 Option A

Answer 4

this is the answer

Answer 5

Option (A) is correct 4+0+11=15/3=5ms