A simple algorithm is:
 * Go through memory unmarking (i.e. clearing a hidden flag) all objects.
 * Find the root objects (the bootstrap class loader, running threads,
etc).
 * Mark each root object.
 * For each object you have just marked, mark each object it refers to.
 * Repeat previous step with newly marked objects until there is none left.
 * Go through memory adding still unmarked objects to your free list.

That isn't a very fast algorithm, and can't run concurrently. Good
collectors will however be equivalent (some take a more conservative
approach). There is lots of research into faster and much more
complicated algorithms.

If you're interested, you could get a copy of Garbage Collection:
Algorithms for Automatic Dynamic Memory Management,
by Richard Jones and Rafael Lins, although that is over a decade old.

http://www.amazon.co.uk/dp/0471941484/

Tom Hawtin

e.g. Using the concept of reachability (vs. reference count).

IBM has interestingly detailed documentation of their implementation of the
JVM: http://www-128.ibm.com/developerworks/java/jdk/diagnosis/.

On Mar 29, 1:28 pm, gaddamsande...@gmail.com wrote:

There's a few good articles here:

http://www-128.ibm.com/developerworks/java/library/j-jtp10283/
Java theory and practice: A brief history of garbage collection

http://www.javaworld.com/javaworld/jw-03-2003/jw-0307-j2segc.html
J2SE 1.4.1 boosts garbage collection - Java World

http://java.sun.com/docs/hotspot/gc1.4.2/
Tuning Garbage Collection with the 1.4.2 Java[tm] Virtual Machine

There are various JVM switches (in Sun's JVM at least) that allow you
to modify the behaviour of the GC algorithms.

There are plenty of algorithms for this. Many of them are highly
non-trivial.

Basically a collector knows a root set of objects that are live, like
referenced from global variables or from current stack frames. Then it
follows the pointers in those objects to find the rest, but takes care
to not get stuck in any cycle.

Some simple collectors copy all live objects thus found to a new area,
so that the old area becomes all free. Other simple collectors keep a
map that tells them where there is free memory.

Yet another simple kind keeps a reference counter in every object and
updates it every time a reference becomes live or dies.

Non-trivial kinds may treat short-lived objects specially, for
example.