Tuesday, February 15, 2011

Synchronized over listeners?

Iterate over a synchronized collection is actully not thread safe. As discussed here, there are three approaches to deal with this:
- CopyOnWriteArrayList: good for seledom write case, such as listeners
- Synchronized the collections
- Clone the collection before iteration: If you're doing a lot of work and don't want to block other threads working at the same time, the hit of cloning the collection may well be acceptable. Also, it is recommend to use toArray() for the collection cloning which is safe during copy.

There was a deadlock occurring between two classes A and B, they both have a bunch of synchronized methods and need each other at some point.

My solution is to remove 'Synchronized' from methods in class A and use a thread-safe CopyOnWriteArrayList class for the collection of listeners. The CopyOnWrteArrayList provides lock-free list traversal. Therefore, the lock contention between class A and class B is relieved.

In CopyOnWrteArrayList APIDoc, it states: "This class implements a variant of java.util.ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array. This is ordinarily too costly, but it becomes attractive when traversal operations vastly overwhelm mutations, and, especially, when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads...".

The synchronized collections wrappers, synchronizedMap and synchronizedList, are sometimes called conditionally thread-safe.

Map m = Collections.synchronizedMap(new HashMap());
List l = Collections.synchronizedList(new ArrayList());

// put-if-absent idiom -- contains a race condition
// may require external synchronization
if (!map.containsKey(key))
map.put(key, value);

// ad-hoc iteration -- contains race conditions
// may require external synchronization
for (int i=0; i<list.size(); i++) {
doSomething(list.get(i));
}

// normal iteration -- can throw ConcurrentModificationException
// may require external synchronization
for (Iterator i=list.iterator(); i.hasNext(); ) {
doSomething(i.next());
}

As discussed in this article, the java concurrent package provides some other classes such as ConcurrentHashMap, they aim to reduce lock granularity and perform better than old JDK ones.

Also, in java.util.concurrent.atomic package, there are a bunch of classes such as A AtomicBoolean, provide lock-free alternate. It is a wrapper for 'volatile boolean'. The difference between volatile and synchronized are well discussed in this blog. Basically it is about thread copy of variable, main memory and the synchronization between them.