Introduction

In the previous example, there is no guarantee that statements 1 and 2 will be executed in the order in which they appear in the program. They may be reordered freely by the compiler because there is no happens-before relationship between these two statements.

The possible reorderings between volatile and non-volatile variables are summarized in Table 4. Load and store operations are synonymous to read and write operations, respectively [Lea 2008].

Table 4: Possible Reorderings Between Volatile and Non-Volatile Variables

Can Reorder	2nd Operation
1st Operation	Normal Load	Normal Store	Volatile Load	Volatile Store
Normal load	Yes	Yes	Yes	No
Normal store	Yes	Yes	Yes	No
Volatile load	No	No	No	No
Volatile store	Yes	Yes	No	No

1.1.2Synchronization

A correctly synchronized program is one whose sequentially consistent executions do not have any data races. The example shown below uses a non-volatile variable x and a volatile variable y and is not correctly synchronized.

Table 5: Example Thread Assignment #2

Thread 1	Thread 2
x = 1	r1 = y
y = 2	r2 = x

The two sequentially consistent execution orders of this example are shown in Table 6 and Table 7.

Table 6: Execution Order #1

Step (Time)	Thread#	Statement	Comment
1	t1	x = 1	Write to non-volatile variable
2	t1	y = 2	Write to volatile variable
3	t2	r1 = y	Read of volatile variable
4	t2	r2 = x	Read of non-volatile variable

Table 7: Execution Order #2

Step (Time)	Thread#	Statement	Comment
1	t2	r1 = y	Read of volatile variable
2	t2	r2 = x	Read of non-volatile variable
3	t1	x = 1	Write to non-volatile variable
4	t1	y = 2	Write to volatile variable

In the first case, a happens-before relationship exists between actions such that Steps 1 and 2 always occur before Steps 3 and 4. However, in the second case, no happens-before relationship exists between any of the steps. Consequently, because there is a sequentially consistent execution that has no happens-before relationship, this example contains data races.

CMU/SEI-2010-TR-015 | 5

Introduction

Correct visibility guarantees that multiple threads accessing shared data can view each others’ results, but does not establish the order of when each thread reads or writes the data. Correct synchronization guarantees that threads access data in a proper order. For example, the code shown below ensures that there is only one sequentially consistent execution order that performs all the actions of Thread 1 before Thread 2.

class Assign {

public synchronized void doSomething() { // Perform Thread 1 actions

x = 1; y = 2;

// Perform Thread 2 actions r1 = y;

r2 = x;

}

}

When using synchronization, there is no need to declare the variable y volatile. Synchronization involves acquiring a lock, performing operations, and then releasing the lock. In the above example, the doSomething() method acquires the intrinsic lock of the class object (Assign). This example can also be written to use block synchronization:

class Assign {

public void doSomething() { synchronized (this) {

//Perform Thread 1 actions x = 1;

y = 2;

//Perform Thread 2 actions r1 = y;

r2 = x;

}

}

}

The intrinsic lock used in both examples is the same.

1.1.3The java.util.concurrent Classes

1.1.3.1Atomic Classes

Volatile variables are useful for guaranteeing visibility. However, they are insufficient for ensuring atomicity. Synchronization fills this gap but incurs overheads of context switching and frequently causes lock contention. The atomic classes of package java.util.concurrent.atomic provide a mechanism for reducing contention in most practical environments while at the same time ensuring atomicity. According to Goetz and colleagues [Goetz 2006]

With low to moderate contention, atomics offer better scalability; with high contention, locks offer better contention avoidance.

The atomic classes consist of implementations that exploit the design of modern processors by exposing commonly needed functionality to the programmer. For example, the AtomicInteger.incrementAndGet() method can be used for atomically incrementing a variable. The compare-and-swap instruction(s) provided by modern processors offer more finegrained control and can be used directly by invoking high-level methods such as

CMU/SEI-2010-TR-015 | 6

Introduction

java.util.concurrent.atomic.Atomic*.compareAndSet() where the asterisk can be, for example, an Integer, Long, or Boolean.

1.1.3.2The Executor Framework

The java.util.concurrent package provides the Executor framework that offers a mechanism for executing tasks concurrently. A task is a logical unit of work encapsulated by a class that implements Runnable or Callable. The Executor framework allows task submission to be decoupled from low-level scheduling and thread management details. It provides the thread pool mechanism that allows a system to degrade gracefully when presented with more requests than the system can handle simultaneously.

The Executor interface is the core interface of the framework and is extended by the ExecutorService interface that provides facilities for thread pool termination and obtaining return values of tasks (Futures). The ExecutorService interface is further extended by the ScheduledExecutorService interface that provides a way to run tasks periodically or after some delay. The Executors class provides several factory and utility methods that are preconfigured with commonly used configurations of Executor, ExecutorService, and other related interfaces. For example, the Executors.newFixedThreadPool() method returns a fixed size thread pool with an upper limit on the number of concurrently executing tasks and maintains an unbounded queue for holding tasks while the thread pool is full. The base (actual) implementation of the thread pool is provided by the ThreadPoolExecutor class. This class can be instantiated to customize the task execution policy.

The java.util.concurrent utilities are preferred over traditional synchronization primitives such as synchronization and volatile variables because the java.util.concurrent utilities abstract the underlying details, provide a cleaner and less error-prone API, are easier to scale, and can be enforced using policies.

1.1.3.3Explicit Locking

The java.util.concurrent package provides the ReentrantLock class that has additional features not provided by intrinsic locks. For example, the ReentrantLock.tryLock() method does not block waiting if another thread is already holding the lock. Acquiring and releasing a ReentrantLock has the same semantics as acquiring and releasing an intrinsic lock.

CMU/SEI-2010-TR-015 | 7

Introduction

CMU/SEI-2010-TR-015 | 8