A simplified look at the automatic memory management technique known as garbage collection.
Hopefully complementary, but less 'code-y' than viterbiSearcher's writeup above. A software development writeup.
Geek factor: high.
What is it?
Garbage collection is a technique for automatic memory management used in most modern programming languages (such as Java and Microsoft's C#).
It was invented around 1958 for the programming language LISP. It differs from the manual memory management normally used in languages such as C and C++, in that programmers do not need to explicitly call a function (such as free()) to release allocated memory. Many of the techniques for automatic memory management were developed for the Smalltalk language.
The garbage collector is a service provided by the language (most commonly, by the virtual machine). The garbage collector's job is to identify areas of memory that are no longer in active use and make that space available for future allocation. Efficiently determining which areas of memory are
in use and reclaiming the remaining memory is done in many different ways, and is an ongoing area of study.
The garbage collector may also reduce fragmentation. During program execution, objects are allocated and discarded in no particular order. Over time, this leads to active objects being scattered throughout memory, breaking up the free
memory space. When the system needs to allocate a large object, there may not be enough free memory to do so, even if there is a lot of total free memory. Some garbage collectors pack the active objects together to make the maximum amount of contiguous free space.
A garbage collector must attempt to minimize its impact on the application. Common issues to be considered include:
- Overhead - The amount of processing or CPU time taken by the garbage collector;
- Pause time - The time (if any) that the application itself is stopped waiting for garbage collection;
- Memory use - The amount of memory used to track information for the garbage collector.
How does it work?
The exact strategy used depends on the language and the strategy implemented.
Within Java, there are three main types of memory:
- Global or static data - allocated at class load time (there being no global scope in Java), and invariant in size thereafter. Not managed by the garbage collector.
- Stack allocated data - allocated locally during execution when a declaration is encountered within the scope of a function / routine / method etc.
It is released when execution leaves the scope containing the declaration. Each thread will have a stack frame. These are not managed by the garbage collector.
- Heap data - all objects that are dynamically allocated during execution. This is the memory managed by the garbage collector.
Heap objects in Java are created by the new operator. They are never explicitly released. Instead, the garbage collector automatically frees objects when it has determined that they are no longer referenced by the application.
Garbage collection is guaranteed to keep all accessible objects, but there are no guarantees about when, or even if, inaccessible objects will be released.
There is no official Java garbage collection technique, and the language specification does not require memory management at all. Without it, however, memory will fill and things will grind to a halt.
What are some techniques?
The most common type of garbage collector is the Tracing collector, of which there are many subtypes. An alternative strategy is to use Reference counting. Both approaches have their own challenges.
Ideally, a garbage collector would remove from memory any object that would never be used again in the execution of the program. The remaining objects are called "live" objects. It is exceedingly difficult, if not impossible, for the collector to determine liveness. Tracing collectors therefore rely on a concept called reachability (q.v.). In short, reachability is determined by starting with local and static variables and tracing all objects referenced by those variables, and then by those objects, and so on, and so on.
The original tracing collectors used a mark and sweep algorithm, sometimes called a two-phase collector.
In this algorithm all objects contain (or are associated with) a 'reachable' flag.
When the collector starts, the application and all threads
(except the collector's) are suspended. The collector clears the reachable flag for all objects. It then executes the reachability test, setting the reachable flag for all
reachable objects. (Duh!) This is the first phase.
It then takes a second pass over memory, in address space
order, and adds any objects without the flag set to the 'free
list'. This is the second phase. In Java the finalizer
methods are run during the sweep phase of a mark and sweep
collector.
The simplest collectors then scavenge free memory by making
all contiguous free blocks into single blobs of free emory.
Some tracing collectors can also move the reachable objects and compact the heap. The simplest approach to this is to
copy reachable objects to one end of the heap, leaving the
free memory pooled at the other. An advance on this method
is the copy collector. It divides the heap into
two portions, only one of which is actively used at any
one time. When the active half of the heap fills, the garbage
collector runs, after (or as) reachable objects are
identified, they are copied to the other half of the heap.
Once all objects are copied, the formerly active half of the heap becomes inactive, and processing resumes with the 'new' half of the heap used for object allocation.
These types of collectors are sometimes called "stop-the-world" collectors. They are increasingly disparaged because their Pause time grows with application complexity and increasing heap size.
Java virtual machine implementors are working to
introduce incremental collectors. These work on small areas of memory, using an intermediary process called a mutator to handle memory allocation and access. The mutator seamlessly handles the relocation of objects as well as allocation.
This allows the collector to work without blocking the application.
One type of incremental collector know in common use is the
generational collector.
The idea behind this algorithm is that a large percentage of the objects allocated by an application are short-lived.
Relatively few objects remain reachable for a longer portion of the program's execution. Thus, memory is divided into an area for short-term objects (variously called the nursery or Eden), which is collected frequently, and an area for venerable objects, which is collected less often.
The collectors run faster, and scan consistently reachable objects less often.
Often the generational collector is implemented using a combination of the previous techniques: the new-object space is managed by a quick but conservative collector, and the old-object space by a slower but more robust collector such as mark and sweep.
As garbage collectors grow more complex, train collectors are beginning to appear, with many memory spaces for different generations of objects, tunable in size and using different collectors at each step. Trying to explain the object transitions without a complex diagram defeats my patience for this writeup!
For C/C++ programmers, a garbage collector for C and C++ can be found at: http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Sources
http://www.memorymanagement.org/
http://www.artima.com/insidejvm/ed2/ch09GarbageCollection01.html
Disclaimers
You may notive I forgot the reference count collectors. I don't know enough about them yet. Someday I hope to come back and add it, unless someone wants to tackle it below.
The only language I've used that has a garbage collector is Java. I talked as generically as I can, but I may miss things that apply only to other languages, such as Smalltalk, Prolog or LISP. Additions and clarifications welcome.
That's how E2 works after all....