edited by
18,811 views
42 votes
42 votes

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
edited by

5 Answers

Best answer
53 votes
53 votes

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$

edited by
18 votes
18 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 .

10 votes
10 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)

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

 
 
 
edited by
Answer:

Related questions

35 votes
35 votes
6 answers
1
go_editor asked Feb 14, 2015
30,238 views
The maximum number of processes that can be in $\textit{Ready}$ state for a computer system with $n$ CPUs is :$n$$n^2$$2^n$Independent of $n$
69 votes
69 votes
6 answers
3
go_editor asked Feb 14, 2015
20,370 views
Two processes $X$ and $Y$ need to access a critical section. Consider the following synchronization construct used by both the processes$$\begin{array}{|l|l|}\hline \text...