Page 215 - A First Course In Stochastic Models

208 MARKOV CHAINS AND QUEUES

throughputs of the given L i -policy have the respective values 15.236 (±0.004),
15.244 (±0.004) and 15.231 (±0.005), where the numbers in parentheses indicate
the 95% confidence intervals.

5.4.2 The M/G/1 Queue with Processor Sharing
Another queueing system in which the limiting distribution of the number of cus-
tomers in the system is insensitive to the service-time distribution is the M/G/1
queue with the processor-sharing service discipline. Under this service discipline a
customer never has to wait in queue and the processing rate of the server is equally
divided among all customers present. The M/G/1 processor-sharing system can be
used to approximate time-shared computer systems among others. To formulate the
model, assume that customers arrive according to a Poisson process with rate λ and
that the service requirements of the customers are independent random variables
which are distributed according to the random variable S. It is assumed that S has
a general probability distribution. A generalized processor-sharing rule is used: if
i customers are present, each of the i customers is provided with service at a rate
of f (i) per time unit. That is, the attained service time of each of the i customers
grows by an amount f (i) x in a time x with x small. Here f (i) is a given
positive function. Let ρ = λE(S) denote the offered load and let
  −1
 j

φ(j) = f (k) , j = 0, 1, . . .
 
k=1
∞ k
with φ(0) = 1 by convention. Assuming that k=0 ρ φ(k)/k! is finite, it holds
that the limiting distribution {p j , j = 0, 1, . . . } of the number of customers present
is insensitive to the form of the service-requirement distribution and is given by

j
(ρ /j!)φ(j)
, j = 0, 1, . . . .
∞ (ρ /k!)φ(k)
p j =
k
k=0
A proof of this result can be found in Cohen (1979). Denoting by E(W | s) the
expected amount of time spent in the system by a customer who arrives when the
system has reached statistical equilibrium and whose required service time is s, it
was also shown in Cohen (1979) that
∞
k
s (ρ /k!)φ(k + 1)
k=0
E(W | s) = , s > 0,
∞
k
(ρ /k!)φ(k)
k=0
This remarkable result shows that the processor-sharing rule discriminates between
customers in a fair way. A customer requiring a service time twice as long as some
other will spend on average twice as long in the system. The standard M/G/1