First-fit allocation of queues: tight probabilistic bounds on wasted space

E. G. Coffman, Leopold Flatto and F. T. Leighton

Stochastic Processes and their Applications, 1990, vol. 36, issue 2, 311-330

Abstract: We analyze a dynamic queue-storage problem where the arrival and departure processes are those of the single-server Poisson (M/M/1) queue. The queue is stored in a linear array of cells numbered 1, 2, 3,..., with at most one item (customer) per cell. The storage policy is first-fit, i.e., an item is placed at the time of its arrival into the lowest numbered unoccupied cell, where it remains until it is served and departs. Let S(t) be the set of occupied cells at time t, and define the wasted space as W(t) = maxS(t) - S(t), i.e. W(t) is the number of interior unoccupied cells. We analyze wasted space under the first-in-first-out (FIFO) and processor-sharing (PS) service disciplines. The results are expressed in terms of the 'traffic intensity' measure n = limt-->[infinity]ES(t), i.e. the expected number in the system in statistical equilibrium. An asymptotic analysis of the steady state provides the following two tight bounds , . These results are to be compared with the corresponding result, , already known for the infinite server queue. In proving the new bounds, we also obtain estimates of the tails of the distributions of wasted space. Dynamic storage allocation in computers is an important application of the above results. The bounds show that, on average, wasted space is asymptotically a negligible fraction of the total space spanned by the queue. This in turn means that in heavy traffic time-consuming compaction (garbage collection) schemes can have very little effect on storage efficiency.

Keywords: queues; random; walk; Poisson; process; normal; distribution (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/0304-4149(90)90098-D
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:36:y:1990:i:2:p:311-330

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().