Atomic Ptr Plus Project Home
Atomic Ptr Plus project page
What this project is
This project is a collection of various lock-free synchronization
primitives and fast pathed synchronization functions. See
here for a definition and explanation of lock-free.
- Lock-free futex based Posix condition variable for Linux --
This a faster version than NPTL's. Much faster as
you can see by the timings
- Lock-free futex based eventcount for Linux --
Eventcounts, your basic non lossy lock-free signaling mechanism.
The waiting can't be considered lock-free because it blocks but
having the signaling part lock-free has major performance implications.
- atomic_ptr proxy GC
A proxy GC scheme with an api much like RCU which is also a
proxy based GC. Amortizes the atomic_ptr overhead for read access.
This has a C++ OO api.
- RCU+SMR - hazard pointers w/o memory barriers
This is an implementation of Maged Michael's hazard pointers
without the need for expensive memory barriers. It also handles
non cyclic traversal of linked data structures without the need
for some other mechanism like reference counting.
- rcpc (reference counted proxy collector)
like appc except it's in C, not C++, and only requires
single word compare and swap if double word compare and swap
or load reserved/store conditional is not available.
- eventcount 0.0.0 -- pre-alpha futex based eventcount
- fastcv 0.0.0 -- pre-alpha futex based fast pathed condition variable
- atomic-ptr-plus 0.0.4 -- pre-alpha release of
atomic_ptr and appc (atomic pointer proxy collector)
- fastsmr 0.0.3 -- pre-alpha RCU+SMR hazard pointer implementation
- rcpc 0.0.2 -- pre-alpha (yet another) reference counted proxy collector
This kind of project takes a lot of resources, particularly
in the area of hardware since it has to be ported to different
platforms and tested on multi-core machines. Also, I don't want
to freeze the api until I get to use it in a serious application.
Since lock-free is about scalability among other things this means
applications on the large side which also means a lot of resources.
For example, try writing a full blown OLAP database from scratch
as a proof of lock-free scalability and to firm out the api.
Future development will depend on if and when any resources
These pages are somewhat out of date. Future enhancements
to fastsmr will probably entail support for reference counting
and/or tracing GC instead of the fifo ordering requirement
on scheduling object deallocation. Or maybe not.
Current design issues and direction
Synchronization techniques for
possible future implementation.
Various lock-free patents and patent applications,
some by me, some by others, in the
area of lock-free programming.
- 20060037026 Lightweight reference counting using single-target synchronization
Lock-free reference counting very similar to atomic_ptr or so it would seem.
- 20040107227 Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation
Hazard pointers, the SMR (safe memory reclamation) in RCU+SMR
- 20030174572 Non-blocking memory management mechanism for supporting dynamic-sized data structures
Repeat Offender Problem (ROP)
- 20030140085 Single-word lock-free reference counting
Lock-free reference counting using ROP. If you have GC,
lock-free reference counting is easy, see RCU based refcounting,
rcuref, in the Linux kernel.
- 20060130061 Use of rollback RCU with read-side modifications to RCU-protected data structures
An RCU for preemptive user threads that never panned out.
Somewhat moot since RCU+SMR is probably a better way to go.
See "RCU for preemptive user threads" usenet references
below for earlier discussions on this.
To look at any of the above patent applications go to
uspto publication number search
and paste in the patent application number.
- 6,993,770 Lock free reference counting
- 4,809,168 Passive serialization in a multitasking environment
An early version of RCU.
- 5,295,262 Read-only access without blocking via access vectors
Basis for rcpc and part basis for atomic_ptr.
- more RCU patents. See RCU papers below for now.
Stuff previously disclosed on usenet
- RCU papers
Paul McKenney's Read, Copy, Update papers. Also contains discussions
the general technique and some dicussions and reference to other lock-free
algorithms. See annotated bibiography document for more references.
Michael's publications page Includes paper on SMR hazard pointers.
Herlihy's publications page. The definitions for lock-free, wait-free,
and obstruction-free are out there somewhere.
Lock-Free Reference Counting. You can't implement this algorithm
unless you have cpu's with DCAS but it does sort of cover the issues of
lock-free reference counting.
- R. K. Treiber. Systems Programming: Coping with Parallelism. RJ 5118, IBM Almaden Research Center, April 1986.
for further discussion on this and lock-free and multithreaded programming
jseigh at users.sourceforge.net
This project hosted by