Synchronization and concurrency
Deadlock (and avoiding it)
Java 5: ConcurrentHashMap
When is it safe to omit synchronization?
The inclusion of this section may seem a bit surprising given the previous sections. So far, we've been trying to hammer home the fact that whenever you have shared data, there must be some synchronization mechanism, be it via the synchronized keyword, the volatile keyword, or one of the new concurrency utilities such as the Java 5 atomic classes, components such as explicit locks or Semaphores etc. We've tried to stress that "patterns" that try to avoid any kind of synchronization, such as the infamous double-checked locking, are wrong.
So now I want to introduce an interesting exception:
You can access a shared variable without synchronization iff your program performs adequately in all possible outcomes resulting from not having the synchronization.
So what do we mean by this? Well, imagine we have a single integer value, x. We are going to allow multiple threads to read and write it concurrently, but we will not declare it volatile or synchronize on it in any way. Each concurrent thread will perform an operation consisting of:
Now, depending on the JVM and architecture we're running on, any of the following could happen:
If this sounds a bit complicated, it is, and that's why the rule of thumb is not to try and omit synchronization unless you're really sure it's safe! But if we could show that our code behaves correctly in all three cases, then we could potentially leave out synchronization.
Coming back to the above possibilities, the idea of having a variable where it doesn't effectively matter whether it behaves as a thread-local variable or not may sound a bit strange. But it turns out that Sun's JDK implementation has at least one example.
Example: implementation of ConcurrentSkipListMap
An interesting example occurs in the implementation of ConcurrentSkipListMap. We won't go into all the details of the skip list algorithm here. But essentially, every time an item is added to the map, a random number needs to be generated to decide on exactly how the new object is added to the skip list's internal structure. The random number generation algorithm used is Marsaglia's XORShift, which uses a single integer state variable (i.e. we essentially have a read-calculate-set each time). Since the aim is to eliminate contention on put operations as much as possible, it wouldn't be desirable to introduce an extra lock on the random number generator. An option could be an AtomicInteger, or possibly even plain volatile variable with the risk of occasional duplicates when a race condition occurred.
But in fact, what the designers decided was "sod it, let's just use a plain old integer variable". No synchronization. No volatile. No atomic variable. No nothing. For the random number generation in ConcurrentSkipListMap, this is generally an appropriate decision because:
After all this thought process, I'm sure you'll agree that cases where it's safe to leave out synchronization are going to be rare and difficult to justify. This case in the JDK has surely involved some thrashing things out among concurrency experts working on the collections library. The take-home message should generally be "don't do this at home".
Copyright © Neil Coffey 2013. All rights reserved.