ISRO2007-11, GATE CSE 2001 | Question: 1.19
in Operating System
9,445 views
20 votes
20 votes

Consider a set of n tasks with known runtimes $r_1, r_2, \dots r_n$ to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

  1. Round Robin
  2. Shortest job first
  3. Highest response ratio next
  4. first come first served
in Operating System
9.4k views

4 Comments

why not (c) Highest response ratio next

explain plz
0
0

@rajormanoj

-- Highest-Response-Ratio-Next policy favours shorter jobs, but it also limits the waiting time of longer jobs

https://www.geeksforgeeks.org/operating-system-highest-response-ratio-next-hrrn-scheduling/

0
0
Why not Round Robin?
0
0

Option B is correct.


But just for information's sake, HRRN has a formula of its own as per which it schedules processes. The formula is $\frac{WT+BT}{BT}$

WT = Waiting Time. BT = Burst Time.

Clearly, if Burst Time is very small, the overall number would be greater and it'll have a higher chance of running.

If Waiting Time is very large, same as above. (Hence prevents starvation)

1
1

Subscribe to GO Classes for GATE CSE 2022

5 Answers

36 votes
36 votes
 
Best answer

Answer :  Shortest job first

Throughput means total number of tasks executed per unit time. Shortest Job First has maximum throughput because in this scheduling technique shortest jobs are executed first hence maximum number of tasks are completed.
Note: Highest-Response-Ratio-Next policy favors shorter jobs, but it also limits the waiting time of longer jobs.

selected by

2 Comments

What will be the answer, if they ask Consider a set of n tasks with unknown runtimes r1, r2,....., rn to be run on a uniprocessor machine​​​​​​? In case of unknown runtime which algorithm works best?

0
0
15 votes
15 votes
ans is B.

SJF serves all the shorter processes first therefore number of processes completed in some time interval will be more in SJF than any other.

3 Comments

Can someone give an example here ? Lets say I have two processes with 10s and 20s as burst time, which ever algorithm I use, the total time taken will be the same, ie. 30s, so would still be Throughput = 2/30 for ALL the scheduling algorithms, right ?

And according to wikipedia, the only advantage we get out of SJF is, it has the least average waiting time https://en.wikipedia.org/wiki/Shortest_job_next  

4
4
This is among special case (that you are talking about).

But in general, if i have many jobs then according to the definition of..

Shortest Job First : all the shortest jobs will be completed first, hence maximum throughput than the rest.

Thus the answer is (B)
0
0
more understandable
0
0
10 votes
10 votes

Throughput means total number of tasks executed per unit time.
Shortest Job First has maximum throughput because in this scheduling technique shortest jobs are executed first hence maximum number of tasks are completed.
Highest-Response-Ratio-Next policy favors shorter jobs, but it also limits the waiting time of longer jobs.

2 Comments

what is highest response ratio next
0
0
Ok see editing.
0
0
3 votes
3 votes

In Round Robin if Time quantum is less, More number of processes are present and  All processes burst times are high than TQ then throughput decreases because all processes execute for TQ and wait in queue

In HRRN It favors shorter jobs but limit waiting time of longer processes

In FIFO if longer jobs arrived first then its Throughput decreases

In SJF smaller processes will execute first, it cause starvation of longer processes but compared to other scheduling algorithms SJF  results maximum throughput.

So Answer is SJF

0 votes
0 votes

I have a different opinion on this old question : According to me, answer is B and D.

Let me make my points : 

Throughput = #processes executed per unit time. If context switch time = 0; then no matter what algorithm you use, throughput is going to be same. Now, if CS time matters, throughput will be higher in non-preemptive algorithms.(as less #CS will happen here). So that rules out HRRN and RR as you may have more CS resulting in more time to complete all the n tasks, thus low throughput compared to non-preemptive algorithms.

But, the rest 2 are non-preemptive : SJF and FCFS. Take any example and draw the gnatt for it, your end time will always be the same as #CS are same. Thus throughput will be same in all non-preemptive algorithms : (CT of last process – AT of first process) / n ; 

 

Answer:

Related questions