Tuesday, September 29, 2009

NESS 2009: multithreading and the Java memory model

At the New England Software Symposium, I attended Brian Goetz's session called "The Java Memory Model". When I saw the phrase "memory model" in the title I thought it would be about garbage collection, memory allocation and memory types. Instead, it is really about multithreading. The difference is that this presentation focuses on visibility, not locking or atomicity. This is my attempt to summarize his talk.



The importance of visibility

Visibility here refers to the memory that an executing thread can see once it is written. The big gotcha is that when thread A writes something before thread B reads it, it does not mean thread B will read the correct value. You could ensure that threads A and B are ordered with locking but you can still be in deep doo doo because the memory is not written and read in order, or is read in a partially written state.

A big part of this peril comes from the layered memory architecture of modern hardware: multi-CPU, multi-core CPUs, multi-level caches on and off chip etc. Instructions could be executed in parallel or out of order. The memory being written may not even be in RAM at all: it could be on a remote core's register. But the danger could also come from old-fashioned compiler optimizations. One of Brian's examples is the following loop which depends on another thread to set the boolean field asleep:

while (!asleep) ++sheep;

The compiler may notice that asleep is loop-invariant and optimize its evaluation out of the loop:

if (!asleep) while (true) ++sleep; 

The result is an infinite loop. The fix in this case is to use a volatile variable.

The Java Memory Model

A memory model describes when one thread's actions are guaranteed to be visible to another. The Java memory model (JMM) is quite an achievement: previously, memory models were specific to each processor architecture. A cross-platform memory model takes portability well beyond being able to compile the same source code: you really can run it anywhere. It took until Java 5 (JSR 133) to get the JMM right.

The JMM defines a partial ordering on program actions (read/write, lock/unlock, start/join threads) called happens-before. Basically, if action X happens-before Y, then X's results are visible to Y. Within a thread, the order is basically the program order. It's straightforward. But between threads, if you don't use synchronized or volatile, there are no visibility guarantees. As far as visible results go, there is no guarantee that thread A will see them in the order that thread B executes them. Brian even invoked special relativity to describe the disorienting effects of relative views of reality. You need synchronization to get inter-thread visibility guarantees.

The basic tools of thread synchronization are:
  • The synchronized keyword: an unlock happens-before every subsequent lock on the same monitor.
  • The volatile keyword: a write to a volatile variable happens-before subsequent reads of that variable.
  • Static initialization: done by the class loader, so the JVM guarantees thread safety
In addition to the above, the JMM offers a guarantee of initialization safety for immutable objects.

The Rules

Here are points that Brian emphasized:
  • If you read or write a field that is read/written by another thread, you must synchronize. This must be done by both the reading and writing threads, and on the same lock.
  • Don't try to reason about ordering in undersynchronized programs. 
  • Avoiding synchronization can cause subtle bugs that only blow up in production. Do it right first, then make it fast.
Case study: double-checked locking

One example of synchronization avoidance gone bad is the popular double-checked locking idiom for lazy initialization, which we now know is broken:

private Thing instance = null;
public Thing getInstance() {
   if (instance == null) {
      synchronized (this) {
         if (instance == null) instance = new Thing();
      }
   }
   return instance;
}

This idiom can result in a partially constructed Thing object, because it only worries about atomicity at the expense of visibility. There are ways to fix this, of course, such as using a volatile field or switching to using static initializers. But it's easy to get it wrong, so Brian questions why we would want to do something like this in the first place.

The main motivation was to avoid synchronization in the common case. While it used to be expensive in the past, uncontended synchronization is much cheaper now. There is still a lot of advice to avoid supposedly expensive Java operations out there, but the JVM has improved tremendously and a lot of old performance tips (like object pooling) just don't make sense anymore. Beware of reading years-old advice when you Google for Java tips. Remember Brian's advice above against premature optimization. That said, he also showed a couple of better alternatives for lazy initialization.

Some thoughts

This talk was a reminder to me that low-level multithreading is hard. It's hard enough that it took years to get the JMM right. It's hard enough that a university professor would say "don't do it". And if you faithfully follow Brian's rules and use synchronization primitives everywhere, you might find yourself vulnerable to thread deadlocks (hmmm ... why does JConsole have a deadlock detection function?).

The primary danger in multithreading is in shared, mutable state. Without shared mutable data, threads might as well be separate processes, and the danger evaporates. So while it's wonderful what JMM has done for cross-platform visibility guarantees, I think we would do ourselves a favor if we tried to minimize shared mutable data. There are often higher level alternatives. For example, Scala's Actor construct relies on passing immutable messages instead of sharing memory.

Update: this blog entry has been republished as a Javalobby article.

6 comments:

  1. Thanks for the summary. I'm curious what Brian's alternatives for lazy initialization were.

    ReplyDelete
  2. Check out {http://en.wikipedia.org/wiki/Singleton_pattern#The_solution_of_Bill_Pugh}

    Bill Pugh is the brains behind all of this.

    ReplyDelete
  3. 1. The double checking idiom is not only known as broken - there are also will known ways to fix it: see J. Bloch's "Efficient Java".
    2. I hear a lot about Actors recently. This is fine, but what about shared mutable collections that are needed in many situations?
    Sometimes I start thinking that guys who are so exited about actors and functional programming had never participated in real-life projects.

    ReplyDelete
  4. java concurrency in practice - the complete answer for all questions

    ReplyDelete
  5. Bill Pugh's SingletonHolder pattern only works for statics. For non-static lazy initialisation use something like our LazyReference that encapsulates all the logic and is tuned for performance.

    http://labs.atlassian.com/wiki/display/CONCURRENT/LazyReference

    ReplyDelete
  6. Java multi threading is important for the multi tasking work like pipeline processing.
    More importantly it is useful because it uses less memory or you can say shared memory for doing work..Because it using less memory as compared to single process oriented works.

    ReplyDelete