The Gateway to Computer Science Excellence
+4 votes

     Measurements  of a certain  system  have shown that a process  runs, on the
     average,  for time T  before  blocking  for  Input/Output.  Process  switch
     requires time S which is overhead.  For round robin scheduling with quantum
     Q, give a formula for the cpu efficiency in each of the following cases:

     (a) Q=infinity  (b) Q>T  (c) S<Q<T  (d) Q=S  (e)  Q nearly 0
     cpu efficiency is useful cpu time/total cpu time, i.e.  sum of cpu
     useful time and cpu overhead in switching processes.

     For (a) and (b) a  process  runs  for T and a  switch  occurs  when it gets
     blocked.  Efficiency is T/(T+S)

     In (c), since Q<T, each run of T requires T/Q process  switches,  resulting
     in overhead of ST/Q and therefore, the efficiency is T/(T+(ST/Q))  which is

     For (d), take Q for S in (c) and we get Q/(Q+Q) which is 50%
     For (e), the efficiency goes to 0 as Q goes to 0

Can somebody please explain option c and hence option D with example ,Thanks and sorry if it is naive question :)

in Operating System by Active (1.2k points) | 2.2k views

1 Answer

+2 votes
Best answer

There is one more solution to this question:

 Assume T is the total processing time and S is the overhead for each 
     content switch. Then the CPU efficiency can be represented by the 
     equation: T / ([T/Q] - 1) * S + T 
               where [T/Q] = k is an integer and k >= T/Q and k < T/Q + 1.

     (a) Q = infinity. It becomes T / T = 1

     (b) Q > T. It becomes T / T = 1

     (c) S < Q < T. The efficieny is T / ([T/Q] - 1) * S + T. 

     (d) Q = S. 

         If T > Q,
         T / (T/Q * S - S) + T = T / (T - S) + T = T / 2T - S = T / 2T - Q.
         If T < Q, it becomes T / T = 1.

     (e) Q is nearly zero. It becomes T / infinity = 0.

Let us solve option c first:


here the closer the value of Q is from T then more the efficiency 

In option d if the value of T < S then the efficiency is 100% 

by Boss (36.5k points)
selected by
In your solution T is the processing time for each process and the second solution T is the total processing time
what i want : In efficiency formula how you write T/Q ,I want logic behind it or how you got entire formula,Please explain that.Thanks for reply.

Execution Time = T

[T/Q] * S since we need the total switching times, but now we are counting switch after the last process has finished(an extra count) so we subtract 1. 

In my example when i put Q = 2 we are switching 3 times and when we put Q = 3 we can do the execution in just 1 switch between each process P1 and P2 so that's that.

Efficiency = Execution Time/ Execution time + Switching time 

Efficieny = T / T + ([T/Q] - 1) * S  
what i understood is Q is less than T, so before process go for I/O i.e before T ,it is switching due to time quantum Q and now T=6 and Q=2 S=2 ,then there will be 3 switch and each switch require 2 unit as follows

S*(T/Q)=(6/2) *2 =6

efficiency =6/(6+6)  or from your formula 6/(6+4).

Thanks :)
Yeah but if T itself depends on the execution time of individual processes. like if there are 2 process with execution time 3 units then there will be one switch ((6/3)-1) with Q = 3

So if T is 6 and Q=2 no matter what processes you have there can never be 3 switches.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,322 answers
105,144 users