Synchronization

In most practical multithreaded applications, two or more threads need to share access to the same objects. 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 next section, you'll see how to synchronize data access.

In the next test program, we simulate a bank with a number of accounts. We randomly generate transactions that move money between these accounts. Each account has one thread. Each transaction moves a random amount of money from the account serviced by the thread to another random account.

The simulation code is straightforward. We have the class Bank with the method TRansfer. This method transfers some amount of money from one account to another. If the source account does not have enough money in it, then the call simply returns. Here is 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 transferRunnable class. Its run method keeps moving money out of a fixed 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.

 class TransferRunnable implements Runnable {    . . .    public void run()    {       try       {          int toAccount = (int) (bank.size() * Math.random());          double amount = maxAmount * 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:

[View full width]
 . . . Thread[Thread-11,5,main]     588.48 from 11 to 44 Total Balance:  100000.00 Thread[Thread-12,5,main]     976.11 from 12 to 22 Total Balance:  100000.00 Thread[Thread-14,5,main]     521.51 from 14 to 22 Total Balance:  100000.00 Thread[Thread-13,5,main]     359.89 from 13 to 81 Total Balance:  100000.00 . . . Thread[Thread-36,5,main]     401.71 from 36 to 73 Total Balance:   99291.06 Thread[Thread-35,5,main]     691.46 from 35 to 77 Total Balance:   99291.06 Thread[Thread-37,5,main]      78.64 from 37 to 3 Total Balance:   99291.06 Thread[Thread-34,5,main]     197.11 from 34 to 69 Total Balance:   99291.06 Thread[Thread-36,5,main]      85.96 from 36 to 4 Total Balance:   99291.06 . . . 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. When you run this program, you may find that errors 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 this bank.

Example 1-3 provides the complete source code. See if you can spot the problem with the code. We will unravel the mystery in the next section.

Example 1-3. UnsynchBankTest.java

   1. /**   2.    This program shows data corruption when multiple threads access a data structure.   3. */   4. public class UnsynchBankTest   5. {   6.    public static void main(String[] args)   7.    {   8.       Bank b = new Bank(NACCOUNTS, INITIAL_BALANCE);   9.       int i;  10.       for (i = 0; i < NACCOUNTS; i++)  11.       {  12.          TransferRunnable r = new TransferRunnable(b, i, INITIAL_BALANCE);  13.          Thread t = new Thread(r);  14.          t.start();  15.       }  16.    }  17.  18.    public static final int NACCOUNTS = 100;  19.    public static final double INITIAL_BALANCE = 1000;  20. }  21.  22. /**  23.    A bank with a number of bank accounts.  24. */  25. class Bank  26. {  27.    /**  28.       Constructs the bank.  29.       @param n the number of accounts  30.       @param initialBalance the initial balance  31.       for each account  32.    */  33.    public Bank(int n, double initialBalance)  34.    {  35.       accounts = new double[n];  36.       for (int i = 0; i < accounts.length; i++)  37.          accounts[i] = initialBalance;  38.    }  39.  40.    /**  41.       Transfers money from one account to another.  42.       @param from the account to transfer from  43.       @param to the account to transfer to  44.       @param amount the amount to transfer  45.    */  46.    public void transfer(int from, int to, double amount)  47.    {  48.       if (accounts[from] < amount) return;  49.       System.out.print(Thread.currentThread());  50.       accounts[from] -= amount;  51.       System.out.printf(" %10.2f from %d to %d", amount, from, to);  52.       accounts[to] += amount;  53.       System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());  54.    }  55.  56.    /**  57.       Gets the sum of all account balances.  58.       @return the total balance  59.    */  60.    public double getTotalBalance()  61.    {  62.       double sum = 0;  63.  64.       for (double a : accounts)  65.          sum += a;  66.  67.       return sum;  68.    }  69.  70.    /**  71.       Gets the number of accounts in the bank.  72.       @return the number of accounts  73.    */  74.    public int size()  75.    {  76.       return accounts.length;  77.    }  78.  79.    private final double[] accounts;  80. }  81.  82. /**  83.    A runnable that transfers money from an account to other  84.    accounts in a bank.  85. */  86. class TransferRunnable implements Runnable  87. {  88.    /**  89.       Constructs a transfer runnable.  90.       @param b the bank between whose account money is transferred  91.       @param from the account to transfer money from  92.       @param max the maximum amount of money in each transfer  93.    */  94.    public TransferRunnable(Bank b, int from, double max)  95.    {  96.       bank = b;  97.       fromAccount = from;  98.       maxAmount = max;  99.    } 100. 101.    public void run() 102.    { 103.       try 104.       { 105.          while (true) 106.          { 107.             int toAccount = (int) (bank.size() * Math.random()); 108.             double amount = maxAmount * Math.random(); 109.             bank.transfer(fromAccount, toAccount, amount); 110.             Thread.sleep((int) (DELAY * Math.random())); 111.          } 112.       } 113.       catch (InterruptedException e) {} 114.    } 115. 116.    private Bank bank; 117.    private int fromAccount; 118.    private double maxAmount; 119.    private int DELAY = 10; 120. } 

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:

1.	Load accounts[to] into a register.
2.	Add amount.
3.	Move the result back to accounts[to].

Now, suppose the first thread executes Steps 1 and 2, and then it is interrupted. 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-4.)

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!)

NOTE

You can actually peek at the virtual machine bytecodes that execute each statement in our 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 bytecodes:

 aload_0 getfield        #2; //Field accounts:[D iload_2 dup2 daload dload_3 dadd dastore 

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 the point of any instruction.

What is the chance of this corruption occurring? We boosted the chance of observing the problem by interleaving the print statements with the statements that update the balance.

If you omit the print statements, the risk of corruption is quite a bit 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 completely go away. If you run lots of threads on a heavily loaded machine, then 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 once every few days.

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, then the state of the bank account object would never be corrupted.

Lock Objects

Starting with JDK 5.0, there are two mechanisms for protecting a code block from concurrent access. Earlier versions of Java used the synchronized keyword for this purpose, and JDK 5.0 introduces the ReentrantLock class. The synchronized keyword automatically provides a lock as well as an associated "condition." We believe that it is easier to understand the synchronized keyword after you have seen locks and conditions in isolation. JDK 5.0 provides separate classes for these fundamental mechanisms, which we explain here and on page 30. We will discuss the synchronized keyword on page 35.

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 blocked 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 {    public void transfer(int from, int to, int amount)    {         bankLock.lock();       try       {          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());       }       finally       {          bankLock.unlock();       }    }    . . .    private Lock bankLock = new ReentrantLock(); // ReentrantLock implements the Lock interface } 

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 1-5).

Figure 1-5. 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, then the lock serves to serialize the access. However, if two threads access different Bank objects, then each thread acquires a different lock and neither thread is blocked. This is as it should be, because the threads cannot interfere with 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 keeps 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 that is protected by a lock can call another method that uses the same locks.

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 require multiple operations to update or inspect a data structure. You are then assured that these operations run to completion before another thread can use the same object.

CAUTION

You need to be careful that code in a critical section is not bypassed through the throwing of an exception. If an exception is thrown before the end of the section, then the finally clause will relinquish the lock but the object may be in a damaged state.

 java.util.concurrent.locks.Lock 5.0 

• void lock()

  acquires this lock; blocks if the lock is currently owned by another thread.

• void unlock()

  releases this lock.

 java.util.concurrent.locks.ReentrantLock 5.0 

• ReentrantLock()

  constructs a reentrant lock that can be used to protect a critical section.

Condition Objects

Often, a thread enters a critical section, only to discover that it can't proceed until a condition is fulfilled. You 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 the thread cannot be interrupted between the test and the insertion. 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 {    public Bank()    {       . . .       sufficientFunds = bankLock.newCondition();    }    . . .    private Condition sufficientFunds; } 

If the TRansfer method finds that sufficient funds are not available, it calls

 sufficientFunds.await(); 

The current thread is now blocked 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 unblocked when the lock is available. Instead, it stays blocked until another thread has called the signalAll method on the same condition.

When another thread transfers money, then it should call

 sufficientFunds.signalAll(); 

This call unblocks all threads that are 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 fulfilledthe signalAll 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.

NOTE

In general, a call to await should always be inside a loop of the 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, it has no way of unblocking itself. It puts its faith in the other threads. If none of them bother to unblock 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, then it also blocks. No thread is left to unblock the others, and the program hangs.

When should you call signalAll? 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. In our example, we call signalAll when we 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. It only unblocks the waiting threads so that they can compete for entry into the object after the current thread has exited the synchronized method.

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, then it becomes blocked again. If no other thread calls signal again, then the system deadlocks.

CAUTION

A thread can only call await, signalAll, or signal on a condition when it owns the lock of the condition.

If you run the sample program in Example 1-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, you need to press CTRL+C to terminate the program.) You may also notice that the program runs a bit slowerthis is the price you pay for the added bookkeeping involved in the synchronization mechanism.

Example 1-4. SynchBankTest.java

   1. import java.util.concurrent.locks.*;   2.   3. /**   4.    This program shows how multiple threads can safely access a data structure.   5. */   6. public class SynchBankTest   7. {   8.    public static void main(String[] args)   9.    {  10.       Bank b = new Bank(NACCOUNTS, INITIAL_BALANCE);  11.       int i;  12.       for (i = 0; i < NACCOUNTS; i++)  13.       {  14.          TransferRunnable r = new TransferRunnable(b, i, INITIAL_BALANCE);  15.          Thread t = new Thread(r);  16.          t.start();  17.       }  18.    }  19.  20.    public static final int NACCOUNTS = 100;  21.    public static final double INITIAL_BALANCE = 1000;  22. }  23.  24. /**  25.    A bank with a number of bank accounts.  26. */  27. class Bank  28. {  29.    /**  30.       Constructs the bank.  31.       @param n the number of accounts  32.       @param initialBalance the initial balance  33.       for each account  34.    */  35.    public Bank(int n, double initialBalance)  36.    {  37.       accounts = new double[n];  38.       for (int i = 0; i < accounts.length; i++)  39.          accounts[i] = initialBalance;  40.       bankLock = new ReentrantLock();  41.       sufficientFunds = bankLock.newCondition();  42.    }  43.  44.    /**  45.       Transfers money from one account to another.  46.       @param from the account to transfer from  47.       @param to the account to transfer to  48.       @param amount the amount to transfer  49.    */  50.    public void transfer(int from, int to, double amount)  51.       throws InterruptedException  52.    {  53.       bankLock.lock();  54.       try  55.       {  56.          while (accounts[from] < amount)  57.             sufficientFunds.await();  58.          System.out.print(Thread.currentThread());  59.          accounts[from] -= amount;  60.          System.out.printf(" %10.2f from %d to %d", amount, from, to);  61.          accounts[to] += amount;  62.          System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());  63.          sufficientFunds.signalAll();  64.       }  65.       finally  66.       {  67.          bankLock.unlock();  68.       }  69.    }  70.  71.    /**  72.       Gets the sum of all account balances.  73.       @return the total balance  74.    */  75.    public double getTotalBalance()  76.    {  77.       bankLock.lock();  78.       try  79.       {  80.          double sum = 0;  81.  82.          for (double a : accounts)  83.             sum += a;  84.  85.          return sum;  86.       }  87.       finally  88.       {  89.          bankLock.unlock();  90.       }  91.    }  92.  93.    /**  94.       Gets the number of accounts in the bank.  95.       @return the number of accounts  96.    */  97.    public int size()  98.    {  99.       return accounts.length; 100.    } 101. 102.    private final double[] accounts; 103.    private Lock bankLock; 104.    private Condition sufficientFunds; 105. } 106. 107. /** 108.    A runnable that transfers money from an account to other 109.    accounts in a bank. 110. */ 111. class TransferRunnable implements Runnable 112. { 113.    /** 114.       Constructs a transfer runnable. 115.       @param b the bank between whose account money is transferred 116.       @param from the account to transfer money from 117.       @param max the maximum amount of money in each transfer 118.    */ 119.    public TransferRunnable(Bank b, int from, double max) 120.    { 121.       bank = b; 122.       fromAccount = from; 123.       maxAmount = max; 124.    } 125. 126.    public void run() 127.    { 128.       try 129.       { 130.          while (true) 131.          { 132.             int toAccount = (int) (bank.size() * Math.random()); 133.             double amount = maxAmount * Math.random(); 134.             bank.transfer(fromAccount, toAccount, amount); 135.             Thread.sleep((int) (DELAY * Math.random())); 136.          } 137.       } 138.       catch (InterruptedException e) {} 139.    } 140. 141.    private Bank bank; 142.    private int fromAccount; 143.    private double maxAmount; 144.    private int repetitions; 145.    private int DELAY = 10; 146. } 

 java.util.concurrent.locks.Lock 5.0 

• Condition newCondition()

  returns a condition object that is associated with this lock.

 java.util.concurrent.locks.Condition 5.0 

• void await()

  puts this thread on the wait set for this condition.

• void signalAll()

  unblocks all threads in the wait set for this condition.

• void signal()

  unblocks one randomly selected thread in the wait set for this condition.

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.

Before the Lock and Condition interfaces were added to JDK 5.0, the Java language used a different concurrency mechanism. Ever since version 1.0, every object in Java has an implicit lock. If a method is declared with the synchronized keyword, then the object's lock protects the entire method. That is, to call the method, a thread must acquire the object lock.

In other words,

public synchronized void method()
{
   method body
}

is the equivalent of

public void method()
{
   implicitLock.lock();
   try
   {
      method body
   }
   finally { implicitLock.unlock(); }
}

For example, instead of using an explicit lock, we can simply declare the transfer method of the Bank class as synchronized.

The implicit 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

implicitCondition.await();
implicitCondition.signalAll();

NOTE

The wait and signal methods belong to the Object class. The Condition methods had to be named await and signalAll so that they don't conflict with the final methods wait and notifyAll methods of the Object class.

For example, you can implement the Bank class in Java like this:

 class Bank {    public synchronized void transfer(int from, int to, int amount) throws InterruptedException    {       while (accounts[from] < amount)          wait(); // wait on object lock's single condition       accounts[from] -= amount;       accounts[to] += amount;       notifyAll(); // notify all threads waiting on the condition    }    public synchronized double getTotalBalance() { . . . }    private double accounts[]; } 

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 implicit lock, and that the lock has an implicit condition. The lock manages the threads that try to enter a synchronized method. The condition manages the threads that have called wait.

However, the implicit locks and conditions have some limitations. Among them are:

• 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.

• The virtual machine locking primitives do not map well to the most efficient locking mechanisms available in hardware.

What should you use in your codeLock and Condition objects or synchronized methods? Here is our recommendation:

1. 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.util.concurrent package that do all the locking for you. For example, on page 48, you will see how to use a blocking queue to synchronize threads that work on a common task.

2. If the synchronized keyword works for your situation, by all means, use it. You write less code and have less room for error. Example 1-5 shows the bank example, implemented with synchronized methods.

3. Use Lock/Condition if you specifically need the additional power that these constructs give you.

NOTE

At least for now, using the synchronized keyword has an added benefit. Tools that monitor the virtual machine can report on the implicit locks and conditions, which is helpful for debugging deadlock problems. It will take some time for these tools to be extended to the java.util.concurrent mechanisms.

Example 1-5. SynchBankTest2.java

   1. /**   2.    This program shows how multiple threads can safely access a data structure, using   3.    synchronized methods.   4. */   5. public class SynchBankTest2   6. {   7.    public static void main(String[] args)   8.    {   9.       Bank b = new Bank(NACCOUNTS, INITIAL_BALANCE);  10.       int i;  11.       for (i = 0; i < NACCOUNTS; i++)  12.       {  13.          TransferRunnable r = new TransferRunnable(b, i, INITIAL_BALANCE);  14.          Thread t = new Thread(r);  15.          t.start();  16.       }  17.    }  18.  19.    public static final int NACCOUNTS = 100;  20.    public static final double INITIAL_BALANCE = 1000;  21. }  22.  23. /**  24.    A bank with a number of bank accounts.  25. */  26. class Bank  27. {  28.    /**  29.       Constructs the bank.  30.       @param n the number of accounts  31.       @param initialBalance the initial balance  32.       for each account  33.    */  34.    public Bank(int n, double initialBalance)  35.    {  36.       accounts = new double[n];  37.       for (int i = 0; i < accounts.length; i++)  38.          accounts[i] = initialBalance;  39.    }  40.  41.    /**  42.       Transfers money from one account to another.  43.       @param from the account to transfer from  44.       @param to the account to transfer to  45.       @param amount the amount to transfer  46.    */  47.    public synchronized void transfer(int from, int to, double amount)  48.       throws InterruptedException  49.    {  50.       while (accounts[from] < amount)  51.          wait();  52.       System.out.print(Thread.currentThread());  53.       accounts[from] -= amount;  54.       System.out.printf(" %10.2f from %d to %d", amount, from, to);  55.       accounts[to] += amount;  56.       System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());  57.       notifyAll();  58.    }  59.  60.    /**  61.       Gets the sum of all account balances.  62.       @return the total balance  63.    */  64.    public synchronized double getTotalBalance()  65.    {  66.       double sum = 0;  67.  68.       for (double a : accounts)  69.          sum += a;  70.  71.       return sum;  72.    }  73.  74.    /**  75.       Gets the number of accounts in the bank.  76.       @return the number of accounts  77.    */  78.    public int size()  79.    {  80.       return accounts.length;  81.    }  82.  83.    private final double[] accounts;  84. }  85.  86. /**  87.    A runnable that transfers money from an account to other  88.    accounts in a bank.  89. */  90. class TransferRunnable implements Runnable  91. {  92.    /**  93.       Constructs a transfer runnable.  94.       @param b the bank between whose account money is transferred  95.       @param from the account to transfer money from  96.       @param max the maximum amount of money in each transfer  97.    */  98.    public TransferRunnable(Bank b, int from, double max)  99.    { 100.       bank = b; 101.       fromAccount = from; 102.       maxAmount = max; 103.    } 104. 105.    public void run() 106.    { 107.       try 108.       { 109.          while (true) 110.          { 111.             int toAccount = (int) (bank.size() * Math.random()); 112.             double amount = maxAmount * Math.random(); 113.             bank.transfer(fromAccount, toAccount, amount); 114.             Thread.sleep((int) (DELAY * Math.random())); 115.          } 116.       } 117.       catch (InterruptedException e) {} 118.    } 119. 120.    private Bank bank; 121.    private int fromAccount; 122.    private double maxAmount; 123.    private int repetitions; 124.    private int DELAY = 10; 125. } 

 java.lang.Object 1.0 

• void notifyAll()

  unblocks the threads that called wait on this object. This method can only be called from within a synchronized method or block. The method throws an IllegalMonitorStateException if the current thread is not the owner of the object's lock.

• void notify()

  unblocks one randomly selected thread among the threads that called wait on this object. This method can only be called from within a synchronized method or block. The method throws an IllegalMonitorStateException if the current thread is not the owner of the object's lock.

• void wait()

  causes a thread to wait until it is notified. This method can only be called from within a synchronized method. It throws an IllegalMonitorStateException if the current thread is not the owner of the object's lock.

• void wait(long millis)

• void wait(long millis, int nanos)

  causes a thread to wait until it is notified or until the specified amount of time has passed. These methods can only be called from within a synchronized method. They throw an IllegalMonitorStateException if the current thread is not the owner of the object's lock.

  Parameters:	millis	The number of milliseconds
  	nanos	The number of nanoseconds, < 1,000,000

  
  

Monitors

The 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. Because 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] >= balance 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 implicit lock and an implicit condition. If a method is declared with the synchronized keyword, then it acts like a monitor method. The condition variable is accessed by calling wait/notify/notifyAll.

However, a Java object differs from a monitor in two important ways, compromising its security:

• Fields are not required to be private.

• Methods are not required to be synchronized.

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:3845, April 1999]

Synchronized Blocks

However, a Java object differs from a monitor in three ways:

• Fields are not required to be private.

• Methods are not required to be synchronized.

• The lock has only one condition.

If you deal with legacy code, you need to know something about the built-in synchronization primitives. Recall that each object has a lock. A thread can acquire the lock in one of two ways, by calling a synchronized method or by entering a synchronized block. If the thread calls obj.method(), it acquires the lock for obj. Similarly, if a thread enters a block of the form

synchronized (obj) // this is the syntax for a synchronized block
{
   critical section
}

then the thread acquires the lock for obj. The lock is reentrant. If a thread has acquired the lock, it can acquire it again, incrementing the hold count. In particular, a synchronized method can call other synchronized methods with the same implicit parameter without having to wait for the lock.

You will often find "ad hoc" locks in legacy code, such as

 class Bank {    public void transfer(int from, int to, int amount)    {       synchronized (lock) // an ad-hoc lock       {          accounts[from] -= amount;          accounts[to] += amount;       }       System.out.println(. . .);    }    . . .    private double accounts[];    private Object lock = new Object(); } 

Here, the lock object is created only to use the lock that every Java object possesses.

It is legal to declare static methods as synchronized. If such a method is called, it acquires the lock of the associated class object. For example, if the Bank class has a static synchronized method, then the lock of the Bank.class object is locked when it is called.

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, then 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 http://www.jcp.org/en/jsr/detail?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 http://www-106.ibm.com/developerworks/java/library/j-jtp02244.html.

NOTE

Brian Goetz coined the following "synchronization motto": "If you write a variable which may next be read by another thread, or you read a variable which may have last been written by another thread, you must use synchronization."

The volatile keyword offers a lock-free mechanism for synchronizing access to an instance field. If you declare a field as volatile, 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. You have two choices:

1. Use a lock, for example:

    public synchronized boolean isDone() { return done; } private boolean done; 

   
   

   (This approach has a potential drawback: the isDone method can block if another thread has locked the object.)

2. Declare the field as volatile:

    public boolean isDone() { return done; } private volatile boolean done; 

   
   

Of course, accessing a volatile variable will be slower than accessing a regular variablethat is the price to pay for thread safety.

NOTE

Prior to JDK 5.0, the semantics of volatile were rather permissive. The language designers attempted to give implementors leeway in optimizing the performance of code that uses volatile fields. However, the old specification was so complex that implementors didn't always follow it, and it allowed confusing and undesirable behavior, such as immutable objects that weren't truly immutable.

In summary, concurrent access to a field is safe in these three conditions:

• The field is volatile.

• The field is final, and it is accessed after the constructor has completed.

• The field access is protected by a lock.

Deadlocks

Locks and conditions cannot solve all problems that might arise in multithreading. Consider the following situation:

Account 1: $1,200

Account 2: $1,300

Thread 1: Transfer $300 from Account 1 to Account 2

Thread 2: Transfer $400 from Account 2 to Account 1

As Figure 1-6 indicates, Threads 1 and 2 are clearly blocked. Neither can proceed because the balances in Accounts 1 and 2 are insufficient.

Figure 1-6. A deadlock situation

Is it possible that all threads are 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. Because there are 100 accounts and a total of $100,000 in them, at least one of the accounts must have more than $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 thread with a maxAmount of 2000 and run the program. The program will run for a while and then hang.

TIP

When the program hangs, type CTRL+\. You will get a thread dump that lists all threads. Each thread has a stack trace, telling you where it is currently blocked.

Another way to create a deadlock is to make the i'th thread responsible for putting money into the i'th account, rather than for taking it out of the i'th 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 TRansferRunnable 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 signalAll method to signal in the SynchBankTest program. You will find that the program hangs eventually. (Again, it is best to 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,

Thread 1: Transfer $997 to 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.

Fairness

When you construct a ReentrantLock, you can specify that you want a fair locking policy:

 Lock fairLock = new ReentrantLock(true); 

A fair lock favors the thread that has been waiting for the longest time. However, this fairness guarantee can be a significant drag on performance. Therefore, by default, locks are not required to be fair.

Even if you use a fair lock, you have no guarantee that the thread scheduler is fair. If the thread scheduler chooses to neglect a thread that has been waiting a long time for the lock, then it doesn't get the chance to be treated fairly by the lock.

CAUTION

It sounds nicer to be fair, but fair locks are a lot slower than regular locks. You should only enable fair locking if you have a specific reason why fairness is essential for your problem. This is definitely an advanced technique.

 java.util.concurrent.locks.ReentrantLock 5.0 

• ReentrantLock(boolean fair)

  constructs a lock with the given fairness policy.

Lock Testing and Timeouts

A thread blocks indefinitely when it calls the lock method to acquire a lock that is owned by another thread. You can be more cautious about acquiring a lock. The tryLock method tries to acquire a lock and returns true if it was successful. Otherwise, it immediately returns false, and the thread can go off and do something else.

 if (myLock.tryLock())    // now the thread owns the lock    try  { . . .  }    finally  { myLock.unlock(); } else   // do something else 

You can call tryLock with a timeout parameter, like this:

 if (myLock.tryLock(100, TimeUnit.MILLISECONDS)) . . . 

TimeUnit is an enumeration with values SECONDS, MILLISECONDS, MICROSECONDS, and NANOSECONDS.

These methods deal with fairness and thread interruption in subtly different ways.

The tryLock method with a timeout parameter respects fairness in the same way as the lock method. But the tryLock method without timeout can barge inif the lock is available when the call is made, the current thread gets it, even if another thread has been waiting to lock it. If you don't want that behavior, you can always call

 if (myLock.tryLock(0, TimeUnit.SECONDS)) . . . 

The lock method cannot be interrupted. If a thread is interrupted while it is waiting to acquire a lock, the interrupted thread continues to be blocked until the lock is available. If a deadlock occurs, then the lock method can never terminate.

However, if you call tryLock with a timeout, then an InterruptedException is thrown if the thread is interrupted while it is waiting. This is clearly a useful feature because it allows a program to break up deadlocks.

You can also call the lockInterruptibly method. It has the same meaning as tryLock with an infinite timeout.

When you wait on a condition, you can also supply a timeout:

 myCondition.await(100, TimeUnit.MILLISECONDS)) 

The await method returns if another thread has activated this thread by calling signalAll or signal, or if the timeout has elapsed, or if the thread was interrupted.

The await methods throw an InterruptedException if the waiting thread is interrupted. In the (perhaps unlikely) case that you'd rather continue waiting, use the awaitUninterruptibly method instead.

 java.util.concurrent.locks.Lock 5.0 

• boolean tryLock()

  tries to acquire the lock without blocking; returns true if it was successful. This method grabs the lock if it is available even if it has a fair locking policy and other threads have been waiting.

• boolean tryLock(long time, TimeUnit unit)

  tries to acquire the lock, blocking no longer than the given time; returns true if it was successful.

• void lockInterruptibly()

  acquires the lock, blocking indefinitely. If the thread is interrupted, throws an InterruptedException.

 java.util.concurrent.locks.Condition 5.0 

• boolean await(long time, TimeUnit unit)

  enters the wait set for this condition, blocking until the thread is removed from the wait set or the given time has elapsed. Returns false if the method returned because the time elapsed, TRue otherwise.

• void awaitUninterruptibly()

  enters the wait set for this condition, blocking until the thread is removed from the wait set. If the thread is interrupted, this method does not throw an InterruptedException.

Read/Write Locks

The java.util.concurrent.locks package defines two lock classes, the ReentrantLock that we already discussed and the ReentrantReadWriteLock class. The latter is useful when there are many threads that read from a data structure and fewer threads that modify it. In that situation, it makes sense to allow shared access for the readers. Of course, a writer must still have exclusive access.

Here are the steps that are necessary to use read/write locks:

1.	Construct a ReentrantReadWriteLock object: private ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
2.	Extract read and write locks: private Lock readLock = rwl.readLock(); private Lock writeLock = rwl.writeLock();
3.	Use the read lock in all accessors: public double getTotalBalance() { readLock.lock(); try { . . . } finally { readLock.unlock(); } }
4.	Use the write lock in all mutators: public void transfer(. . .) { writeLock.lock(); try { . . . } finally { writeLock.unlock(); } }

 java.util.concurrent.locks.ReentrantReadWriteLock 5.0 

• Lock readLock()

  gets a read lock that can be acquired by multiple readers, excluding all writers.

• Lock writeLock()

  gets a write lock that excludes all other readers and writers.

Why the stop and suspend Methods Are Deprecated

JDK 1.0 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.

Both of these methods have been deprecated since JDK 1.2. 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 transferThread 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 calledtechnically, by throwing a ThreadDeath exception. As a consequence, the thread relinquishes the 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, then 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(new    ActionListener()    {       public void actionPerformed(ActionEvent event)       {          for (int i = 0; i < threads.length; i++)             threads[i].suspend(); // Don't do this       }    }); resumeButton.addActionListener(. . .); // calls resume on all transfer threads 

Suppose a paintComponent method paints a chart of each account, calling a getBalances method to get an array of balances.

As you will see on page 72, both the button actions and the repainting occur in the same thread, the event dispatch thread. Consider the following scenario:

1. One of the transfer threads acquires the lock of the bank object.

2. The user clicks the Pause button.

3. All transfer threads are suspended; one of them still holds the lock on the bank object.

4. For some reason, the account chart needs to be repainted.

5. The paintComponent method calls the getBalances method.

6. 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 methodsomewhere your thread doesn't lock objects that other threads need. When your thread finds that the suspendRequested variable has been set, keep waiting until it becomes available again.

The following code framework implements that design:

 public void run() {    while (. . .)    {       . . .       if (suspendRequested)       {          suspendLock.lock();          try { while (suspendRequested) suspendCondition.await(); }          finally { suspendLock.unlock(); }       }    } } public void requestSuspend() { suspendRequested = true; } public void requestResume() {    suspendRequested = false;    suspendLock.lock();    try { suspendCondition.signalAll(); }    finally { suspendLock.unlock(); } } private volatile boolean suspendRequested = false; private Lock suspendLock = new ReentrantLock(); private Condition suspendCondition = suspendLock.newCondition();