By John E. Shore
Communications of the ACM,
August 1975,
Vol. 18 No. 8, Pages 433-440
10.1145/360933.360949
Comments
Published comparisons of the external fragmentation produced by first-fit and best-fit memory allocation have not been consistent. Through simulation, a series of experiments were performed in order to obtain better data on the relative performance of first-fit and best-fit and a better understanding of the reasons underlying observed differences. The time-memory-product efficiencies of first-fit and best-fit were generally within 1 to 3 percent of each other. Except for small populations, the size of the request population had little effect on allocation efficiency. For exponential and hyperexponential distributions of requests, first-fit outperformed best-fit; but for normal and uniform distributions, and for exponential distributions distorted in various ways, best-fit out-performed first-fit. It is hypothesized that when first-fit outperforms best-fit, it does so because first-fit, by preferentially allocating toward one end of memory, encourages large blocks to grow at the other end. Sufficient contiguous space is thereby more likely to be available for relatively large requests. Results of simulation experiments supported this hypothesis and showed that the relative performance of first-fit and best-fit depends on the frequency of requests that are large compared to the average request. When the coefficient of variation of the request distribution is greater than or approximately equal to unity, first-fit outperformed best-fit.
The full text of this article is premium content
No entries found
Log in to Read the Full Article
Need Access?
Please select one of the options below for access to premium content and features.
Create a Web Account
If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.
Join the ACM
Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
Subscribe to Communications of the ACM Magazine
Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.
Purchase the Article
Non-members can purchase this article or a copy of the magazine in which it appears.
