retagged by
9,002 views
14 votes
14 votes
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.
retagged by

6 Answers

Best answer
23 votes
23 votes

We get minimum achievable average waiting time using SJF scheduling.

Lets just name these processes for explanation purpose only as $A = 16, B = 20$ and $C = 10.$

Order them according to burst time as $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.

2 votes
2 votes

 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 by
2 votes
2 votes
  • 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.

Ref: SJF(non-preemptive algorithm)

0 votes
0 votes
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
Answer:

Related questions

13 votes
13 votes
5 answers
1
Arjun asked Feb 18, 2021
8,018 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
8 votes
8 votes
3 answers
2
Arjun asked Feb 18, 2021
10,693 views
Consider the following undirected graph with edge weights as shown:The number of minimum-weight spanning trees of the graph is ___________.