[gclist] Multi threaded reference counting
Sat, 18 Jan 1997 19:35:51 -0700
At 3:41 PM -0800 1/18/97, Henry G. Baker wrote:
>> I am trying to figure out how to do multi threaded reference counting
>> and have only one problem. When an object's ref count drops to zero
>> you can't free it immediately because it is not possible to atomically
>> dereference the object and decrement its count, another object
>> might have incremented it while you were decrementing it.
>Huh? If the reference count is _really_ the reference count, then
>refcount=0 means that _you_ are the only one who can reference it, and
>there can't possibly be any contention.
>There has been a lot of work done on this problem under the guise
>of 'distributed GC'. Perhaps a web search will turn up something....
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 :
say array X contains the only reference to object Y and thread A
stores NIL into X while thread B pushes X onto its stack.
It is possible for Y's refcount to become zero due to thread A
as thread B tries to increment it.
Say the code executes in the following sequence:
/* load contents of X to a register. */
obj = X;
thread A :
/* store NIL in object get previous contents */
prevobj = fetch_and_store(&X, NIL);
/* decrement refcount of previous contents */
/* free it */
if (refcount <= 0)
thread B interrupts:
obj->refcount++; /* crash! object has been freed by thread A. */
>Of course, this finesses the whole issue of how you get a _real_
>reference count in a multi-threaded system in the first place.
Well that is exactly the issue I need to solve. The system I've proposed
is a non-blocking non-copying incremental shared memory multi threaded GC
which is exactly the sort of thing that I need.
I haven't found any literature that describes such a thing. If you know of
one please advise. Web searches have not turned up anything and I've
printed out dozens of papers.
By deferring the freeing of the object as I proposed in my previous post
I prevent the race condition and crash above.
--- james mccartney email@example.com firstname.lastname@example.org
If you have a PowerMac check out SuperCollider, a real time synth program: