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

Intel_C_Intel — Tue, 05 Aug 2003 12:15:30 GMT

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?

;)

topic Lock-Free Garbage-Collectors, without atomic_ptr... in Intel® Moderncode for Parallel Architectures

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