Cheney's Algorithm

Cheney's Algorithm is a method of performing a copying garbage collection using semi-spaces, that is, it works by splitting heap memory into two parts and only using one at a time.
Essentially, at any given moment there is an active part of memory from which new objects are allocated. When conditions get such that a garbage collection is needed, the live objects of the active part of memory are copied to the other memory part, which is marked active, and then old active part is marked inactive and reclaimed in one big chunk.
Cheney's algorithm provides a method of doing this collection. The two parts of the heap are labeled the from-space and the to-space, which correspond to the old active part (called "from-space" because objects are copied from it during the collection) and the new active part (called the "to-space" because objects are copied to it during the collection). To begin the to-space is empty and the from-space contains both live and garbage objects. Cheney's algorithm will check each object reference on the stack (which by definition refer to live objects), and will take one of two actions:

Forward the referred object to to-space if it has not already been forwarded. This means allocating an identical object in to-space and copying the object data over. In addition, a forwarding pointer is left at the object's old location in from-space which will point to its new location in to-space.
Simply update the object reference if the referred object has already been forwarded. This is a simple matter of following the forwarding pointer.

Once all the stack object references have been scanned, the algorithm will scan any object references in the new to-space objects that were created. The algorithm will use the same two actions listed above on these references. Once all to-space object references have been scanned, the collection is complete and the entire from-space may be reclaimed.
The algorithm is illustrated by the applet below using a simplified model where only one type of object, called a cons cell, may be allocated. A cons cell is simply a structure with a left and right pointer that point either to null or to other cons cells.

The applet shows the state of memory before collection begins. The top row is the set of stack objects, called the root set. The second row is the from-space, which is the collection of heap objects -- some of which might be garbage. The bottom row is the to-space and begins empty, but will grow as live objects are copied from the from-space.
Press the button to step through the collection process. At each step another object reference, marked in yellow, will be scanned and updated. When the reference is updated, cells will be marked in green to indicate the old value of the yellow reference, and when cells are copied into the to-space. As the collection proceeds, references are marked in pink to indicate they have been scanned. Eventually, all root and to-space references will be pink and the collection will be complete.
The applet also allows the collection to be stepped through backwards in order to review earlier parts of the process. The text window at the bottom shows a description of each of the steps taken so far.