In most practical multithreaded applications, two or more threads need to share access to the same data. What happens if two threads have access to the same object and each calls a method that modifies the state of the object? As you might imagine, the threads can step on each other’s toes. Depending on the order in which the data were accessed, corrupted objects can result. Such a situation is often called a race condition.
1. An Example of a Race Condition
To avoid corruption of shared data by multiple threads, you must learn how to synchronize the access. In this section, you’ll see what happens if you do not use synchronization. In the next section, you’ll see how to synchronize data access.
In the next test program, we continue working with our simulated bank. Unlike the example in Section 12.1, “What Are Threads?,” on p. 734, we randomly select the source and destination of the transfer. Since this will cause problems, let us look more carefully at the code for the transfer method of the Bank class.
public void transfer(int from, int to, double amount)
// CAUTION: unsafe when called from multiple threads
{
System.out.print(Thread.currentThread());
accounts[from] -= amount;
System.out.printf(” %10.2f from %d to %d”, amount, from, to);
accounts[to] += amount;
System.out.printf(” Total Balance: %10.2f%n”, getTotalBalance());
}
Here is the code for the Runnable instances. The run method keeps moving money out of a given bank account. In each iteration, the run method picks a random target account and a random amount, calls transfer on the bank object, and then sleeps.
Runnable r = () ->{
try
{
while (true)
{
int toAccount = (int) (bank.size() * Math.random());
double amount = MAX_AMOUNT * Math.random();
bank.transfer(fromAccount, toAccount, amount);
Thread.sleep((int) (DELAY * Math.random()));
}
}
catch (InterruptedException e)
{
}
};
When this simulation runs, we do not know how much money is in any one bank account at any time. But we do know that the total amount of money in all the accounts should remain unchanged because all we do is move money from one account to another.
At the end of each transaction, the transfer method recomputes the total and prints it.
This program never finishes. Just press Ctrl+C to kill the program.
Here is a typical printout:
As you can see, something is very wrong. For a few transactions, the bank balance remains at $100,000, which is the correct total for 100 accounts of $1,000 each. But after some time, the balance changes slightly. When you run this program, errors may happen quickly, or it may take a very long time for the balance to become corrupted. This situation does not inspire confidence, and you would probably not want to deposit your hard-earned money in such a bank.
See if you can spot the problems with the code in Listing 12.3 and the Bank class in Listing 12.2. We will unravel the mystery in the next section.
2. The Race Condition Explained
In the previous section, we ran a program in which several threads updated bank account balances. After a while, errors crept in and some amount of money was either lost or spontaneously created. This problem occurs when
two threads are simultaneously trying to update an account. Suppose two threads simultaneously carry out the instruction
accounts[to] += amount;
The problem is that these are not atomic operations. The instruction might be processed as follows:
- Load accounts[to] into a register.
- Add amount.
- Move the result back to accounts[to].
Now, suppose the first thread executes Steps 1 and 2, and then it is preempted. Suppose the second thread awakens and updates the same entry in the account array. Then, the first thread awakens and completes its Step 3.
That action wipes out the modification of the other thread. As a result, the total is no longer correct (see Figure 12.2).
Our test program detects this corruption. (Of course, there is a slight chance of false alarms if the thread is interrupted as it is performing the tests!)
What these codes mean does not matter. The point is that the increment command is made up of several instructions, and the thread executing them can be interrupted at any instruction.
What is the chance of this corruption occurring? On a modern processor with multiple cores, the risk of corruption is quite high. We boosted the chance of observing the problem on a single-core processor by interleaving the print statements with the statements that update the balance.
If you omit the print statements, the risk of corruption is lower because each thread does so little work before going to sleep again, and it is unlikely that the scheduler will preempt it in the middle of the computation. However, the risk of corruption does not go away completely. If you run lots of threads on a heavily loaded machine, the program will still fail even after you have eliminated the print statements. The failure may take a few minutes or hours or days to occur. Frankly, there are few things worse in the life of a programmer than an error that only manifests itself irregularly.
The real problem is that the work of the transfer method can be interrupted in the middle. If we could ensure that the method runs to completion before the thread loses control, the state of the bank account object would never be corrupted.
3. Lock Objects
There are two mechanisms for protecting a code block from concurrent access. The Java language provides a synchronized keyword for this purpose, and Java 5 introduced the ReentrantLock class. The synchronized keyword automatically provides a lock as well as an associated “condition,” which makes it powerful and convenient for most cases that require explicit locking. However, we believe that it is easier to understand the synchronized keyword after you have seen locks and conditions in isolation. The java.utit.concurrent framework provides separate classes for these fundamental mechanisms, which we explain here and in Section 12.4.4, “Condition Objects,” on p. 758. Once you have understood these building blocks, we present the synchronized keyword in Section 12.4.5, “The synchronized Keyword,” on p. 764.
The basic outline for protecting a code block with a ReentrantLock is:
myLock.lock(); // a ReentrantLock object
try
{
critical section
}
finally
{
myLock.unlock(); // make sure the lock is unlocked even if an exception is thrown
}
This construct guarantees that only one thread at a time can enter the critical section. As soon as one thread locks the lock object, no other thread can get past the lock statement. When other threads call lock, they are deactivated until the first thread unlocks the lock object.
Let us use a lock to protect the transfer method of the Bank class.
public class Bank
{
private Lock bankLock = new ReentrantLock();
…
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
System.out.print(Thread.currentThread());
accounts[from] -= amount;
System.out.printf(” %10.2f from %d to %d”, amount, from, to);
accounts[to] += amount;
System.out.printf(” Total Balance: %10.2f%n”, getTotalBalance());
}
finally
{
bankLock.unlock();
}
}
}
Suppose one thread calls transfer and gets preempted before it is done. Suppose a second thread also calls transfer. The second thread cannot acquire the lock and is blocked in the call to the lock method. It is deactivated and must wait for the first thread to finish executing the transfer method. When the first thread unlocks the lock, then the second thread can proceed (see Figure 12.3).
Try it out. Add the locking code to the transfer method and run the program again. You can run it forever, and the bank balance will not become corrupted.
Note that each Bank object has its own ReentrantLock object. If two threads try to access the same Bank object, then the lock serves to serialize the access. However, if two threads access different Bank objects, each thread acquires a different lock and neither thread is blocked. This is as it should be, because the threads cannot interfere with one another when they manipulate different Bank instances.
The lock is called reentrant because a thread can repeatedly acquire a lock that it already owns. The lock has a hold count that keeps track of the nested calls to the lock method. The thread has to call unlock for every call to lock in order to relinquish the lock. Because of this feature, code protected by a lock can call another method that uses the same locks.
For example, the transfer method calls the getTotatBatance method, which also locks the bankLock object, which now has a hold count of 2. When the getTotatBatance method exits, the hold count is back to 1. When the transfer method exits, the hold count is 0, and the thread relinquishes the lock.
In general, you will want to protect blocks of code that update or inspect a shared object, so you can be assured that these operations run to completion before another thread can use the same object.
4. Condition Objects
Often, a thread enters a critical section only to discover that it can’t proceed until a condition is fulfilled. Use a condition object to manage threads that have acquired a lock but cannot do useful work. In this section, we introduce the implementation of condition objects in the Java library. (For historical reasons, condition objects are often called condition variables.)
Let us refine our simulation of the bank. We do not want to transfer money out of an account that does not have the funds to cover the transfer. Note that we cannot use code like
if (bank.getBalance(from) >= amount)
bank.transfer(from, to, amount);
It is entirely possible that the current thread will be deactivated between the successful outcome of the test and the call to transfer.
if (bank.getBalance(from) >= amount)
// thread might be deactivated at this point
bank.transfer(from, to, amount);
By the time the thread is running again, the account balance may have fallen below the withdrawal amount. You must make sure that no other thread can modify the balance between the test and the transfer action. You do so by protecting both the test and the transfer action with a lock:
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
while (accounts[from] < amount)
{
// wait
…
}
// transfer funds
…
}
finally
{
bankLock.unlock();
}
}
Now, what do we do when there is not enough money in the account? We wait until some other thread has added funds. But this thread has just gained exclusive access to the bankLock, so no other thread has a chance to make a deposit. This is where condition objects come in.
A lock object can have one or more associated condition objects. You obtain a condition object with the newCondition method. It is customary to give each condition object a name that evokes the condition that it represents. For example, here we set up a condition object to represent the “sufficient funds” condition.
class Bank
{
private Condition sufficientFunds;
…
public Bank()
{
…
sufficientFunds = bankLock.newCondition();
}
}
If the transfer method finds that sufficient funds are not available, it calls
sufficientFunds.await();
The current thread is now deactivated and gives up the lock. This lets in another thread that can, we hope, increase the account balance.
There is an essential difference between a thread that is waiting to acquire a lock and a thread that has called await. Once a thread calls the await method, it enters a wait set for that condition. The thread is not made runnable when the lock is available. Instead, it stays deactivated until another thread has called the signatAtt method on the same condition.
When another thread has transferred money, it should call
sufficientFunds.signatAtt();
This call reactivates all threads waiting for the condition. When the threads are removed from the wait set, they are again runnable and the scheduler will eventually activate them again. At that time, they will attempt to reenter the object. As soon as the lock is available, one of them will acquire the lock and continue where it left off, returning from the call to await.
At this time, the thread should test the condition again. There is no guarantee that the condition is now fulfilled—the signatAtt method merely signals to the waiting threads that it may be fulfilled at this time and that it is worth checking for the condition again.
It is crucially important that some other thread calls the signatAtt method eventually. When a thread calls await, it has no way of reactivating itself. It puts its faith in the other threads. If none of them bother to reactivate the waiting thread, it will never run again. This can lead to unpleasant deadlock situations. If all other threads are blocked and the last active thread calls await without unblocking one of the others, it also blocks. No thread is left to unblock the others, and the program hangs.
When should you call signatAtt? The rule of thumb is to call signatAtt whenever the state of an object changes in a way that might be advantageous to waiting threads. For example, whenever an account balance changes, the waiting threads should be given another chance to inspect the balance. In our example, we call signatAtt when we have finished the funds transfer.
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
white (accounts[from] < amount)
sufficientFunds.await();
// transfer funds
…
sufficientFunds.signalAll();
}
finatty
{
bankLock.unlock();
}
}
Note that the call to signalAll does not immediately activate a waiting thread. It only unblocks the waiting threads so that they can compete for entry into the object after the current thread has relinquished the lock.
Another method, signal, unblocks only a single thread from the wait set, chosen at random. That is more efficient than unblocking all threads, but there is a danger. If the randomly chosen thread finds that it still cannot proceed, it becomes blocked again. If no other thread calls signal again, the system deadlocks.
If you run the sample program in Listing 12.4, you will notice that nothing ever goes wrong. The total balance stays at $100,000 forever. No account ever has a negative balance. (Again, press Ctrl+C to terminate the program.) You may also notice that the program runs a bit slower—that is the price you pay for the added bookkeeping involved in the synchronization mechanism.
In practice, using conditions correctly can be quite challenging. Before you start implementing your own condition objects, you should consider using one of the constructs described in Section 12.5, “Thread-Safe Collections,” on p. 781.
Listing 12.4 synch/Bank.java
5. The synchronized Keyword
In the preceding sections, you saw how to use Lock and Condition objects. Before going any further, let us summarize the key points about locks and conditions:
- A lock protects sections of code, allowing only one thread to execute the code at a time.
- A lock manages threads that are trying to enter a protected code segment.
- A lock can have one or more associated condition objects.
- Each condition object manages threads that have entered a protected code section but that cannot proceed.
The Lock and Condition interfaces give programmers a high degree of control over locking. However, in most situations, you don’t need that control—you can use a mechanism that is built into the Java language. Ever since version 1.0, every object in Java has an intrinsic lock. If a method is declared with the synchronized keyword, the object’s lock protects the entire method. That is, to call the method, a thread must acquire the intrinsic object lock.
In other words,
public synchronized void method()
{
method body
}
is the equivalent of
public void method()
{
this. intrinsicLock .lock();
try
{
method body
}
finally { this.intn’nsicLock.unlock(); }
}
For example, instead of using an explicit lock, we can simply declare the transfer method of the Bank class as synchronized.
The intrinsic object lock has a single associated condition. The wait method adds a thread to the wait set, and the notifyAll/notify methods unblock waiting threads. In other words, calling wait or notifyAll is the equivalent of
intrinsicCondition .await();
intrinsicCondition .signalAll();
For example, you can implement the Bank class in Java like this:
class Bank {
private double[] accounts;
public synchronized void transfer(int from, int to, int amount)
throws InterruptedException
{
while (accounts[from] < amount)
wait(); // wait on intrinsic object lock’s single condition
accounts[from] -= amount;
accounts[to] += amount;
notifyAll(); // notify all threads waiting on the condition
}
public synchronized double getTotalBalance() {…}
}
As you can see, using the synchronized keyword yields code that is much more concise. Of course, to understand this code, you have to know that each object has an intrinsic lock, and that the lock has an intrinsic condition. The lock manages the threads that try to enter a synchronized method. The condition manages the threads that have called wait.
It is also legal to declare static methods as synchronized. If such a method is called, it acquires the intrinsic lock of the associated class object. For example, if the Bank class has a static synchronized method, then the lock of the Bank.ctass object is locked when it is called. As a result, no other thread can call this or any other synchronized static method of the same class.
The intrinsic locks and conditions have some limitations. Among them:
- You cannot interrupt a thread that is trying to acquire a lock.
- You cannot specify a timeout when trying to acquire a lock.
- Having a single condition per lock can be inefficient.
What should you use in your code—Lock and Condition objects or synchronized methods? Here is our recommendation:
- It is best to use neither Lock/Condition nor the synchronized keyword. In many situations, you can use one of the mechanisms of the java.utit.concurrent package that do all the locking for you. For example, in Section 12.5.1, “Blocking Queues,” on p. 781, you will see how to use a blocking queue to synchronize threads that work on a common task. You should also explore parallel streams—see Chapter 1 of Volume II.
- If the synchronized keyword works for your situation, by all means, use it. You’ll write less code and have less room for error. Listing 12.5 shows the bank example, implemented with synchronized methods.
- Use Lock/Condition if you really need the additional power that these constructs give you.
6. Synchronized Blocks
As we just discussed, every Java object has a lock. A thread can acquire the lock by calling a synchronized method. There is a second mechanism for acquiring the lock: by entering a synchronized block. When a thread enters a block of the form
synchronized (obj) // this is the syntax for a synchronized block
{
critical section
}
then it acquires the lock for obj.
You will sometimes find “ad hoc” locks, such as
public class Bank
{
private double[] accounts;
private Lock lock = new Object();
…
public void transfer(int from, int to, int amount)
{
synchronized (lock) // an ad-hoc lock
{
accounts[from] -= amount;
accounts[to] += amount;
}
System.out.println(. . .);
}
}
Here, the lock object is created only to use the lock that every Java object possesses.
Sometimes, programmers use the lock of an object to implement additional atomic operations—a practice known as client-side locking. Consider, for example, the Vector class, which is a list whose methods are synchronized. Now suppose we stored our bank balances in a Vector<Double>. Here is a naive implementation of a transfer method:
public void transfer(Vector<Double> accounts, int from, int to, int amount) // ERROR
{
accounts.set(from, accounts.get(from) – amount);
accounts.set(to, accounts.get(to) + amount);
System.out.println(. . .);
}
The get and set methods of the Vector class are synchronized, but that doesn’t help us. It is entirely possible for a thread to be preempted in the transfer method after the first call to get has been completed. Another thread may then store a different value into the same position. However, we can hijack the lock:
public void transfer(Vector<Double> accounts, int from, int to, int amount)
{
synchronized (accounts)
{
accounts.set(from, accounts.get(from) – amount);
accounts.set(to, accounts.get(to) + amount);
}
System.out.println(. . .);
}
This approach works, but it is entirely dependent on the fact that the Vector class uses the intrinsic lock for all of its mutator methods. However, is this really a fact? The documentation of the Vector class makes no such promise. You have to carefully study the source code and hope that future versions do not introduce unsynchronized mutators. As you can see, client-side locking is very fragile and not generally recommended.
7. The Monitor Concept
Locks and conditions are powerful tools for thread synchronization, but they are not very object-oriented. For many years, researchers have looked for ways to make multithreading safe without forcing programmers to think about explicit locks. One of the most successful solutions is the monitor concept that was pioneered by Per Brinch Hansen and Tony Hoare in the 1970s. In the terminology of Java, a monitor has these properties:
- A monitor is a class with only private fields.
- Each object of that class has an associated lock.
- All methods are locked by that lock. In other words, if a client calls obj.method(), then the lock for obj is automatically acquired at the beginning of the method call and relinquished when the method returns. Since all fields are private, this arrangement ensures that no thread can access the fields while another thread manipulates them.
- The lock can have any number of associated conditions.
Earlier versions of monitors had a single condition, with a rather elegant syntax. You can simply call await accounts[from] >= amount without using an explicit condition variable. However, research showed that indiscriminate retesting of conditions can be inefficient. This problem is solved with explicit condition variables, each managing a separate set of threads.
The Java designers loosely adapted the monitor concept. Every object in Java has an intrinsic lock and an intrinsic condition. If a method is declared with the synchronized keyword, it acts like a monitor method. The condition variable is accessed by calling wait/notifyAH/notify.
However, a Java object differs from a monitor in three important ways, compromising thread safety:
- Fields are not required to be private.
- Methods are not required to be synchronized.
- The intrinsic lock is available to clients.
This disrespect for security enraged Per Brinch Hansen. In a scathing review of the multithreading primitives in Java, he wrote: “It is astounding to me that Java’s insecure parallelism is taken seriously by the programming community, a quarter of a century after the invention of monitors and Concurrent Pascal. It has no merit” [Java’s Insecure Parallelism, ACM SIGPLAN Notices 34:38-45, April 1999].
8. Volatile Fields
Sometimes, it seems excessive to pay the cost of synchronization just to read or write an instance field or two. After all, what can go wrong? Unfortunately, with modern processors and compilers, there is plenty of room for error.
- Computers with multiple processors can temporarily hold memory values in registers or local memory caches. As a consequence, threads running in different processors may see different values for the same memory location!
- Compilers can reorder instructions for maximum throughput. Compilers won’t choose an ordering that changes the meaning of the code, but they make the assumption that memory values are only changed when there are explicit instructions in the code. However, a memory value can be changed by another thread!
If you use locks to protect code that can be accessed by multiple threads, you won’t have these problems. Compilers are required to respect locks by flushing local caches as necessary and not inappropriately reordering instructions. The details are explained in the Java Memory Model and Thread Specification developed by JSR 133 (see www.jcp.org/en/jsr/detaiI?id=133). Much of the specification is highly complex and technical, but the document also contains a number of clearly explained examples. A more accessible overview article by Brian Goetz is available at www.ibn.con/devetoperworks/tibrary/j-jtp02244.
The votatite keyword offers a lock-free mechanism for synchronizing access to an instance field. If you declare a field as votatite, then the compiler and the virtual machine take into account that the field may be concurrently updated by another thread.
For example, suppose an object has a boolean flag done that is set by one thread and queried by another thread. As we already discussed, you can use a lock:
private boolean done;
public synchronized boolean isDone() { return done; }
public synchronized void setDone() { done = true; }
Perhaps it is not a good idea to use the intrinsic object lock. The isDone and setDone methods can block if another thread has locked the object. If that is a concern, one can use a separate lock just for this variable. But this is getting to be a lot of trouble.
In this case, it is reasonable to declare the field as volatile:
private volatile boolean done;
public boolean isDone() { return done; }
public void setDone() { done = true; }
The compiler will insert the appropriate code to ensure that a change to the done variable in one thread is visible from any other thread that reads the variable.
9. Final Variables
As you saw in the preceding section, you cannot safely read a field from multiple threads unless you use locks or the volatile modifier.
There is one other situation in which it is safe to access a shared field—when it is declared final. Consider
final var accounts = new HashMap<String, Double>();
Other threads get to see the accounts variable after the constructor has finished.
Without using final, there would be no guarantee that other threads would see the updated value of accounts—they might all see null, not the constructed HashMap.
Of course, the operations on the map are not thread-safe. If multiple threads mutate and read the map, you still need synchronization.
10. Atomics
You can declare shared variables as volatile provided you perform no operations other than assignment.
There are a number of classes in the java.util.concurrent.atomic package that use efficient machine-level instructions to guarantee atomicity of other operations without using locks. For example, the AtomicInteger class has methods incrementAndGet and decrementAndGet that atomically increment or decrement an integer. For example, you can safely generate a sequence of numbers like this:
public static AtomicLong nextNumber = new AtomicLong();
// in some thread. . .
long id = nextNumber.incrementAndGet();
The incrementAndGet method atomically increments the AtomicLong and returns the post-increment value. That is, the operations of getting the value, adding 1, setting it, and producing the new value cannot be interrupted. It is guaranteed that the correct value is computed and returned, even if multiple threads access the same instance concurrently.
There are methods for atomically setting, adding, and subtracting values, but if you want to make a more complex update, you have to use the compareAndSet method. For example, suppose you want to keep track of the largest value that is observed by different threads. The following won’t work:
public static AtomicLong largest = new AtomicLong();
// in some thread. . .
largest.set(Math.max(largest.get(), observed)); // ERROR–race condition!
This update is not atomic. Instead, provide a lambda expression for updating the variable, and the update is done for you. In our example, we can call
largest.updateAndGet(x -> Math.max(x, observed));
or
largest.accumulateAndGet(observed, Math::max);
The accumulateAndGet method takes a binary operator that is used to combine the atomic value and the supplied argument.
There are also methods getAndUpdate and getAndAccumulate that return the old value.
When you have a very large number of threads accessing the same atomic values, performance suffers because the optimistic updates require too many retries. The LongAdder and LongAccumulator classes solve this problem. A LongAdder is composed of multiple variables whose collective sum is the current value. Multiple threads can update different summands, and new summands are automatically provided when the number of threads increases. This is efficient in the common situation where the value of the sum is not needed until after all work has been done. The performance improvement can be substantial.
If you anticipate high contention, you should simply use a LongAdder instead of an AtomicLong. The method names are slightly different. Call increment to increment a counter or add to add a quantity, and sum to retrieve the total.
var adder = new LongAdder();
for (. . .)
pool.submit(() -> {
white (. . .) {
…
if (. . .) adder.increment();
}
});
…
long total = adder.sum();
The LongAccumutator generalizes this idea to an arbitrary accumulation operation. In the constructor, you provide the operation, as well as its neutral element. To incorporate new values, call accumutate. Call get to obtain the current value. The following has the same effect as a LongAdder:
var adder = new LongAccumulator(Long::sum, 0);
// in some thread. . .
adder.accumulate(value);
Internally, the accumulator has variables a1, a2, . . ., an. Each variable is initialized with the neutral element (0 in our example).
When accumulate is called with value v, then one of them is atomically updated as ai = ai op v, where op is the accumulation operation written in infix form. In our example, a call to accumulate computes ai = ai + v for some i.
The result of get is a1 op a2 op . . . op an. In our example, that is the sum of the accumulators, a1 + a2 + . . . + an.
If you choose a different operation, you can compute maximum or minimum. In general, the operation must be associative and commutative. That means that the final result must be independent of the order in which the intermediate values were combined.
There are also DoubteAdder and DoubteAccumutator that work in the same way, except with double values.
11. Deadlocks
Locks and conditions cannot solve all problems that might arise in multithreading. Consider the following situation:
- Account 1: $200
- Account 2: $300
- Thread 1: Transfer $300 from Account 1 to Account 2
- Thread 2: Transfer $400 from Account 2 to Account 1
As Figure 12.4 indicates, Threads 1 and 2 are clearly blocked. Neither can proceed because the balances in Accounts 1 and 2 are insufficient.
It is possible that all threads get blocked because each is waiting for more money. Such a situation is called a deadlock.
In our program, a deadlock cannot occur for a simple reason. Each transfer amount is for, at most, $1,000. Since there are 100 accounts and a total of $100,000 in them, at least one of the accounts must have at least $1,000 at any time. The thread moving money out of that account can therefore proceed.
But if you change the run method of the threads to remove the $1,000 transaction limit, deadlocks can occur quickly. Try it out. Set NACCOUNTS to 10. Construct each transfer runnable with a max value of 2 * INITIAL_BALANCE and run the program. The program will run for a while and then hang.
Another way to create a deadlock is to make the ith thread responsible for putting money into the ith account, rather than for taking it out of the ith account. In this case, there is a chance that all threads will gang up on one account, each trying to remove more money from it than it contains. Try it out. In the SynchBankTest program, turn to the run method of the TransferRunnabte class. In the call to transfer, flip fromAccount and toAccount. Run the program and see how it deadlocks almost immediately.
Here is another situation in which a deadlock can occur easily. Change the signatAtt method to signal in the SynchBankTest program. You will find that the program eventually hangs. (Again, set NACCOUNTS to 10 to observe the effect more quickly.) Unlike signalAll, which notifies all threads that are waiting for added funds, the signal method unblocks only one thread. If that thread can’t proceed, all threads can be blocked. Consider the following sample scenario of a developing deadlock:
- Account 1: $1,990
- All other accounts: $990 each
- Thread 1: Transfer $995 from Account 1 to Account 2
- All other threads: Transfer $995 from their account to another account
Clearly, all threads but Thread 1 are blocked, because there isn’t enough money in their accounts.
Thread 1 proceeds. Afterward, we have the following situation:
- Account 1: $995
- Account 2: $1,985
- All other accounts: $990 each
Then, Thread 1 calls signal. The signal method picks a thread at random to unblock. Suppose it picks Thread 3. That thread is awakened, finds that there isn’t enough money in its account, and calls await again. But Thread 1 is still running. A new random transaction is generated, say,
1. Thread 1: Transfer $997 from Account 1 to Account 2
Now, Thread 1 also calls await, and all threads are blocked. The system has deadlocked.
The culprit here is the call to signal. It only unblocks one thread, and it may not pick the thread that is essential to make progress. (In our scenario, Thread 2 must proceed to take money out of Account 2.)
Unfortunately, there is nothing in the Java programming language to avoid or break these deadlocks. You must design your program to ensure that a deadlock situation cannot occur.
12. Thread-Local Variables
In the preceding sections, we discussed the risks of sharing variables between threads. Sometimes, you can avoid sharing by giving each thread its own instance, using the ThreadLocal helper class. For example, the SimpleDateFormat class is not thread-safe. Suppose we have a static variable
public static final SimpleDateFormat dateFormat = new SimpleDateFormat(“yyyy-MM-dd”);
If two threads execute an operation such as
String dateStamp = dateFormat.format(new Date());
then the result can be garbage since the internal data structures used by the dateFormat can be corrupted by concurrent access. You could use synchronization, which is expensive, or you could construct a local SimpleDateFormat object whenever you need it, but that is also wasteful.
To construct one instance per thread, use the following code:
public static final ThreadLocal<SimpleDateFormat> dateFormat
= ThreadLocal.withInitial(() -> new SimpleDateFormat(“yyyy-MM-dd”));
To access the actual formatter, call
String dateStamp = dateFormat.get().format(new Date());
The first time you call get in a given thread, the lambda in the constructor is called. From then on, the get method returns the instance belonging to the current thread.
A similar problem is the generation of random numbers in multiple threads. The java.util.Random class is thread-safe. But it is still inefficient if multiple threads need to wait for a single shared generator.
You could use the ThreadLocal helper to give each thread a separate generator, but Java 7 provides a convenience class for you. Simply make a call such as
int random = ThreadLocalRandom.current().nextInt(upperBound);
The call ThreadLocalRandom.current() returns an instance of the Random class that is unique to the current thread.
13. Why the stop and suspend Methods Are Deprecated
The initial release of Java defined a stop method that simply terminates a thread, and a suspend method that blocks a thread until another thread calls resume. The stop and suspend methods have something in common: Both attempt to control the behavior of a given thread without the thread’s cooperation.
The stop, suspend, and resume methods have been deprecated. The stop method is inherently unsafe, and experience has shown that the suspend method frequently leads to deadlocks. In this section, you will see why these methods are problematic and what you can do to avoid problems.
Let us turn to the stop method first. This method terminates all pending methods, including the run method. When a thread is stopped, it immediately gives up the locks on all objects that it has locked. This can leave objects in an inconsistent state. For example, suppose a TransferRunnable is stopped in the middle of moving money from one account to another, after the withdrawal and before the deposit. Now the bank object is damaged. Since the lock has been relinquished, the damage is observable from the other threads that have not been stopped.
When a thread wants to stop another thread, it has no way of knowing when the stop method is safe and when it leads to damaged objects. Therefore, the method has been deprecated. You should interrupt a thread when you want it to stop. The interrupted thread can then stop when it is safe to do so.
NOTE: Some authors claim that the stop method has been deprecated because it can cause objects to be permanently locked by a stopped thread. However, that claim is not valid. A stopped thread exits all synchronized methods it has called-technically, by throwing a ThreadDeath exception. As a consequence, the thread relinquishes the intrinsic object locks that it holds.
Next, let us see what is wrong with the suspend method. Unlike stop, suspend won’t damage objects. However, if you suspend a thread that owns a lock, then the lock is unavailable until the thread is resumed. If the thread that calls the suspend method tries to acquire the same lock, the program deadlocks: The suspended thread waits to be resumed, and the suspending thread waits for the lock.
This situation occurs frequently in graphical user interfaces. Suppose we have a graphical simulation of our bank. A button labeled Pause suspends the transfer threads, and a button labeled Resume resumes them.
pauseButton.addActionListener(event -> {
for (int i = 0; i < threads.tength; i++)
threads[i].suspend(); // don’t do this
});
resumeButton.addActionListener(event -> {
for (int i = 0; i < threads.tength; i++)
threads[i].resume();
});
Suppose a paintComponent method paints a chart of each account, getBatances method to get an array of balances.
As you will see in Section 12.7.3, “Long-Running Tasks in User Callbacks,” on p. 823, both the button actions and the repainting occur in the same thread, the event dispatch thread. Consider the following scenario:
- One of the transfer threads acquires the lock of the bank object.
- The user clicks the Pause button.
- All transfer threads are suspended; one of them still holds the lock on the bank object.
- For some reason, the account chart needs to be repainted.
- The paintComponent method calls the getBatances method.
- That method tries to acquire the lock of the bank object.
Now the program is frozen.
The event dispatch thread can’t proceed because the lock is owned by one of the suspended threads. Thus, the user can’t click the Resume button, and the threads won’t ever resume.
If you want to safely suspend a thread, introduce a variable suspendRequested and test it in a safe place of your run method—in a place where your thread doesn’t lock objects that other threads need. When your thread finds that the suspendRequested variable has been set, it should keep waiting until it becomes available again.
Source: Horstmann Cay S. (2019), Core Java. Volume I – Fundamentals, Pearson; 11th edition.