Subj : Re: Proxy GC
To   : comp.programming.threads
From : Chris Thomasson
Date : Wed Sep 28 2005 01:51 pm

> So freeing the objects
> in the same order they were "deleted" is the safe way to go.
>
> This allows lock-free traversal of the linked data structure.
> RCU uses FIFO order.  The RCU+SMR I did used FIFO order.  APPC,
> atomic pointer proxy collector, used FIFO order.   Chris can
> confirm whether VZOOM uses FIFO order.

Well, yes and no... ;)

It depends on the synchronization strategy an application chooses to use. 
The algorithm basically requires threads to "episodically or periodically" 
perform a "synchronization operation", that's all. An application can decide 
to take full control of this requirement ( very portable; FIFO not 
required ), or it can let the algorithm take care of it ( os and/or cpu 
dependant; FIFO required ).

I prefer the first method, because it gives you control over the polling 
logic, and its highly portable.




[...]
> RCU and other proxy schemes allow unlimited
> remembering for the duration of the proxy guarded access.

My algorithm refers to these types of references as "non-persistent", 
because they simply cannot persist across "synchronization points". However, 
it does defines another type of reference that can indeed persist across 
them. The algorithm allows a thread to acquire basically any number of these 
types of "persistent references".

With persistent references, you could do recursive/cyclic traversals with 
synchronization points in random places throughout the duration of the 
traversal, no problem. Also, VZOOM allows a thread to safely traverse, while 
calling user-provided function pointers that may call synchronization points 
and/or traverse another structures. I don't think that there are very many 
schemes out there that can do that...

;)

.