GATE1998-2.17, UGCNET-Dec2012-III: 43

9.2k 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}$

edited
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".
5
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?

7

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

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$

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 ???
42

#for easy understanding attached diagram.

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

1

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.

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 ??
16

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 ???
0

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

how is this same with -  each process is guaranteed to get its turn at the CPU atmost every t seconds

as the t >= (n-1)q + ns will implies the atmost time t.

0
why time quantum= q(n-1)?

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)

edited
1 vote
 $P1$ ///// $P2$ ///// $P3$ ///// $P4$ ///// $P1$ $s$ $q$ $s$ $q$ $s$ $q$ $s$

$t\geq n\times s+(n-1)\times q$

$\dfrac{t-ns}{n-1}\geq q$

$Ans:A$

As given in question total 'n' processes are there and all those 'n' processes sharing the CPU in Round Robin fashion.

Each process switch takes 's' seconds.

'n' processes -> p1, p2, p3, ..., pn

Quantum size is 'q' -> Which we need to find in a way that overhead resulting from process switching is minimized.

Overhead is Process Switching or Context Switching. Its called overhead as during switching CPU is not executing any process and is not doing any work which can help us improve efficiency.

Each process runs for 'q' time in CPU.

'n' process -> p1 | p2 | p3 | ... | pn | p1

As given that each process is guaranteed to get its turn at the CPU at least every 't' second.

After 't' seconds p1 will be given to CPU for execution. So, sum up all the time and it must be less than or equal to 't' because as we need to give process to CPU again after 't' seconds. if it's more than 't' then you cant guarantee to give process to CPU after 't'.

p1 to p1 it's having 'n' context or process switches.

from p2 to pn total 'n-1' processes and all executing for 'q' Quantum time. We need to count after pi executes so, 'n-1' processes.

(n-1)*q + n*s <= t

Related questions

1
4.6k views
In a computer system where the best-fit' algorithm is used for allocating jobs' to memory partitions', the following situation was encountered:$\begin{array}{|l|l|} \hline \textbf{Partitions size in$KB$} & \textbf{$4K \ 8K \ 20K \ 2K$} \\\hline \textbf{Job sizes in$KB$} & \text{$2K ... $} \\\hline \end{array}$When will the $20K$ job complete?
Four jobs are waiting to be run. Their expected run times are $6, 3, 5$ and $x.$ In what order should they be run to minimize the average response time? Write a concurrent program using $\text{par begin-par end}$ to represent the precedence graph shown below.
Consider a system having m resources of the same type. These resources are shared by $3$ processes $A$,$B$, and $C$ which have peak demands of $3$, $4$ and $6$ respectively. For what value of m deadlock will not occur? $7$ $9$ $10$ $13$ $15$