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

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.