On-the-Fly Garbage Collection¶
Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., & Steffens, E. F. M. (1978). On-the-Fly Garbage Collection: An Exercise in Cooperation. ACM, 21(11), 966-975.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Garbage Collection
- The two — and only two — failure modes the prime predicts appear here precisely: a mis-declared root set (forget to scan a register, and a live object is swept, producing a dangling pointer) and a closure computed over stale data (a concurrent mutation during the mark phase, requiring a write barrier to notify the collector of every pointer change).
This sourceConcurrent collection requires a write barrier to notify the collector of pointer mutations during the mark phase, preventing a live object hidden behind an already-scanned one.
Supported in partVerified against the work's full text
Dijkstra et al. show a mutator must shade the target of a new edge during marking (a write-barrier-like step); they do not enumerate a mis-declared root set or dangling-pointer failure modes.
“Additional action is now required from the mutator when it is about to introduce an edge from a black node to a white one”
- The two — and only two — failure modes the prime predicts appear here precisely: a mis-declared root set (forget to scan a register, and a live object is swept, producing a dangling pointer) and a closure computed over stale data (a concurrent mutation during the mark phase, requiring a write barrier to notify the collector of every pointer change).
Mechanisms¶
- Concurrent Collection Barrier
- The correctness rests on the tricolor marking invariant.
This sourceDijkstra and coauthors prove their concurrent collector using invariants over white, grey, and black marking states.
- The correctness rests on the tricolor marking invariant.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 2 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:9e656d5c3717 · see in the full table