GATE CSE 2015 Set 3 | Question: 34

Question

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}$$

• A. First Come First Serve
• B. Non-preemptive Shortest job first
• C. Shortest Remaining Time
• D. Round Robin with Quantum value two

Comments

@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??

---

@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.

---

can we directly say it will be srtf without checking because for given set of processes srtf will always give the lowest wt...

---

What I did is, RR and FCFS is eliminated as @sutanay3 said. Then between SJF and SRTF, calculate in mind the completion time of each process using both algorithm, you will notice that because of preemption we get less waiting time in SRTF because shorter job preempts and gets processed firstly. So, as SJF doesn’t supports preemption, SRTF is preferable choice. Please correct me if I am wrong.

Answer 1

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$

Comments

@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

---

@ Abhisek Tiwari 4 I have same doubt

---

@Arjun sir

https://gateoverflow.in/2602/gate1995-1-15?show=348471#c348471

but in this ques @bikram sir said that RR is better than SRTF.

Is it like in time sharing OS we are concerned mainly on response time minimization ???

cause SRTF gives the best TAT(turn around time) among all the algo’s

Answer 2

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 .

Comments

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.  

---

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

SRTF is less among them hence answer is option C ....

---

Yes this is correct way. Why everyone is doing wrong

Answer 3

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)

Comments

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 ?

---

Yes, I have also same doubt.

Answer 4

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.

 

 

 

Comments

Turn around times for A, B, C, D are 5, 14, 9, 5.

---

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 !

---

I have added in the answer.