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.

The Gateway to Computer Science Excellence

+31 votes

Best answer

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 O**S, 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 starvatio**n 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.

0

where we can predict the next burst time using exponential averaging )

what is the meaning of exponential averaging )

+1

The exponential averaging/aging is the dynamic method to predict the burst time , To predict the time of (n+1)th process , let it be (T{n+1}), we are going to take

**Τ{n+1} = α.t{n} + (1-α)Τ{n}**

where **t{n} = actual time of previous process
Τ{n} = predicted time of previous process**

where α is the smoothening factor and its value lies between [0,1] i.e.

Let's say you are having a process P5 then i am going to depend on two things, one is what happened to P4(actual time) and then what is the predicted time of P4.

+9 votes

0

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 !

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 !

+12

SJF is a **non-preemptive algorithm**

and RR is **preemptive algo** and thats why **most suitable for time shared OS**

0

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.

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.

+15

See,

We are discussing about **Time shared O**S, 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 starvatio**n 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,497 answers

195,490 comments

100,813 users