I’ve been working on a simple object virtual machine on and off for the past few months. There are details which continue to confuse me, parts of the wikipedia article which are unclear (but are clearly described elsewhere).
This GC is a four-state process in which memory
allocations and de-allocations, ALLOC and FREE
operations respectively, modify the different sets
in between ticks.
I am not 100% sure on the design and implementation but a code-version of this should be coming soon.
GC_TICK
STATE=A
BLACKⁿ = (BLACKⁿ⁻¹ ∪ ROOT) \ (GREYⁿ⁻¹)
WHITEⁿ = U
GREYⁿ = ∅
STATE = B
STATE=B
GREYⁿ = GREYⁿ ∪ { CHILDREN_OF(x) : x∈WHITEⁿ }
WHITEⁿ = ∅
STATE = C
STATE=C
BLACKⁿ = BLACKⁿ ∪ (ROOT ∩ GREYⁿ)
WHITEⁿ = (BLACKⁿ ∪ GREYⁿ)'
STATE = D
STATE=D
GREYⁿ = GREYⁿ ∪ { PARENT_OF(x) : x∈WHITEⁿ }
TO_DELETEⁿ = WHITEⁿ \ (BLACKⁿ ∪ GREYⁿ)
BLACKⁿ = ∅
WHITEⁿ = ∅
STATE = A
ALLOC
ALL = ALL ∪ {NEW_ID}
BLACKⁿ = BLACKⁿ ∪ {NEW_ID}
GC_TICK
FREE
ROOT = ROOT \ {ID}
BLACKⁿ = BLACKⁿ \ {ID}
GREYⁿ = (GREYⁿ \ {ID}) ∪ REFS({ID})
WHITEⁿ = WHITEⁿ ∪ {ID}
GC_TICK