Incremenatal Garbage Collectors

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 colletion:

  • 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