Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T07:14:36.309Z Has data issue: false hasContentIssue false
  • English
  • Français

On a storage allocation model with finite capacity

Published online by Cambridge University Press:  17 February 2016

EUNJU SOHN  and
CHARLES KNESSL
EUNJU SOHN
Affiliation:
Department of Science and Mathematics, Columbia College Chicago, 600 South Michigan Avenue, Chicago, IL 60605-1996, USA email: [email protected]
CHARLES KNESSL
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607-7045, USA email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a storage allocation model with a finite number of storage spaces. There are m primary spaces that are ranked {1,2,. . .,m} and R secondary spaces ranked {m + 1, m + 2,. . .,m + R}. Items arrive according to a Poisson process, occupy a space for a random exponentially distributed time, and an arriving item takes the lowest ranked available space. Letting N1 and N2 denote the numbers of occupied primary and secondary spaces, we study the joint distribution Prob[N1 = k, N2 = r] in the steady state. The joint process (N1, N2) behaves as a random walk in a lattice rectangle. We shall obtain explicit expressions for the distribution of (N1, N2), as well as the marginal distribution of N2. We also give some numerical studies to illustrate the qualitative behaviors of the distribution(s). The main contribution is to study the effects of a finite secondary capacity R, whereas previous studies had R = ∞.

Keywords

dynamic storage allocationfinite capacityPoisson processrandom walksteady-state joint distributionwasted spaceErlang loss modelmaximum occupied space
Type
Papers
Information
European Journal of Applied Mathematics , Volume 27 , Issue 5 , October 2016 , pp. 738 - 755
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aldous, D. (1986) Some interesting processes arising as heavy traffic limits in an M/M/∞ storage process. Stoch. Process. Appl. 22, 291–313.Google Scholar
[2] Coffman, E. G. Jr., (1983) An introduction to combinatorial models of dynamic storage allocation. SIAM Rev. 25, 311–325.Google Scholar
[3] Coffman, E. G. Jr., Kadota, T. T. & Shepp, L. A. (1986) A stochastic model of fragmentation in dynamic storage allocations. SIAM J. Comput. 14, 416–425.Google Scholar
[4] Knessl, C. (2000) Asymptotic expansions for a stochastic model of queue storage. Ann. Appl. Probab. 10, 592–615.Google Scholar
[5] Knessl, C. (2003) Geometrical optics and models of computer memory fragmentation. Stud. Appl. Math. 111, 185–238.CrossRefGoogle Scholar
[6] Knessl, C. (2004) Some asymptotic results for the M/M/∞ queue with ranked servers. Queueing Syst. 47, 201–250.Google Scholar
[7] Knuth, D. E. (1997) Fundamental Algorithms, 3rd ed., vol. 1, Addison-Wesley, Reading, MA.Google Scholar
[8] Kosten, L. (1937) Uber Sperrungswahrscheinlichkeiten bei Staffelschltungen. Electra Nachr.-Tech. 14, 5–12.Google Scholar
[9] Newell, G. F. (1984) The M/M/∞ Service System with Ranked Servers in Heavy Traffic, Springer, New York.CrossRefGoogle Scholar
[10] Preater, J. (1997) A perpetuity and the M/M/∞ ranked server system. J. Appl. Probab. 34, 508–513.Google Scholar
[11] Sohn, E. & Knessl, C. (2008) The distribution of wasted spaces in the M/M/∞ queue with ranked servers. Adv. Appl. Probab. 40, 835–855.Google Scholar
[12] Sohn, E. & Knessl, C. (2008) A simple direct solution to a storage allocation model. Appl. Math. Lett. 21, 172–175.Google Scholar
[13] Standish, T. A. (1980) Data Structure Techniques, Addison-Wesley, Reading, MA.Google Scholar