Learning garbage collection theory

I want to learn the theory behind garbage collection. How do i go about it?

I am also a dabbler interested in garbage collection (to the point that I wrote my own garbage collected VM called HLVM). I learned by reading as many research papers on garbage collection as I could get my hands on and by playing with the ideas myself, both raw in my virtual machine and also by writing memory-safe high-level simulations.

The obvious answer is - a compiler textbook... The question is, is it necessary to learn lexical analysis, parsing and other stuff that usually precedes garbage collection in a text?

The lexical analysis, parsing and other stuff is not relevant to garbage collection. You might get an outdated cursory overview of garbage collection from a compiler book but you need to read research papers to get an up-to-date view, e.g. with regard to multicore.

In short, what are the prerequisites to learning about Garbage collection theory?

You need to know about basic graph theory, pointers, stacks, threads and (if you're interested in multi-threading) low-level concurrency primitives such as locks.

Garbage collection is all about determining reachability. When a program can no longer obtain a reference to a value because that value has become unreachable then the GC can recycle the memory that value is occupying. Reachability is determined by traversing the heap starting from a set of "global roots" (global variables and pointers on the thread's stacks and in the core's registers)

GC design has many facets but you might begin with the four main garbage collection algorithms:

• Mark-and-sweep (McCarthy, 1960)
• Mark-and-compact (Haddon and Waite, 1967)
• Stop-and-copy (Cheney, 1970)
• Mark-region (McKinley et al., 20