GATE Overflow | Operating Systems | Test 1 | Question: 21

Question

Consider $m$ processes sharing the CPU in a round-robin manner. Assume that each process switch takes $p$ seconds. For which value of quantum size $w$, the overhead resulting from process switch is minimized but at the same time each process is guaranteed to get it's turn of the CPU at least every $n$ seconds?

• A. $w \leq \frac{n- mp}{m-1}$
• B. $w \geq \frac{n- mp}{m-1}$
• C. $w \leq \frac{n- mp}{m+1}$
• D. $w \leq \frac{n- mp}{m+1}$

Answer 1

According to question,

(m-1)w + mp <= n

So, w <= (n-mp)/(m-1)

Answer 2

Answer is - A)  $w\leq \frac{n- mp}{m-1}$

Comments

@ arjun sir sorry for the silly doubt but i m doing mistake in atleast and atmost. case ..how can i picturize easily

---

me too .. did the same  "P .. I marked option B just because of misunderstanding of "at least". If it was within n sec or "at most" n sec then I would have marked option A.

@Arjun sir, What is the meaning of at least n sec. here ?? Sorry for the silly doubt :P

---

Context Sensitive Grammar

:P

each process is guaranteed to get it's turn of the CPU at least every n seconds?

This means waiting time is "at most" n seconds. De-Morgan's law used in English :)

Answer 3

here P1|P2|P3|......Pm processes are running each taking time quantum= w units and process switch is p seconds so we have to find when one process will get its time again so suppose there are 4 processes P1,P2,P3,P4

P1|P2|P3|P4|P1 to get when p1 will again get its chance let it n seconds

there are 4 switches happen and between first time execution and second time execution of P1 three processes spend quantum time

so in this case 4p+3w<=n

and now generalise it, it will be

mp+(m-1)w<=n

so $w<= \frac{n-mp}{m-1}$