PCCST303 · Module 2: Linked List and Memory Management
Garbage Collection and Compaction
Repeated allocation and deallocation, exactly what linked lists and stacks/queues built from them do constantly, leaves memory in an increasingly scattered state: freed blocks of different sizes end up sitting between blocks still in use. Two separate problems come from this, and two separate techniques solve them.
Garbage collection: reclaiming unreachable memory
Definition
Garbage is allocated memory that is no longer reachable from any active pointer in the program: it was allocated but never freed, and nothing can reach it anymore to free it manually. Garbage collection is the automatic process of finding and reclaiming this memory.
A block becomes garbage the moment the last pointer that referenced it is overwritten or goes out of scope, without free() having been called on it first. In a language with manual memory management, that memory is permanently lost for the rest of the program's run: a memory leak. Garbage collection exists to catch these blocks automatically instead of relying on the programmer to free everything correctly.
Mark-and-sweep
The most common garbage collection algorithm works in two passes:
MARK_AND_SWEEP()
1. Mark phase:
For each root pointer (global variables, active stack variables)
Mark the block it points to as REACHABLE
Recursively mark every block reachable from it
2. Sweep phase:
For each allocated block in memory
If block is not marked REACHABLE
free(block)
Else
Clear the mark for the next cycleMark phase. Starting from every root (a pointer a running program can currently access directly: global variables, local variables on the call stack), the collector follows every pointer it finds, marking each block it reaches. A block reachable only through a chain of pointers, root to node to another node, still gets marked, as long as some unbroken chain connects it back to a root.
Sweep phase. Every allocated block in memory is then checked: if it was never marked, nothing in the program can reach it anymore, so it is garbage, and its memory is reclaimed. Marked blocks survive, with their mark cleared so the next collection cycle starts fresh.
Key Idea
A block with zero incoming pointers is unambiguously garbage, but a block can also be garbage while still having pointers to it, if none of those pointers are themselves reachable from a root. Mark-and-sweep handles this correctly because it only marks blocks reachable by walking from a root: a block that only points to another unreachable block never gets marked either.
n is the total number of allocated blocks: every reachable block is visited once during marking, and every allocated block is checked once during sweeping.
Compaction: merging scattered free space
Definition
Compaction is the process of relocating all currently allocated blocks to one end of memory, so that every free block ends up contiguous at the other end, merged into one large usable chunk instead of many small scattered ones.
Garbage collection (or ordinary free() calls) reclaims memory, but it doesn't reorganize it: freed blocks are just marked available where they already sit. Over time, this produces external fragmentation: enough total free memory exists to satisfy a request, but no single free block is large enough, because the free space is broken into scattered pieces separated by blocks still in use.
Before compaction, memory holds three allocated blocks with a free region after each of the first two:
Two free regions exist, sizes 20 and 10, totaling 30, but neither alone can satisfy a request for, say, 25, even though 30 is available overall.
Compaction algorithm
COMPACT(memory)
1. NEW_ADDR = start of memory
2. For each allocated block, in address order
Move block to NEW_ADDR
Update every pointer that referenced the block's old address
NEW_ADDR = NEW_ADDR + block size
3. Mark everything from NEW_ADDR to end of memory as one free blockSliding blocks A, B, and C down to eliminate the gaps between them:
The two separate 20 and 10 free regions have merged into a single free region of 30, now able to satisfy a request that neither fragment could have handled alone.
Key Idea
Step 2's pointer update is the expensive and delicate part: every reference anywhere in the program to a moved block's old address has to be found and rewritten to the new address, otherwise those pointers would dangle. This is why compaction is a comparatively costly operation, done periodically rather than after every single deallocation.
Garbage collection vs. compaction
Key Idea
Garbage collection answers "is this memory still needed?", reclaiming blocks nothing can reach anymore. Compaction answers a different question, "where should the memory that IS still needed sit?", rearranging still-live blocks so freed space isn't left scattered. The two are often run together: collect first to free what's unreachable, then compact to merge the resulting free regions into one usable block.
Quick recall
- Garbage is allocated memory no longer reachable from any root pointer; garbage collection reclaims it automatically.
- Mark-and-sweep marks every block reachable from a root, then frees every unmarked (unreachable) allocated block; both phases are O(n) in the number of blocks.
- A block can be garbage even while other unreachable blocks still point to it, since mark-and-sweep only counts reachability from a root, not incoming pointer count.
- Compaction slides all live blocks together, merging previously separate free regions into one larger contiguous free block.
- Compaction's real cost is updating every pointer to a block's new address after it moves, not the move itself.
That covers every topic in Module 2. For a focused list of the questions most likely to appear from this module, see Most Expected Questions.