2.3k 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.
none of the 2 answers is making sense.. @bikram sir

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.

Hope this makes some sense now .
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:)
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?
if not RR do you see any other close match ?

yes it is not exactly RR but approximately RR.
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.
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 " .....
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.
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 ...

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.

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

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

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

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

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

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

@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