[gclist] Multi threaded reference counting

[James McCartney]

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. However all I need
to do is put it on a list and wait until every other thread has completed
one virtual machine instruction. If at that time the object's count is
still zero then it can be freed. If it is not zero then it is just
removed from the to-be-freed list and continues being live. How to
cheaply and safely do this check is my problem. Here's one idea:

each thread has a items-to-be-freed list. Every N virtual machine instructions
it checks this list. Items whose refcounts are nonzero are simply removed,
other items are moved to the next thread's list. If an item makes it all
the way back around to the thread that originally marked it to be freed,
it is put on the honest-to-god-free-list. So the lists are like a circular
bucket brigade.

This scheme results items being freed only after
num_threads * num_VM_instructions_per_check
instructions have passed.

The advantage is that of the above operations can be performed in a
nonblocking way.

Anyone know of / care to think of a better way?
Have I overlooked anything? major flaws?


   --- james mccartney     james@clyde.as.utexas.edu   james@lcsaudio.com
If you have a PowerMac check out SuperCollider, a real time synth program:
ftp://mirror.apple.com//mirrors/Info-Mac.Archive/gst/snd/super-collider-demo.hqx