The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
3.4k views

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

  1. Shortest Job First
  2. Round Robin
  3. First Come First Serve
  4. Elevator
asked in Operating System by Veteran (59.7k points)
edited by | 3.4k views
0

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.

3 Answers

+26 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 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.

answered by Veteran (71.4k points)
edited by
0
if the operating system is not shared then which algo will be proffered ? @bikram sir
0

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

what is the meaning of exponential averaging )

0
nice explanation @ bikaram sir
0

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. 0<=α<=1 
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
B. Round Robin.
answered by Boss (11.6k points)
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 !
+10

 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.
+14

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.

+7 votes

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.

answered by (363 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,297 questions
49,785 answers
164,372 comments
65,857 users