Garbage Collection and LINDA

Tuple spaces come in and out of scope; they are created, and thrown away. Once all references to a tuple space are discarded, its contents become unreachable, and may be removed so that the memory can be reclaimed. However, we get an interesting side-effect if we consider processes to be active tuples; that is, a process is an expression which evaluates to a tuple which is placed in a tuple space. Now, garbage collection not only affects passive tuples, but active tuples (processes).

The theory goes something like this: We can build a graph, where nodes are tuple spaces, and arcs show that one tuple space is reachable by another. A tuple space t is reachable from another, s if

t appears in a tuple in s
t is used by an active tuple in s

Tuple space usage within an active tuple is dynamically changing, but can often be determined by looking at scoping information, or by a local processes garbage collection routine.

By building this graph, we can determine which tuple spaces can be garbage collected, and which are still required. To do this, though, we require a distinguished tuple space, which we call GTS, which contains passive tuples containing persistant tuple spaces, and active tuples which constitute main processes.

Some research is still required to determine how garbage collection is to be implemented. It is clear that the information required can be kept and maintained on-the-fly. But it is still not clear when to perform garbage collection. It very much depends upon how the tuple space is implemented; a single tuple space server is a simple case, as during the maintanence of the required information, we can easily see when to remove tuple spaces. However, if the tuple space is distributed, as in the York Linda Kernel, determining when to perform garbage collection is the main problem.

The only other reference to the garbage collection of tuple spaces appears in Gelernter's paper, Multiple Tuple Spaces in Linda, where a hierarchy of multiple tuple spaces is proposed. The approach here is to be able to remove and freeze active tuple spaces - discarding a frozen tuple space removes it forever. However, this is not a proper solution, since doing so can leave primitives blocked forever on a non-existent tuple space. Our approach avoids this by only remove a tuple space when it is certain that it is no longer required.

An interesting application of garbage collection appears to be relaxation style algorithms. One Linda solution to such problems has a novel termination condition, where a set of worker processes deadlock at the point where a solution is reached. A broker process can monitor this happening within a local tuple space. Once the condition is reached, the local tuple space can be discarded, triggering garbage collection and the removal of the deadlocked processes.