Browse Prior Art Database

Dynamic Storage Allocation Techniques Disclosure Number: IPCOM000147961D
Original Publication Date: 1976-Apr-30
Included in the Prior Art Database: 2007-Mar-28
Document File: 122 page(s) / 4M

Publishing Venue

Software Patent Institute

Related People

Weinstock, Charles Burr: AUTHOR [+2]


Charles Burr Weinstock

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 122





Dynamic Storage Allocation Techniques

Charles Burr Weinstock

April 1976

Dcpartmcnt of Computer Science Carnegie-Mollon Ur\iversity Pittsburgh, Pennsylvar~ia 15213

Sukmitted to Carnegie-Mcllon Ut\iversity in partial fulfillment of the requirements for the '

degree of Doctor of Philosophy,

This. research was supported in part by the Advanced Research Projects Agency of the Office of the Secretary of Defense (Contract F44620-73-C-0074) and monitored by the Air Farce Office of Sctent~fic Research, This document has been approved for public release and sale; its d~stributlon is unlimited.

[This page contains 1 picture or other non-text object]

Page 2 of 122


Mnny computer scientists occupy their time by studying the problent of run time allocation of conlputer resources. This thesis exanrines that portion of the problem that deals with thc dyr~amic allocation of primary memory. Wc *call this process Dynamic Storage Allocation. A model is developed which identifies six parameters of a dynamic storage allocation mathod including; 1) a search criterion, 2) a free list ordering, 3) a roundir~g rule, 4) a rule for handling the excess portion when a block must bc split, 5) a criterion for collapsing, and 6) a criterion' for compacting. The model is used to descr~bu those techniques in current use. The model is also used to describe a new method called Quick Fit which differs froni the more commonly used mcthods (i.e. Best Fit and First Fit) in that it is actually a hierarchy of methods. TO cornparc the methods an experimental methodology is developed, as well as measures of both storage ut~llzat~on
and speed. Results are presented which indicate that there is no all arocrnd "best" method. The fastest ntethods do not always utilize storage as efficiently as some of the slower niathods. The results indicate that the "best" method, in ternis of storage utilization, cl~anges with varying system characteristics. However, Bcst Fit generally does better than most of the others. In terms of speed of allocation, Quick Fit is always the best for the system characteristics that were studied. A means of choosing a mcthod for a balance of good storage utilization and speed is provided.

[This page contains 1 picture or other non-text object]

Page 3 of 122



This work could not. have been completed without the help of many others. I am

particularly grateful for the advice and guidance given by the members of my committee; Bill Wulf, Mary Shaw, Sam Fuller, and Paul Shaman. I am also grateful to Richard Johnsson and Philip Kal-lton for their help in debugging the simulator. ,

    To all cif these people, and to the many others that offered moral and technical encouragenrent I
say: "My hbther thanks you, my Father thanks you, my Sister thanks you, and I thank you."

[This page contains 1 picture or other non-te...