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

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