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

Answer 1

Answer is (A). $5$ms

Gantt Chart

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

Comments

Scheduling is carried out only at arrival or completion of processes

Doesn't this statement mean non-pre emptiveness? Even though question asks us to calculate using the pre-emptive shortest job first scheduling algorithm. Blockquoted text confuses me. I even tried with non pre emptive scheduling and I get answer as 6.33ms (C). Could some one help me understand?

---

"Scheduling is carried out only at arrival or completion of processes"

Doesn't this statement mean non-pre emptiveness

---

Yes, that is what is done here! At time 0, only P0 is there which has a burst of 9units and is taken into execution. At time 1, P1 arrives whose BT is 4 which is less than P0's(8 now), hence P0 is pre empted and so on

---

@Shalini Dutta , what do you think of this statement,

"Scheduling is carried out only at arrival or completion of processes"

---

yes , which means scheduling is carried out only when a process arrives/completes. By my explanation P0 os pre empted when P1 arrives(Note : arrival OR completion)

---

Thanks for the clarification. I misunderstood it.

---

"Scheduling is carried out only at arrival 'or' completion of processes".
It may seems like this statement makes the question about non preemptive shortest job first scheduling algo but the difference is made by "or" statement.
Tricked

---

Can someone explain why P2 cannot be scheduled in 5th sec?

Understood my mistake: I took $P_1$ as $10$ initially.

Thank you @ankitgupta.1729

---

@Manoja, yes, initially both processes $P_{0}$ and  $P_{2}$ have same burst time but process $P_{0}$ got processor between time $0$ ms to $1$ ms ...So, at time = $5$ ms , remaining burst time of $P_{0}$ is $8$ ms which is less than the burst time of process $P_{2}$ which is $9$ ms.

---

Scheduling is carried out only at arrival or completion of processes

this is what we do in preemptive mode ..schduling happens when new process comes( arrives) based on criteria.

In non preemptive mode ..scheduling happens only when process completes..process arrival in between doesn't affect

---

great observation.

---

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

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