[gclist] Multi threaded reference counting

Marc Shapiro shapiro@prof.inria.fr
Mon, 20 Jan 1997 16:09:38 +0100

 || From: James McCartney <james@clyde.as.utexas.edu>
 || Date: Sat, 18 Jan 1997 19:35:51 -0700
 || Subject: Re: [gclist] Multi threaded reference counting
 || In the distributed GCs I've seen only one thread owns an object.
 || I need a shared memory GC where every thread can access the
 || contents of every object. In that environment you can have a race
 || condition where one thread is decrementing the reference to an object
 || while another is incrementing it :

Larchant is a persistent DSM system.  It has exactly this problem.  We solve
the problem and we prove the solution is correct.

Our solution delays any decrement (on behalf of some process) until all
previous increments (on behalf of the same process) have been acted upon.

Your solution seems to have a similar effect.  The advantage of our more
general formulation is that it allows to delay increments and decrements
arbitrarily, as long as the "increments before decrements" rule is followed.
There are many performance advantages to delaying.  The main one is that we do
not have to overload pointer assignments in the application code; instead, we
do partial traces, a small portion of the memory at a time.

In fact we solve an even more general problem.  Ours is a large-scale
distributed system.  The GC does not know if the local copy of an object is
up-to-date.  The general solution is to execute increments immediately, but to
delay decrements until it is safe.

I can send you a paper that states the five very simple safety rules the
system must obey for the GC to be safe and live.