Java Concurrency (&c)

(Note: I've cribbed this from my doctoral dissertation. I tried to edit it heavily to ease up on the mangled academic syntax required by thesis committees, but I may have missed some / badly edited in places. Let me know if there is something confusingly written or just plain confusing, and I'll try to untangle it.) There are these three concepts, you see. And they are fundamental to correct concurrent programming. When a concurrent program is not correctly written, the errors tend to fall into one of the three categories: atomicity , visibility , or ordering . Atomicity deals with which actions and sets of actions have indivisible effects. This is the aspect of concurrency most familiar to programmers: it is usually thought of in terms of mutual exclusion. Visibility determines when the effects of one thread can be seen by another. Ordering determines when actions in one thread can be seen to occur out of order with respect to another. Let's talk about t

Here's a question I get a lot. Is the following code snippet "thread safe"? volatile int v = 0; Thread 1: v++; Thread 2: v--; The question asks what the possible results of this code are; the questioners usually want the answer "v can only be 0 after this code is run". This isn't the way it works! If you do an increment of a volatile integer, you are actually performing three separate operations: Read the integer to a local. Increment the local. Write the integer back out to the volatile field. So what you really have is this: volatile int v = 0; Thread 1: r1 = v; r2 = r1 + 1; v = r2; Thread 2: r3 = v; r4 = r3 - 1; v = r4; So, if Threads 1 and 2 both read v and see the value 0, then Thread 1 will write 1 to it and Thread 2 will write -1 to it. You are not guaranteed to see the value 0! If you want an atomic increment (or decrement), you have to use the java.util.concurrent.atomic classes , which allow you to create object that represent numbers that can

Those of you who attend JavaOne will know Josh Bloch, Neal Gafter and Bill Pugh's series of highly entertaining Java Puzzlers. Now, for the first time, one of these talks is available to people who are not JavaOne attendees: Josh and Bill gave this year's Java Puzzlers talk at Google. I wouldn't dare spoil the fun by posting any of the puzzlers or their solutions (although Josh blows the surprise on one of them). This is definitely worth the time of anyone who does any programming in Java (and has 1 hour and 14 minutes to kill). I would be remiss if I didn't point out the Java puzzlers web site , where a book is available.

This is another one of those Google talks. This time, it is Mark Moir talking about the transactional memory work he is doing at Sun . It is very useful if you are interested in listening to a strong statement about building hybrid software / hardware transactional memory systems. As someone who has written papers on transactional memory systems, I am still unconvinced that they are the panacea that some of their supporters seems to claim (not Mark, as far as I can tell). Plusses: a) Deadlock avoidance (if the semantics are chosen correctly), b) More easily programmed non-blocking algorithms (if the system is implemented incredibly carefully). Minuses: a) They are still prey to the other problems of parallel shared memory systems, like data races and atomicity problems, b) I have yet to hear a convincing argument as to what their actual semantics should be, especially as regards nested transactions, but even for ordinary transactions. One language design (which shall remain nameles

Ooookay. You are now, presumably, fresh from reading the original post about using AsyncGetCallTrace and the more recent post about how to use SIGPROF in C++ . The next obvious question is... Can I Register a Signal Handler in Java? Um... Kind of! There is an undocumented and unsupported interface called sun.misc.Signal present in most Java implementations. For those of you who have downloaded the JDK, the files live in /src/share/classes/sun/misc. If you import sun.misc.Signal and sun.misc.SignalHandler , you can define a signal handler like this: // Handles SIGHUP Signal.handle(new Signal("HUP"), new SignalHandler() { // Signal handler method public void handle(Signal signal) { System.out.println("Got signal" + signal); } }); You can raise a signal like this: Signal.raise(new Signal("HUP")); You can even register a native signal handler with the Signal.handle0 method (I'll leave that as an exercise for the reader). Having said that

First, read this post about profiling with JVMTI and SIGPROF . A poster on that entry asked me to elaborate a little on exactly what happens when the timer goes off and the signal is raised. In this post, I'll explain that in a little more detail. First, I'll back up a little. Edited to add: Okay, I wrote this whole thing, and very, very briefly answered the actual question at the end. So, if you are interested in the answer to the actual question, and not a long discourse on how to use SIGPROF, look at the end of this entry . What is a Signal? A signal is a very basic method used either to indicate odd behavior in a program synchronously in UNIX-alike systems. If a process divides by zero, for example, a SIGFPE (Floating Point Exception) is synchronously sent to that process. Signals can also be used asynchronously; for example, one process can send another a signal. The other process determines how it wants to handle that signal when it receives it. That process can ei

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

Although I didn't go this year, one of my favorite parts of JavaOne is always Josh Bloch and Neal Gafter's talk on Java Puzzlers. (This year, Bill Pugh, my graduate advisor, stepped in for Neal.) A puzzler is a short snippet of code which has unexpected results, usually because some language or API feature behaves in a strange way. I enjoy them because I always think it is truly wonderful to have the depth of my ignorance exposed. Josh and Neal wrote an excellent book with all of the Java Puzzlers through 2005 , which is highly recommended, and occupies a place of honor in the stack of books in my bathroom. The point of all of this is that occasionally, I will send Josh a multithreaded puzzler, and he will tell me it is no good, because you can't reproduce it every time. Here's one I sent him a couple of months ago. It turns out that the following snippet of code displays the odd behavior 100% of the time under the JVM on my MacBook Pro (JDK 1.5.0_07), and won't

This is a follow up from my previous post about profiling with SIGPROF and JVMTI . There are, in fact, a very large number of ways of getting stack traces out of a JVM. If you send a system-dependent signal to your JVM process, it will spit out a stack dump of every currently live thread. On Solaris and Linux, the signal is a SIGQUIT, which you can get by using kill -3 on the JVM PID (or the PID of the parent JVM process under Linux 2.4), or hitting Control-\. On Windows, you can achieve the same effect by hitting Ctrl-Break on Windows. If you call Thread.dumpStack() , or create a new Throwable , and invoke getStackTrace() on it, you can get the current stack trace programmatically. If you use ThreadMXBean 's getThreadInfo methods, you can get stack traces out of any threads you want. If you use JVMTI 's GetStackTrace or GetAllStackTraces methods, you can get stack trace information in native code. Most of these methods will tell you if your thread can be scheduled by

There is a very good talk by Lawrence Crowl on the upcoming threading changes to C++ . I wrote a brief entry about his talk on C++0x (where they are hoping for x < 10). They have developed heavily on the work done for the Java model, so that they could resolve some of the C++ absurdities that inevitably occur. Hans Boehm, who was heavily involved in the Java effort, has been leading the effort. One neat feature is the proposed atomic keyword. All accesses to a variable declared atomic will be, obviously enough, atomic. It will support features like compare-and-swap and atomic increment (of numerical types). The neat part is that this will work for more than just scalar types (as it does in most current systems). You can declare an entire object to be atomic, and update it all at once. Efficiency depends, of course, on whether the hardware supports such operations, or they need to be emulated in software. As this is C++, they felt the need to overload operators for atomic

I love Wikipedia, I really do. I use it for everything. Well, not everything. For example, if I want a really good piece of chocolate cake, I tend to use flour, sugar, butter, eggs, chocolate, and not Wikipedia at all . For many things, however, Wikipedia cannot be surpassed. Imagine, then, my surprise when I found out that their page on Double-Checked Locking gave an example of a version of double-checked locking that does not work . // Broken -- Do Not Use! class Foo {   private Helper helper = null;   private boolean initialized = false;   public Helper getHelper() {     if (!initialized) {       synchronized(this) {         if (!initialized) {           helper = new Helper();           initialized = true;         }       }     }   return helper; } (For background on Double-Checked Locking, see Bill Pugh's "Double-Checked Locking is Broken" Declaration .) The problem with this code is exactly the same as the problem with all of the other varia

This post is not about the memory model, but, instead, is about being able to get, asynchronously, the stack trace of a currently executing thread out of Sun's Java VM. Getting one synchronously is easy, of course. I was trying to profile some Java applications under Linux, and I wanted to use SIGPROF and JVMTI to find out what code was running at any given second. This is just a posting to document how I did it, as I ended up using some undocumented JVM features, and I can't find a proper reference for them anywhere else. More information as to why you might want to do this is here . JVMTI is the Java Virtual Machine Toolkit Interface. It's a C/C++ interface to the virtual machine that allows you to hook in debuggers and profilers. More information can be found here . SIGPROF is a POSIX signal. The way it is set up under Linux is that you can set a timer that goes off at intervals, and, whenever the timer expires, the SIGPROF signal is sent to the application. The

By the way, gentle reader, in case you haven't noticed, I am running a series of talks at Google. All of them can be found here . Updated July 2015 : They seem to be available on YouTube, now that Google Video is a long forgotten service: They can now be found here .

I've been asked by a couple of people lately about what a compiler can do with code motion around synchronized blocks. The first person asked me about the following example, so let's run with it: x = 1; synchronized(o) { z = z + 1; } y = 1; I may have answered this already (at some point), but I feel free to repeat myself. The JMM has what we call "roach motel" ordering. "Roach Motel" is Black Flag's name for their cockroach trap; in grad school, my apartment had lots and lots and lots of cockroaches, so I find it particularly salient (although I think it was probably Bill Pugh who came up with this association). In the 1980s, the slogan for Black Flag Roach Motels was "Roaches check in, but they don't check out". The memory model is the same: accesses can be moved into synchronized blocks, but they can't be moved out. So, in this case, you can get: x = 1; synchronized(o) { z = z + 1; } y = 1; if we want to move the write to y ea

Adam Welc, from Intel's Programming Systems Lab, came to Google to give a talk about what they are doing in the realm of Software Transactional Memory. He also talks briefly, at the end, about Intel's hardware plans. For those who are interested in such things, this is a talk worth seeing. Click Here.

I forgot to post about this at the time. Cliff Click gave a talk about his lock-free hashtable at Google; it is definitely worth a peek. Available here . There is a very funny thread on the concurrency-interest mailing list this week about "lock-free mania". Apparently, software engineers are going to start choosing "trendy" lock-free data structures for no valid reason, resulting in lots of fragile code. In related news, recursion, memoization and every data structure more complicated than a hash table just started laughing their arses off. B+ Trees were quoted as saying, "I can't count the number of times some database-implementing hack has thrown together a cheap and poorly tested implementation of me because he thinks it is 'trendy' to put together an indexing mechanism. Oh, wait. Zero is a number. Never mind!" In all seriousness, I have actually stopped someone from using a lock-free algorithm where a lock would have been more rea

Okay, so I lied about the contents of my next post. I bet no one even notices. Anyone even reading these? Yeah, right. I was asked a question about fairness. The notion of fairness is one where there are some number of individual entities trying to make progress (in our case, threads), and there is some level of guarantee that this will actually happen. Java has no meaningful fairness guarantee . A Java virtual machine is allowed to let a thread hog all of the CPU time. If I have: Thread 1: while (true); Thread 2: System.out.println("Hi there!"); There is no guarantee that Thread 2 will actually ever print its message. This is so that Java implementors can create cooperative implementations, where context switching only happens when Thread.yield is called, or when blocking occurs. (In point of fact, this applies almost exclusively to the Oracle Java server . The popular VM implementations from Sun and IBM are preemptive.) You could even have a wait loop: Thread 1: wh

Another question from a viewer. We have this code: class C {   private int x;   public C(int v) {     this.x = v;   }   public synchronized int get() {     return this.x;   }   public synchronized void set(int v) {     this.x = v;   } } (For the actual question as it was worded, the short answer is, "yes") The question was one I get a lot. He asked how one thread can safely read the initial write of v to x. That is to say, if we have: Thread 1: globalRef = new C(5); Thread 2: C ref = globalRef; if (ref != null) {   int r1 = ref.x; } How can we change this code to guarantee that the read in Thread 2 will see the value 5 for x (assuming that ref is not null)? Let's back up for a minute, and talk about why, in the code as written, the read in Thread 2 will not see the value 5 for x . Under the Java memory model, for one thread to be guaranteed to see an update made to a variable by another thread, there must be a happens-before relationship between the update and th

The slides from the JMM talk are available here for people's perusal . Enjoy!

A question from a viewer. In my talk, I had a class that looked like this: class Future {  private volatile boolean ready;  private Obj data;  ...  public synchronized void setOnce(Obj o) {   if (ready) throw ...;   data = o;   ready = true;  }  public Object get() {   if (!ready)    return null;   return data;  } } The setOnce method is executed by one thread, and get is executed by another. The point of this example is to examine what difference the volatile modifier on ready makes. In this case, if ready is not marked volatile , the compiler can reorder the writes to data and ready . This has the result that the thread that invokes get can see the value true when it reads ready , even if data has not been set yet. Messy. The questioner asked why setOnce is synchronized. This is somewhat orthogonal to the example, which is why I didn't mention it in the talk. However, I thought it was important enough to include it on the slide. If this method is not synchronize

This fellow is rather handsome, dashing and well-informed . If you would like a primer on the Java memory model, this is a good place to start. I was running out of time toward the end, though, so the last 15 minutes may be a little rushed. Perhaps I'll do a two-part followup at some point. One thing I forgot to say, at the very beginning: The Java memory model defines how threads interact through memory. That's why it's called the Java memory model. It has nothing to do with garbage collection or the object model (except where multithreading is important to those things). If the mood strikes, please feel free to ask questions about the memory model, or anything I said in the talk. I put a note in the talk to ask questions at: http://jeremymanson.blogspot.com/2007/03/jmm-questions-go-here.html .

It is important to read the documentation. Lots of people don't seem to do this, and they get bitten by it. The iterator for java.util.HashSet is documented as follows: Returns an iterator over the elements in this set. The elements are returned in no particular order. Of course, I've now seen code that ignores this, so I thought I would draw a few underlines for the kind of folks who miss it. I wish to state for the record that I did not write this code . It turns out that HashSets (and HashMaps) don't just use the user-defined hashCode as the hash value for objects they are passed. They rehash the number that method returns with their own hash function, to defend against poor quality hash functions. This makes a lot of sense, as many people write bad hash functions. Anyway, this means that when they change this function, objects will hash to different places. Then, when iterators visit these items, they will be visited in a different order. I wouldn't be posting

I gave a talk on the Java memory model this afternoon, and there was a question from the audience which I didn't answer to my own satisfaction, so I am answering it again, for my vast readership of none. At issue was the following bit of code: class Animator implements Runnable {  private volatile boolean stop = false;  public void stop() { stop = true; }  public void run() {   while (!stop) {    oneStep();    try { Thread.sleep(100); } …;   }  }  private void oneStep() { /*...*/ } } This is a pretty common idiom. One thread calls run(), and another thread (eventually) calls stop(), which sets the stop flag to true , and halts the loop. This is fairly intuitive. What is not intuitive about this code is that if the variable is not declared volatile , then regardless of whether another thread calls stop(), this code is not guaranteed to terminate . A compiler (in this case, likely Java's JIT compiler) can: Look at the run() method, Notice that stop is never updated, and the

I just gave a talk in which I said that people could post questions on the Java memory model here. So feel free to post JMM questions below!

Lawrence Crowl gave an interesting talk at Google last week . It would seem that the next revision of the C++ standard is getting: A new memory model, Garbage collection, Concepts (which are more-or-less type checking for templates. This roughly boils down to "generics") Unicode support, A regular expression library, A for-each loop! This is all starting to sound terribly familiar. I'm starting to like that language! Now all they have to do is get rid of multiple inheritance and their awful operator overloading semantics, and replace the STL, and I'll be sold. The new standard will be C++0x. They haven't decided whether x is 8 or 9 yet. Knowing the standards process, I imagine it will be 9. I hope they keep x to single digits... Anyway, in addition to all of this, it is getting move semantics for rvalues, lots of new syntax for initializers, and buckets of other things. Check out the talk for more.