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

Consider $n$ processes sharing the CPU in a round-robin fashion. Assuming that each process switch takes $s$ seconds, what must be the quantum size $q$ such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every $t$ seconds?

  1. $q \leq \frac{t-ns}{n-1}$

  2. $q \geq \frac{t-ns}{n-1}$

  3. $q \leq \frac{t-ns}{n+1}$

  4. $q \geq \frac{t-ns}{n+1}$

asked in Operating System by Veteran (59.6k points)
recategorized by | 4.6k views
+1
Ans is A or B? I think answer should be Bombay because option A means "within t seconds" where as option B means "at least after t seconds".
+2
The answer is A only. t>= ns + (n-1)q

but, q<= t - ns/ (n-1).

Also check that the option is given in terms of time quantum q. Whereas you are talking in terms of time. You are right at your place.
+1
@vikranth It should be A only. Option A means 'atleast' every t seconds. Whilst option b implies within t seconds.
0
if you still have doubt take q=2 s=1 n=4

now t will come 10

the above data is for q=(t-ns)/(n-1)

now if in doubt take q>2 -> not satisfying i.e within t=10 process not getting turn

put t<2 getting turn
0

wht does this line mean ?

at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?

+4

set2018 

wht does this line mean ?

at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?

Let consider this scenario :   process p1 is running for q time quantum then it is preempted , when p1 is preempted then again after t time units p1 gets chance to run into cpu.

In this t time unit p1 is waiting in the ready queue . 

P1 .P2..............Pn-1.. P1

    | .. .. .... t ..............| 

0
correct answer is A

4 Answers

+41 votes
Best answer

Answer: (A)

Each process runs for q period and if there are n process: $p_{1}$, $p_{2}$,$p_{3}$,, ....., $p_{n}$,.
Then $p_1$'s turn comes again when it has completed time quanta for remaining process p2 to pn, i.e, it would take at most $(n-1)q$ time. 
So,, each process in round robin gets its turn after $(n-1)q$ time when we don't consider overheads but if we consider overheads then it would be $ns + (n-1)q$
So, we have $ns + (n-1)q \leq t$

answered by Boss (34k points)
edited by
+1
When we dont consider overhead each process gets its turn after at most  (n-1)q  time

And if we consider overhead each process gets its turn after atmost ns+(n-1)q..right or not??

If not then why????

How's t=> ns+(n-1)q ???
+28

#for easy understanding attached diagram.

+1
@Bikram Sir,

If the sum q(n-1) + ns = 4 and t is 5, what will happen in this case? So if sum is equal to 't', then the first process will come again for execution at 't'seconds. If it is less than the 't', that means p1 will come again for exection at atmost 't' seconds not atleast 't'seconds.

Please clarify this.
+1

AnilGoudar

If the sum q(n-1) + ns = 4 and t is 5

then  the first process will come again for execution at 't' seconds. so in this case first process come after minimum 4 seconds and maximum 5 seconds .

In question see it asked " overhead resulting from process switching is minimized" so that means after 4 seconds first process must come in this scenario. 

+1

@Bikram Sir,

 Sorry for the late response, 

I am unable to follow the statement "overhead resulting from process switching is minimized". 

Please explain if possible. I am not getting the logic, but when i gave some numbers to the variables n,t and s. I am getting the option as A, but from the statement it is still unclear.

please clarify this Sir.

+2

overhead resulting from process switching is minimized

this line tells 

q(n-1) + ns  ≤ t

where overhead is  (n-1)q + ns

now  we get q(n-1) + ns = 4 and t = 5

as it is minimum overhead,  then q(n-1) + ns = 4 only ..

 ns + (n-1)q = 5 also as t =5 but we choose value 4 just because of that above mention line .

+2
Thank You Sir .

Now i got it :)
0
How to diiferentiate between opt. A and opt. B ....means how to decide less than or equal to or greater than or equal to?
+1
we are getting the overhead as q(n-1) + ns so after this the process will again execute and we have given that every process is guaranteed to execute in every t second which means the overhead is equal to t  and also they said that the overhead contest switching is minimized so if we have the overhead value less than t then we can also switch the process you can also refer to the above example taken t=5 and overhead value as 4.
0
Sir what if question is like every process should get chance every 't' sec with minimum context switching overhead.

Equation will remain same right ??
+1

I had the same confusion b/w >=t and <=t. But this is the way i made myself understand that :

each process is guaranteed to get its turn at the CPU at least every t seconds

So each process must get it's turn within t secs i.e. if it gets turn after 1 sec then good..if 2 secs then also good..in t secs still okay.. but if in (t+1) secs then not at all okay.. 

So whatever be the time we calculated [(n-1)q+ns] that can be either 1 or 2 or anything less than equal to t.

So, (n-1)q+ns <=t

Hope it helps.. :)

0
It says each process will get it's turn in at least t sec

So shouldn't we do this

ns + nq <=t

Or ns + (n-1)q < t ???
+6 votes

ANS is A

Let us take a simple example of 4 processes P1 , P2 , P3 and P4 . Here n=4

Consider  P1 || P2 || P3 || P4 || P1 || P2 || ..... will be the round robin scheduling order.

Now acc to the question the context switch time is S , here context is shown by " || "

and time quantum is " Q "

and T is the time taken by a process to again get the CPU after scheduling once .

if we see our scheduling pattern P1 || P2 || P3 || P4 || P1 || P2 ||

P1 gets the CPU again after 4 ( = n) context switch and 3 ( =n-1) time quantum.

So 4S + 3Q <= T

In general, where n is the process count , this becomes

nS + (n-1) Q <= T

(n-1)Q <= T - nS

=> Q <= (T- nS ) / ( n-1)

answered by Active (1.7k points)
+3 votes
answered by Boss (11.4k points)
edited by
–2 votes
Ans A
answered by Active (1.1k points)
0
Can anyone explain t<= vs t>= . Iam confused.


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

41,078 questions
47,675 answers
147,462 comments
62,393 users