Goal: reduce pause times

Do not stop the program to do garbage collection

Instead, perform steps of garbage collection as the program is running

Consider this situation:

• collector already processes reachable node x and its fields
• program modifies x.f=y
• collector now needs to know that y is also reachable

Three kinds of objects:

• white - not visited yet (entirely unmarked)
• greay - marked bu their children not examined
  • on the stack in mark-and-sweep
  • between scan and next in copying collector
• black - marked and their children also marked

General algorithm:

while (there are any grey objects) {
  select a grey record p
  for (each field f_i of p) {
    if (record p.f_i is white)
      color record p.f_i grey
  }
  color record p black
}

Key invariants:

1. a black object does not point to a white object
2. every grey object is in grey-set (the collector's data structure)

Example algorithm: Baker's algorithm

Starting collection:

• forward all roots
• swap to and from

Invariant: mutator only has pointers into to-space

When alloc called, allocated from end of to-space

• also scan a few records to make progress in collection

When mutator stores field, nothing special needed

• because of the invariant

When mutator loads, must forward the pointer

• to ensure invariant