Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-09T07:30:47.940Z Has data issue: false hasContentIssue false
  • English
  • Français

Storage allocation under processor sharing II: Further asymptotic results

Published online by Cambridge University Press:  30 November 2010

EUNJU SOHN  and
CHARLES KNESSL
EUNJU SOHN
Affiliation:
Department of Mathematics, Boyd Graduate Studies Research Center, University of Georgia, Athens, GA 30602, USA email: [email protected]
CHARLES KNESSL
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, 851 South Morgan (M/C 249), Chicago, IL 60607-7045, USA email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a processor-sharing storage allocation model, which has m primary holding spaces and infinitely many secondary ones, and a single processor servicing the stored items. All of the spaces are numbered and ordered. An arriving customer takes the lowest available space. Dynamic storage allocation and the fragmentation of computer memory are well-known applications of this model. We define the traffic intensity ρ to be λ/μ, where λ is the customers' arrival rate and μ is the service rate of the processor. We study the joint probability distribution of the numbers of occupied primary and secondary spaces. We study the problem in two asymptotic limits: (1) m → ∞ with a fixed ρ < 1, and (2) ρ ↑ 1, m → ∞ with m(1-ρ) = O(1). The asymptotics yield insight into how many secondary spaces tend to be needed, and into the sample paths leading to the occupation of the two types of spaces. We show that the asymptotics lead to accurate numerical approximations.

Type
Papers
Information
European Journal of Applied Mathematics , Volume 22 , Issue 1 , February 2011 , pp. 45 - 82
Copyright
Copyright © Cambridge University Press 2010

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.CrossRefGoogle Scholar
[2]Coffman, E. G. Jr. (1983) An introduction to combinatorial models of dynamic storage allocation. SIAM Rev. 25, 311–325.CrossRefGoogle Scholar
[3]Coffman, E. G. Jr., Flatto, L. & Leighton, F. T. (1990a) First fit allocation of queues: tight probabilistic bounds on wasted space. Stoch. Process. Appl. 36, 311–330.CrossRefGoogle Scholar
[4]Coffman, E. G. Jr., Flatto, L. & Leighton, F. T. (1990b) First-fit storage of linear lists: tight probabilistic bounds on wasted space. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 272–279.Google Scholar
[5]Coffman, E. G. Jr., Kadota, T. T. & Shepp, L. A. (1985a) A stochastic model of fragmentation in dynamic storage allocation. SIAM J. Comput. 14, 416–425.CrossRefGoogle Scholar
[6]Coffman, E. G. Jr., Kadota, T. T. & Shepp, L. A. (1985b) On the asymptotic optimality of first-fit storage allocation. IEEE Trans. Softw. Eng. SE-11, 235–239.CrossRefGoogle Scholar
[7]Coffman, E. G. Jr. & Leighton, F. T. (1989) A provably efficient algorithm for dynamic storage allocation. J. Comput. Syst. Sci. 8, 2–35.CrossRefGoogle Scholar
[8]Coffman, E. G. Jr. & Mitrani, I. (1988) Storage of the single-server queue, In: Queueing Theory and its Applications, Liber Amicorum for J. W. Cohen. In: Boxma, O. J. & Syski, R. (editors), CWI Monogr., 7th ed., North-Holland, Amsterdam, pp. 193–205.Google Scholar
[9]Courant, R. & Hilbert, D. (1989) Methods of Mathematical Physics, Vol. 2, Wiley-VCH, Wiley Classics Libray 20.Google Scholar
[10]Knessl, C. (2000) Asymptotic expansions for a stochastic model of queue storage. Ann. Appl. Probab. 10, 592–615.CrossRefGoogle Scholar
[11]Knessl, C. (2003) Geometrical optics and models of computer memory fragmentation. Stud. Appl. Math. 111, 185–238.CrossRefGoogle Scholar
[12]Knessl, C. (2004) Some asymptotic results for the M/M/∞ queue with ranked servers. Queueing Syst. 47, 201–250.CrossRefGoogle Scholar
[13]Kosten, L. (1937) Uber sperrungswahrscheinlichkeiten bei staffelschaltungen. Electra Nachr.-Tech. 14, 5–12.Google Scholar
[14]Knuth, D. E. (1997) Fundamental Algorithms, 3rd ed., Vol. 1, Addison-Wesley, Reading, MA.Google Scholar
[15]Newell, G. F. (1984) The M/M/∞ Service System with Ranked Servers in Heavy Traffic, Springer, New York.CrossRefGoogle Scholar
[16]Preater, J. (1997) A perpetuity and the M/M/∞ ranked server system. J. Appl. Probab. 34, 508–513.CrossRefGoogle Scholar
[17]Sohn, E. & Knessl, C. (2008) A simple direct solution to a storage allocation model. Appl. Math. Lett. 21, 172–175.CrossRefGoogle Scholar
[18]Sohn, E. & Knessl, C. (2008) The distribution of wasted spaces in the M/M/∞ queue with ranked servers. Adv. Appl. Probab. 40, 835–855.CrossRefGoogle Scholar
[19]Sohn, E. & Knessl, C. (2010) Storage allocation under processor sharing I: Exact solutions and asymptotics. Queueing Syst. 65, 1–18. http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.3693v1.pdf.CrossRefGoogle Scholar
[20]Standish, T. A. (1980) Data Structure Techniques, Addison-Wesley, Reading, MA.Google Scholar