[gclist] Hughes' algorithm

[Marc Shapiro]

 || From: wilson@cs.utexas.edu (Paul R. Wilson)
 || Date: Fri, 22 Mar 1996 09:37:41 -0600
 || 
 || Suppose the list has 10 elements, and during the 5th GC, you end up with
 || the list being marked this way:

Allow me to name the processes:
        A    B    C    D    E    F    G    H    I    J

 ||     5 -> 5 -> 5 -> 5 -> 5 -> 0 -> 0 -> 0 -> 0 -> 0
 || 
 || That is, any marks for 2, 3, and 4 that started down the list got clobbered
 || by 5's.

So, processes A, B, ..., E think that all marks up to 5 have been propagated.
Processes F, ..., J think that all marks up to 0 have been propagated.  The
minimum of 5 and 0 is 0.  So all objects marked less than 0 are garbage.

Where is the problem?

Your example points out a flaw I had never noticed before.  A process that
contains only garbage will never propagate anything and therefore the minimum
will not increase.  The algorithm is not live.  But it IS safe!

                                                Marc