06/01/1990 09:00 AM
Computer Science
Dynamically allocated memory is a pervasive element of modern programming practices, but efficient dynamic memory reclamation is difficult. One class of algorithms that accomplish this is *copying garbage collection*. These algorithms require one pass to collect and compact objects in memory. It is the preferred form of garbage collection for systems with large virtual memories and large free-stores because the work of these algorithms is proportional to the amount of living data rather than the total data allocated. A copying collector organization appropriate for object-oriented imperative programming languages is presented. The system is both encapsulated and efficient. The efficiency of reclaiming a data structure depends solely on the size of the data structure, not the size of the program. It remains within the philosophy of its implementation language, C++, because code fragments that do not use the collector are not affected in any way. Any number of collectors can coexist concurrently in an application on disjoint data structures, making it an appropriate component of an object-oriented system. This system adds an important feature to C++ that increases productivity and makes the language more convenient. It makes dynamic memory management more efficient than manual reclamation for an important class of problems. It serves as a platform for research into reclamation techniques, particularly virtual memory issues, and it provides an appropriate organization for automatic dynamic memory reclamation in object-oriented imperative programming languages.