Garbage collector implementation

Perl does garbage collection by reference counting. The drawback is circular reference.

Java does this by mark-and-sweep.

C# does this by mark-and-compaction. Mark is similar to Java. Compaction is to copy used blocks together to avoid memory fragmentation.

A usual way of doing garbage collection is:
1) establish directed graph on objects.
2) do reachability test and mark reachable objects.
3) remove unreachable objects.

See here: A Simple Garbage Collector for C++.