Lock-Free Garbage-Collectors, without atomic_ptr...

[Intel_C_Intel]

It is possible to create dynamic lock-free lists that allow for concurrent pushes, pops, and iterations using a "special" reference counted garbage-collector. You implement this using the wonderful cmpxchg8b instruction... ( why didn't intel do a cmpxchg16b for 64-bit? )


The garbage-collector is referenced and collects garbage nodes on the fly, in a 100% lock-free manor. It is used to protect CAS sections. Any nodes that any CAS-section pops, would get tossed in the current garbage collector...


This garbage-collector uses application threads when they reach the zero-reference count on the current garbage-collector. This make this algo as efficient as atomic_ptr.


Look here for some caveats on this:

caveats


Here is my lock-free stack and garbage-collector algo code:

stack.h


Here is a pthread test program:

main.cpp

thread.cpp

thread.h

lfsema.cpp

lfsema.h

mutex.h

atomic.h


What do you guys think of my algo?

;)