Lock-Free Data Structures (2004)
drdobbs.com
drdobbs.com
[1] https://www.google.com.au/search?q=%22lock-free+algorithms%2...
There is a lot of genius in the article and references, but I will say from experience it is very easy to implement these approaches incorrectly, so unless an application requires the performance benefits provided, it is probably still a better bet to use standard locking mechanisms.
I find the entire concept of implementing novel container data-structures specifically for your application kind of ridiculous. This sort of thing should be implemented exactly once--in the language runtime library.
Or simply use battle-hardened APIs which are known to be fast and correct and which, themselves, have been implemented by using lock-free algorithms?
For example if I'm not mistaken throughout time the Java concurrency APIs did evolve to use more and more facilities using lock-free CAS operations under the hood.
You can also use 3rd party APIs, like the incredibly fast LMAX disruptor pattern (which also makes great use of CAS operations IIRC).
All this without being forced to come up yourself with the low-level stuff.
Then you can also use a recent language where concurrency has been built in from day 1: like Clojure which is pretty much deadlock free because it doesn't even give you access to locks.
I guess my point is: you don't have to implement yourself these advanced techniques to greatly benefit from them.
I agree though that the use should normally be contained to a small area and the details carefully abstracted away from the rest of the code because it takes real care to get the details right.
I guess the problem with this implementation is it requires a last reader for every write. If there are always readers, the second Update will block.
// infogulch's lock-free implementation of WRRMMap
template <class K, class V>
class WRRMMap {
Map<K, V>* pMap_, * pGC_;
unsigned readers;
public:
V Lookup (const K& k) {
unsigned r
while (r = readers, !CAS(&readers, r, r+1)); // increment readers
V ret = (*pMap_) [k];
while (r = readers, !CAS(&readers, r, r-1)); // decrement
if (r == 1 && pGC_) { // last reader. garbage collect
delete pGC_;
pGC_ = 0;
}
return ret;
}
void Update(const K& k,
const V& v) {
Map<K, V>* pNew = 0, * pOld;
do {
pOld = pMap_;
delete pNew;
pNew = new Map<K, V>(*pOld);
(*pNew) [k] = v;
} while (!CAS(&pMap_, pOld, pNew));
// DON'T delete pMap_;
// wait for the GC spot to be open, set it
while (!CAS(&pGC_, 0, pOld));
}
};