Lock free data structures, good and bad

I'm playing with making some lock free versions of sync blocks in code I wrote before. The code is currently protected by either sync blocks or read/write locks. Lock free approaches avoid sync blocks altogether and so in theory offer better concurrency in todays multi-core world.

Lets examine what exactly lock free means. Typically, it means having an atomic reference to a shared read only data structure. Threads can get a reference to the data structure and access it without fear of other threads because the data structure is read only.

If a thread wants to change the data structure then it must copy the current data structure and only update the copy with the new changes. Then, it basically does the equivalent of an optimistic database lock. It uses a compare and swap operation which will replace the atomic reference to the data structure with the new one only if no other thread can also modified it since the updating thread read the original data structure.

If the compare and swap succeeds then all is good. If not then the thread must get a reference to the current data structure and try to make the change to that one and then do compare and swap again. It has to keep trying to do this until it succeeds.

Clearly, first of all for read mostly data structures this approach is pretty cool and is a LOT better than a read/write lock. If writes are more frequent then contention will start to occur between writes as they compete to get to the compare and swap first. Frequent writes would also mean frequent copy operations. Once per loop try per thread. If you have a lot of contention AND the data structure is expensive to copy then this is going to burn a lot of CPU in those copy and update loops.

Java 5 has support for this type of lock programming. Look at the AtomicReference class and its compareAndSwap method. The trick to using it is NEVER update a data structure, always copy and then either update while copying or update after copy. Then try change the AtomicReference to the updated copy using compareAndSwap and if it fails then try updating the data structure that the AtomicReference now points to.

Comments

[Elliott Steele]

Take a look at the Clojure programming language.

http://clojure.org/concurrent_programming

[Josh Patel]

I am not a very technical person but the way you have explained lock free version of sync in code is really amazing. I hope to read about all this in the future.
Just stumbled and submitted your site to Viralogy. Hope you get some great traffic from it. Your blog is here http://www.viralogy.com/blogs/my/12785

- Josh

[Anthony Williams]

That's certainly one way to implement lock-free data structures, and on a garbage-collected platform like Java then it works really well. If you don't like the overhead of copying the data structure in its entirety then you can move to a different data structure where you can replace smaller chunks.

It's not the only way to write lock-free data structures though, and I wouldn't like to assert that any particular method was "typical".