edited by
21,697 views
89 votes
89 votes

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 by

5 Answers

Best answer
109 votes
109 votes

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 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
27 votes
27 votes

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)

Answer:

Related questions

23 votes
23 votes
5 answers
1
47 votes
47 votes
5 answers
4