Am Saturday 16 January 2010 03:15:44 schrieb Chris M. Thomasson:
FWIW Helge, here is a new proxy garbage collector algorithm of mine that I am currently experimenting with:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a 53f24de178b419f
interesting concept, but AFAICT it shares two undesirable properties with my implementation: Reclamation can be delayed indefinitely if - one thread is "stuck" within the critical section (e.g. scheduled away) - threads interlock such that at least one thread is always within the critical section Right? It's not that I consider this problematic (there is no reason I would ever want to share a data structure between threads if I know that the above can pose a problem).
The algorithm is wait-free in practice on systems with native fetch-and-add and swap instructions like x86-32/64. If the architecture forces you to implement fetch-and-add with a damn LL/SC or CAS loop, well, then it's not really wait-free now is it? No, I am afraid it's lock-free, or whatever semantics the LL/SC is which could even be obstruction-free. Sad...
Depends how it is implemented -- LL/SC is wait-free iff other reads to the location do not invalidate the reservation (PowerPC is in that category). I strongly suspect that CAS on x86 is actually just a micro-coded LL/SC anyway... Regards, Helge