[gclist] Distributed Garbage Collection Revisited 1

[Rick Hudson]

>From my reading of the algorithms they traverse the graph twice. Once to see
if any node in the graph is reachable and a confirming trace to determine if
the graph has changed since the first traversal.  During the first trace each
object in the graph notes when this node was visited. Between the time the
node is first visited and the time the confirming trace of the graph is done a
barrier is built around the object and any new references are noted.  When the
confirming trace is done the node indicates that it has leaked a reference and
therefore this chain can not collected. Some algorithms pass the first pass
information around with the traversal information. I am not sure how where
they keep the last time updated information.

Before the object can be collected one must somehow determine if the last read
of the node happened after the first trace. Determining that the object is
locally unreachable at the time of the confirming trace reaches it is not
enough since the reference could have been leaked and the path to the leakage
could have been removed before the confirming trace arrives.

- Rick Hudson


>>>>> "HCC" == H C C Rodrigues <hccdr@ukc.ac.uk> writes:

    HCC> Matthew,
    >> Will you be making a description of your algorithm available over the
    >> Web, or post it here?  Is this similar to Lang, et al.'s algorithm of
    >> ever growing groups?

    HCC> I am preparing a camera-ready version for the WDAG96, that I will
    HCC> send to you if you are intersted. I would like to get some comments
    HCC> from you.

    >> Since computation is not halted during DGC, it is inevitable that some
    >> garbage will not be collected, although one should certainly try to
    >> minimize this.  This is partly an implementation issue.  The local
    >> system can (should?) choose to perform a local GC, or briefly delay the
    >> algorithm until one can be performed, before continuing the distributed
    >> trace or replying.

    HCC> I agree that the system can do that, but the algorithm would be very
    HCC> dependent from the time a local collection is performed. May happen
    HCC> that the DGC returns several times to the same processor. In this
    HCC> case I agree that an implementation would be necessary to study
    HCC> theses cases.

    >> I assume by "confirming trace" you mean a local collection from the
    >> scions?  There are two ways to address this: 1) Use a different bit for
    >> marking nodes involved in a DGC.  2) Continue performing collections as
    >> before, which involves tracing from the scions.  This will remark all
    >> the necessary nodes.

    HCC> I didn't understand what do you mean with 1) and 2).  "confirming
    HCC> trace" is the token ("CHECK-SEQUENCE, ...) in Gustavo Algorithm, and
    HCC> what Giuliano means when he says:

    HCC> "The solution is to make a second pass, and to implement a "new
    HCC> scion" barrier. This is similar to the write barrier used by local
    HCC> collectors to determine that they must rescan an area of memory."

    >> I am not sure I understand.  The algorithm would only not terminate if
    >> an infinite number of new incoming references appear before the
    >> distributed trace terminates.  The new incoming reference can only come
    >> to a scion, since there cannot be a remote reference to any object
    >> without a scion.  The new incoming reference can only belong to either:

    HCC> I think it is not necessary an infinite number of new incoming
    HCC> references appear before the distributed trace terminates to not
    HCC> terminate the algorithm.  We can have a cycle of objects spawning two
    HCC> processes being reachable from a root either in one process or in the
    HCC> other. The DGC may never reach a root.

    >> 1) A remotely rooted object.  If there are no garbage processes, we can
    >> just use this as proof the object is alive.

    HCC> I think the problem I presented does not exist if you consider the
    HCC> objects being remotely accessed live. In this case I imagine that the
    HCC> back-search would terminate.  What would happen when a "grey" object
    HCC> is remoteley accessed?  Sorry If am thinking to much in an
    HCC> implementation level, but I think that it was what is more important
    HCC> now. There are lots of algorithms in DGC litterature, without being
    HCC> implemented.

    HCC> I would like to ask as well to the people working in implementations,
    HCC> which kind of applications/tests they are using?

    HCC> Thank you, Helena Rodrigues.