The Fluid Limit of a Heavily Loaded Processor Sharing Queue
H. C. Gromoll, A. L. Puha and R. J. Williams
Abstract
Consider a single server queue with renewal arrivals
and i.i.d. service times in which the server operates
under a processor sharing service discipline. To describe
the evolution of this system, we use a measure valued
process that keeps track of the residual service times of all
jobs in the system at any given time. From this measure valued
process, one can recover the traditional performance processes,
including queue length and workload. We propose and study a
critical fluid model (or formal law of large numbers approximation)
for a heavily loaded processor sharing queue. The fluid model state
descriptor is a measure valued function whose dynamics are governed
by a nonlinear integral equation. Under mild assumptions, we prove
existence and uniqueness of fluid model solutions. Furthermore, we
justify the critical fluid model as a first order approximation of
a heavily loaded processor sharing queue by showing that, when
appropriately rescaled, the measure valued processes corresponding
to a sequence of heavily loaded processor sharing queues
converge in distribution to a limit
that is almost surely a fluid model solution.
Appears in Annals of Applied Probability, Vol 12 (2002), 797-859.
For a copy of a preprint for personal scientific non-commercial use only,
click here.