Garbage Collection

Basic Garbage Collection

Garbage Collection (GC) is the automatic reclamation of heap records that will never again be accessed by the program. GC is universally used for languages with closures and complex data structures that are implicitly heap-allocated. GC may be useful for any language that supports heap allocation, because it obviates the need for explicit deallocation, which is tedious, error-prone, and often non-modular.
GC technology is increasingly interesting for “conventional” language implementation, especially as users discover that free isn’t free. i.e., explicit memory management can be costly too. We view GC as part of an allocation service provided by the runtime environment to the user program, usually called the mutator( user program). When the mutator needs heap space, it calls an allocation routine, which in turn performs garbage collection activities if needed.

Many high-level programming languages remove the burden of manual memory management from the programmer by offering automatic garbage collection, which deallocates unreachable data. Garbage collection dates back to the initial implementation of Lisp in 1958. Other significant languages that offer garbage collection include Java, Perl, ML, Modula-3, Prolog, and Smalltalk.

Principles
The basic principles of garbage collection are:
1. Find data objects in a program that cannot be accessed in the future
2. Reclaim the resources used by those objects

Many computer languages require garbage collection, either as part of the language specification (e.g., Java, C#, and most scripting languages) or effectively for practical implementation (e.g., formal languages like lambda calculus); these are said to be garbage collected languages. Other languages were designed for use with manual memory management, but have garbage collected implementations available (e.g., C, C++). Some languages, like Ada, Modula-3, and C++/CLI allow both garbage collection and manual memory management to co-exist in the same application by using separate heaps for collected and manually managed objects.




Simple Heap Model
For simplicity, consider a heap containing “cons” cells.



Heap consists of two-word cells and each element of a cell is a pointer to another cell. There may also be pointers into the heap from the stack and global variables; these constitute the root set (root set is used as the starting point in determining all reachable data). At any given moment, the system’s live data are the heap cells that can be reached by some series of pointer traversals starting from a member of the root set. Garbage is the heap memory containing non-live cells.