The name "garbage collection" implies that objects no longer needed by
the program are "garbage" and can be thrown away. A more accurate and
up-to-date metaphor might be "memory recycling." When an object is no
longer referenced by the program, the heap space it occupies can be
recycled so that the space is made available for subsequent new
objects. The garbage collector must somehow determine which objects
are no longer referenced by the program and make available the heap
space occupied by such unreferenced objects. In the process of freeing
unreferenced objects, the garbage collector must run any finalizers of
objects being freed.
In addition to freeing unreferenced objects, a garbage collector may
also combat heap fragmentation. Heap fragmentation occurs through the
course of normal program execution. New objects are allocated, and
unreferenced objects are freed such that free portions of heap memory
are left in between portions occupied by live objects. Requests to
allocate new objects may have to be filled by extending the size of
the heap even though there is enough total unused space in the
existing heap. This will happen if there is not enough contiguous free
heap space available into which the new object will fit. On a virtual
memory system, the extra paging (or swapping) required to service an
ever growing heap can degrade the performance of the executing
program. On an embedded system with low memory, fragmentation could
cause the virtual machine to "run out of memory" unnecessarily.
Garbage collection relieves you from the burden of freeing allocated
memory. Knowing when to explicitly free allocated memory can be very
tricky. Giving this job to the Java virtual machine has several
advantages. First, it can make you more productive. When programming
in non-garbage-collected languages you can spend many late hours (or
days or weeks) chasing down an elusive memory problem. When
programming in Java you can use that time more advantageously by
getting ahead of schedule or simply going home to have a life.
A second advantage of garbage collection is that it helps ensure
program integrity. Garbage collection is an important part of Java's
security strategy. Java programmers are unable to accidentally (or
purposely) crash the Java virtual machine by incorrectly freeing memory.
A potential disadvantage of a garbage-collected heap is that it adds
an overhead that can affect program performance. The Java virtual
machine has to keep track of which objects are being referenced by the
executing program, and finalize and free unreferenced objects on the
fly. This activity will likely require more CPU time than would have
been required if the program explicitly freed unnecessary memory. In
addition, programmers in a garbage-collected environment have less
control over the scheduling of CPU time devoted to freeing objects
that are no longer needed.
****** GC Algorithms
The Java virtual machine can be implemented such that the garbage
collector knows the difference between a genuine object reference and
a primitive type (for example, an int) that appears to be a valid
object reference. (One example is an int that, if it were interpreted
as a native pointer, would point to an object on the heap.) Some
garbage collectors, however, may choose not to distinguish between
genuine object references and look-alikes. Such garbage collectors are
called conservative because they may not always free every
unreferenced object. Sometimes a garbage object will be wrongly
considered to be live by a conservative collector, because an object
reference look-alike referred to it. Conservative collectors trade off
an increase in garbage collection speed for occasionally not freeing
some actual garbage.

1 Reference counting
Reference counting was an early garbage collection strategy. In this
approach, a reference count is maintained for each object on the heap.
When an object is first created and a reference to it is assigned to a
variable, the object's reference count is set to one. When any other
variable is assigned a reference to that object, the object's count is
incremented. When a reference to an object goes out of scope or is
assigned a new value, the object's count is decremented. Any object
with a reference count of zero can be garbage collected. When an
object is garbage collected, any objects that it refers to have their
reference counts decremented. In this way the garbage collection of
one object may lead to the subsequent garbage collection of other
objects. An advantage of this approach is that a reference counting
collector can run in small chunks of time closely interwoven with the
execution of the program. This characteristic makes it particularly
suitable for real-time environments where the program can't be
interrupted for very long. A disadvantage is that reference counting
does not detect cycles: two or more objects that refer to one another.
An example of a cycle is a parent object that has a reference to a
child object that has a reference back to the parent. These objects
will never have a reference count of zero even though they may be
unreachable by the roots of the executing program. Another
disadvantage of reference counting is the overhead of incrementing and
decrementing the reference count each time. Because of the
disadvantages inherent in the reference counting approach, this
technique is currently out of favor. It is more likely that the Java
virtual machines you encounter in the real world will use a tracing
algorithm in their garbage-collected heaps.

2 Tracing
Tracing garbage collectors trace out the graph of object references
starting with the root nodes. Objects that are encountered during the
trace are marked in some way. Marking is generally done by either
setting flags in the objects themselves or by setting flags in a
separate bitmap. After the trace is complete, unmarked objects are
known to be unreachable and can be garbage collected.
The basic tracing algorithm is called "mark and sweep." This name
refers to the two phases of the garbage collection process. In the
mark phase, the garbage collector traverses the tree of references and
marks each object it encounters. In the sweep phase, unmarked objects
are freed, and the resulting memory is made available to the executing
program. In the Java virtual machine, the sweep phase must include
finalization of objects.

3 Compacting
Garbage collectors of Java virtual machines will likely have a
strategy to combat heap fragmentation. Two strategies commonly used by
mark and sweep collectors are compacting and copying. Both of these
approaches move objects on the fly to reduce heap fragmentation.
Compacting collectors slide live objects over free memory space toward
one end of the heap. In the process the other end of the heap becomes
one large contiguous free area. All references to the moved objects
are updated to refer to the new location.
Updating references to moved objects is sometimes made simpler by
adding a level of indirection to object references. Instead of
referring directly to objects on the heap, object references refer to
a table of object handles. The object handles refer to the actual
objects on the heap. When an object is moved, only the object handle
must be updated with the new location. All references to the object in
the executing program will still refer to the updated handle, which
did not move. While this approach simplifies the job of heap
defragmentation, it adds a performance overhead to every object access.