3.9k views

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 | 3.9k views
0
none of the 2 answers is making sense.. @bikram sir
+29

Shivansh Gupta

" 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 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.

+2
Hope this makes some sense now .
0
Thx @bikram sir its clear now.

I was wrongly thinking about waiting time of process. Waiting time of process will not increase when it executes on cpu. Small mistake:)
0
I have a different doubt, if there are 5 processes all arriving at time 0, and all processes have priority 0 (both conditions are as per the question), how is RR going to pick a process for execution? Say, even if it picks P1 randomly, then after T time, P2-P5 all have priority 1. Then how it is going to pick the next process?
0
if not RR do you see any other close match ?

yes it is not exactly RR but approximately RR.
0
Yes as per the options given, we have no other choice but RR, all I said is even RR doesn't seem to be perfect.
+1
I think this statement is enough to prove its round robin .. "The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule " .....
0
Hello Puja

No, I think you're going wrong here because as i'm able to see this can be the case in SRTF algorithm also , where a short term scheduler is bound to make decision after every 'T' time units.
0
SRTF - Shortest remaining time first ... where priority is remaining time of the process ... So how is it bounded to make decision after "T" time units ?? Because less the time span to execute .... more priority of that process ... So T time unit will not be constant Like round robin ... correct me if i am wrong ...
+1

For a second remove line "Priority is proportional to the waiting time of a process" from our original question.Now From our this updated question we now don't know ,on what bases priority is being assigned after every T time units.So in that scenario the answer would be either SRTF or RR scheduling algorithm because we can make such arrangement of processes in that short term scheduler have to take scheduling decision after every 'T' time units like this one

 Processes Arriving time Burst time $P_{1}$ $0$ $6$ $P_{2}$ $2$ $4$ $P_{3}$ $4$ $1$

in case of like above arrangement of process requests , Short term scheduler have to make scheduling decision after $2$ time units (most of the time).

Edit :- During writing this i noticed , there is strict $T=0$ arrival time for all processes so in that case yes! that line if enough to conclude that scheduling algorithm is almost like RR.

Pardon me puja that i missed to notice that before.

0
So it means the answer have nothing to do with waiting time? All processes arriving at time 0 implies that answer is RR?

(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
0
Why do this is not SRTF? Could you plz explain where I'm wrong?
0

What should I consider about priority since it is not given whether the priority is directly proportional or indirectly proportional to waiting time??

0
@tuhin dutta no need of knowing that.. because all arrive at same time so their priorities will be evaluated to be same always.. so tie will occur always..
+7

Why do this is not SRTF ? Could you plz explain where I'm wrong?

see in question , it says

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

~ This makes Option  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

But our requirement is waiting time so SRTF is rejected .

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
0
can u please give me the main diff. between option c and option d..
+1

But process is picked after the currently executing process is terminated

I think this statement is wrong . SRTF is preemtive shedule and new process is picked as and when a process with small remaing time comes up . Need not required to wait till its completion

0
here D is wrong bcz in srtf depends upon burst time of process and it can be varying but here they given fix time as T . this is only indication of time quantum
0

@cse7

The main difference between option C and option D is :

option C is SJF  , which is non preemptive.

option D is SRTF , which is pre-emptive .

Now question says , requirement is pre-emptive scheduling algo so option C is rejected.

And " assigns priority proportional to the waiting time" that's why SRTF is rejected as in SRFT we need to assign priority based on burst time.

" 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

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

 $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.!!

0

1
2