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.
