Before addressing actual algorithms for garbage collection, we need to talk about allocation and deallocation of objects. We will also need to know which specific objects on the heap to garbage collect, and we need to briefly discuss how they get there and how they are removed.
Allocation on a per-object basis normally, in the common case, never takes place directly on the heap. Rather, it is performed in thread local buffers or similar constructs that are promoted to the heap from time to time. However, in the end, allocation is still about finding appropriate space on the heap for the newly allocated objects or collections of objects.
In order to put allocated objects on the heap, the memory management system must keep track of which sections of the heap are free (that is, those which contain no live objects). Free heap space is usually managed by maintaining a free list—a linked list of the free memory chunks on the heap, prioritized...