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

best throughput, min avg waiting time and min turn around time always lowest in SRTF in case of preemptive while SJF in case of non preemptive

best response time occurs in round robin.

---

most optimal among all-SJF
but when srtf enters it become the most optimal in the house
and infact srtf has less avg waiting and turnaroung time then sjf
SRTF is the most optimal algo even better than SJF
even if other are trying to minimum they can be equal to srtf average only
and since its mcq we will directly go for srf
next time
gate can give such question as msq
then we need to check others along with srtf

---

Explanation...if you don't know anything then 

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

we can direlty mark as we know that srtf has least wt and tat in case only preemptive then sjf comes and we know fcfs and rr has high so direlty eliminate 1 sec answer

---

Yes you are exactly correct we can easily say srtf but for every kind of problem we can't guarantee right I mean in generalized we can say but for specific problem directly we can't say
So it's much better to do for confirmation because gate always try to prove us worng and it will definitely add spices to question
And it is 2015 question so we can directly say if nowadays this type of question came we shouldn't take risk

---

We dont' need to do all these, 

Answer is (C) SRTF 

There is no exception. SRTF is provably optimal for minimum average waiting time and minimum average turnaround time. There is no dataset of processes where any other algorithm beats it. 

The only edge case to be aware of:

When all processes arrive at the same time (arrival time = 0 for all), SRTF and non-preemptive SJF give the exact same result, because there's nothing to preempt.

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.

---

@Shaik Masthan sir I have also the same doubt please make it clear.

Thanks

---

Yes. Average waiting time in SRTF algorithm is lessthan or equal to SJF.

---

Thanks @Shaik Masthan sir

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.

Answer 5

Directly Answer:

SRTF is the pre-emptive version of SJF which will always give the minimal wait time. So directly answer C.

Why SJF is Optimal?

Consider two processes

	Execution Time
P1	2
P2	5

 

if P1 executes first,

$\Rightarrow$ P2 will have to wait till P1 Completes

$\Rightarrow$ That is 2 unit of time.

if P2 executes first,

$\Rightarrow$ P1 will have to wait till P2 Completes

$\Rightarrow$ That is 5 unit of time.

Better to execute shortest ones first so that others will have to wait till shorter execution times. 

 

Answer 6

Here the correct option would be option C- shortest remaining time and not SJF.

The main confusion is why SRTF and not SJF? Well if the arrival time is same both SRTF and SJF gives the minimum average waiting time but when the arrival time is different like in this case, the preemptive scheduling algo has advantage over non preemptive one and hence lower waiting time .  So we can directly say SRTF waiting time < SJF waiting time for processes that are premptive and having different arrival time otherwise its the same for arrival time =0 .