Future Synchronization

These are various lock-free synchronization techniques not currently planned for implementation. I may add or implement these at a future date. Or not.

Versioned Proxy Hazard Pointers

Hazard pointers don't have to just work with pointer values. They can work with version numbers if those numbers are incorporated into the objects being reclaimed assuming the GC logic uses those version numbers to scan against instead of the object address. This is an advantage for proxy GC since a global or collection scoped version count can be substituted for the proxy object. Furthermore, since the version numbers are sequentially ordered, unlike memory allocation which returns effectively randomly ordered addresses, things like combining trees can be used for more efficient scanning. Also there is significant synergism when combined with lock-free versioned transaction processing.

GC based thread-safe refcounting

The problem with atomically thread-safe reference counting was ensuring the storage containing the reference count didn't get get reallocated before you could attempt to increment the reference count. atomic_ptr implements two different ways of doing that. The other way was to use GC to prevent the reference count from being deallocated before the increment could complete. If you use tracing GC, refcounting doesn't make much sense. If you use RCU or some form of proxy GC, this scheme makes more sense. Some implementations of this, e.g. Linux, use atomic_increment_not_zero (increment if not zero) to avoid having a refcounted object go live again if it has been scheduled for GC. This typically involves not entirely trivial compare and swap logic. If you have an architecture with fetch_and_increment as well as compare and swap, you can have loop free increment refcount logic using this scheme. (just ignore the weak ptr part).

Of course this is probably all unneccesary since RCU references typically aren't stored into shared refcounted pointers.

Process level smart pointers

Hazard pointers are a good choice for use as process level smart pointers since they don't require write access to shared memory. This allows the use of lock-free data structures in read-only shared memory segments for really efficient IPC, i.e. no syscalls required to resolve read-only requests.

RCU for preemptive user threads

This deals with the problem of preemption in an RCU critical section by restarting the critical section so the suspended thread will not hold up RCU based GC.

The comp.programming.threads discussion on this starts here or here for the whole thread. I may copy and edit the discussion into here at a later time.

Efficient Caching

TBA

Lock-free b-trees

TBA



SourceForge.net Logo