top of page
admin

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.

31 views0 comments

Recent Posts

See All

Commentaires


bottom of page