A Stochastic Model of Fragmentation in Dynamic Storage Allocation
| Autor: | Larry A. Shepp, Edward G. Coffman, T. T. Kadota |
|---|---|
| Rok vydání: | 1985 |
| Předmět: | |
| Zdroj: | SIAM Journal on Computing. 14:416-425 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/0214032 |
| Popis: | 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, \cdots \}$. 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 (S) - E|S|) /E|S| \to 0$ as the traffic intensity $\rho \to \infty $. Moreove... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|