A Stochastic Model of Fragmentation in Dynamic Storage Allocation (Q3742707)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3978370
Language Label Description Also known as
default for all languages
No label defined
    English
    A Stochastic Model of Fragmentation in Dynamic Storage Allocation
    scientific article; zbMATH DE number 3978370

      Statements

      A Stochastic Model of Fragmentation in Dynamic Storage Allocation (English)
      0 references
      0 references
      0 references
      0 references
      1985
      0 references
      checkerboarding
      0 references
      M/M/\(\infty \) queue
      0 references
      memory allocation
      0 references
      Poisson stream
      0 references
      fragmentation
      0 references
      paged computer systems
      0 references
      containerization
      0 references
      interacting particles
      0 references
      We study a model of dynamic storage allocation in which requests for single units of memory arrive in a Poisson stream at rate \(\lambda\) and are accommodated by the first available location found in a linear scan of memory. Immediately after this first-fit assignment, an occupied location commences an exponential delay with rate parameter \(\mu\), after which the location again becomes available. The set of occupied locations (identified by their numbers) at time t forms a random subset \(S_ t\) of \(\{\) 1,2,...\(\}\). The extent of the fragmentation in \(S_ t\), i.e. the alternating holes and occupied regions of memory, is measured by \(\max (S_ t)-| S_ t|\). In equilibrium, the number of occupied locations, \(| S|\), is known to be Poisson distributed with mean \(\rho =\lambda /\mu\). We obtain an explicit formula for the stationary distribution of max(S), the last occupied location, and by independent arguments we show that (E max(X)-\(E| S|)/E| S| \to 0\) as the traffic intensity \(\rho\to \infty\). Moreover, we verify numerically that for any \(\rho\) the expected number of wasted locations in equilibrium is never more than 1/3 the expected number of occupied locations. Our model applies to studies of fragmentation in paged computer systems, and to containerization problems in industrial storage applications. Finally, our model can be regarded as a simple concrete model of interacting particles [\textit{F. Spitzer}, Adv. Math. 5, 246-290 (1970; Zbl 0312.60060)].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references