This is the answer to the riddle posed in my earlier puzzler posting. You should probably look at that question before looking at this answer.
I suppose I should call it something other than a puzzler, to avoid getting hit by Josh and Neal's angry team of vicious, snarling lawyers...
This program certainly looks straightforward. It just looks as if two threads are writing to two variables. In fact, you probably expected me to say something "who-cares" oriented about compiler optimizations at this point. Well, they are volatile variables, so you can worry a lot less about potential reorderings. In fact, this one has absolutely nothing to do with program transformations, and, if you ran the program on my laptop, you found that it hangs!
It turns out that this is the result of one of those vicious little static initialization quirks that provide so many hours of headaches. What happens is something very like the following. The first thread encounters A; this class has not been initialized, so that thread tries to initialize it. When you try to initialize a class, you acquire a lock on that class, so that no one else can initialize it at the same time. Are you starting to see where this could lead to problems?
At the same time as this, the second thread encounters B, and so acquires the lock on the B class. It then runs the static initializer for B, which encounters A. "Wait!" it says -- "A hasn't been initialized! Better acquire that initialization lock..." It tries to acquire the lock, but the first thread already has it, so it waits for the first thread to finish.
Meanwhile, the same process goes on in the first thread. It runs the static initializer for A, which encounters B. "Wait!" it says -- "B hasn't been initialized! Better acquire that initialization lock..." It tries to acquire the lock, but the second thread already has it, so it waits for the second thread to finish.
Result: Both threads wait forever. Deadlock!
This whole process is scheduling / hardware / OS / JVM dependent, of course. If the first thread runs to completion without letting the second thread start, then it will quite happily initialize both A and B without the other thread acquiring any locks. This will avoid deadlock nicely. This seems to happen on Linux, but not OS X.
How do you avoid this? Well, that's a little tricky. In this case, you would probably rewrite the code so that it doesn't perform the initialization in two separate threads. That's not always a general-purpose solution, though. Your best bet, in general, is to avoid having circularities like this in your static initializers. As with constructors, it is important to keep your static initializers as simple as possible.
Keeping it simple might mean not doing anything that might trigger subsequent static initialization. That's a good first option, if you can manage it, but it is not always possible.
The second option is to make sure that you have an order over your classes. For example, if you have three classes, A, B and C, you could structure them so that C can refer to A and B in its static initializer, B can only refer to A, and A can only refer to itself. This will prevent deadlocks by enforcing a strict order over when the implicit locks can be acquired.
The final option -- if you know this will be a problem -- is to make sure that the initialization can only happen in a single thread. This may mean having to force it to occur earlier, by referencing the class earlier than it would otherwise have been referenced.
I feel like there should be a moral. The moral is that static initialization has all sorts of hidden gotchas, and you should look out for it.
I suppose I should call it something other than a puzzler, to avoid getting hit by Josh and Neal's angry team of vicious, snarling lawyers...
This program certainly looks straightforward. It just looks as if two threads are writing to two variables. In fact, you probably expected me to say something "who-cares" oriented about compiler optimizations at this point. Well, they are volatile variables, so you can worry a lot less about potential reorderings. In fact, this one has absolutely nothing to do with program transformations, and, if you ran the program on my laptop, you found that it hangs!
It turns out that this is the result of one of those vicious little static initialization quirks that provide so many hours of headaches. What happens is something very like the following. The first thread encounters A; this class has not been initialized, so that thread tries to initialize it. When you try to initialize a class, you acquire a lock on that class, so that no one else can initialize it at the same time. Are you starting to see where this could lead to problems?
At the same time as this, the second thread encounters B, and so acquires the lock on the B class. It then runs the static initializer for B, which encounters A. "Wait!" it says -- "A hasn't been initialized! Better acquire that initialization lock..." It tries to acquire the lock, but the first thread already has it, so it waits for the first thread to finish.
Meanwhile, the same process goes on in the first thread. It runs the static initializer for A, which encounters B. "Wait!" it says -- "B hasn't been initialized! Better acquire that initialization lock..." It tries to acquire the lock, but the second thread already has it, so it waits for the second thread to finish.
Result: Both threads wait forever. Deadlock!
This whole process is scheduling / hardware / OS / JVM dependent, of course. If the first thread runs to completion without letting the second thread start, then it will quite happily initialize both A and B without the other thread acquiring any locks. This will avoid deadlock nicely. This seems to happen on Linux, but not OS X.
How do you avoid this? Well, that's a little tricky. In this case, you would probably rewrite the code so that it doesn't perform the initialization in two separate threads. That's not always a general-purpose solution, though. Your best bet, in general, is to avoid having circularities like this in your static initializers. As with constructors, it is important to keep your static initializers as simple as possible.
Keeping it simple might mean not doing anything that might trigger subsequent static initialization. That's a good first option, if you can manage it, but it is not always possible.
The second option is to make sure that you have an order over your classes. For example, if you have three classes, A, B and C, you could structure them so that C can refer to A and B in its static initializer, B can only refer to A, and A can only refer to itself. This will prevent deadlocks by enforcing a strict order over when the implicit locks can be acquired.
The final option -- if you know this will be a problem -- is to make sure that the initialization can only happen in a single thread. This may mean having to force it to occur earlier, by referencing the class earlier than it would otherwise have been referenced.
I feel like there should be a moral. The moral is that static initialization has all sorts of hidden gotchas, and you should look out for it.
Comments
I think the most persuasive argument would be that if you had one initializer lock, you could end up with one poorly (or maliciously) written static initializer that stops every other thread from doing any class initialization, ever, without even having the cycles I have in this example!
To illustrate, imagine the same example, but replace one of the static initializers with:
static {
while (true) {}
}
Eventually, other threads are probably going to want to do some class initialization, and so the VM might end up starving. This is probably more of a security risk than the other approach.
The one-big-lock approach would also be outside of spec (JLS, Section 12.4.2), so a random JVM couldn't do it without a fairly major JLS revision.
Ultimately, I think it is actually more intuitive to have the initializer lock on the class object instead of having one initializer lock to rule them all.
Also, other puzzlers already illustrate that you can lock up the VM by locking on Thread.class, etc. (I think I remember that one right).
A single static initialiser routine per module would be more like it.
==
The Thread related lock most often cited is the instance lock, which IIRC holding prevents the thread exiting and hence deadlocking in conjunction with join. (Thread exits also cause a quasi-spurious notify on the instance lock.) The lock on Thread.class itself prevents new thread being created as nextThreadID (and nextThreadNum) fail to use AtomicInteger.
Anyway, it's easy to DoS. I accidentally kept making my own X highly unresponsive on Wednesday afternoon. There's plenty of other static locks you can hold if you want a more covert DoS.
Bob --
In the interests of not undercutting Neal and Josh's book, I will tell you that I believe that you are referring to puzzle 85, without further elaborating.
A more interesting solution: in an ideal world, you could do a short analysis of the initializer block (and transitively, of all initializer blocks that might get triggered by that block) to see what classes might be initialized. Then prevent initialization of any of those classes by any other thread while your static initializer runs. In effect, you would just be eagerly acquire all of the locks you might need.
No one else would be able to do it at the same time, of course, and if you couldn't get all of the locks, you would back off and try again.
This implementation might even be legal now, come to think of it.