edited by
28,351 views
63 votes
63 votes

A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with zero (the lowest priority). The scheduler re-evaluates the process priorities every $T$ time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

  1. This algorithm is equivalent to the first-come-first-serve algorithm.
  2. This algorithm is equivalent to the round-robin algorithm.
  3. This algorithm is equivalent to the shortest-job-first algorithm.
  4. This algorithm is equivalent to the shortest-remaining-time-first algorithm.
edited by

5 Answers

Best answer
60 votes
60 votes

(B) Because here the quanta for round robin is $T$ units, after a process is scheduled it gets executed for $T$ time units and waiting time becomes least and it again gets chance when every other process has completed $T$ time units.

edited by
67 votes
67 votes

Consider three processes $P_1,P_2,P_3$ all arriving at time 0, having same priority 0 initially and they arrive in order $P_1,P_2,P_3$

Now my ready queue looks like

$P_1$ $P_2$ $P_3$

 

After $T$ time units,

Waiting times of P1,P2,P3 are 0,T,T respectively. Clearly, since priority is assigned proportional to the waiting time, P2 and P3 would be given priority over P1 and P1 is sure to get preempted.

Ready queue says P2 will be executed next. Cool!

So, P1 put at the tail of the ready queue and the ready queue is now

$P_2$ $P_3$ $P_1$

 

After another $T$ units of time

Waiting times of P1,P2,P3=T,T,2T

Clearly, P2 will be preempted now and P3 would get a chance

Ready queue becomes

$P_3$ $P_1$ $P_2$

 

After another T units of time

Waiting times of P1,P2,P3=2T,2T,2T. All have same priorities, so T3 can be allowed to execute next.

After another T units of time

Waiting times of P1,P2,P3=3T,3T,2T. Now surely P3 would be preempted and now ready queue becomes

$P_1$ $P_2$ $P_3$

P1 executed next for T units of time.

Waiting times of P1,P2,P3=3T,4T,3T

P2 would get chance now and the ready queue will be

$P_2$ $P_3$ $P_1$

 

Clearly this scheme is not one of SRTF or SJF or FCFS because otherwise after T time units, in case of SRTF atleast one job would have been computed in it's entirety at some point of time and same with the SJF, and with FCFS, arrival time would have mattered and not priority based on waiting time!!

So basically this algorithm is ensuring that the waiting time of each job is bounded by some constant in terms of time quanta T units and ensure every job gets a  chance.That is the job of RR scheduling.!!

Answer-(B)

 

18 votes
18 votes

Answer is option B.Why?

Given algorithm is : After every 'T' time units, processes are given priority w.r.t. waiting time. 

lets analyse each option :

(a) not possible. as in FCFS there is no time quantum.

(C) not possible.. SJF is different. It is not preemptive.

(D) In SRTF although a process with shortest burst time is picked. But here priority is assigned based on Burst Time of a process.  

The requirement of scheduling algorithm is priority should be assigned based on WaitingTime of a process.   Hence this is not the answer.

So the remaining option (B) RR is the answer.

edited by
18 votes
18 votes

" The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. "


~ This means there must be a time quantum T exists , without time quantum scheduler can not re evaluates the process priorities .

So now option A , FCFS gone wrong, as in FCFS there is no time quantum.
And option C , SJF also gone wrong as it is also not pre emptive scheduling algorithm.

so we left with option B and option D .

-------------
Now option D is wrong because it says "  assigns priority proportional to the waiting time of a process. " .


" A scheduling algorithm assigns priority proportional to the waiting time of a process. "


~ This makes Option C and D wrong , because in  SJF ( shortest JOB First ) and SRTF( it is just the preemptive version of SJF, those who have less BURST time after first process executed, executed before large burst time process   )  , priority is assigned based on Burst Time of a process.

FCFS and Round Robin scheduling , priority is assigned based on waiting time of process. ( when arrival time is not same )

so we are left with only option B , which is RR scheduling .

That's why only option B is correct.

edited by
Answer:

Related questions