Technical blog

"We must view with profound respect the infinite capacity of the human mind to resist the introduction of useful knowledge." - Thomas R. Lounsbury

| github | goodreads | linkedin | twitter |

ansible 2 / books 1 / elasticsearch 2 / kernel 1 / learning 31 / linux 2 / mnemonics 1 / nginx 1 / paper 31 / personal 5 / research 30 / review 31 / rust 2 / scientific 31 / tools 2 /- Author: Edsger W. Dijkstra, Leslie Lamport, A.J. Martin, C.S. Scholten, E.F.M. Steffens
- Name: On-the-Fly Garbage Collection: An Exercise in Cooperation
- Link: http://research.microsoft.com/en-us/um/people/lamport/pubs/garbage.pdf

WC 259 / RT 2min

TweetIn our abstract form of the problem, we consider a directed graph of varying structure but with a fixed number of nodes, in which each node has at most two outgoing edges. More precisely, each node may have a left-hand outgoing edge and may have a right-hand outgoing edge, but either of them or both may be missing. In this graph a fixed set of nodes exists, called “the roots.” A node is called “reachable” if it is reachable from at least one root via a directed path along the edges.

The subgraph consists of all reachable nodes and their interconnections is called ‘the data structure’; nonreachable nodes that do not belong to the data structure are called garbage.

Data structure can modified: - Redirecting an outgoing edge of a reachable node towards an already reachable one. - Redirecting an outgoing edge of a reachable node towards a not yet reachable one without outgoing edges. - Adding–where an outgoing edge was missing an edge pointing from a reachable node towards an already reachable one. - Adding–where an outgoing edge was missing an edge pointing from a reachable node towards a not yet reachable one without outgoing edges. - Removing an outgoing edge of a reachable node

Mutator: redirect an outgoing edge of reachable node towards an already reachable one.

Collector: - marking phase: mark all reachable nodes - appending phase: append all unmarked nodes to the free list and remove the markings from all marked nodes

Free list - collection of nodes that have been identified as garbage.