GATE CSE 1998 | Question: 2.17, UGCNET-Dec2012-III: 43

Question

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?

• A. $q \leq \frac{t-ns}{n-1}$
• B. $q \geq \frac{t-ns}{n-1}$
• C. $q \leq \frac{t-ns}{n+1}$
• D. $q \geq \frac{t-ns}{n+1}$

Comments

@caffeinesoul thanks.

---

They should have mentioned that ready queue is already in work in an intermediate state else (n-1)q+(n-1)s would have come.

---

then why did they give overhead should be minimised , what did we solved regarding this in answer

Answer 1

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 p₂ to p_n, 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$

Comments

Most of the solutions are wrong. It should be q>= t-ns/n-1, as for the at least every t seconds condition, time quantum (q) should be greater than  t-ns/n-1

           q= t-ns/n-1 (EXACTLY AFTER T SECONDS)

           q <= t-ns/n-1 (ATLEAST ONCE WITHIN T SECONDS)

            q >= t-ns/n-1 (ATLEAST EVERY  T SECONDS).

---

Yes exactly. There is some ambiguity in the question itself.

---

@V_Sarath_Chandra @Aaditya_Kumar_Singh  Refer this solution it will help you with the exact doubt that you are having (i had the same doubt and just thought for a while and came up with this solution): https://gateoverflow.in/1690/gate-cse-1998-question-2-17-ugcnet-dec2012-iii-43?show=542881#a542881

Answer 2

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)

Comments

thanks for the simplified approach...

Answer 3

$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$

Answer 4

 

So ans is A.

Answer 5

BEST ANSWER

Comments

T-Means Maximum time allowed for a process to get CPU again

Answer 6

Answer is A 

Refer - https://gateoverflow.in/119288/scheduling