A provably efficient algorithm for dynamic storage allocation

摘要

The design and analysis of algorithms for on-line dynamic storage allocation has been a fundamental problem area in computer science for many years. In this paper we study the stochastic behavior of dynamic allocation algorithms under the natural assumption that files enter and leave the system according to a Poisson process. In particular, we prove that for any dynamic allocation algorithm and any distribution of file sizes, the expected wasted space (or fragmentation) in the system at any time is Ω(√N √log log N), where N is the expected number of items (or used space) in the system. This result is known to be tight in the special case when all files have the same size. More importantly, we also construct a dynamic allocation algorithm which for any distribution of file sizes wastes only O(√N log34N) space with very high probability. This bound is also shown to be tight for a wide variety of file-size distributions, including for example the uniform and normal distributions. The results are significant because they show that the cumulative wasted space in the holes formed by the continual arrival and departure of items is a vanishingly small portion of the used space, at least on the average. This fact is in striking contrast with Knuth's well-known 50% rule which states that the number of these holes is linear in the used space. Moreover, the proof techniques establish a surprising connection between stochastic processes, such as dynamic allocation, and static problems such as bin-packing and planar matching. We suspect that the techniques will also prove useful in analyzing other stochastic processes which might otherwise prove intractable. Lastly, we present experimental data in support of the theoretical proofs, and as a basis for postulating several conjectures.