Efficient implementation of the first-fit strategy for dynamic storage allocation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient implementation of the first-fit strategy for dynamic storage allocation

Full text

Pdf (1.05 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 11 , Issue 3 (July 1989) table of contents

Pages: 388 - 403

Year of Publication: 1989

ISSN:0164-0925

Author

R. P. Brent

Australian National Univ., Canberra, ACT, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 103, Citation Count: 8

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/65979.65981 What is a DOI?

ABSTRACT

We describe an algorithm that efficiently implements the first-fit strategy for dynamic storage allocation. The algorithm imposes a storage overhead of only one word per allocated block (plus a few percent of the total space used for dynamic storage), and the time required to allocate or free a block is O(log W), where W is the maximum number of words allocated dynamically. The algorithm is faster than many commonly used algorithms, especially when many small blocks are allocated, and has good worst-case behavior. It is relatively easy to implement and could be used internally by an operating system or to provide run-time support for high-level languages such as Pascal and Ada. A Pascal implementation is given in the Appendix.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Carter Bays, A comparison of next-fit, first-fit, and best-fit, Communications of the ACM, v.20 n.3, p.191-192, March 1977 [doi>10.1145/359436.359453]
	2	Gerald Bozman, The software lookaside buffler reduces search overhead with linked lists, Communications of the ACM, v.27 n.3, p.222-227, March 1984 [doi>10.1145/357994.358020]
	3	BOZMAN, G., BUCO, W., DALY, T. P., ANO TETZLAFF, W. H. Analysis of free-storage algo-{ rithms--revisited. IBM Syst. J. 23, 1 (1984), 44-64.
	4	BRENT, R.P. Efficient implementation of the first-fit strategy for dynamic storage allocation. Australian Comput. Sci. Commun. 3, 1 (May 1981), 25-34.
	5	BRENT, R.P. Efficient implementation of the first-fit strategy for dynamic storage allocation. Rep. CMA-R33-84, Centre for Mathematical Analysis, Australian National University, Aug. 1984.
	6	BRENT, R.P. Dynamic storage allocation on a computer with virtual memory. Rep. CMA-R37- 84, Centre for Mathematical Analysis, Australian National University, Sept. 1984.
	7	P. A. Fox , A. P. Hall , N. L. Schryer, The PORT Mathematical Subroutine Library, ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.104-126, June 1978 [doi>10.1145/355780.355783]
	8	GEROVAC, B.J. An implementation of new and dispose using boundary tags. Pascal News 19 (Sept. 1980), 49-59.
	9	HrXT, J.B. A storage management laboratory. Aust. Comput. Sci. Commun. 2, 1 (Jan. 1980), 185-193.
	10	Arie Kaufman, Tailored-List and Recombination-Delaying Buddy Systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.118-125, Jan. 1984 [doi>10.1145/357233.357239]
	11	Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, v.8 n.10, p.623-624, Oct. 1965 [doi>10.1145/365628.365655]
	12	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	13	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	14	James L. Peterson , Theodore A. Norman, Buddy systems, Communications of the ACM, v.20 n.6, p.421-431, June 1977 [doi>10.1145/359605.359626]
	15	ROBSON, J.M. Worst case fragmentation of first fit and best fit storage allocation strategies. Comput. J. 20, 3 (Aug. 1977), 242-244.
	16	John E. Shore, On the external storage fragmentation produced by first-fit and best-fit allocation strategies, Communications of the ACM, v.18 n.8, p.433-440, Aug. 1975 [doi>10.1145/360933.360949]
	17	John E. Shore, Anomalous behavior of the fifty-percent rule in dynamic memory allocation, Communications of the ACM, v.20 n.11, p.812-820, Nov. 1977 [doi>10.1145/359863.359880]
	18	C. J. Stephenson, New methods for dynamic storage allocation (Fast Fits), Proceedings of the ninth ACM symposium on Operating systems principles, p.30-32, October 10-13, 1983, Bretton Woods, New Hampshire, United States
	19	Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]

CITED BY 8

	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Reducing sweep time for a nearly empty heap, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-389, January 19-21, 2000, Boston, MA, USA
	Benjamin Zorn , Dirk Grunwald, Evaluating models of memory allocation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.1, p.107-131, Jan. 1994
	Michael G. Luby , Joseph (Seffi) Naor , Ariel Orda, Tight bounds for dynamic storage allocation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.724-732, January 23-25, 1994, Arlington, Virginia, United States
	Miguel Masmano , Ismael Ripoll , Alfons Crespo, A comparison of memory allocators for real-time applications, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	Lori Carter , Scott Rae, Bridging the gap between the undergraduate and graduate experience in computer systems studies, Proceedings of the 2003 workshop on Computer architecture education: Held in conjunction with the 30th International Symposium on Computer Architecture, June 08, 2003, San Diego, California
	Benjamin Zorn , Dirk Grunwald, Empirical measurements of six allocation-intensive C programs, ACM SIGPLAN Notices, v.27 n.12, p.71-80, Dec. 1992
	Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992
	M. Masmano , I. Ripoll , J. Real , A. Crespo , A. J. Wellings, Implementation of a constant-time dynamic storage allocator, Software—Practice & Experience, v.38 n.10, p.995-1026, August 2008

INDEX TERMS

Primary Classification:
D. Software
D.4 OPERATING SYSTEMS
D.4.2 Storage Management
Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Design, Languages, Performance

REVIEW

"Gerald David Chandler : Reviewer"

This paper describes the many types of dynamic memory allocation strategies and discusses the many possible implementation algorithms for each. Perhaps the most commonly used strategy is first-fit, in which a list is maintained of the more...

Collaborative Colleagues:

R. P. Brent: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player