Seven Concurrency Models in Seven Weeks (2014)

Chapter 2. Threads and Locks

Threads-and-locks programming is like a Ford Model T. It will get you from point A to point B, but it is primitive, difficult to drive, and both unreliable and dangerous compared to newer technology.

Despite their well-known problems, threads and locks are still the default choice for writing much concurrent software, and they underpin many of the other technologies we’ll be covering. Even if you don’t plan to use them directly, you should understand how they work.

The Simplest Thing That Could Possibly Work

Threads and locks are little more than a formalization of what the underlying hardware actually does. That’s both their great strength and their great weakness.

Because they’re so simple, almost all languages support them in one form or another, and they impose very few constraints on what can be achieved through their use. But they also provide almost no help to the poor programmer, making programs very difficult to get right in the first place and even more difficult to maintain.

We’ll cover threads-and-locks programming in Java, but the principles apply to any language that supports threads. On day 1 we’ll cover the basics of multithreaded code in Java, the primary pitfalls you’ll encounter, and some rules that will help you avoid them. On day 2 we’ll go beyond these basics and investigate the facilities provided by the java.util.concurrent package. Finally, on day 3 we’ll look at some of the concurrent data structures provided by the standard library and use them to solve a realistic real-world problem.

A Word About Best Practices

We’re going to start by looking at Java’s low-level thread and lock primitives. Well-written modern code should rarely use these primitives directly, using the higher-level services we’ll talk about in days 2 and 3 instead. Understanding these higher-level services depends upon an appreciation of the underlying basics, so that’s what we’ll cover first, but be aware that you probably shouldn’t be using the Thread class directly within your production code.

Day 1: Mutual Exclusion and Memory Models

If you’ve done any concurrent programming at all, you’re probably already familiar with the concept of mutual exclusion—using locks to ensure that only one thread can access data at a time. And you’ll also be familiar with the ways in which mutual exclusion can go wrong, including race conditions and deadlocks (don’t worry if these terms mean nothing to you yet—we’ll cover them all very soon).

These are real problems, and we’ll spend plenty of time talking about them, but it turns out that there’s something even more basic you need to worry about when dealing with shared memory—the Memory Model. And if you think that race conditions and deadlocks can cause weird behavior, just wait until you see how bizarre shared memory can be.

We’re getting ahead of ourselves, though—let’s start by seeing how to create a thread.

Creating a Thread

The basic unit of concurrency in Java is the thread, which, as its name suggests, encapsulates a single thread of control. Threads communicate with each other via shared memory.

No programming book is complete without a “Hello, World!” example, so without further ado here’s a multithreaded version:

This code creates an instance of Thread and then starts it. From this point on, the thread’s run method executes concurrently with the remainder of main. Finally join waits for the thread to terminate (which happens when run returns).

When you run this, you might get this output:

Or you might get this instead:

Which of these you see depends on which thread gets to its println first (in my tests, I saw each approximately 50% of the time). This kind of dependence on timing is one of the things that makes multithreaded programming tough—just because you see one behavior one time you run your code doesn’t mean that you’ll see it consistently.

Joe asks:

Why the Thread.yield?

Our multithreaded “Hello, World!” includes the following line:

According to the Java documentation, yield is:

a hint to the scheduler that the current thread is willing to yield its current use of a processor.

Without this call, the startup overhead of the new thread would mean that the main thread would almost certainly get to its println first (although this isn’t guaranteed to be the case—and as we’ll see, in concurrent programming if something can happen, then sooner or later it will, probably at the most inconvenient moment).

Try commenting this method out and see what happens. What happens if you change it to Thread.sleep(1)?

Our First Lock

When multiple threads access shared memory, they can end up stepping on each others’ toes. We avoid this through mutual exclusion via locks, which can be held by only a single thread at a time.

Let’s create a couple of threads that interact with each other:

Here we have a very simple Counter class and two threads, each of which call its increment method 10,000 times. Very simple, and very broken.

Try running this code, and you’ll get a different answer each time. The last three times I ran it, I got 13850, 11867, then 12616. The reason is a race condition (behavior that depends on the relative timing of operations) in the two threads’ use of the count member of Counter.

If this surprises you, think about what the Java compiler generates for ++count. Here are the bytecodes:

Even if you’re not familiar with JVM bytecodes, it’s clear what’s going on here: getfield #2 retrieves the value of count, iconst_1 followed by iadd adds 1 to it, and then putfield #2 writes the result back to count. This pattern is commonly known as read-modify-write.

Imagine that both threads call increment simultaneously. Thread 1 executes getfield #2, retrieving the value 42. Before it gets a chance to do anything else, thread 2 also executes getfield #2, also retrieving 42. Now we’re in trouble because both of them will increment 42 by 1, and both of them will write the result, 43, back to count. The effect is as though count had been incremented once instead of twice.

The solution is to synchronize access to count. One way to do so is to use the intrinsic lock that comes built into every Java object (you’ll sometimes hear it referred to as a mutex, monitor, or critical section) by making increment synchronized:

Now increment claims the Counter object’s lock when it’s called and releases it when it returns, so only one thread can execute its body at a time. Any other thread that calls it will block until the lock becomes free (later in this chapter we’ll see that, for simple cases like this where only one variable is involved, the java.util.concurrent.atomic package provides good alternatives to using a lock).

Sure enough, when we execute this new version, we get the result 20000 every time.

But all is not rosy—our new code still contains a subtle bug, the cause of which we’ll cover next.

Mysterious Memory

Let’s spice things up with a puzzle. What will this code output?

If you’re thinking “race condition!” you’re absolutely right. We might see the answer to the meaning of life or a disappointing admission that our computer doesn’t know it, depending on the order in which the threads happen to run. But that’s not all—there’s one other result we might see:

What?! How can answer possibly be zero if answerReady is true? It’s almost as if something switched lines 6 and 7 around underneath our feet.

Well, it turns out that it’s entirely possible for something to do exactly that. Several somethings, in fact:

· The compiler is allowed to statically optimize your code by reordering things.

· The JVM is allowed to dynamically optimize your code by reordering things.

· The hardware you’re running on is allowed to optimize performance by reordering things.

It goes further than just reordering. Sometimes effects don’t become visible to other threads at all. Imagine that we rewrote run as follows:

Our program may never exit because answerReady may never appear to become true.

If your first reaction to this is that the compiler, JVM, and hardware should keep their sticky fingers out of your code, that’s understandable. Unfortunately, it’s also unachievable—much of the increased performance we’ve seen over the last few years has come from exactly these optimizations. Shared-memory parallel computers, in particular, depend on them. So we’re stuck with having to deal with the consequences.

Clearly, this can’t be a free-for-all—we need something to tell us what we can and cannot rely on. That’s where the Java memory model comes in.

Memory Visibility

The Java memory model defines when changes to memory made by one thread become visible to another thread.^[6] The bottom line is that there are no guarantees unless both the reading and the writing threads use synchronization.

We’ve already seen one example of synchronization—obtaining an object’s intrinsic lock. Others include starting a thread, detecting that a thread is stopped with join, and using many of the classes in the java.util.concurrent package.

An important point that’s easily missed is that both threads need to use synchronization. It’s not enough for just the thread making changes to do so. This is the cause of a subtle bug still remaining in the code. Making increment synchronized isn’t enough—getCount needs to be synchronized as well. If it isn’t, a thread calling getCount may see a stale value (as it happens, the way that getCount is used in the code is thread-safe, because it’s called after a call to join, but it’s a ticking time bomb waiting for anyone who uses Counter).

We’ve spoken about race conditions and memory visibility, two common ways that multithreaded programs can go wrong. Now we’ll move on to the third: deadlock.

Multiple Locks

You would be forgiven if, after reading the preceding text, you thought that the only way to be safe in a multithreaded world was to make every method synchronized. Unfortunately, it’s not that easy.

Firstly, this would be dreadfully inefficient. If every method were synchronized, most threads would probably spend most of their time blocked, defeating the point of making your code concurrent in the first place. But this is the least of your worries—as soon as you have more than one lock (remember, in Java every object has its own lock), you create the opportunity for threads to become deadlocked.

We’ll demonstrate deadlock with a nice little example commonly used in academic papers on concurrency—the “dining philosophers” problem. Imagine that five philosophers are sitting around a table, with five (not ten) chopsticks arranged like this:

A philosopher is either thinking or hungry. If he’s hungry, he picks up the chopsticks on either side of him and eats for a while (yes, our philosophers are male—women would behave more sensibly). When he’s done, he puts them down.

Here’s how we might implement one of our philosophers:

Lines 14 and 15 demonstrate an alternative way of claiming an object’s intrinsic lock: synchronized(object).

On my machine, if I set five of these going simultaneously, they typically run very happily for hours on end (my record is over a week). Then, all of a sudden, everything grinds to a halt.

After a little thought, it’s obvious what’s going on—if all the philosophers decide to eat at the same time, they all grab their left chopstick and then find themselves stuck—each has one chopstick, and each is blocked waiting for the philosopher on his right. Deadlock.

Deadlock is a danger whenever a thread tries to hold more than one lock. Happily, there is a simple rule that guarantees you will never deadlock—always acquire locks in a fixed, global order.

Here’s one way we can achieve this:

Joe asks:

Can I Use an Object’s Hash to Order Locks?

One piece of advice you’ll often see is to use an object’s hash code to order lock acquisition, such as shown here:

This technique has the advantage of working for any object, and it avoids having to add a means of ordering your objects if they don’t already define one. But hash codes aren’t guaranteed to be unique (two objects are very unlikely to have the same hash code, but it does happen). So personally speaking, I wouldn’t use this approach unless I really had no choice.

Instead of holding on to left and right chopsticks, we now hold on to first and second, using Chopstick’s id member to ensure that we always lock chopsticks in increasing ID order (we don’t actually care what IDs chopsticks have—just that they’re unique and ordered). And sure enough, now things will happily run forever without locking up.

It’s easy to see how to stick to the global ordering rule when the code to acquire locks is all in one place. It gets much harder in a large program, where a global understanding of what all the code is doing is impractical.

The Perils of Alien Methods

Large programs often make use of listeners to decouple modules. Here, for example, is a class that downloads from a URL and allows ProgressListeners to be registered:

Because addListener, removeListener, and updateProgress are all synchronized, multiple threads can call them without stepping on one another’s toes. But a trap lurks in this code that could lead to deadlock even though there’s only a single lock in use.

The problem is that updateProgress calls an alien method—a method it knows nothing about. That method could do anything, including acquiring another lock. If it does, then we’ve acquired two locks without knowing whether we’ve done so in the right order. As we’ve just seen, that can lead to deadlock.

The only solution is to avoid calling alien methods while holding a lock. One way to achieve this is to make a defensive copy of listeners before iterating through it:

This change kills several birds with one stone. Not only does it avoid calling an alien method with a lock held, it also minimizes the period during which we hold the lock. Holding locks for longer than necessary both hurts performance (by restricting the degree of achievable concurrency) and increases the danger of deadlock. This change also fixes another bug that isn’t related to concurrency—a listener can now call removeListener within its onProgress method without modifying the copy of listeners that’s mid-iteration.

Day 1 Wrap-Up

This brings us to the end of day 1. We’ve covered the basics of multithreaded code in Java, but as we’ll see in day 2, the standard library provides alternatives that are often a better choice.

What We Learned in Day 1

We covered how to create threads and use the intrinsic locks built into every Java object to enforce mutual exclusion between them. We also saw the three primary perils of threads and locks—race conditions, deadlock, and memory visibility, and we discussed some rules that help us avoid them:

· Synchronize all access to shared variables.

· Both the writing and the reading threads need to use synchronization.

· Acquire multiple locks in a fixed, global order.

· Don’t call alien methods while holding a lock.

· Hold locks for the shortest possible amount of time.

Day 1 Self-Study

Find

· Check out William Pugh’s “Java memory model” website.

· Acquaint yourself with the JSR 133 (Java memory model) FAQ.

· What guarantees does the Java memory model make regarding initialization safety? Is it always necessary to use locks to safely publish objects between threads?

· What is the double-checked locking anti-pattern? Why is it an anti-pattern?

Do

· Experiment with the original, broken “dining philosophers” example. Try modifying the length of time that philosophers think and eat and the number of philosophers. What effect does this have on how long it takes until deadlock? Imagine that you were trying to debug this and wanted to increase the likelihood of reproducing the deadlock—what would you do?

· (Hard) Create a program that demonstrates writes to memory appearing to be reordered in the absence of synchronization. This is difficult because although the Java memory model allows things to be reordered, most simple examples won’t be optimized to the point of actually demonstrating the problem.

Day 2: Beyond Intrinsic Locks

Day 1 covered Java’s Thread class and the intrinsic locks built into every Java object. For a long time this was pretty much all the support that Java provided for concurrent programming. Java 5 changed all that with the introduction of java.util.concurrent. Today we’ll look at the enhanced locking mechanisms it provides.

Intrinsic locks are convenient but limited.

· There is no way to interrupt a thread that’s blocked as a result of trying to acquire an intrinsic lock.

· There is no way to time out while trying to acquire an intrinsic lock.

· There’s exactly one way to acquire an intrinsic lock: a synchronized block.

· This means that lock acquisition and release have to take place in the same method and have to be strictly nested. Note that declaring a method as synchronized is just syntactic sugar for surrounding the method’s body with the following:

ReentrantLock allows us to transcend these restrictions by providing explicit lock and unlock methods instead of using synchronized.

Before we go into how it improves upon intrinsic locks, here’s how ReentrantLock can be used as a straight replacement for synchronized:

The try … finally is good practice to ensure that the lock is always released, no matter what happens in the code the lock is protecting.

Now let’s see how it lifts the restrictions of intrinsic locks.

Interruptible Locking

Because a thread that’s blocked on an intrinsic lock is not interruptible, we have no way to recover from a deadlock. We can see this with a small example that manufactures a deadlock and then tries to interrupt the threads:

This program will deadlock forever—the only way to exit it is to kill the JVM running it.

Joe asks:

Is There Really No Way to Kill a Deadlocked Thread?

You might think that there has to be some way to kill a deadlocked thread. Sadly, you would be wrong. All the mechanisms that have been tried to achieve this have been shown to be flawed and are now deprecated.^[7]

The bottom line is that there is exactly one way to exit a thread in Java, and that’s for the run method to return (possibly as a result of an InterruptedException). So if your thread is deadlocked on an intrinsic lock, you’re simply out of luck. You can’t interrupt it, and the only way that thread is ever going to exit is if you kill the JVM it’s running in.

There is a solution, however. We can reimplement our threads using ReentrantLock instead of intrinsic locks, and we can use its lockInterruptibly method:

This version exits cleanly when Thread.interrupt() is called. The slightly noisier syntax of this version seems a small price to pay for the ability to interrupt a deadlocked thread.

Timeouts

ReentrantLock lifts another limitation of intrinsic locks: it allows us to time out while trying to acquire a lock. This provides us with an alternative way to solve the “dining philosophers” problem from day 1.

Here’s a Philosopher that times out if it fails to get both chopsticks:

Instead of using lock, this code uses tryLock, which times out if it fails to acquire the lock. This means that, even though we don’t follow the “acquire multiple locks in a fixed, global order” rule, this version will not deadlock (or at least, will not deadlock forever).

Livelock

Although the tryLock solution avoids infinite deadlock, that doesn’t mean it’s a good solution. Firstly, it doesn’t avoid deadlock—it simply provides a way to recover when it happens. Secondly, it’s susceptible to a phenomenon known as livelock—if all the threads time out at the same time, it’s quite possible for them to immediately deadlock again. Although the deadlock doesn’t last forever, no progress is made either.

This situation can be mitigated by having each thread use a different timeout value, for example, to minimize the chances that they will all time out simultaneously. But the bottom line is that timeouts are rarely a good solution—it’s far better to avoid deadlock in the first place.

Hand-over-Hand Locking

Imagine that we want to insert an entry into a linked list. One approach would be to have a single lock protecting the whole list, but this would mean that nobody else could access it while we held the lock. Hand-over-hand locking is an alternative in which we lock only a small portion of the list, allowing other threads unfettered access as long as they’re not looking at the particular nodes we’ve got locked. Here’s a graphical representation: