When A Synchronized Class Isn’t Threadsafe

Every Java programmer has heard this advice before: “Prefer ArrayList over Vector. Vector is fully synchronized, and as such you’re paying the synchronization penalty even when you don’t need it.”

ArrayList is not synchronized, so when you need it you need to perform synchronization yourself, or alternatively, as the ArrayList javadoc entry says: “… the list should be “wrapped” using the Collections.synchronizedList method.” Something like this:

List list = Collections.synchronizedList(new ArrayList());

The resulting List will be synchronized, and therefore can be considered safe.
Or is it?
Not really. Consider the very contrived example below.

final List<String> list = Collections.synchronizedList(new ArrayList<String>());
final int nThreads = 1;
ExecutorService es = Executors.newFixedThreadPool(nThreads);
for (int i = 0; i < nThreads; i++) {
    es.execute(new Runnable() {
        public void run() {
            while(true) {
                try {
                    list.clear();
                    list.add("888");
                    list.remove(0);
                } catch(IndexOutOfBoundsException ioobe) {
                    ioobe.printStackTrace();
                }
            }
        }
    });
}

As long nThreads is 1, everything runs just fine. However, increase the number of nThreads to 2, and you start getting this:

java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

at java.util.ArrayList.RangeCheck(Unknown Source)

at java.util.ArrayList.remove(Unknown Source)

at java.util.Collections$SynchronizedList.remove(Unknown Source)

Changing the synchronized List to Vector doesn’t help either. What happened here? Well, individual method calls of synchronized List and Vector are synchronized. But list.add() and list.remove() can be called in any order between the 2 threads. So if you print list.size() after list.add(), the output is not always 1. Sometimes it’s 0, sometimes it’s 2. Likewise, thread 1 may call list.add(), but before it gets a chance to call list.remove(), thread 2 gets into action and calls list.clear(). Boom, you get IndexOutOfBoundsException.

In that example above, the 3 calls to List’s methods have to be atomic. They must happen together as one unit, no interference from other threads, or else we’ll get the IndexOutOfBoundsException again. The fact that the individual methods are synchronized is irrelevant. In fact, we can go back to using the non-synchronized ArrayList, and the program will work, as long as we synchronize properly to make the 3 calls happen as one atomic, indivisible unit of execution:

synchronized (list) {
    list.clear();
    list.add("888");
    list.remove(0);
}

The moral of the story is that just because a class is fully synchronized, doesn’t mean it’s threadsafe (UPDATE: as in doesn’t mean your code will be threadsafe from using it–thanks Alex). You still have to be on the look for those sequence of method calls that have to occur atomically, because method level synchronization won’t help in this regard. In other words, watch what you’re doing. (And yes, we should still prefer ArrayList over Vector.)

Threadsafe Iteration & ConcurrentModificationException

Sometimes it’s not so obvious when exactly we’re supposed to synchronize our use of Collections. Ever encountered a ConcurrentModificationException before? I bet it’s probably because your code looks something like this (a.k.a.: why the for-each loop isn’t such a great idea actually):

final List<String> list = new ArrayList<String>();
list.add("Test1");
list.add("Test2");
list.add("Test3");
for(String s : list) {
    if(s.equals("Test1")) {
        list.remove(s);
    }
}

ConcurrentModificationException will be thrown in this case, even when there’s only a single thread running. To fix this problem, we can’t use the for-each loop since we have to use the remove() method of the iterator, which is not accessible within the for-each loop. Instead we have to do this:

for(Iterator<String> iter = list.iterator(); iter.hasNext();) {
    String s = iter.next();
    if(s.equals("Test1")) {
        iter.remove();
    }
}

The point is that iteration is something that we’d probably want to happen atomically–that is, while we’re iterating over a collection, we don’t want other threads to be modifying that collection. If it happens most probably something is wrong with our design.

This is why if you look into the JDK source code, the implementation for Iterator usually checks the expected modification count (i.e.: how many times is this collection supposed to have been modified?) against the collection’s current modification count (how many times this collection has been modified). If they don’t tally, the Iterator assumes that another thread has modified the collection while the iteration is going on, so it throws the ConcurrentModificationException. (This is exactly what happens in our single-threaded case about too by the way–the call list.remove() increases the modification count such that it no longer tallies with the one that the iterator holds (whereas iter.remove() resets the mod count so they still tally.) ConcurrentModificationException is a useful exception–it informs us of a probable fault in our design.

When Volatile Fails

However, ConcurrentModificationException is not 100% reliable. The implementation of Iterator.next() may look something like this:

 
public E next() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // other stuff

That is, ConcurrentModificationException is supposed to be thrown when the mod counts don’t tally. But it may not get thrown because the thread on which the modCount check is running is seeing a stale value of modCount. That is, let’s say you have thread A iterating through a collection. Whenever you call iter.next(), it checks that modCount == expectedModCount. But modCount may have been modified by thread B, and yet A is still seeing the unmodified value. If you remember, this is what the volatile keyword is about–it is to guarantee that a thread will always see the most recent value of a variable marked as such.

So why didn’t Joshua Bloch (or whoever took his place in Sun to take care of the Collections API) mark the modCount volatile? That would at least make the concurrent modification detection mechanism more reliable, yes? Well… no. Actually marking modCount volatile won’t help, because although volatile guarantees uptodateness, it doesn’t guarantee atomicity.

What does that mean? Well, if you examine the implementation of ArrayList, you’ll see that methods that modify the list increment the modCount (non-volatile) variable by one (i.e.: modCount++). So theoretically, if we mark modCount as volatile, whenever thread B says modCount++, thread A should always immediately see the value and throws ConcurrentModificationException.

But there is a problem: the increment operator (++) is not atomic. It is actually a compound read-modify-write sequence. So while thread B is in the middle of executing modCount++, it’s entirely possible that the thread scheduler will kick thread B out and decide to run thread A, which then checks for modCount before B has a chance to write back the new value of modCount.

Hidden Iteration

As if things aren’t hairy enough as they are, it’s not always obvious when an iteration over a collection is happening. Sure, it’s probably pretty easy to spot iteration code we’ve written ourselves, so we can synchronize those. However, much less obvious are the iterations that happen within the harmless-looking methods of the Collections API. If you examine the source code of java.util.AbstractCollection class, for example, you’ll see that methods like contains(), containsAll(), addAll(), removeAll(), retainAll(), clear()… practically almost all of them trigger an iteration over the collection. Iteration suddenly becomes a LOT harder to spot!

So What Do We Do?

Sounds pretty hopeless, isn’t it? Well… nah. A very, very smart CS professor named Doug Lea has figured it out for the rest of us. He came up with concurrent collection classes, which handle the problems listed above for the most common cases. These concurrent collections have been part of the standard Java API in java.util.concurrent package. For most cases, they are drop-in replacement for the corresponding non-threadsafe classes in java.util package, and if you haven’t taken a good look at them, it’s time that you do!

About these ads

26 thoughts on “When A Synchronized Class Isn’t Threadsafe

  1. Good article… There are performance considerations to take into account with any solution. I find the best way around (for very large systems) is to use a Thread unsafe collection, and wrap all access to it in a ReadWriteLock, since even the Collections in java.util.concurrent are only Thread-safe on a method-by-method basis (I actually just finished a post on ReadWriteLocks and Thread-safe Collections about an hour ago… so you can imaging my surprise to see your post :P)

  2. I think IMHO that you mixed your concepts. In this case, the class in need of synchronization is the class you are designing, not the lists you are using.
    Basically, you have to define you critical paths and make sure those are synchronized.
    Java offers the monitors for this, and you can easily use the synchronized keyword to achieve this.

    synchronized(list) {
    list.clear();
    list.add(“888″);
    list.remove(0);
    }

    Thread safety for a List instance using Collections.synchronizedList(), it refers to the internal workings of the List class, not it’s external use.
    In essence, you got the very basic principle of thread safety for collections wrong.

  3. jps, George, didn’t you see that the VERY topic of this post is that “mixed concepts” that you were referring to?

    What I am discussing in this blog entry, in so many words, is EXACTLY what jps said in this sentence: “Thread safety for a List instance using Collections.synchronizedList(), it refers to the internal workings of the List class, not it’s external use.” That’s the VERY IDEA I’m trying to get across from the title because I’ve seen such misunderstanding while doing code review!

    Did you even read through the entry? Heck, your suggested solution was even copied straight out of the post (yes, see above!):

    synchronized (list) {
    list.clear();
    list.add(“888″);
    list.remove(0);
    }

    So what you George and jps are saying is: “Because he is discussing why something is wrong, he must have got that something wrong.” It’s like saying that “Because Joshua Bloch tells us in his book that using BigDecimal(String) constructor is wrong/dangerous, that means Joshua Bloch doesn’t understand BigDecimal”. (Not that I’m comparable to Joshua Bloch or whatever, but the line of reasoning is the same.)

    Where did you two get this twisted reasoning from? Is it from the title of the entry?

  4. While the points you make are valid and important, I must nit-pick the assertion that a synchronized List is not “thread-safe”. I would assert that a synchroized List (or Vector) is thread-safe. There is no data race or possibility of seeing an invalid value.

    Now the code you list is *incorrect* for the desired goal of your program. And as you describe that illustrates an important point about the need to consider composite operations against an object that provides thread-safe access for single actions. But that’s a different thing than thread safety. A synchronized list provides no guarantee to the atomicity of a set of actions upon it. It doesn’t intend to. It does provide safe access to a list of items, such that all modification to internal state is properly protected by synchronization.

    A better design would either lock on the List itself while performing the composite operations (this is explicitly and intentionally supported just for this reason) or you could wrap the list in your own object that encapsulates the composite operations as a single atomic operation. I’d probably opt for the latter.

    To that end, I think it would be more accurate to call this post “When A Synchronized Class Isn’t Sufficient”. But then I hate it when people tell me what to call my posts and nit-pick every detail so I guess I’m a hypocrite.

  5. “A better design would either lock on the List itself while performing the composite operations (this is explicitly and intentionally supported just for this reason)…”

    Yes… this is exactly what I said (see above in the entry itself):

    synchronized (list) {
    list.clear();
    list.add(“888″);
    list.remove(0);
    }

    I understand why the title can cause confusion–but the 5-liners is originally already there in the post–so I don’t understand why I’ve got 2 comments, from Alex and jps, that pointed out to me that these 5 lines should be the solution? (Although I’ve put forward those very 5 lines in the post as the correct thing to do?)

    I’m getting a bit confused now…

  6. Yes, I saw it. I’m not questioning the solution; I was just reiterating possible solutions. I was questioning your use of the term “thread-safe”. After sleeping on it, I think can voice my objection more succinctly:

    There are two layers of code here – the synchronized List (or Vector) and the program in the post that uses it. The title and first couple paragraphs imply that a synchronized List isn’t thread-safe whereas I would say that a synchronized List *is* thread-safe, but the program itself is not.

    Another interesting related note on iteration: Use of an Iterator over a list returned from the synchronizedList() (or other similar methods) is NOT thread-safe. The docs state that you must synchronize on the list/collection/etc while iterating. And if you do that, then modCount will always be read/written in a synchronized block, which guarantees that all threads *will* see the correct modCount (same goes for Vector). Although your comments on modCount visibility are still completely valid for an unsynchronized list which is why the docs say it is a “best-effort” fail fast. I’m guessing this is done to optimize the performance for the use of an unsynchronized List in multi-threaded but externally synchronized usage. [Which if access to the list is protected via an external synchronized lock, would still guarantee that modCount changes would be visible.]

    Don’t get me wrong – I like your post, and I think this is a really important topic. But that also makes it worth striving for precision.

  7. Yes, agreed; the point is valid, and I’m sure many of the readers might be surprised by some of what they read, but it doesn’t mean the class isn’t thread-safe, just means that thread-safe is not enough for this particular case.

  8. What I always like to consider and explain to my developers is that:
    – The best ‘thread-safe’ is not thread at all, and
    – The best ‘concurrency-modification-safe’ is no modification at all

    As many of you already pointed out, you can experience concurrency problems even with just one thread. The key point is modification. The pragmatic point of view is to make your objects inmutable, as in Lisp. And you have the masterpiece of concurrent language: Erlang, wich happens to be ‘inmutable-oriented’.

  9. This article is NOT about thread-safe, but rather about concept of atomic operation, which is applicable to anything from Java collection framework to dumb super duper simple StringBuffer object. It is not a rocket science to know that in order to ensure clear, add, and remove a thread-safe operation (or rather – an atomic operation) one has to enclose the three operations in a single synchronized keyword (or acquiring a mutex).

    So, to me you’re someone who’s trying to say: “I am a dumb ass who is smarter than average guy with a year or two java programming experience, and nobody knows about this thing since I myself (the genius, master of universe) found it very mesmerizing. So before anybody got the chance to write same thing about this, I had to write it first, who knows it would magically appear in javaworld or perhaps even James Gosling the Java almighty might find it very fascinating”.

    Your level of knowledge is such a newbie for someone who claim to have enormous experience in java, C#’ and C++.

  10. Alex #2 (not Alex Miller).

    You are right in saying that ultimately the article is not about Thread Safety, rather atomic operations, but Ray had already acknowledged this in previous comments and dialogue with Alex Miller. Even if you personally do not find the post useful, I am sure there are score of less experience developers who would benefit from this article.

    Further, I don’t see how your vitriolic comments are relevant or contribute in a meaningful fashion, and if you do want to fling vitriol at others on the internet, consider using proper English grammar. Please grow up.

  11. I immediately got irritated with the way ray responded to jps/george, if they (jps&george) said ray was mixed up, yes he really was, verily … unfortunately, sometime when one (ray) thinks himself very good or knowledgeable, he won’t admit mistake (sometime silly mistake) very easily.. he needs to be convinced that he’s arguing with person better than him (in this case, Alex Miller) before giving up with many excuses…

  12. Of course I (and I hope everybody else too) need to be convinced, that is the whole point of understanding and learning! You don’t just accept everything you’re told, you accept it when it makes sense to you. This has NOTHING to do with how good you are or not.

    I didn’t understand what jps and george were telling me, I thought *they* didn’t understand. I understood what Alex Miller was telling me after he clarified, and I promptly acknowledge that and thank him. And no, I didn’t “give up” because Alex Miller is better than me–I didn’t even know who Alex Miller was until I started reading up about Java 7 recently. But because he explained well.

    Like I said, you really need to go out more Alex. Getting THAT worked up over something that was settled months ago in a total stranger’s obscure blog and started throwing puerile remarks like that. I sense a lot of pent-up anger and frustration there. Hope things will get better for you soon.

  13. Still writing code? Are you crazy? Yes, you can’t live without coding, hahahahaha ….

    An old friend from Canada.

  14. What will happen if two cocurrent thread try to remove the third object of a collection(ArrayList or Vector). How it will behave.

    run()
    {
    vector.remove(2);
    }

    or

    run()
    {
    ArrayList.remove(2);
    }

    Vector is Synchornized and ArrayList is unSynchronized but two threads are performing the same operation on these collection.

  15. “But list.add() and list.remove() can be called in any order between the 2 threads.”
    I think this is also wrong, JVM doesnt do such modifications. These are two methods of same object!!
    That code is getting exceptions just because remove(0) is called just after clear() method.

    I dont know why anyone hasnt stated the obvious? Or I did missed that one :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s