. M/G/1-PS model Consider an M/ G/1 queue where the queue discipline is processor shar-

ing or time-sharing. This discipline implies that if there are already (n-1)

customers in the system, then the arriving customer as well as the other (waiting) customers in the system all start receiving service immediately at the average rate of p / n. There is no queue as such, and the rate at which units receive service changes each time a new arrival joins the system and each time a unit whose service requirement is fully met departs from the system.
We denote the system by M/G/1-PS.

(a) Show that the steady-state distribution of the number in the system N has the same geometric distribution as that in a standard M/ M/1 queue (with FIFO discipline)-that is, for p = >/p < 1, Pr(N=n}=(1-p)p", n =0,1,2 ,....

(b) If B is DF of the service-time distribution S with mean E(S) and W is the response time (waiting time in the system), then show that t E{W|S=t) =-
1 - p and that 00 E{W} = 1 E(S)
dB(1) = 1 - p 1 - p

(c) Show that the average conditional delay (see Note (1) below) experi-
enced by a customer is given by E[D|S=t]= E[W|S=t)-t pt = 1 - p and that PE(S)
E[D] = 1- p

(d) Show further that the output process is Poisson (Kleinrock, 1967).

Notes:
(1) A customer experiences a delay D as the full service time required by the customer cannot be had in a single installment because the discipline is processor-sharing (though there is no queue as such and an arrival starts receiving service immediately on arrival).
(2) For an M/G/1-PS queue, E[ W] depends on the distribution of the service time S only through its expected value E [S], whereas in case of a standard M/G/1-FIFO service, both the first and second moments of S enter in the expression for E [ W] (as is given by the Pollaczek-Khinchine formula).

(3) M/G/1-PS can be used as model of some time-shared computer systems.
(4) The distribution of D is not known in the general case. See the next problem for the special case G = M.