# GATE CSE 2021 Set 1 | Question: 25

359 views
Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$ bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.

recategorized ago

1 vote

we get minimum achievable average waiting time using SJF scheduling.

let just name these processes for explaining purpose only A = 16, B = 20, C = 10.

order them acooring to burst time C<A<B

C will not wait for anyone,  schedule first ( wait time = 0)

A will wait for only C (wait time = 10)

B will wait for both C and A (wait time = 10 + 16)

average wait time = $\frac{0+ 10 + (10+16)}{3} = \frac{36}{3} = 12.$

No need to make any table or chart.

This is all for explaining purpose, you can actually ans this within 10-15 sec after reading the complete question.

1 vote

Required to find min mum avg. weighting time of non preemptive scheduler.

SJF give min mun avg. weighting time

 No Process B.T. C.T. T.A.T. W.T. 1 P1 16 26 26 10 2 P2 20 46 46 26 3 P3 10 10 10 0

 P3(10) P1(16) P2(26)

Avg W.T. = (10 + 26 + 0)/3 = 12

Ans : 12

edited
1 vote
• SJF gives minimum average waiting time over other non-premitive CPU scheduling algorithms.
• in the SJF technique select the process which has minimum burst time

 PNO AT BT CT TAT WT $A$ $0$ $16$ $26$ $26$ $10$ $B$ $0$ $20$ $46$ $46$ $26$ $C$ $0$ $10$ $10$ $10$ $0$

1. $\textrm{TAT=CT-AT}$
2. $\textrm{WT=TAT-BT}$

$\therefore$ average wt = $\frac{10+26+0}{3}\implies12ms$

so correct answer is $12$ ms.

For minimum average waiting time we will choose SJF (shortest job first).Which is non preemptive algorithm.

Minimum burst time will be criteria for choosing the next process for scheduling.

P3 will complete at 10th second.

P1 will complete at 26th second.

P2 will complete at 46th second.

Turn around time for P1: 26 seconds

TAT for P2: 46 seconds

TAT for P3: 10 seconds

Waiting time for P1: 10 seconds

WT for P2: 26 seconds

WT for P3: 0 seconds

So,average waiting time will be (10+26+0)/3 = 12 seconds

ANS IS 12.

HERE IN QUESTION, IT IS MENTIONED THAT “SCHEDULER HAS PRIOR KNOWLEDGE ABOUT THE LENGTH OF THE CPU BURSTS” SO IT MEANS WE HAVE TO USE SJF.

PS: BY MISTAKE I WROTE AVG TAT IT IS AVG WT ONLY. :)

## Related questions

1
385 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
2
422 views
Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.
1 vote
3
487 views
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter $2$. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to $2$ decimal places) is ____________.
There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that: The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.