Chapter 8. Many cooks in the kitchen: Thread safety

This chapter covers

• Recognizing and avoiding deadlocks and race conditions
• Using explicit locks
• Using lock-free synchronization
• Designing immutable classes

The plan for this chapter is to make your implementation thread-safe. For a class to be thread-safe, multiple threads should be able to interact with the objects of that class with no explicit synchronization. In other words, a thread-safe class takes care of the synchronization issues. The clients can just freely invoke any class method, even simultaneously on the same object, with no adverse effects. The design-by-contract methodology I presented in chapter 5 allows you to precisely characterize what an adverse effect would be: the violation of a postcondition or an invariant.

Admittedly, thread safety is not as general a property as efficiency or readability. However, its importance is on the rise because of the ubiquity of parallel hardware. Compared with other functional defects, lack of thread safety can go unnoticed for much longer. Some synchronization defects become apparent only in special circumstances, when the timing and the scheduling are just right (or wrong) for a race condition to mess up the state of an object or for a deadlock to freeze your program. That’s one more reason to read this chapter carefully!

This chapter assumes you’re familiar with basic multithreading in Java, such as creating threads and using synchronized blocks to achieve mutual exclusion. As a self-test, consider working through exercise 1 at the end of this chapter. It’ll remind you of the main properties of the synchronized keyword.

8.1. Challenges to thread safety

The two main enemies of thread safety are race conditions and deadlocks. Generally speaking, the first arises from too little synchronization and the latter from too much of it. A race condition occurs when two operations requested concurrently by different threads may lead to at least one operation violating its postcondition. It’s easy to obtain a race condition by manipulating shared objects with no synchronization.

Say that multiple threads share an instance of the following class:

public class Counter {
   private int n;
   public void increment() { n++; }
   ...
}

If two threads invoke increment at about the same time, it’s possible for the counter to be incremented once, instead of twice.^[1] That’s because n++ is not an atomic operation. It’s roughly equivalent to the following sequence of three atomic operations:

¹

It’s also possible that the two threads will see different values for the counter because of visibility issues that are unrelated to the race condition.

1. Copy the current value of n on a register (for a register machine) or on the stack (for the JVM).
2. Increment it by one.
3. Store the updated value of n back into the Counter object to which it belongs.

If two threads execute the first step at the same time (or, in any case, before either of them has had the opportunity to store the updated value in the third step), both threads will read the same old value for n, increment it, and then store the same n+1 value. That is, the same value n+1 will be stored twice.

You can check this by yourself if you run the class eis.chapter8.threads.Counter from the online repository (https://bitbucket.org/mfaella/exercisesinstyle). It launches five threads that call the increment method on the same object 1,000 times each. At the end, the program prints the value of the counter. On my laptop, on three executions I got the following outputs:

4831
4933
3699

As you can see, race conditions are extremely common under these conditions. In the last execution, over 26% of the increments were lost due to a race condition. As you might know, you solve race conditions by introducing synchronization primitives, such as mutexes or monitors, that render all calls to increment mutually exclusive: if one such call is executing on a given Counter object, any other call to the same object must wait for the current one to finish before it can enter the method. In Java, the synchronized keyword constitutes the basic form of synchronization.

At the other extreme, unregulated synchronization may lead to a deadlock, a situation when two or more threads become permanently stuck, waiting for each other in a cyclic fashion. An example of this phenomenon arises in section 8.2.

In the rest of this chapter, you’ll learn how to recognize and avoid both race conditions and deadlocks, using low-level synchronization primitives like synchronized blocks and explicit locks. In the spirit of this book, I’ll stick to a practical and to-the-point presentation tailored to the water container running example, which turns out to require an interesting and nonstandard form of synchronization.

To get a more comprehensive understanding of multithreading issues and solutions, you should review the fundamental memory model rules of your language of choice. In Java, the best reference is still the book Java Concurrency in Practice, mentioned in the Further reading section. Moreover, you should become familiar with the higher level concurrency facilities that your language offers.

Since the beginning, Java has been at the forefront of multithreading support, thanks to its native support for threads. In recent years, such support has been steadily increasing, with three progressively higher levels of abstraction, illustrated in figure 8.1:

• Executor services (Java 5). A small set of classes and interfaces that take care of creating the appropriate number of threads to perform user-defined tasks. Check out the interface ExecutorService and the class Executors from the package java.util.concurrent.
• The fork-join framework (Java 7). A smart way to split a complex computation among multiple threads (fork) and merge their results into a single value (join). For starters, check out the ForkJoinPool class.
• Parallel streams (Java 8). A powerful library for applying uniform operations to sequential data providers. You can start from the Stream class, but you’d be better off picking up a book from the Further reading section to appreciate the many subtleties of this library.

Figure 8.1. The main layers of multithreading support in Java, labeled with the Java version in which they were initially introduced (or fixed, in the case of the JMM). This chapter only deals with the three lowest levels.

8.1.1. Levels of concurrency

If thread safety was truly our only objective, we could apply a simple technique that works in all circumstances and with all self-contained classes: use a global lock to synchronize all methods. In Java, locks are implicitly provided with each object, so as a global lock for all containers, we can use the one attached to the object Container.class.^[2] Then, we can wrap the body of all methods in the Container class in a synchronized block, like this:

²

That’s the same lock that any synchronized static method of the class would use.

 synchronized (Container.class) {
    ...  1 Method body
}

In this way, all access to the class is fully serialized. That is, even if method calls arrive from different threads to different objects, only one method at a time can enter its body. This coarse-grained approach is extremely harsh and voids any performance gain that might have come from concurrency. Worse, the lock acquire and release operations may actually slow down even a single-threaded program.^[3] We can call this technique class-level concurrency and put it at one end of a spectrum, whose notable cases are summarized in table 8.1.

³

Optimized runtime environments may employ techniques to avoid those overheads. For example, HotSpot’s biased locking recognizes when a single thread mostly owns a lock and optimizes that case.

Table 8.1. Common concurrency policies for a class, ordered by increasing amount of concurrency allowed. The second column describes the operations that are allowed to proceed simultaneously. The third column identifies the locks that are needed to implement that policy.

Ideally, we’d like to ensure thread safety while maintaining as much concurrency as possible. To this aim, proceed in two steps:

1. Specification step— Figure out how much concurrency your class(es) can support, that is, what methods or code fragments can run simultaneously with no race conditions arising. In practice, those are the code fragments that operate on different data.
2. Implementation step— Add synchronization primitives that allow the legal cases of concurrency while serializing the illegal ones.

Whenever the objects of a class are isolated (that is, they don’t contain references to each other or to shared objects of other types), multiple methods can run in parallel, as long as they operate on different objects, and the proper thread-safe implementation involves simply slapping synchronized on all instance methods. This is the common case of object-level concurrency, illustrated by plain old classes like the following:

   public class Employee {
      private String name;
      private Date hireDate;
      private int monthlySalary;
      ...
      public synchronized increaseSalary(int bonus) {
         monthlySalary += bonus;
      }
   }

By the way, you can improve even such a simple case: best practices dictate not declaring entire methods synchronized because that may come into conflict with an Employee being used as a monitor by a client. It’s more robust, but slightly more cumbersome and space-inefficient, to use a private field as the monitor. In this way, being synchronized becomes a private implementation matter, as it should be:

   public class Employee {
      private String name;
      private Date hireDate;
      private int monthlySalary;
      private Object monitor = new Object();
      ...
      public increaseSalary(int bonus) {
         synchronized (monitor) {
            monthlySalary += bonus;
         }
      }
   }

Moving on to the third row of table 8.1, method-level concurrency is quite uncommon, and for good reasons. It makes sense only when all methods are independent of one another. For two methods of the same object to be independent, they need to operate on different parts of the object state. If all methods in a class are mutually independent, that’s a sign of poor cohesion; you’ve put together information that belongs to different classes. Before mulling over the concurrency policy, you’d better split that class into multiple classes.

lock (object) {
   ...
}

[MethodImpl(
 MethodImplOptions.Synchronized)]

Pop Quiz 1

Who cares about the concurrency policy of a class—its users or its implementors?

Finally, the anarchy level generally applies to classes that are either stateless or immutable. In both cases, concurrent usage by multiple threads is innocuous. For example, comparators (that is, objects implementing the Comparator interface) are usually stateless. They can be freely shared among threads with no special precautions. I’ll talk about immutability in section 8.4.

Our water containers sport a custom concurrency level, halfway between class-level and object-level, requiring a little more effort for us to both describe and implement them, as demonstrated in the following sections.

8.1.2. A concurrency policy for water containers

No matter the implementation, containers need to reference each other in some way; otherwise, they can’t fulfill their contractual obligations. Specifically, the methods con nectTo and addWater must be able to change the state of multiple containers. As a result, it’s not enough to lock the current object to obtain thread safety.

The connectTo method is the trickiest because it modifies two groups of containers, eventually merging them into a single one. To avoid race conditions, no other thread should access any container that belongs to either of the two groups being merged. More precisely, reading the state of such a container with getAmount may be allowed, but changing it with addWater or connectTo should definitely be forbidden, that is, delayed until the first connectTo terminates.

Summarizing, we obtain the following concurrency policy for the Container class:

1. The class must be thread-safe.
2. If containers a and b don’t belong to the same group, any method invocation on a can run concurrently with any method invocation on b.
3. All other pairs of invocations require synchronization.

Only property 1 is intended for the users of the Container class. It tells clients that they can use the class from different threads simultaneously, without worrying about synchronization issues.

Properties 2 and 3, instead, are destined for the Container class developers and set out the target level of supported concurrency. Relative to table 8.1, this level lies between class-level and object-level concurrency because it allows concurrency between different groups of objects. In the rest of this chapter, we’ll examine different ways to achieve this objective using Java synchronization primitives, namely synchronized, volatile, and the ReentrantLock class.

8.2. Dealing with deadlocks

Rather than modifying Reference, we’ll work with Speed1 from chapter 3, which is more efficient and more suited to thread safety. Recall the basic structure of Speed1: each container holds a reference to a group object, which in turn knows the amount of water in each container and the set of all members of that group, as shown in the following snippet:

public class Container {
   private Group group = new Group(this);

   private static class Group {
      double amountPerContainer;
      Set<Container> members;

      Group(Container c) {
         members = new HashSet<>();
         members.add(c);
      }
   }

It’s quite clear from the policy specification that groups are the synchronization units of our class. In practice, connectTo should acquire the monitors of the two groups being merged. Anytime a method needs more than one monitor, the risk of a deadlock arises. A deadlock is a condition where two or more threads are stuck, each one waiting for a monitor that another one holds. They’re waiting for each other in a cyclic pattern, forever.

The simplest deadlock scenario occurs when thread 1 attempts to acquire monitor A and then monitor B, whereas thread 2 requests them in the opposite order. An unlucky scheduling may cause thread 1 to successfully acquire A and then thread 2 to successfully acquire B before thread 1 does. At that point, the threads are stuck in a deadlock. This scenario can easily play out with the following natural but faulty implementation of connectTo:

   public void connectTo(Container other) {
      synchronized (group) {
         synchronized (other.group) {
            ...   1 The actual operation here
         }
      }
   }

If one thread invokes a.connectTo(b) and another thread simultaneously invokesb.connectTo(a), they risk the textbook case of deadlock. Generally speaking, you have two ways to avoid such deadlocks without restricting the class clients in any way: atomic lock sequences or ordered lock sequences.

Pop Quiz 2

Can you get into a deadlock if each thread is guaranteed to hold one lock at a time?

8.2.1. Atomic lock sequences

First, you can render atomic the sequence of lock acquisitions that generates that deadlock risk. This entails using an extra lock—let’s call it globalLock—to make sure that no two such sequences can run concurrently. In this way, a sequence of lock requests can start only when no other sequence is in progress. If a sequence blocks because one of the required locks is busy, it’ll block while holding the global lock, so no other sequence can start and risk going into a deadlock. Notice that even sequences that require a completely different set of locks must stall until the current sequence completes. This is a very cautious approach that avoids deadlocks by limiting the amount of concurrency allowed.

In Java, the global lock can’t be an implicit lock because by design implicit locks must be released in the opposite order in which they were acquired. So, if globalLock is acquired before monitor A, it can’t be released before the latter. In other words, the following fragment is faulty:

   synchronized (globalLock) {
      synchronized (group) {
         synchronized (other.group) {
   }  1 We’d like to release globalLock here.
            ...  2 The actual operation here
         }
      }

Despite the misleading indentation, the first right brace is releasing other.group, not globalLock as intended. Explicit locks provided in the Java API by the ReentrantLock class overcome this limitation. A ReentrantLock is more flexible than an implicit lock: in particular, it can be freely acquired and released at any time using its lock and unlock methods. In this approach, we’d add an explicit lock to the class:

private static final ReentrantLock globalLock = new ReentrantLock();

Then, we’d use that global lock to guard the beginning of connectTo, until the two implicit locks are acquired, as you can see in the following listing.

Listing 8.1. AtomicSequence: Preventing deadlocks by an atomic lock sequence

   public void connectTo(Container other) {
      globalLock.lock();
      synchronized (group) {
         synchronized (other.group) {
            globalLock.unlock();
            ...  1 Compute new amount
            group.members.addAll(other.group.members);
            group.amountPerContainer = newAmount;
            for (Container x: other.group.members)
               x.group = group;
         }
      }
   }

Because only one thread can hold globalLock at any given time, only one thread can be in the middle of the sequence of two synchronized lines, and no deadlock can arise.

Pop Quiz 3

What happens if an exception is thrown from inside a synchronized block? What if instead the thread throwing the exception owns a ReentrantLock?

8.2.2. Ordered lock sequences

The second and more efficient way to avoid deadlocks is to order monitors in a global sequence known to all threads, and make sure that all threads request them in that order. You can establish such a global sequence by assigning a unique integral ID to each group. In turn, you obtain unique IDs by introducing a global (that is, static) counter that’s incremented for each new instance and provides the ID for every new object.

You need to properly synchronize access to such a shared counter; otherwise, a race condition affecting two simultaneous increments may result in two groups having the same ID. The easiest solution is to employ the class AtomicInteger, one of the atomic variable types in figure 8.1. Objects of that class are thread-safe mutable integers. As its name suggests, the instance method incrementAndGet is perfect for generating unique sequential IDs in a thread-safe manner.

The following listing shows the beginning of the Container class, including its fields and the nested class. It’s very similar to Speed1, except for the addition of unique group IDs.

Listing 8.2. OrderedSequence: Preventing deadlocks by ordered locking

public class Container {
   private Group group = new Group(this);

   private static class Group {
      static final AtomicInteger nGroups =
         new AtomicInteger();  1 Total number of groups so far
      double amount;
      Set<Container> elems = new HashSet<>();
      int id = nGroups.incrementAndGet();  2 Automatically assigned progressive ID

      Group(Container c) {
         elems.add(c);
      }
   }

Each new Group object now receives a unique progressive ID, starting from 1, just like an auto-increment field in a database. As you can see in listing 8.3, the method connectTo will request the two monitors in the order of their IDs, thus avoiding deadlocks.

Listing 8.3. OrderedSequence: Method connectTo.

   public void connectTo(Container other) {
      if (group == other.group) return;
      Object firstMonitor, secondMonitor;
      if (group.id < other.group.id) {
         firstMonitor  = group;
         secondMonitor = other.group;
      } else {
         firstMonitor  = other.group;
         secondMonitor = group;
      }
      synchronized (firstMonitor) {
         synchronized (secondMonitor) {
            ...  1 Computes new amount
            group.members.addAll(other.group.members);
            group.amountPerContainer = newAmount;
            for (Container x: other.group.members)
               x.group = group;
         }
      }
   }

If you have some way to assign unique IDs to the objects that you need to lock, this is the way to go to avoid deadlocks. If instead those objects don’t come with unique IDs and you can’t modify their class, the global locking technique from the previous section may be your only option.

Pop Quiz 4

Why does the ordered locking technique prevent deadlocks?

8.2.3. A hidden race condition

The two techniques from sections 8.2.1 and 8.2.2 are general ways to avoid deadlocks, but in the case of water containers, they’re affected by subtle race conditions. The problem is that the group objects that double as monitors can be replaced by a simultaneous connection operation. As a result, an invocation to connectTo may end up acquiring the lock of an obsolete group that’s no longer associated with any container. In that case, the operations that connectTo performs won’t be mutually exclusive with other operations on the new group of this container.

It’s quite straightforward to recognize this problem in the ordered lock technique from section 8.2.2. The first lines of connectTo, comparing group IDs and establishing the order between monitors, aren’t guarded by any synchronization. Hence, it may happen that either of the two groups changes before the current thread has a chance to acquire the corresponding monitor. The natural solution is to add a global lock that protects that first phase, from the beginning of the method to just after the two monitors have been acquired. This would bring the code close to our other solution, the atomic lock sequence. But globally locking the first phase renders useless the whole lock ordering machinery because the global lock is enough to prevent deadlocks! At the end of the day, you’d end up with exactly the atomic lock sequence version. But is the latter free from race conditions?

Close scrutiny or focused testing reveal that it’s not. It’s still possible for connectTo to acquire the wrong monitor and break the stated concurrency policy, as shown in figure 8.2. Indeed, suppose thread 1 starts a.connectTo(b) but is preempted^[4] before updating the group of b, that is, before the assignment b.group = a.group. This may happen for a number of reasons, the simplest being that some other thread is scheduled to run on the same hardware core. After all, your JVM doesn’t run in isolation. It shares your hardware with an OS and plenty of other processes.

⁴

That is, its execution is suspended by the OS scheduler.

Figure 8.2. A race condition affecting the atomic lock sequence connectTo implementation

At this point, suppose that thread 2 runs b.connectTo(c). The second thread gets stuck on synchronized (b.group), because the first thread holds that monitor. When the first thread releases it, the second thread will acquire it, even though that monitor doesn’t correspond to any group anymore because it’s the monitor of an obsolete group object that’s ready for GC. The second thread is under the “illusion” that it’s holding the monitor for the group of b, whereas it’s actually holding a stale monitor. Its subsequent operations won’t be mutually exclusive with other operations on the current group of b.

This scenario is depicted in figure 8.2, and solved in the next section, which finally presents a truly thread-safe water container implementation.

8.3. Thread-safe containers    [ThreadSafe]

To get a truly thread-safe implementation, we start with OrderedSequence (listings 8.2 and 8.3), which is free from deadlocks and allows full parallelism between method calls involving different groups of containers, and we set out to solve the race conditions described in the previous section. The new implementation, denoted by Thread-Safe, has the same fields and the same nested Group class as OrderedSequence, and, like OrderedSequence, it doesn’t need any global locking when connecting two containers. However, it may try to acquire the right monitors multiple times, as explained in the following section.

8.3.1. Synchronizing connectTo

To remove the race condition, you must make sure that connectTo acquires the monitors of the current groups of the two containers being connected. To do this without sacrificing too much concurrency, you need to shift your mindset from classic lock-based synchronization to a form of lock-free synchronization. Unless you use a global lock and lose all parallelism, you can never be sure to acquire the right monitors on your first attempt. You need to try multiple times, as shown in the following listing, until you recognize that the acquired monitors are the current ones. That’s why you should wrap the ordered lock sequence code borrowed from OrderedSequence into a potentially infinite loop.

Listing 8.4. ThreadSafe: Method connectTo

public void connectTo(Container other) {
   while (true) {
      if (group == other.group) return;
      Object firstMonitor, secondMonitor;
      if (group.id < other.group.id) {
         firstMonitor  = group;
         secondMonitor = other.group;
      } else {
         firstMonitor  = other.group;
         secondMonitor = group;
      }
      synchronized (firstMonitor) {  1 Tentatively acquires monitors
         synchronized (secondMonitor) {
            if ((firstMonitor == group && secondMonitor == other.group) ||
                (secondMonitor == group && firstMonitor == other.group)) {
               ...  2 The actual operation here
               return;
            }
         }
      }
       3 At least one of the two monitors was stale---retry.
   }
}

In every iteration, you tentatively acquire the two chosen monitors, only to immediately check whether they’re current, that is, whether their respective containers still point to them as their groups. If the check is positive, you perform the usual group merging operations (omitted in the listing). Otherwise, you release the two monitors and try again by rereading the group fields of the two containers being merged. You can call this an optimistic approach to synchronization: you assume that no other thread is messing with these two containers. If your assumption is violated, you try again.

do {
   old = dst
   src = some new value, usually based on old
} while (cas(src, dst, old) == failed)

8.3.2. Synchronizing addWater and getAmount

Let’s move on to the remaining two methods: addWater and getAmount. addWater exhibits a structure similar to the one of connectTo. Indeed, even when acquiring the monitor of a single group, it’s possible that another thread will replace the group of this container in the meantime.

The reason is that entering even the simplest synchronized block isn’t an atomic operation. For a detailed analysis we need to go behind the scenes of the Java code and take a look at the corresponding bytecode.

For example, suppose addWater started as follows:

   public void addWater(double amount) {
      synchronized (group) {   1
         ...
      }
   }

The second line translates to the following bytecode:

As you can see, what appears like an atomic lock acquisition is in fact translated into a short sequence of bytecode instructions whose last instruction actually requests the monitor. If another thread changes the group of this container between bytecode lines 2 and 5, the current thread will acquire the monitor of an obsolete group, and its subsequent operations won’t be mutually exclusive with other operations on the new group of this container. In that case, the culprit must be a concurrent invocation to connectTo because that’s the only method modifying the group references.

We must try multiple times, as shown in the following listing, until we’re certain that the acquired monitor is current.

Listing 8.5. ThreadSafe: Method addWater

   public void addWater(double amount) {
      while (true) {
         Object monitor = group;
         synchronized (monitor) {    1 Tentatively acquires the monitor
            if (monitor == group) {  2 The monitor is up-to-date.
               double amountPerContainer = amount / group.elems.size();
               group.amount += amountPerContainer;
               return;
            }
         }
          3 The monitor was stale---retry.
      }
   }

Finally, as you can see in listing 8.6, getAmount is a simple getter, so you may be wondering whether it’s really necessary to apply any synchronization to it. After all, it only reads a primitive value. In the worst case, it may read a slightly stale value that’s just being modified. Right? Wrong. The Java memory model specifies that even a single read of a double value isn’t an atomic operation. That is to say that the 64-bit read operation may be divided into two 32-bit reads, and those two reads may be interleaved with a write operation by another thread. Without the synchronized block, you might end up reading an absurd value, whose higher 32 bits are new and whose lower 32 bits are stale, or vice versa. By the way, adding the volatile modifier to the amount field also would solve this problem by rendering the read operation atomic.

Listing 8.6. ThreadSafe: Method getAmount

   public double getAmount() {
      synchronized (group) {
         return group.amount;
      }
   }

For getAmount, you don’t need to worry about the accessed group being stale because that would only give us a slightly out-of-date value, but not a wrong one. In a multi-threaded environment, even the now-current value can be updated and become stale at any time. Given that fact, it’s pointless to spend extra effort to ensure that we’re reading the amount from the current group.

Compare this situation with addWater. If you update a stale group with addWater, you get an inconsistency because you’d be adding water to a group that that no container points to. The added water would vanish, and the method would have violated its postcondition.

8.4. Immutability    [Immutable]

Thread unsafety ultimately arises from one thread writing to shared memory while other threads are reading from or writing to the same memory location. An entirely diffent approach to obtaining thread safety is to ensure that all the shared objects are immutable, so the previous situation can’t occur, because no thread can modify an object after it has been initialized and shared. Unfortunately, this approach doesn’t play well with the API we established in chapter 1. The simple fact that you can invoke getA mount twice on the same container and get two different values back implies that containers have mutable state. Mutable objects are the default in Java, even though the language features a couple of immutable classes in pretty prominent places, like String and Integer. In fact, those standard classes make sure that all Java programmers have some experience with immutable objects and know that it’s possible to base their programs on them.

As a refresher, a class is immutable if all its fields are final, and all the references it holds point to other immutable classes.^[5] Whereas a method of a mutable class can change the state of the current object, the analogous method of an immutable class creates and returns a new object of the same type, with the desired content.

⁵

To be precise, a class can be immutable even if no field is final, but the final keyword ensures that it’s so. This is the same distinction between a final and an effectively final variable, the latter property being relevant to inner class visibility issues.

Let’s quickly review this principle in action in the standard String and Integer classes. Those classes offer no method that modifies their content. To aid the programmer, however, this immutability is cleverly disguised by compile-time mechanisms that allow you to write, for a String s and an Integer n:

 s += " and others";
 n++;

As you probably know, despite appearances, the previous two lines don’t modify the objects that s and n point to, but rather create new objects that replace the old ones. For example, the compiler turns the innocent-looking string concatenation into the following eyesore, which even involves an entirely different class:

StringBuilder temp = StringBuilder();
temp.append(s);
temp.append(" and others");
s = temp.toString();

Similarly, for an Integer increment, the compiler generates bytecode that unboxes the value, increments it, and then wraps it again via a static factory method.^[6] That process looks similar to the following Java snippet:

⁶

Compared to a constructor, a factory method is not forced to return a new object. In fact, valueOf caches all integers in the range –128 to 127.

int value = n.intValue();        1 Unwrapping
n = Integer.valueOf(value + 1);  2 Rewrapping

Back to our actual purposes, we’re discussing immutable classes in this chapter because they’re automatically thread-safe. Multiple threads can invoke methods on the same object, and those invocations can’t step on each other’s toes, simply because they can’t write to the same memory. In particular, if one of those methods is supposed to return a complex value, it’ll do so by creating a new object that other threads can’t possibly see until the method actually returns it.

Pop Quiz 5

Why are immutable classes automatically thread-safe?

8.4.1. The API

Let’s break the confines of the API I established in chapter 1 and sketch the public interface for an immutable version of our containers, offering the same services as the mutable one. Assuming that containers are immutable, the addWater method must return a new container with the updated water amount, but this isn’t enough. If the current container is connected to other ones, new objects with an updated water amount must replace all those other containers. Imagine how cumbersome it would be to invoke addWater and receive as a result the set of all updated containers that are connected to the current one. We need to put the API through a more extensive refactoring.

The idea is to base the API design on a larger perspective, in which the main object we manipulate is a system of containers. Each system is created with a fixed number n of containers, indexed from 0 to n – 1, and is itself immutable. Operations that change the state of even a single container must appear to return a new system of containers. Whether the new object internally shares data with the old one is an implementation issue that I’ll discuss later.

As a first attempt, let’s draft an API supporting a ContainerSystem class and a Con tainer class. The following snippet shows how you might go about creating a system of 10 containers and then adding 42 units of water to the sixth one. Since these objects are immutable, adding water returns a new system of containers.

ContainerSystem s1 = new ContainerSystem(10);  1 A new system of 10 containers
Container c = s1.getContainer(5);  2 The sixth container
ContainerSystem s2 = s1.addWater(c, 42);  3 A new system where c holds 42 units of water

This type of behavior, when a mutating operation returns a new object, is called a persistent data structure. The name expresses the fact that such data structures make available to the clients their entire history. For example, in the previous snippet, system s1 is still available after you’ve obtained system s2 from it. The opposite situation, when a data structure is modified in-place and doesn’t keep its past state, is called ephemeral, and it’s the default behavior of classical imperative data structures. Because persistent data structures offer more functionality, it’s not surprising that they’re generally less efficient, in terms of time and space, than ephemeral ones.

Going back to the new API, notice that the container c is immutable and belongs to system s1. This raises an important design choice: is c also a valid container for s2? That is, can we invoke something like s2.addWater(c, 7)? If we can’t, the API is very cumbersome to use. Every modification to any container generates a new system and invalidates all current container objects. If we can, then we can expect c to represent the “container of index 5” in any system of containers. In other words, c becomes a thinly disguised alias for the index 5. Neither scenario is particularly satisfying. Instead, let’s get rid of Container altogether (as in Memory3 and Memory4 from chapter 4) and identify containers using bare integer IDs.

The first snippet, which creates a 10-container system and adds water to the sixth container, becomes the following:

ContainerSystem s1 = new ContainerSystem(10);
ContainerSystem s2 = s1.addWater(5, 42);  1 Adds 42 liters to container 5

What if we realize we need an eleventh container, but we don’t want to start a new system from scratch? An instance method of ContainerSystem can return a new system with an extra container:

ContainerSystem s3 = s2.addContainer();  2 Adds 11th container

Naturally, the connectTo method (renamed connect for the occasion) must accept two container IDs and return an entirely new system of containers:

s3 = s3.connect(5, 6);            3 Connects containers 5 and 6
double amount = s3.getAmount(5);  4 Holds the value 21.0

Summarizing, you end up with the following methods:

public class ContainerSystem {
   public ContainerSystem(int containerCount)
   public ContainerSystem addContainer()
   public int containerCount()   5 The number of containers in this system

   public ContainerSystem connect(int containerID1, int containerID2)
   public double getAmount(int containerID)
   public ContainerSystem addWater(int containerID, double amount)
}

8.4.2. The implementation

To convert a given mutable implementation to immutability, you can apply the following copy-on-write technique:

1. A system of containers holds the same data that was spread among all containers in the mutable implementation.
2. Each mutating operation (addWater and connectTo) creates and returns a new system holding a modified copy of the entire data structure.

This is the simplest way to turn a mutable class into an immutable one, but generally not the most efficient. A more sophisticated approach would try to reuse as much as possible of the old object, when you apply a mutating operation to it, instead of making a full duplicate. In the case of water containers, you can imagine a smart immutable implementation duplicating containers on-demand, that is, copying only the group of containers that a given mutating operation (say, a call to addWater) affects, and reusing all other containers until they also become involved in a call to addWater or connectTo.

In principle, you could apply the simple copy-on-write approach to any of the solutions we explored in the previous chapters, producing as many different implementations of the immutable API as we developed in the previous section. In practice, most of the mutable implementations you’ve seen so far make little sense once they become immutable copy-on-write classes. Consider the most efficient mutable implementation from chapter 3: the parent-pointer trees from Speed3. The value of that implementation is tied to its mutability: it’s efficient to update and to query. If every connectTo operation were to copy the entire forest of trees (yes, that’s what a set of trees is called), you’d completely lose the update efficiency because each connectTo takes linear time. At that point, you might as well use a simpler data structure to begin with.

Indeed, let’s sketch an immutable version of Memory3 instead. That implementation is based on two arrays, which are easy and efficient to copy. The method connectTo will still require linear time, but at least you’ll be able to copy all of the data with two simple lines. Also, copying two chunks of contiguous memory is faster than copying a linked forest of trees, despite having the same asymptotic complexity.

First, recall the data structures that Memory3 uses:

• The group array maps a container ID to its group ID.
• The amount array maps a group ID to the amount of water found in each container of that group.

Each instance of ContainerSystem will hold these two arrays. It may be a good idea to declare them as final, as a hint to their immutability. Of course, a final array reference doesn’t prevent the content of the array from being modified. That’s why the final modifier in this case is just a reminder that you’re aiming at a much stronger form of immutability.

In Memory3, you keep the amount array as short as possible: when two containers are connected and their groups are merged, one cell is removed from amount because there’s one less group around. Here, we’re not particularly concerned with memory occupancy, so you can take the simpler approach and keep the two arrays at the same length, equal to the total number of containers.

The only public constructor for ContainerSystem creates a system with a given number of empty and isolated containers. To accomplish this aim, the constructor gives each container its own group, and the ID of the i-th group is just i.

Given a container ID, the getAmount method will access the group array to obtain the group ID for that container, then the amount array to obtain the water amount in that group, as you can see in the following listing:

Listing 8.7. Immutable: Fields, constructor, and method getAmount

public class ContainerSystem {
   private final int group[];      1 From containerID to its groupID
   private final double amount[];  2 From groupID to
                                     the per-container amount

   public ContainerSystem(int containerCount) {
      group = new int[containerCount];
      amount = new double[containerCount];
      for (int i=0; i<containerCount; i++) {
         group[i] = i;  3 The groupID of the i-th container is i.
      }
   }

   public double getAmount(int containerID) {
      final int groupID = group[containerID];
      return amount[groupID];
   }

The getAmount method is straightforward (and very similar to the one in Memory3) because it provides a read-only functionality. Next, let’s consider the first mutating method: addContainer, the method that returns a new system with one extra container. Because the two arrays are declared final, you must initialize them in a constructor. Later, you’ll use the same constructor for the other mutating methods, addWater and connect, so it’s convenient to pass two parameters to it:

• The existing system to be copied.
• The new number of containers. Method addContainer uses this parameter to increase the number of containers by one, whereas the other mutating methods leave this number unchanged.

Listing 8.8 shows both addContainer and its support constructor.

Listing 8.8. Immutable: Method addContainer and support constructor

   public ContainerSystem addContainer() {
      final int containerCount = group.length;
      ContainerSystem result =
         new ContainerSystem(this, containerCount + 1);  1 Call to private constructor
      result.group[containerCount] = containerCount;
      return result;
   }
   private ContainerSystem(ContainerSystem old, int length) {
      group = Arrays.copyOf(old.group, length);  2 An efficient way to copy an array
      amount = Arrays.copyOf(old.amount, length);
   }

Next, addWater also needs to create an entirely new system of containers, with updated water amounts. Unless there’s no water to be added, it invokes the private constructor from the previous listing and then updates the amount in the appropriate group, as shown in the following listing.

Listing 8.9. Immutable: Method addWater

   public ContainerSystem addWater(int containerID, double amount) {
      if (amount == 0)  1 No need for a new system!
         return this;

      ContainerSystem result =
         new ContainerSystem(this, group.length);  2 Call to private constructor
      int groupID = group[containerID],
          groupSize = groupSize(groupID);
      result.amount[groupID] += amount / groupSize;
      return result;
   }

Finally, the connect method also creates a new system of containers using the private constructor and then connects two containers by merging their groups. You can find its source code in the accompanying repository(https://bitbucket.org/mfaella/exercisesinstyle).

8.5. And now for something completely different

In this section, you’ll face a different application requiring the same techniques I introduced earlier in the chapter in the context of water containers. You’ll design a class Repository<T>, representing a fixed-size container that stores its elements in indexed cells, like an array. Repositories come with a built-in operation that switches the content of two cells. Naturally for this chapter, your users want this class to be thread-safe so that multiple threads can easily share and manipulate repositories.

In detail, the class must offer the following constructor and methods:

• public Repository(int n)—Creates a repository with n cells, initially holding null
• public T set(int i, T elem)—Inserts object elem into the i-th cell and returns the object previously located there (or null)
• public void swap(int i, int j)—Swaps the contents of cells i and j

As discussed earlier, before implementing the class itself, you need to clarify its concurrency policy. Recall that such a policy specifies which operations will be able to proceed in parallel and which need to be mutually exclusive instead.

Because different repositories don’t share any data, the simplest concurrency policy that guarantees thread safety is the object-level policy: one lock per repository and all methods synchronized on that lock. If many threads use a repository concurrently, this policy may give bad performance because all operations on the same repository—even those involving different indices—must acquire the same lock.

A more permissive and efficient concurrency policy forbids concurrent access to the same index and allows all other operations to proceed concurrently. You can state it as follows:

• Two calls to set on the same index must be serialized.
• Two calls to swap that share at least an index must be serialized.
• A call to swap(i, j) and a call to set on index i or j must be serialized.
• All other operations are allowed to proceed concurrently.

This policy requires a lock for each cell in the repository, including empty cells (those holding null). Hence, the class needs one extra object for each cell, used as a monitor for that cell. You can store the elements and the monitors in two ArrayLists:

public class Repository<T> {
   private final List<T> elements;
   private final List<Object> monitors;

   public Repository(int size) {
      elements = new ArrayList<>(size);
      monitors = new ArrayList<>(size);
      for (int i=0; i<size; i++) {
         elements.add(null);      1 Lists must be filled before you can call get and set.
         monitors.add(new Object());
      }
   }

The set method simply acquires the monitor of the cell being written:

   public T set(int i, T elem) {
      synchronized (monitors.get(i)) {
         return elements.set(i, elem);
      }
   }

The swap method acquires the monitors of the two cells being swapped, in increasing index order, to avoid deadlocks:

   public void swap(int i, int j) {
      if (i == j) return;
      if (i > j) {  2 Makes sure that i is the smaller index
         int temp = i;
         i = j;
         j = temp;
      }
      synchronized (monitors.get(i)) { {  3 Acquires monitors in index order
         synchronized (monitors.get(j)) {
            elements.set(i, elements.set(j, elements.get(i)));
             4 This one-liner uses the fact that List.set
         }     returns the value previously at that position.
      }
   }

Notice that in this way you’re allowing different threads to read and even modify an ArrayList at the same time, provided they use different indices. However, ArrayList is not a thread-safe class. Is this code wrong? If you read the ArrayList documentation carefully, you’ll realize that the caller only needs to serialize structural modifications (such as calling add); concurrent calls to get and set on different indices are fine.

8.6. Real-world use cases

In this chapter, we’ve discussed how to make water containers thread-safe so that multiple threads can interact with them without requiring the client code to handle synchronization explicitly. But why did we decide to get into trouble refactoring the code to make it thread-safe? The single-threaded version works just fine. To answer this question, let’s look at some use cases where concurrency is not only beneficial but crucial.

• You love chess, and at the same time you’re a gifted programmer. For fun and practice, you decide to create a chess program in Java to play against your computer. After a few games of chess, you realize that your program is great (modesty is not one of your traits), and you want to share it with the world. You decide to turn your program into a service, where the computer will be able to compete against multiple users. You can handle multiple games in two ways: either you put users in a queue and handle them serially, or you can exploit concurrency and handle many players simultaneously. The second approach can take advantage of parallel hardware, such as a multi-core machine.
• Applications, operating systems, network devices, databases—in other words, virtually all ongoing services in a computational system—create logs. They don’t generate such log files for fun: well-managed organizations analyze their contents in batches or in real time to mitigate risks. A basic analysis workflow involves parsing log files; identifying important patterns or anomalies; and generating aggregate statistics, reports, and alerts. A common pattern for dealing efficiently with large log files is the Map-Reduce paradigm. As you might have guessed, this pattern consists of two steps: map and reduce. The map step enables the log analysis system to process independent chunks of log data concurrently, often on a distributed network of machines, and generate intermediate results. The reduce step collects the results and computes the final aggregates. The fork-join framework I mentioned at the beginning of this chapter is a variant of this idea, tailored to single multicore architectures.
• If you’ve ever lived in the United Kingdom, you’ve probably realized that football is extremely popular. In fact, during a Sunday afternoon, you can categorize people into those who drink beer and those who don’t. Football players and minors are those who don’t (hopefully). Having noticed this passion for sports, you decide to create a platform that will send live sports news feeds and distribute them to your subscribers. The live feeds will produce streams of data and put them in a container data structure, and subscriber clients will request data from the container to inform your subscribers. A thread-safe news container will enable data producers and consumers to run in multiple threads, giving your clients the satisfaction of raising a pint to their team before their neighbors.
• A program isolated from the rest of the world is rarely very useful. On the contrary, real programs will frequently wait for some input/output operation from an external resource, such as a file or a network connection. Multithreading allows a user-facing program to remain responsive while waiting on such slow peripherals. For example, think of a single-threaded web browser that stops being interactive while downloading a file from the network. Can you guess how many users this web browser would have? At most one: its creator.

8.7. Applying what you learned

Exercise 1

The following subclass of Thread increments all elements of an array of integers by one. As you can see, all instances of this class share the array.

class MyThread extends Thread {
   private static int[] array = ...  1 Some initial value

   public void run() {
      _____1_____   2 A placeholder
      for (int i=0; i<array.length; i++) {
          _____2_____
          array[i]++;
          _____3_____
      }
      _____4_____
   }
}

A program creates two instances of MyThread and launches them as two concurrent threads, with the intention of incrementing each array element by two. Which of the following insertions make the program correct by removing all race conditions? (Multiple options may be correct.)

Exercise 2

Design the thread-safe class AtomicPair, which holds two objects and offers the following methods:

public class AtomicPair<S,T> {
   public void setBoth(S first, T second);
   public S getFirst();
   public T getSecond();
}

Respect the following concurrency policy: Calling setBoth is an atomic operation. That is, if a thread calls setBoth(a,b), any subsequent call to getFirst and getSecond will view both updated values.

Exercise 3

In a simple social network, each user holds a set of friends, and friendship is symmetrical. The implementation is based on the following class:

public class SocialUser {
   private final String name;
   private final Set<SocialUser> friends = new HashSet<>();

   public SocialUser(String name) {
      this.name = name;
   }
   public synchronized void befriend(SocialUser other) {
      friends.add(other);
      synchronized (other) {
         other.friends.add(this);
      }
   }
   public synchronized boolean isFriend(SocialUser other) {
      return friends.contains(other);
   }
}

Unfortunately, when multiple threads establish friendships at the same time, sometimes the system hangs and needs to be restarted. Do you know why? Can you fix the problem by refactoring SocialUser?

Exercise 4

Consider the following mutable class, Time, representing a time of the day in hours, minutes, and seconds:

• public void addNoWrapping(Time delta)—Adds a delay to this time, maxing out at one second before midnight (23:59:59)
• public void addAndWrapAround(Time delta)—Adds a delay to this time, wrapping around at midnight
• public void subtractNoWrapping(Time delta)—Subtracts a delay from this time, stopping at 00:00:00
• public void subtractAndWrapAround(Time delta)—Subtracts a delay from this time, wrapping around if needed

Convert this API into an immutable version and implement it.

Summary

• A reasoned concurrency policy is a crucial prerequisite for thread safety.
• The main enemies of thread safety are race conditions and deadlocks.
• You can avoid deadlocks by using a global lock or an ordered lock policy.
• Differently from implicit locks, you can acquire and release explicit locks in any order.
• Immutability is an alternative path to thread safety.

Answers to quizzes and exercises

Pop Quiz 1

Users of a class should know only that the class is thread-safe. The rest of the concurrency policy is intended for the class implementors. In practice, however, users may be interested in the concurrency policy for appraising the class performance.

Pop Quiz 2

You can’t get into a deadlock if the locks are reentrant, that is, if a thread can reacquire a lock that it already owns. In Java, both implicit and explicit locks are reentrant. In other frameworks, such as Posix mutexes, locks can be non-reentrant, and a single thread can deadlock if it tries to reacquire a lock it already owns.

Pop Quiz 3

If an exception is thrown from inside a synchronized block, the monitor is automatically released. On the other hand, you need to explicitly release a ReentrantLock. That’s why its unlock operation is usually put in the finally part of a try...catch block, to make sure it’s executed under all circumstances.

Pop Quiz 4

The ordered locking technique prevents deadlocks because requesting locks in a fixed global order prevents cycles from being formed.

Pop Quiz 5

Immutable classes are automatically thread-safe because you can only read their objects, and concurrent reads by multiple threads pose no safety concerns. Methods creating new objects may employ mutable local variables because they live on the stack and aren’t shared with other threads.

Exercise 1

The correct options are (c) and (e). Both ensure that if a thread is performing array[i]++, the other thread can’t be performing the same instruction, even on a different i. What’s more, (c) completely serializes the threads: one for loop is executed entirely before the other loop can start.

Options (a) and (d) don’t provide any mutual exclusion because the two threads would be synchronizing on two different monitors. Options (b) and (f) cause compilation errors because a synchronized block needs to specify the object providing the monitor (and array[i] is not an object).

Exercise 2

To obey the concurrency policy, you just use synchronized blocks in all three methods, locking the same monitor. As explained in this chapter, it’s better to synchronize on a private object rather than synchronize on this, even if the latter would allow you to replace the synchronized blocks with a sleeker method modifier.

public class AtomicPair<S,T> {
   private S first;
   private T second;
   private final Object lock = new Object();  1 Provides a private monitor

   public void setBoth(S first, T second) {
      synchronized (lock) {
         this.first = first;
         this.second = second;
      }
   }
   public S getFirst() {
      synchronized (lock) {
         return first;
      }
   }
   ...  2 getSecond is analogous.
}

It may look odd to put a single return statement in a synchronized block, but it’s essential for both mutual exclusion and visibility reasons. First, you don’t want getFirst and getSecond to occur when setBoth is halfway through its body. Second, without a synchronized block, threads calling getFirst would have no guarantee of seeing the updated value of first. By the way, declaring both first and second as volatile would solve the second issue (visibility) but not the first one (mutual exclusion).

Exercise 3

The class SocialUser may cause a deadlock if a thread invokes a.befriend(b) and another thread simultaneously invokes b.befriend(a), for two SocialUser objects a and b. To avoid this risk, you can adopt the ordered locking technique, which starts with equipping each object with a unique id:

public class SocialUserNoDeadlock {
   private final String name;
   private final Set<SocialUserNoDeadlock> friends = new HashSet<>();
   private final int id;
   private static final AtomicInteger instanceCounter = new AtomicInteger();

   public SocialUserNoDeadlock(String name) {
      this.name = name;
      this.id = instanceCounter.incrementAndGet();
   }

The befriend method then avoids deadlocks by requesting the two locks in the order of increasing id:

   public void befriend(SocialUserNoDeadlock other) {
      Object firstMonitor, secondMonitor;
      if (id < other.id) {
         firstMonitor = this;
         secondMonitor = other;
      } else {
         firstMonitor = other;
         secondMonitor = this;
      }
      synchronized (firstMonitor) {
         synchronized (secondMonitor) {
            friends.add(other);
            other.friends.add(this);
         }
      }
   }

Exercise 4

To convert the API from mutable to immutable, you make every mutating method return a new object of the class. It’s also a good idea to declare all fields final. The rest is simple arithmetic, needed to carry the overflows from seconds to minutes and from minutes to hours.

public class Time {
   private final int hours, minutes, seconds;

   public Time addNoWrapping(Time delta) {
      int s = seconds, m = minutes, h = hours;
      s += delta.seconds;
      if (s > 59) {  1 Second overflow: carries over to minutes
         s -= 60;
         m++;
      }
      m += delta.minutes;
      if (m > 59) {  2 Minute overflow: carries over to hours
         m -= 60;
         h++;
      }
      h += delta.hours;
      if (h > 23) {  3 Hour overflow: set to max
         h = 23;
         m = 59;
         s = 59;
      }
      return new Time(h, m, s);  4 Returns new object
   }

You can find the rest of this class in the accompanying repository (https://bitbucket.org/mfaella/exercisesinstyle). Notice that the standard Java class java.time.LocalTime provides functionality similar to that which this Time class provides.

Further reading

• B. Goetz, T. Peierls, Joshua Bloch, J. Bowbeer, D. Holmes, and D. Lea. Java Concurrency in Practice. Addison-Wesley, 2006. The must-read on Java concurrency. It discusses all kinds of concurrency issues in a fortunate combination of technical rigor and captivating style. Unfortunately, as of this writing it hasn’t been updated with the high-level concurrency facilities added to the JDK starting from version 7. (See the next book for that.)
• R.-G. Urma, M. Fusco, and A. Mycroft. Modern Java in Action. Manning Publications, 2019. A comprehensive introduction to data streams, with a chapter dedicated to parallel computation using streams and the fork-join framework.
• Joshua Bloch. Effective Java. Addison-Wesley, 2017. As a rule, I’m trying to suggest different books for each chapter, but I’m making an exception for this book because it contains so much good advice on so many different topics. Chapter 11 is entirely devoted to concurrency, and item 17 to immutability in particular.
• R. J. Anderson and H. Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem.” 1991. The thread-safe water container class developed in this chapter is based on Speed1, which is not a particularly efficient representation. This research paper shows how to create a thread-safe implementation of the much faster parent-pointer trees of Speed3 which in addition is wait-free. It achieves thread safety using the compare-and-swap instruction instead of locks.
• Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998. The author of this book expanded his PhD thesis into an in-depth treatise on persistent data structures, with examples in ML and Haskell.