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.
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 following section, you’ll see how to synchronize data access.
The test program is of a simulated bank, where money is transferred between accounts. The bank starts with 100 accounts, each with a $1,000 balance. This example randomly selects the source and destination of the transfer. This could cause problems in a multithreaded system, as you can see in 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, you do not know how much money is in any specific bank account at any time. But you do know that the total amount of money in all the accounts should remain unchanged because all the program does is move money from one account to another.
At the end of each transaction, the transfer method recomputes the total and prints it. Here is a typical printout.
...
Thread[Thread-11,5,main]
Thread[Thread-12,5,main]
Thread[Thread-14,5,main]
Thread[Thread-13,5,main]
...
Thread[Thread-36,5,main]
Thread[Thread-35,5,main]
Thread[Thread-37,5,main]
Thread[Thread-34,5,main]
Thread[Thread-36,5,main]
...
Thread[Thread-4,5,main]Thread[Thread-33,5,main] 7.31 from 31 to 32 Total Balance: 99979.24
627.50 from 4 to 5 Total Balance: 99979.24
...
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. The 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 in the code in Listing 1 and the Bank class in Listing 2. The mystery will be unraveled in the next section.
Listing 1. unsynch/UnsynchBankTest.java
package unsynch;
/**
* This program shows data corruption when multiple threads access a data structure.
* @version 1.32 2018-04-10
* @author Cay Horstmann
*/
public class UnsynchBankTest
{
public static final int NACCOUNTS = 100;
public static final double INITIAL_BALANCE = 1000;
public static final double MAX_AMOUNT = 1000;
public static final int DELAY = 10;
public static void main(String[] args)
{
var bank = new Bank(NACCOUNTS, INITIAL_BALANCE);
for (int i = 0; i < NACCOUNTS; i++)
{
int fromAccount = i;
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)
{
}
};
var t = new
t.start();
}
}
}
Listing 2. threads/Bank.java
package threads;
import java.util.*;
/**
* A bank with a number of bank accounts.
*/
public class Bank
{
private final double[] accounts;
/**
* Constructs the bank.
* @param n the number of accounts
* @param initialBalance the initial balance for each account
*/
public Bank(int n, double initialBalance)
{
accounts = new double[n];
Arrays.fill(accounts, initialBalance);
}
/**
* Transfers money from one account to another.
* @param from the account to transfer from
* @param to the account to transfer to
* @param amount the amount to transfer
*/
public void transfer(int from, int to, double amount)
{
if (accounts[from] < amount) return;
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());
}
/**
* Gets the sum of all account balances.
* @return the total balance
*/
public double getTotalBalance()
{
double sum = 0;
for (double a : accounts)
sum += a;
return sum; }
/**
* Gets the number of accounts in the bank.
* @return the number of accounts
*/
public int size()
{
return accounts.length;
}
}
The race condition explained
In the previous section, you ran a program in which several threads updated bank account balances. After a while, errors crept into the bank and some amount of money was either lost or spontaneously created. This problem occurred when two threads simultaneously tried to update the same account. Suppose two threads simultaneously carry out the following instruction:
accounts[to] += amount;
The problem is that these are not atomic operations. The instruction might be processed as follows:
◉ Step 1: Load accounts[to] into a register.
◉ Step 2: Add amount.
◉ Step 3: Move the result back to accounts[to].
Suppose the first thread executes Steps 1 and 2, and then it is pre-empted. 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 1). The 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!)
Figure 1. Simultaneous access by two threads
By the way, you can peek at the JVM bytecode that executes each statement in the class. Run the command
javap -c -v Bank
to decompile the Bank.class file. For example, the line
accounts[to] += amount;
is translated into the following bytecode:
aload_0
getfield #2; //Field accounts:[D
iload_2
dup2
daload
dload_3
dadd
dastore
What these code snippets mean does not matter. The point is that the increment command is made up of several instructions, and the thread executing them might 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. I 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 pre-empt it in the middle of the computation. However, the risk of corruption does not go away completely.
If you run many 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 manifests itself only irregularly.
The real problem is that the work of the transfer method can be interrupted in the middle. If you could ensure that the method runs to completion before the thread loses control, the state of the Bank object would never be corrupted.
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, I believe that it is easier to understand the synchronized keyword after you have seen locks and conditions in isolation. The java.util.concurrent framework provides separate classes for these fundamental mechanisms, which I will explain here. Once you have understood these building blocks, you will learn about the synchronized keyword.
The basic outline for protecting a code block with a ReentrantLock is
myLock.lock(); // a ReentrantLock object
try
{
<em>critical section</em>
}
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.
Caution: It is critically important that the unlock operation is enclosed in a finally clause, because if the code in the critical section throws an exception, the lock must be unlocked. Otherwise, the other threads will be blocked forever.
Note that when you use locks, you cannot use the try-with-resources statement. First off, the unlock method isn’t called close. But even if it were renamed, the try-with-resources statement wouldn’t work because its header expects the declaration of a new variable. However, when you use a lock, you want to keep using the same variable that is shared among threads. Thus, it won’t work.
You can use a lock to protect the transfer method of the Bank class, as in the following:
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 pre-empted 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, the second thread can proceed (see Figure 2).
Figure 2. Comparison of unsynchronized and synchronized threads
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, 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 must call unlock for every call to lock to relinquish the lock. Because of this feature, code protected by a lock can call another method that uses the same lock.
For example, the transfer method calls the getTotalBalance method, which also locks the bankLock object, which now has a hold count of 2. When the getTotalBalance 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.
Be careful to ensure that the code in a critical section is not bypassed by throwing an exception. If an exception is thrown before the end of the section, the finally clause will relinquish the lock, but the object may be left in a damaged state.
Condition objects
Sometimes 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. (For historical reasons, condition objects are often called condition variables.)
To refine the simulation of the bank, you do not want to transfer money out of an account that does not have the funds to cover the transfer. However, you 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, as follows:
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, as follows:
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
while (accounts[from] < amount)
{
// wait
...
}
// transfer funds
...
}
finally
{
bankLock.unlock();
}
}
What do you do when there is not enough money in the account? You can 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, the following sets 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, you 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 signalAll method on the same condition.
When another thread has transferred money, it should call
sufficientFunds.signalAll();
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 re-enter 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 because there is no guarantee that the condition is now fulfilled—the signalAll method merely signals to the waiting threads that the condition may be fulfilled at this time and that it is worth checking for the condition again.
In general, a call to await should be inside a loop of the following form:
while (!(OK to proceed))
condition.await();
It is crucially important that some other thread calls the signalAll method eventually. When a thread calls await, that thread 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.
The rule of thumb is to call signalAll 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. For example, the following code calls signalAll when you have finished the funds transfer:
public void transfer(int from, int to, int amount)
{
bankLock.lock(); try
{
While (accounts[from] < amount)
sufficientFunds.await();
// transfer funds
...
sufficientFunds.signalAll();
}
finally
{
bankLock.unlock();
}
}
Note that the call to signalAll does not immediately activate a waiting thread. The call 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.
Note that a thread can call await, signalAll, or signal on a condition only if it owns the lock of the condition.
If you run the sample program in Listing 3, you will notice that nothing ever goes wrong: The total balance stays at $100,000 forever. No account ever has a negative balance. (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.
Listing 3. synch/Bank.java
package synch;
import java.util.*;
import java.util.concurrent.locks.*;
/**
* A bank with a number of bank accounts that uses locks for serializing access.
*/
public class Bank
{
private final double[] accounts;
private Lock bankLock;
private Condition sufficientFunds;
/**
* Constructs the bank.
* @param n the number of accounts
* @param initialBalance the initial balance for each account
*/
public Bank(int n, double initialBalance)
{
accounts = new double[n];
Arrays.fill(accounts, initialBalance);
bankLock = new ReentrantLock();
sufficientFunds = bankLock.newCondition();
}
/**
* Transfers money from one account to another.
* @param from the account to transfer from
* @param to the account to transfer to
* @param amount the amount to transfer
*/
public void transfer(int from, int to, double amount) throws InterruptedException
{
bankLock.lock();
try
{
while (accounts[from] < amount)
sufficientFunds.await();
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());
sufficientFunds.signalAll();
}
finally
{
bankLock.unlock();
}
}
/**
* Gets the sum of all account balances.
* @return the total balance
*/
public double getTotalBalance()
{
bankLock.lock();
try
{
double sum = 0;
for (double a : accounts)
sum += a;
return sum;
}
finally
{
bankLock.unlock();
}
}
/**
* Gets the number of accounts in the bank.
* @return the number of accounts
*/
public int size()
{
return accounts.length;
}
}
Source: oracle.com
Posts
0 comments:
Post a Comment