Multithreading and Concurrency

Google has a Video indexing facility, and one of the things they index is a series of internal presentations about programming. Frequently they talk about Java, because Google has become a major player in the Java community process and they lead some of the teams working on new features. I want to report on a talk unfortunately titled "Advanced Topics in Programming Languages: The Java Memory Model". This is a widely used confusing term, because among Java experts, it appears, the Memory Model is actually the rules for multithreading and concurrency. You are free, of course, to listen to the entire thing, but there are four punch lines that only take a few minutes to learn:

First, the rules about multithreading have been rewritten in Java 5 because the previous rules were incomplete, unclear, and produced errors. In fact, the purists would argue there were no rules before Java 5.

Second, if you are multithreading, you need to share data between threads,  and there is a class or method in java.util.concurrent or java.util.concurrent.atomic that does what you want, use it. This includes any static or instance variables in a Servlet class that can be called concurrently by many Web requests. These classes were added in Java 5 so you may not be familiar with them. When you want to do this sort of thing, you should spend the time to review the packages.

If you need something that doesn't come in java.util.concurrent, then you almost certainly need to use synchronized. So here is the deal:

First, everything in the creation and initialization of a thread class Happens Before the thread runs.
Also everything in the thread, and all its internal termination Happens Before the event that signals the thread is complete.
Now, if you have two threads with synchronization blocks on the same object:

synchronized   (o) {
  a();
  b();
 }

synchronized   (o) {
  x();
  y();
 }

Then if both of these blocks execute once, then one of these two blocks Happens Before the other which means that all of the access and update to variables that the first one performs is complete and visible to the statements executing in the second block. You have no way to know which will Happen First, but you are guaranteed that one of them will.

What does this mean? Well, on exit from a synchronized block (when the lock is released) the compiler stores to memory all of the data being kept in registers, and it flushes the CPU cache before clearing the lock. Since the second block has to obtain the lock before executing any instructions, this means that the values of all variables changed by the previous block are in memory and are visible to the block that Happens After. Furthermore, the compiler (after Java 5) will never "optimize" code to break this rule.

Database people can think of the exit from the synchronized block as the "commit" of a transaction with updates. Until you commit the transaction, someone looking at the same data from another transaction may not see the updates you made. After the commit, the new data is visible to other users. This is a good analogy which is right 99% of the time and in almost all practical cases. There are a few situations of bad coding practice where you get an unexpected result:

synchronized (o)
{
    a();
    synchronized(o) {
        b();
    }
    c();
}

Here the compiler can detect that that you are already synchronized on the object referenced by "o" in the outer block, so the inner synchronized block is simply ignored (and the registers and cache are not flushed until you exit the outer block).

There is a "volatile" keyword that tells the compiler not to hold the value of a variable in a register. Volatile values are always loaded and stored back immediately. However, this may not be enough:

volatile int i = 0;
...
i++;

Now you might think that if two threads simultaneously increment i that you are guaranteed to end up with a value 2 larger than you started. This will probably be true on an x86 processor that has a memory increment instruction, but remember that RISC processors don't necessarily have such an instruction. The standard does not prevent a processor from loading the value into a register, incrementing it, and writing it back, and if this is not synchronized by a lock, you can easily end up with the two threads each incrementing the original value by one and both then storing the "plus one" value back to memory. This is where the java.util.concurrent.atomic classes come in handy, because they will do the right thing on your current processor. This is a particularly nasty problem because code will work all the time in test (on PCs) and will fail when you move to production (on Sun or AIX).

There are no perpetual motion machines. There is no free lunch. Ordinary humans cannot get multithreaded memory access right without the use of some language features. If you are not using java.util.concurrent and you are not using synchronized (on the same object), then in a very, very few cases volatile by itself may be enough (but typically only for setting flags or testing for null). If you think that there is a trick that will avoid the synchronized statement, you are almost always wrong. Even when things seem obvious in the source, compilers can reorder or optimize the execution of statements in ways you do not expect.