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

same doubt. “atleast every t seconds”

---

“each process is guaranteed to get its turn at the CPU at least every t seconds” means that for a interval of t seconds the current process should get its turn again at least once. It is allowed to get it more than once, but at least once is the minimum.

That is why we take the remaining time (q(n-1) + ns) to be less than or equal to t, so that there is possibility for the process to get its turn even twice, thrice, etc.

On the other hand if you think of at most here, then the condition would be turned opposite
t <= q(n-1) + ns, i.e, the process should only get its turn at most once in the interval of t seconds.

---

can anyone please explain to me why we are assuming that we already executed p1 ? and we need to calculate the time that p1 gets it’s execution again. if we didn’t assume it then equation becomes →  nq + ns <=t . but everyone is doing (n-1)q + ns <=t. I totally get the part why we are getting ns but why are we getting (n-1)q?

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

same doubt

---

same doubt. “atleast every t seconds”

---

how do we get   ns+(n-1)q <= t,

else it should be   ns+(n-1)q >=t,

as t can be less than or equal to  ns+(n-1)q  but not bigger than that as a process runtime may be smaller than time quantum q,

so ans should be option b

can someone clarify this doubt??

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

Answer is A 

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