Jones R., Lins R.D. Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Wiley, 1996. — 406 p. — ISBN10: 0471941484, ISBN13: 978-0471941484.This book is about garbage collection: the automatic reclamation of heap-allocated storage after its last use by a program. Memory is and has always been a scarce 'and precious resource. In the early days of computing, before the advent of very 1arge scale integrated circuits, memory was expensive and even a time-sharing operating system like Unix, was expected to run in just one 64-kilobyte segment. Today, although SIMM memory modules are comparatively cheap to buy and easy to install, programs are increasingly profligate in their consumption of this resource. Microsoft Wfudows’95, an operating system for a single-user personal computer, needs more than twelve megabytes of RAM to operate optimally. Thus main memory alone may account for half the cost of a PC. As with all precious resources, memory needs to be carefully managed and recycled when no longer needed.The storage requirements of many computer programs are simple and predictable. Allocation and deallocation of memory for such programs can be handled by the programmer or the compiler, and indeed is best done so. Other programs have grown enormously in size and complexity. Languages like Lisp and Prolog typically manipulate large data structures with complex inter-dependencies. Functional and logic languages have complex patterns of execution. The result is that the useful lifetimes of many data structures can no longer be determined before execution, either by programmer or by compiler. Automatic storage reclamation is essential.One reflection of the growing importance of garbage collection is the level of debates on this subject within the computer science community. As well as individual papers in journals and conferences, there have been workshops on garbage collection at the 1990, 1991 and 1993 Object-Oriented Systems, Languages and Applications OOPSLA conferences, as well as international workshops exclusively devoted to the topic, in 1992, 1995 and 1998. Garbage collection is also a perennially popular subject for extended argument on Usenet news groups.Object-orientation is the strongest growing area of interest in analysis, design and programming today. The key to good software engineering is the control of complexity. One-of the ways that object-oriented design achieves this goal is the encapsulation of abstractions into objects that communicate through clearly defined interfaces. Programmer-controlled storage management inhibits this modularity. For this reason, most modern object-oriented languages, such as Smalltalk, Eiffel, Java and Dylan, are supported, by garbage collection. Today, even languages used in part for systems programming, such as Modula-3 and Oberon, provide garbage collection for these sound but pragmatic reasons. Garbage collecting libraries are also available for such uncooperative languages as C and e++.The Classical Algorithms.
Reference Counting.
Mark-Sweep Garbage Collection.
Mark-Compact Garbage Collection.
Copying Garbage Collection.
Generational Garbage Collection.
Incremental and Concurrent Garbage Collection.
Garbage Collection for C.
Garbage Collection for C++.
Cache-Conscious Garbage Collection.
Distributed Garbage Collection.