Lock-Free

Lock-Free Data Structures and Algorithm. More...

Modules
	Garbage-collected Object-Pool Forests
	Garbage-collected Object-Pool Forests as in [JUNG13].

Classes
class	GcPointer< T >
	Wrapper for gc_pointer_raw. More...
class	MarkablePointer< T >
	Bit-stealing Atomic Markable Pointer. More...
struct	MarkablePointerChain< NEXT >
	Atomic Markable Pointer Chain for lock-free list/queue/etc. More...

Typedefs
typedef uint16_t	aba_stamp

Detailed Description

Lock-Free Data Structures and Algorithm.

Classes to implemente Lock-Free Data Structures such as LockFreeList and LockFreeQueue. These data structures do not cause blocking, thus are more appropriate for many-core execution. They just need a few atomic operations. They might be still slow on many-socket machines because of expensive inter-socket communications, but way better than traditional blocking implementations.

References

• [KOGAN11] "Wait-Free Queues With Multiple Enqueuers and Dequeuers". Alex Kogan and Erez Petrank. PPoPP'11.

• [MICH02] "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets". Maged M. Michael. SPAA'02.

• [MICH04] "Hazard pointers: Safe memory reclamation for lock-free objects." Maged M Michael. PDS'04.

• [MICH96] "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms". Maged M. Michael and Michael L. Scott. PODC'96.

• [HERLIHY] "The Art of Multiprocessor Programming". Maurice Herlihy, Nir Shavit. (shame if you don't own a copy yet work on lock-free algorithms!)

Typedef Documentation

aba_stamp

typedef uint16_t aba_stamp

Type of ABA counter.