Recent Posts
Joe User Learns About Java Concurrency: Part 1
One of the most common computer science problems deals with concurrency. Our example tells the story of what a programmer may go through in trying to determine how to write a producer-consumer program that runs on separate threads. Follow Joe User as he tries, fails and improves his application.
Joe User has two threads that want to communicate: a Producer of Great Things, and a Consumer of Great Things. Joe’s first attempt looks something like this (code simplified for illustration):
Attempt 1 (naive busy-waiting)
Producer
GreatThing sharedGreatThing = null; while (true) { sharedGreatThing = nextGreatThing(); // Wait for consumption while (sharedGreatThing != null) { } }
Consumer
while (true) { // Wait for sharedGreatThing while (sharedGreatThing == null) { } useGreatThing(sharedGreatThing); // Tell producer we have consumed it sharedGreatThing = null; }
The program runs for a while and then stops producing output. Joe consults a psychic on stackoverflow.com who tells him that because of caching and compiler optimizations, his variable sharedGreatThing needs to be declared volatile in order for both threads to see the same value. So Joe makes the change:
Attempt 2 (busy-waiting with volatile variable)
Producer
volatile GreatThing sharedGreatThing = null; while (true) { sharedGreatThing = nextGreatThing(); // Wait for consumption while (sharedGreatThing != null) { } }
Consumer
while (true) { // Wait for sharedGreatThing while (sharedGreatThing == null) { } useGreatThing(sharedGreatThing); // Tell producer we have consumed it sharedGreatThing = null; }
The program runs great, but Joe notices that CPU usage is too high because of the two busy-waits on sharedGreatThing, so he adds a bit of a delay to the busy-loops:
Attempt 3 (busy-waiting with delay)
Producer
volatile GreatThing sharedGreatThing = null; while (true) { sharedGreatThing = nextGreatThing(); // Wait for consumption while (sharedGreatThing != null) { sleep(100); } }
Consumer
while (true) { // Wait for sharedGreatThing while (sharedGreatThing == null) { sleep(100); } useGreatThing(sharedGreatThing); // Tell producer we have consumed it sharedGreatThing = null; }
Now the CPU usage is fine, but the throughput has declined because of the delays. Joe does some research and comes up with a way to avoid busy-waiting altogether:
Attempt 4 (naive notify/wait)
Producer
volatile GreatThing sharedGreatThing = null; Object syncObject = new Object(); while (true) { sharedGreatThing = nextGreatThing(); // Tell consumer it’s ready syncObject.notify(); // Wait for consumption syncObject.wait(); }
Consumer
while (true) { // Wait for sharedGreatThing syncObject.wait(); useGreatThing(sharedGreatThing); // Tell producer we have consumed it syncObject.notify(); }
The new program works great most of the time, but sometimes it mysteriously stalls. Joe discovers that the stall is called “deadlock.” He adds some debug statements to his program, and learns that the stalls happen when one thread calls notify() before the other thread calls wait(). Then Joe realizes the horrible truth about Java’s most basic synchronization primitive: Object.notify() does nothing if nobody is waiting; the notification is lost. So Joe makes a mental note: “Be very skeptical whenever you see Object.notify() or Object.wait() in Java code.”
Unable to give up hope on Object.notify() and Object.wait(), Joe adds back in the busy-waiting from Attempt 1:
Attempt 5 (notify/wait with busy-waiting)
Producer
volatile GreatThing sharedGreatThing = null; Object syncObject = new Object(); while (true) { sharedGreatThing = nextGreatThing(); // Tell consumer it’s ready syncObject.notify(); // Wait for consumption while (sharedGreatThing != null) syncObject.wait(); }
Consumer
while (true) { // Wait for sharedGreatThing while (sharedGreatThing == null) syncObject.wait(); useGreatThing(sharedGreatThing); // Tell producer we have consumed it sharedGreatThing = null; syncObject.notify(); }
The program works, but Joe can’t sleep at night knowing that his code is such an ugly hack. The next day, Joe scours the Java API looking for a way for one thread to set a condition that another thread waits for. He says to himself, “Surely this is the most common problem in concurrent programming, and Java must have some kind of Condition class that solves this problem.” He soon finds the Condition interface in the Java API, but when he reads the documentation he discovers that it has the very same problem as before: notifications are lost if nobody is waiting for them. Joe curses Java and continues looking.
Finally he stumbles upon the oddly-named CountDownLatch class and finds a way to make it work:
Attempt 6 (CountDownLatches)
Producer
volatile GreatThing sharedGreatThing = null; CountDownLatch ready = new CountDownLatch(1); CountDownLatch consumed = new CountDownLatch(1); while (true) { sharedGreatThing = nextGreatThing(); // Tell consumer it’s ready ready.countDown(); // Wait for consumption consumed.await(); // Reset latch consumed = new CountDownLatch(1); }
Consumer
while (true) { // Wait for sharedGreatThing ready.await(); // Reset latch ready = new CountDownLatch(1); // Do something with the Great Thing useGreatThing(sharedGreatThing); // Tell producer we have consumed it consumed.countDown(); }
Now the program works great, with high throughput and low CPU usage, but Joe is still dissatisfied with the complexity of the solution. He thinks there must be a better way. He searches the Java API again and finds ArrayBlockingQueue, which makes his next attempt a lot simpler:
Attempt 7 (ArrayBlockingQueue)
Producer
ArrayBlockingQueue<GreatThing> queue = new ArrayBlockingQueue<GreatThing>(1); while (true) { queue.put(nextGreatThing()); }
Consumer
while (true) { useGreatThing(queue.take()); }
This concludes our short tutorial on common Java concurrency issues.
Source code for this article can be found here.