GATE CSE 2016 | Set 1 | Question: 20

Question

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

• A. Shortest remaining time first
• B. Round-robin with the time quantum less than the shortest CPU burst 
• C. Uniform random
• D. Highest priority first with priority proportional to CPU burst length

Comments

What is Uniform random process scheduling?

---

waiting time will be reduced when the jobs with lower burst time are completed first which is done by SRTF.

---

@Nitesh12-10 select any proccess from the ready queue at random and run it.

Answer 1

Answer should be (A) SRTF
SJF minimizes average waiting time. Probably optimal.
Now, here as all processes arrive at the same time, SRTF would be same as SJF. and hence, the answer.

Reference: http://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l13-sched.pdf See Slide 16,17 and 23

Comments

Here above in the answer it is given that as all processes arrive at the same time, SRTF would be same as SJF. so it is the answer. But if the processes arrive at different time then also I guess SRTF will give the minimum average waiting time ?

---

@manya03
Yes. SRTF is more optimal than SJF in that scenario

---

Okay I get it !!

Answer 2

Turnaround time is the total time taken by the process between starting and the completion and waiting time is the time for which process is ready to run but not executed by CPU scheduler. As we know, in all CPU Scheduling algorithms, shortest job first is optimal i.ie. it gives minimum turn round time, minimum average waiting time and high throughput and the most important thing is that shortest remaining time first is the pre-emptive version of shortest job first. shortest remaining time first scheduling algorithm may lead to starvation because If the short processes are added to the cpu scheduler continuously then the currently running process will never be able to execute as they will get pre-empted but here all the processes are arrived at same time so there will be no issue such as starvation. So, the answer is Shortest remaining time first, which is answer (A).

Answer 3

this would help

Answer 4

If we take arbitrary set of CPU-bound processes with unequal CPU burst lengths

Process	Burst Time
P1	2
P2	3
P3	4
P4	5

Average waiting of SRTF : (0+2+5+9)/4 = 4

Average waiting of RR(1 ms QT) : (3+6+8+9)/4 = 6.5

Average waiting of Highest priority : (0+5+9+12)/4 = 6.5

Answer : Option A

Answer 5

Shortest remaining time first is optimal. For any scheduling scenario where response time is not a metric of concern, there is no better algorithm than SRTF. SRTF produces the best average waiting time, completion time and turnaround times.

Answer 6

Ans should be srtf but because in srtf their may be possibility of starvation so answer is round robin.

Comments

Sjf will minimum average waiting time .  when all jobs submitted at the same time SJF and SRTF same .

---

Question asked was about average waiting time.. And SRTF is the answer..
http://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l13-sched.pdf