GATE CSE 1995 | Question: 1.15

Question

Which scheduling policy is most suitable for a time shared operating system?

• A. Shortest Job First
• B. Round Robin
• C. First Come First Serve
• D. Elevator

Comments

Note: The elevator algorithm (also SCAN) is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.

---

SJF is a non-preemptive algorithm
and RR is preemptive algo and thats why most suitable for time shared OS

---

In time shared OS we need less response time. This is ensured only by RR. (among the options given)

Answer 1

Answer is Round Robin (RR), option (B).

Now question is Why RR is most suitable for time shared OS?

First of all we are discussing about Time shared OS, so obviously We need to consider pre-emption .

So, FCFS and Elevator these $2$ options removed first , remain SJF and RR from two remaining options.

Now in case of pre-emptive SJF which is also known as shortest remaining time first or SRTF  (where we can predict the next burst time using exponential averaging ), SRTF would NOT be optimal than RR. 

• There is no starvation in case of RR, since every process shares a time slice.
• But In case of SRTF, there can be a starvation , in worse case you may have the highest priority process, with a huge burst time have to wait.That means long process may have to wait indefinite time in case of SRTF. 

That's why RR can be chosen over SRTF in case of time shared OS.

Comments

@bikram sir

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

but in this ques @Arjun sir said that SRTF is provably the best optimal algo and in that ques round robin algo was also in the options.

Is it like in time sharing OS we are concerned mainly on response time minimization ???

cause SRTF gives the best TAT(turn around time) among all the algo’s

---

@Bikram, by

SRTF would NOT be optimal than RR. 

do you mean in practice? Because as far as i know SRTF is optimal theoretically. Kindly confirm, thanks.

---

@air1ankit  

In the context of scheduling tasks or processes in a time shared operating system, exponential averaging might be used to predict the next burst time, which is the amount of time that a task or process will need to execute before it is preempted or yields control of the CPU.

To perform exponential averaging, you would take a series of observations of the burst time for a task or process, and use an exponential smoothing factor to weight the observations in a way that gives more importance to more recent observations. The resulting exponential average can then be used as an estimate of the expected burst time for the task or process in the future.

Answer 2

B. Round Robin

Reason: Generally in time shared systems we need to have a best response time. So if we use Round Robin among the given algorithms we will achieve the best response time.

Answer 3

B. Round Robin.

Comments

Why Round Robin ?

Although, For SJF we can't directly know the Burst Time for the incoming process (directly), but we can predict , the burst time , by exponential averaging .

In Galvin, also, its written that "SJF is provably optimal ". So How come RR is optimal ?

@Arjun Sir !

---

 SJF is a non-preemptive algorithm
and RR is preemptive algo and thats why most suitable for time shared OS

---

Sir !

But there are two mode for SJF :

1) Premptive and

2) Non-premtive

I get that in case of non-preemtive the validation would hold but in case of pre-emption (where we can predict the next burst time using exponential averaging ) , SJF would be optimal than RR.

In RR, the result will also depend on the choice of Time quantum.

a) If its large, the algo downgrades to FCFS

b) if its too small ==> more context switches are required (we need to include context switching time in consideration)

Also, I checked Galvin, and they have clearly written in favour of SJF, I couldn't find anything relating to optimality in case of RR.

---

See,

We are discussing about Time shared OS, so obviously We need to consider pre-emption .

Now in case of pre-emptive SJF  which is also known as shortest remaining time first or SRTF  (where we can predict the next burst time using exponential averaging ) , SRTF would NOT be optimal than RR.

Because:

Point 1: There is no starvation in case of RR, since every process shares a time slice.

But In case of SRTF, there can be a starvation , in worse case you may have the highest priority process, with a huge burst time have to wait.That means long process may have to wait indefinite time in case of SRTF.
[see this link for source : 3rd paragraph :https://en.wikipedia.org/wiki/Shortest_remaining_time ]

Like shortest job first, SRTF has the potential for process starvation; long processes may be held off indefinitely if short processes are continually added.

As our context is Time shared OS ( the Goal is Maximum utilization of CPU time), this point of Starvation is more valuable and it proves why RR is optimal.

And in Answer key the answer is given as B - Round Robin.

Hope you are convinced now.

Answer 4

Refer below link.

Time sharing systems requires min response time which is given by Round Robin.RR consist of Time Quantum which helps in executing process for given time and then context is switched.Hence the  processes need not wait for long to be executed resulting in less response time.

https://www.tutorialspoint.com/time-sharing-operating-system#:~:text=The%20main%20difference%20between%20Time-Sharing%20Systems%20and%20Multiprogrammed%20Batch%20Systems%20is%20that%20in%20case%20of%20Multiprogrammed%20batch%20systems%2C%20the%20objective%20is%20to%20maximize%20processor%20use%2C%20whereas%20in%20Time-Sharing%20Systems%2C%20the%20objective%20is%20to%20minimize%20response%20time.