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

Which process scheduling alogrithm will take max avg waiting time?

---

For max average waiting time, we can not say for sure because it would depend on the input. But minimum is always guaranteed by SJF and SRTF.

---

Why isnt it Round-Robin? Cuz srtf may cause starvation isnt it? And with burst time, every process will get a chance to execute.

---

What we consider if srtf and round robin only two present ?

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

@abhilash why can't it be option D?

isn't A and D indicating the same thing ?

---

Option D is
Highest priority first with priority proportional to CPU burst length..
say

J1 = 10
J2 = 20
J3 = 30
oprtion A SRTF would give the order J1->J2->J3
option D would give J3->J2->J1.. since higher burst length means higher priority..given- priority is proportional to CPU burst length.. as burst length increases, priority also increases.. so it is infact longest job first.

---

Too cool ! Thanx a ton.. But what if it would have been priority inversely proportional to CPU burst length ?

---

then your previous comment was right :) :D

---

@abhilashpanicker29 Isn't option (D) more like longest remaining time first. Because priority is proportional to the burst time and as the burst time decreases (becuase the process is being executed), the priority of the process will also decrease. 

I have taken the assumption that the priority of a process can chance during its execution.

Either-way, LTF or LRTF, the answer will still be (a). 

---

SRTF is a pre-emptive variant of  SJF.

And SJF gives minimum average waiting time for a given set of processes.

Source - Galvin 9 ed.

---

In any way , SRTF is better than SJF because it does not even has convoy effect.

---

What is convoy effect ? and how does SRTF is better than SJF ?

@sushmita, Can you please elaborate ?

---

https://gateoverflow.in/225250/%23galvin-%23cpuscheduling-sjf-srtf-average-waiting-time-doubt

---

"Now, here as all processes arrive at the same time"

If arrival time is different for all processes then also SRTF is the answer. Is this true ?

check link:

https://gateoverflow.in/8492/gate2015-3-34

---

@Satbir

In case of response time, ans is RR with least Time quantum ??

---

abhilashpanicker29 That's not "probably" — that's provably, ie, it can be proved.

---

@abhilashpanicker29 Why not Round Robin?

---

@Shivani Shukla 
Don’t confuse waiting time with response time waiting time will always be minimum in case of SJF 

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

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

Answer 4

B .because fair kind of decision is made by round robbin as it pre empts  the executing process when a slot/ quantum expires.

Comments

read the question once again