The Gateway to Computer Science Excellence
+25 votes
3.7k views

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?$$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Process Time}\\\hline \text{A} & 0 & 3 \\\hline \text{B} & 1 & 6  \\\hline \text{C} & 4 & 4 \\\hline \text{D} & 6 & 2 \\\hline  \end{array}$$

  1. First Come First Serve
  2. Non-preemptive Shortest job first
  3. Shortest Remaining Time
  4. Round Robin with Quantum value two
in Operating System by Veteran (105k points)
edited by | 3.7k views
0

@Arjun sir or @Bikram sir Please guide me on how to approach such questions which need calculation of each times seperately and then finding a conclusion.

for eg.

  1. The above question 
  2. https://gateoverflow.in/1992/gate2014-2-33

While writing test I fear wasting time to find results for all, and I believe there can be a option-elimination like approach to do this??

0

@Ashish Subscription

The average waiting time of RR and FCFS is very long, so no need to check it.And for SJF and SRTF, according to example by Galvin book, SRTF has lower waiting time than SJF.

But to be in the safe side, check for SJF and SRTF and then go for it.

4 Answers

+31 votes
Best answer

Turn Around Time $=$ Completion Time  $-$ Arrival Time

FCFS

Average turn around time $ = [3 \ \text{for A} + (2 + 6) \ \text{for B} + (5 + 4) \ \text{for C} + (7 + 2) \ \text{for D}] / 4 = 7.25$

Non-preemptive Shortest Job First 

Average turn around time $= [3  \ \text{ for A} + (2 + 6) \ \text{for B} + (3 + 2) \ \text{for D}+ (7 + 4)  \ \text{ for C}] = 6.75$

Shortest Remaining Time

Average turn around time $= [3 \ \text{for A } + (2 + 1) \ \text{ for B }+ (0 + 4) \ \text{ for C} + (2 + 2) \ \text{ for D} + (6 + 5)  \ \text{ for remaining B } ]/4 = 6.25$

Round Robin

Average turn around time $=$

$[2 \ \text{ for A (B comes after 1)}$
$+ (1 + 2)  \ \text{ for B {C comes}}$
$+ (2+1) \ \text{for A (A finishes after 3 cycles with turnaround time of} \ 2 + 3 = 5)$
$+ (1+2) \ \text{for C \{D comes\}}$
$+ (3+2) \ \text{ for B}$
$+ (3+2) \ \text{ for D (D finishes with turnaround time of } 3+2 = 5)$
$+  (4+2)  \ \text{ for C (C finishes with turnaround time of } 3 + 6 = 9)$
$+ (4+2)  \ \text{ for B (B finishes after turnaround time of } 3 + 5 + 6 = 14]$
$/4$
$= 8.25$


Shortest Remaining Time First scheduling which is the preemptive version of the SJF scheduling is provably optimal for the shortest waiting time and hence always gives the best (minimal) turn around time (waiting time $+$ burst time). So, we can directly give the answer here.

Correct Answer: $C$

by Veteran (424k points)
edited by
+2
SJF : TAT = 6.75 ,
RR : TAT = 8.25
0
Could you please check avg. turnaround time for RR scheduling? I am getting 8.5 instead of 9.
+11
can't we directly say SRTF as it always have lowest avg. turnaround time
+18
@hkara657

yes, we can say directly that SRTF have minimum Avg TAT .

  As we know TAT = waiting time + burst time

so for SRTF waiting time is least among all scheduling algorithms ( SJF, RR,FCFS )  hence TAT is also minimum , there is such possibility .
+1

@Arjun @Bikram Sir all time it will depend on instance? Or is there any pattern like SRTF tat will less than SJF or any? Can we conclude SRTF waiting time and tat minimum always??

otherwise we have to compute and check for all scheduling algo

0

 I have same doubt

+11 votes

TAT = Completion Time - arrival time 

First Come First Serve

0 A  3 3  B  9 9  C  13  13  D  15

TAT : for A ( 3-0) = 3 

for B (9 - 1) = 8

for C ( 13 - 4) = 9

for D (15 - 6) = 9

so Avg TAT = (3+8+9+9 ) / 4 =  29 /4 = 7.25  for FCFS .

--------------

Round Robin with Quantum value two

0  A  2 2  B  4 4  A  5 5  C  7 7  B  9 9  D  11  11  C  13 13  B  15

In RR after preemption a process go to end of that FIFO queue , so here first A is in queue then at time 1 B comes , time quantum is 2 so after 2 A is preempted then A go to end of queue after B as in queue only A and B is there . Now B continue till 4 then at that time C is in queue so B goes after C . As A was after B so when B preempted at 4 that time A starts and completes at 5 then C comes and at 7 C completes . At this point D arrive and go to after B in queue . Next B continue and C goes after D . B continue  till 9 then D starts and go to till 11 . Then again C comes and complete at 13 at last element of queue is B it completes rest at 15.

so the order in queue is like this A B A C B D C B 

Avg TAT = { ( 5-0) + (15-1) + (13-4) + (11 - 6) } / 4 = 5+14+9+5 / 4 = 33/4 = 8.25 

------------

Shortest Remaining Time  (SRTF)

0  A   3 3  B  4 4 C  8 8  D  10 10  B  15

A start at 0 then at 1 B comes but A have remaining time 2 and B have remaining time 5 so 2<5 and A continues till 3 , then B starts at 4 C comes , remaining time for B is 5 and C is 4 as 4<5 so C starts at 6 D comes , remaining time for B is 5 and 5>2 and for C remain is 2 , 2 = 2 so C continues after that D comes and at last B completes .

Avg TAT is = { (3-0) + (15-1)+(8-4) + (10-6) } / 4 =  (3+14+4+4) / 4 = 25/4 = 6.25

---------------

Non-preemprive Shortest job first  ( SJF)

0  A  3 3  B  9 9  D  11 11 C  15

Avg TAT = { (3-0) + (9-1)+ (15-4) + (11- 6) } / 4 = (3+8+11+5) / 4 =  27/4 = 6.75

so we can see , Avg TAT  for  FCFS = 7.25 ,  SJF = 6.75 ,   SRTF = 6.25   and   RR = 8.25   .

SRTF is less among them hence answer is option C .

by Veteran (72.4k points)
+2

 flash12  

Your understanding about this question is Wrong .. try to read again how RR works,  from Galvin.

Then solve this question again and match with my solution .

+2
Calculated RR with Gantt Chart, with avg. TAT of 8.25
0

@Bikram

In case of RR, at t = 4, both B gets preempted and C arrives in the ready queue.Why is C considered before B in the queue? 

0
In case of RR, at t = 4, both B gets preempted and C arrives in the ready queue. Average C arrives in the ready queue .
0
Yeah , but B also goes to the ready queue after getting preempted, right? Then it might happen that B arrives earlier in the ready queue than C. So why is C considered first? Is it because there will be some context switchinf overhead and B comes late?
0
So why is C considered first .
0

Now B continue till 4 then at that time C is in queue so B goes after C 

I am talking about this. Why would B go after C? Can it not happen that B gets preempted and comes again into the ready queue and then C arrives in the ready queue? In that case C goes after B , although the avg TAT remains same.  

0
FCFS = 7.25 , SJF = 6.75 , SRTF = 6.25 and RR = 8.25

SRTF is less among them hence answer is option C ....
+6 votes

Turn around time is Amount of time taken to complete a particular process. ie 

=> Process Completion Time-Process Arrival Time

Average Turn Around Time (TA) for FCFS will be

=[TA(A)+TA(B)+TA(C)+TA(D)]/4

[(3-0)+(9-1)+(13-4)+(15-6)]/4=7.25

Average Turn Around Time (TA) for SJF will be

=[TA(A)+TA(B)+TA(C)+TA(D)]/4

(3+8+5+11)/4=6.75

Average Turn Around Time (TA) for SRTF will be

=[TA(A)+TA(B)+TA(C)+TA(D)]/4

[(3-0)+(15-1)+(8-4)+(10-6)]/4=6.25 

Average Turn Around Time (TA) for RR with time quanta 2 will be 

=[TA(A)+TA(B)+TA(C)+TA(D)]/4

A B A C B D C B

0           2                4               5               7                9              11               13              15

[(5-0)+(15-1)+(13-4)+(11-6)] /4=( 5+14+9+5)/4

=>33/4=8.25

If we consider non preemptive Round Robin then Gantt Chart will be

0            2               4                6               8        9       10          12               14           16

A B C D A - B C B

Average Turn Around Time Will be

[(9-0)+(16-1)+(14-4)+(8-6)]/4=36/4=>9

So, Lowest Turn Around Time Will be in case of SRTF.

 
 
 
by Active (1.7k points)
edited by
+4

Average Turn Around Time (TA) for RR with time quanta 2 will be 

=[TA(A)+TA(B)+TA(C)+TA(D)]/4

A B C D A B C B

0           2                4               6               8                 9              11               13              15

[(9-1)+(15-1)+(13-4)+(8-6)] /4=( 8+14+9+2)/4

=>33/4=8.25

Sir, in the above answer why are we subtracting 1 from 9 in case of A.

0

@shubhk

There No need to subtract 1 in case of A.

That Gantt chart would be like this :

0 A  2 2  B  4 4  A 5 5  C 7 7  B 9 9  D  11 11  C 13 13  B  15


it would be (5-0)+(15-1)+(13-4)+(11-6)]  / 4

= (5+14+9+5 ) / 4

= 33 / 4

= 8.25

so average turn around time for RR is 8.25

+1
No. RR is not like that. At any stage of the queue only the currently arrived processes are considered.
+1

@Arjun

I understand , the order of RR gnatt chart would be like this 

0 A2 B4 AC7  B9 D11 C13 B15 

TAT for A = 5-0 = 5

B = 15-1 = 14

C = 13-4 = 9

D = 11-6 = 5

so Avg TAT = (5+14+9+5 ) / 4 = 33/4 = 8.25 

+1
Turn around times for A, B, C, D are 5, 14, 9, 5.
+1
Can you draw the gnatt chart for RR ?

I am not getting how TAT for A is 5 ?? really not getting..

plz  draw it .. only from gnatt chart it will clear , even from your answer it is not clear how TAT is 8.2 ..

for other schedulings i will draw charts and add a new answer but for RR i don't get your solution by reading that ..so draw your gnatt chart plz only for RR !
+2
I have added in the answer.
+5 votes

Average Turn around time=$\sum_{i=1}^n\frac{Burst Time_i+Waiting Time_i+Time\,doing\,I/O_i}{n}$

where n=Number of processes in the system.

Assuming all processes are completely CPU bound, for all processes $Time\,I/O=0$

Since, average of Burst time overall process would come to be same irrespective of the scheduling algorithm followed,

My Average turn around time depends directly proportional to the Waiting time of each process.

And below is a snapshot from galvin

Below an example from Galvin, proves an observation: Avg waiting time of preemptive SJF is less than that of non-preemptive SJF.

 

And among all scheduling algorithms, SJF is optimal indeed.

So, among all the options given, Shortest Remaining Time(Preemptive SJF) would minimum average waiting time for all the processes and hence average turn around time compared to others will be low.

Clearly, answer is (C)

by Boss (27.6k points)
0

Does it mean that if we compare SJF with other algorithms it will be optimal but if we bring SRTF in the picture then SRTF will even be better than SJF ?

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,647 questions
56,459 answers
195,378 comments
100,278 users