Software System Components 2 - Year 2, Semester 2, Week 8

Concurrency - Dr Steve Vickers

2: Thread interaction

This week we look at how threads interact with each other, and in particular when they share access to objects. As I wrote last week, this sets some of the most dangerous traps in all of programming. If you don't write your programs in a safe way, the thread interaction can cause sporadic faults that are very difficult to reproduce, and in which the code does not appear to be executing as written. It is very hard to remove such faults by testing and correction, so it is very important to understand the potential problems right from the start and to write the code carefully and correctly so as to avoid the problems. This takes practice.

Remember too that these are general problems of concurrency. They apply not only with threads, but with any situation where different computations are running at the same time and interacting with each other. For example, if different people are accessing a database over the web you get similar problems

At the end of this week's lectures you should know -
Some of the examples this week are adapted from Horstmann's book "Big Java", which is recommended.

Race conditions

A race condition is a situation where, to work properly, a thread has to race to do something before another thread interferes. They are unsafe, because sometimes the thread might lose the race and not work correctly. The solution is to block other threads from interfering.

The problems we look at this week are general problems of concurrency. They apply not only with threads, but with any situation where different computations are running at the same time and interacting with each other.
Example
Suppose you want to book four theatre tickets over the web. The following happens.
  1. The website says what nights there are tickets available.
  2. You choose a night.
  3. You give your credit card details.
  4. The website waits for payment to go through.
  5. The website confirms the ticket details.
Suppose there are 4 tickets left for Friday, and you and someone else are both trying to book them at the same time. There is a race between you and them, and the system must somehow decide who wins. These race conditions are rather typical of interference between concurrent processes. In the end, one person should pay the money and get the tickets.

One outcome that would not be satisfactory is if the system offers the tickets to both parties, accepts payment from both, and confirms the transaction with both. Also, you wouldn't want to go through the trouble of entering credit card details only to be told at the end that someone else bought the tickets after all. And it would be messy for the system if it put the payment through and then discovered that the tickets had gone. Hence when one party chooses the night, they should be given a temporary reservation, or lock, on the tickets that stops any other party trying to buy them.

It might also be worth trying to avoid the situation where a payment fails to go through (for instance, because it is over the credit limit), but meanwhile someone else is told there are no tickets left. That someone else could perhaps be given the option of waiting a short while in case the temporary reservation is lost.

Example: bank account
This example is adapted from Horstmann's "Big Java". It uses 4 classes BankAccount, DepositRunnable, WithdrawRunnable and BankAccountThreadTester. A bank account has a balance, and methods for making deposits and withdrawals. The main method (in BankAccountThreadTester) sets up two threads. One makes 1000 deposits of 100p each, while the other makes 1000 withdrawals of 100p each. Overdrafts (negative balances) are allowed. At the end, the balance should be exactly 0, and if you got any other answer you would think of changing your bank.

But just sometimes you do get other answers, normally only 100 or -100.

Interleaving

When two threads are running concurrently you think of them as running "at the same time", but the reality is more complex. If the computer has only one processor, then actually only one thread can be running at any given time. Periodically, the clock in the computer issues a signal that forces the processor to stop executing the thread code, and instead execute a small piece of code from the operating system. At that point, the operating system can arrange for a different thread to take over. Thus the code from different threads can be "interleaved". This gives the illusion that they are all performing their tasks simultaneously.

Even if the computer has several processors, their accesses (reads or writes) to a shared variable (e.g. balance in the bank account example) occur in a definite order and so there is still some interleaving.

From the point of view of one thread, the interleaved parts or variable accesses of another thread can occur absolutely anywhere, even when the first thread is in the middle of doing something. That is how threads can interfere with each other.
Example
Here is a typical part of the printout where something goes wrong in the bank account example. Clearly something has gone wrong, since after the first line we have two more withdrawals and two more desposits, so the final balance should be 100, not 0.

Depositing 100, new balance is 100
Withdrawing 100, new balance is 0
Depositing 100, new balance is 200
Depositing 100, new balance is 100
Withdrawing 100, new balance is 0

The code for deposit is, in effect, this.

int newBalance = balance + 100;
System.out.println("Depositing 100, new balance is " + newBalance);
balance = newBalance;

(Note: each thread has its own buffer for System.out.print. The buffer is flushed to the standard output on the println call.)

There is a race condition here. Once a thread has done "newBalance = balance + 100;", the race is to write the new value back to balance before some other thread reads the previous, out of date, value.

Here is an example of an unfortunate interleaving that would produce part of the output above. (nB stands for newBalance.)

Deposits
 balance
 output
 Withdrawals

100
 "Dep. 100, nB = 100"
nB = 200





nB = 0


"WD 100, nB = 0"
 println
println
"Dep. 100, nB = 200"
balance = nB
 200


0
balance = nB
nB = 100


println
"Dep. 100, nB = 100"
balance = nB
 100


As you can see, the first deposit and withdrawal are in a race. They both base their calculations on the same value of balance (100). The deposit writes its calculated new value (200), but that is overwritten by the value calculated by the withdrawal (0). Thus the deposit is unrecorded.

Locks

Mutual exclusion

The dangerous part of the bank account example is when the balance field is updated. A thread (executing deposit or withdraw) must first read balance, then calculate the new value, then write balance. Interference happens if some other thread updates balance in between the read and the write. Then the first thread is working with an incorrect, out of date value. The piece of code

int newBalance = balance + 100;
System.out.println("Depositing 100, new balance is " + newBalance);
balance = newBalance;

is called a critical region, which means it is not safe for any other thread to access balance while a thread is executing in its critical region.

The problem is summarized in the phrase mutual exclusion. The threads must have mutually exclusive access to balance, in other words the threads exclude each other in their access to it - if one thread is accessing balance, then the others must not.

Locks

A lock is an object that has the essence of mutual exclusion. Only one thread at a time can "own" the lock - the others are excluded and must wait.

The general way to use locks in Java is specified in the Lock interface. Suppose l is a lock.

lock()
To attempt to take ownership of l (or acquire it or grab it), you call l.lock().

If no other thread already owns it, then you now own the lock and your code continues executing.

If some other thread does already own the lock, then you have to wait. (The lock itself keeps a list of the threads waiting to own it. there may be several, of course.) Your thread is blocked. Its code stops executing until it gets ownership of the lock.

unlock()
If you own the lock but don't need it any more, you call l.unlock(). Then, if any other threads are blocked waiting for it, one of them is given the lock and may start executing again.

Don't call unlock unless you already own the lock. An exception (e.g. IllegalMonitorStateException) is likely to be thrown.

Various classes implement the Lock interface. It's normally easiest to use ReentrantLock. ("Reentrant" means that it behaves sensibly when a thread calls lock() on a thread it already owns.)

Using locks - the general idea

Suppose there is some resource to be shared by several threads, accessing it only one at a time. A typical example is a field in an object whose methods might be executed on several threads. The field balance in BankAccount was like this. You create a lock to protect that shared resource. Then you call lock() before and unlock() after each critical region.

acquire the lock with lock() ... critical region (accessing the shared resource) ... release the lock with unlock()

Then no thread can be executing its critical region unless it owns the lock, and that means only one thread at a time.

lock-try-finally-unlock

You must remember a special way to release locks in Java.
It is very important to release the lock when you have finished with it. Otherwise no other thread can access the resource. In Java you must make sure of this even if the critical region throws an exception, and there is a special mechanism for this using "try {...} finally {...}". This executes the statements after "try", and then, even if an exception was thrown, executes the statements after "finally". (As you know, the keyword "try" is also used with "catch". It is possible to mix them in a try ... catch ... finally statement, although this can get confusing.)

For a critical region protected by a lock l, use Java code like this.

l.lock();
try {
    critical region
} finally {
    l.unlock();
}

You should always use this lock-try-finally-unlock pattern.
Example: bank account
In the bank account example, the shared resource is the balance field. The critical regions where it is accessed are in the deposit and withdraw methods. The BankAccount class must be modified as follows.

First, import the package containing the lock classes (including Lock and ReentrantLock).

import java.util.concurrent.locks.*;

Next, add a new field for the lock.

private Lock balanceChangeLock;

Next, initialize this in the constructor with a line

balanceChangeLock = new ReentrantLock();

Now protect the critical regions in deposit and withdraw. Here is how it is done in deposit.

public void deposit(int amount) {
    balanceChangeLock.lock();
    try {
        System.out.print("Depositing " + amount);
        int newBalance = balance + amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
    } finally {
        balanceChangeLock.unlock();
    }
}

Acquiring a lock for read access

I described mutual exclusion for access to a shared resource such as balance. What about read access? Does the getter method getBalance need to acquire the lock? It does not update the balance field, so there is no race condition involved - it will not interfere with other threads.

However, there is a subtle reason why it is recommended that the lock should be acquired even for read access. Some processor chips "cache" the fields internally instead of working directly on the main RAM all the time. There is therefore a question about how often they must update the RAM version. The Java "memory model" gives rules for this. They are quite complicated, but a consequence of them is that you can be sure of getting the most up-to-date value of the field if you acquire its lock before reading it. For example, getBalance would be rewritten as this.

public int getBalance() {
    balanceChangeLock.lock();
    try {
        return balance;
    } finally {
        balanceChangeLock.unlock();
    }
}

Synchronized

There is a pattern that was standard before Java 1.5 and is still often convenient. As it happens, every object in Java has a lock built in to it. You acquire and release it by using a method specified as synchronized. This automatically does lock-try-method body-finally-unlock, using the lock built into the object executing the method. Typically, the lock on the object is used to protect its fields.
Example
Using this pattern, the deposit method from BankAccount would appear as this.

public synchronized void deposit(int amount) {
    System.out.print("Depositing " + amount);
    int newBalance = balance + amount;
    System.out.println(", new balance is " + newBalance);
    balance = newBalance;
}

I recommend you first to make sure you understand how the explicit locks work, and then to use "synchronized" when convenient.

Thread safety

If a class takes proper care to protect its fields with locks, so that it can work with multiple threads, then it is called thread safe.

You need to be aware of an important fact, that Swing is not thread safe. This is deliberate. If Swing components used locks then the event dispatch thread might sometimes be blocked, and that risks freezing the GUI. Instead, the general rule is to manipulate Swing components only on the event dispatch thread.

The repaint-paint pattern is a good example of this. Repaint can be called on any thread, but it doesn't directly do the repainting. Instead a paint is put on the queue of jobs for the event dispatch thread to execute.

There are one or two exceptions to this rule. setText can normally be called from any thread. Also, if a component has not yet been set visible or added to a visible container, then any thread (typically the main thread when it creates objects) can safely work on it.

Apart from that, if you need to manipulate a Swing component from any other thread then there is a mechanism for putting the manipulation into the queue of jobs for the event dispatch thread. You create a run-object (its class implements Runnable) whose run method does the manipulation, and use it as the argument to a call of the static method invokeLater in class java.awt.EventQueue.

Conditions

Normally, "condition" just means some property that may be true or false. We have also seen it used in the phrase "race condition". But with locks the word has a special meaning which I shall now explain.

Deadlock

Locks are intended to ensure safety, blocking threads that might interfere with each other and forcing them to wait. Sometimes this can go too far, with threads unable to proceed at all because each one is waiting for the others to do something. This is called deadlock.

Deadlock can occur in ordinary life too. Here is an example of a traffic jam that is gridlocked. None of the cars can move, because each one is waiting for another one to get out of its way.



v
>
 >
 >
 >
 >
 v

^


v

^


v

^


v

^
 <
 <
 <
 <
 <

^






Deadlock can easily occur in computer programs because of programming errors. Suppose there are two shared resources, protected by locks lA and lB. A thread that wishes to use the resources must acquire both resources. Now suppose one method acquires lA first, like this,

lA.lock();
lB.lock();
try {
    critical region
} finally {
    lA.unlock();
    lB.unlock();
}

while another method acquires them in the reverse order - lB first, then lA. If two threads call the two methods, then they might reach deadlock with each thread owning one of the locks but unable to acquire the other.

Waiting for a state of affairs

One form of deadlock is the following. A thread holds a lock l, but it cannot proceed because it is waiting for a certain state of affairs. Unfortunately, no other thread can bring about that state of affairs, because they would first need to acquire the lock l.

A condition is a way in which the first thread can temporarily release the lock so that other threads can acquire it.
Example: bank account with no overdraft
This example is again taken from Horstmann's "Big Java", and develops the previous bank account example.

Suppose balance is not allowed to go negative: there is an invariant to say "balance >= 0". The withdraw method must now be revised, since at present it makes no checks and can easily break the new invariant.

One solution is for withdraw to throw an exception if it would otherwise leave a negative balance. That is roughly what banks usually do.

An alternative idea is for withdraw to wait until another thread has called deposit and made the balance big enough.

Here is a first attempt.

public void withdraw(int amount) {
    while (balance < amount) {
    }
    balanceChangeLock.lock();
    try {
        System.out.print("Withdrawing " + amount);
        int newBalance = balance - amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
    } finally {
        balanceChangeLock.unlock();
    }
}

This, of course, has exactly the unsafe interference problems that locks were designed to cure. Between discovering balance >= amount (so the while loop stops) and acquiring the lock, some other thread might have made another withdrawal.

Here is a second attempt.

public void withdraw(int amount) {
    balanceChangeLock.lock();
    try {
        while (balance < amount) {
        }
        System.out.print("Withdrawing " + amount);
        int newBalance = balance - amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
    } finally {
        balanceChangeLock.unlock();
    }
}

Unfortunately, this leads to deadlock. The thread calling withdraw owns the lock and it waiting for some other thread to deposit more funds. But no other thread can do that, since they would first have to acquire the lock.

Our final attempt uses conditions.

The java.util.concurrent.locks.Condition interface

The usage of conditions is specified in an interface, java.util.concurrent.locks.Condition. Each condition is attached to a particular lock, and is created by calling the factory method newCondition() on that lock.

There are two Condition methods that work together: await() and signalAll().

When a thread calls await() it releases the lock and is blocked. The condition object keeps track of all the threads that are waiting on it. Normally they stay blocked until another thread calls signalAll() on the condition. At that point all the waiting threads are allowed to run again, though they still have to wait their turn to acquire the lock. When a thread owns the lock again, it is allowed at last to return from await() and continue its execution.

await() also throws InterruptedException in the same way as Thread.sleep(), so again you have to decide how to handle those exceptions.

A thread should only call await() or signalAll() on a condition if it already owns the corresponding lock. Otherwise an exception will normally be thrown.

Using a condition

Remember that each condition is attached to a lock, and a lock is used to control access to some shared resource. You should use the condition in connection with some testable property of the shared resource, like "enough funds for a withdrawal".

await() is called by a thread when it owns the lock but also needs that testable property to hold and discovers that it does not. By calling await(), the thread says, "I can't go on, I might as well be blocked, and I'll release the lock."

Almost always, the await() is in a loop like this.

while (property is false) {
    condition.await();
}

When the thread finishes the loop, it knows the property is true, and it also owns the lock so no other thread can access the resource and make the property go false unexpectedly.

Example: bank account with no overdraft
This continues the example taken from "Big Java". The shared resource is the balance field, and its lock is balanceChangeLock. The testable property of this (in a call of withdraw) is amount <= balance, so we create a condition sufficientFunds. We are rewriting the BankAccount class.

First, declare a field

private Condition sufficientFunds;

Next, in the constructor, we initialize this by

sufficientFunds = balanceChangeLock.newCondition();

Next, the withdraw method must be rewritten as follows.

/**
 * Withdraws money from this bank account, waiting
 *   until sufficient funds are available.
 * @param amount amount to withdraw.
 * @throws InterruptedException if thread interrupted
 *   before withdrawal can be made.
 *   In that case the balance is unchanged.
 */
public void withdraw(int amount)
    throws InterruptedException
{
    balanceChangeLock.lock();
    try {
        while (balance < amount) {
            sufficientFunds.await();
        }
        System.out.print("Withdrawing " + amount);
        int newBalance = balance - amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
    } finally {
        balanceChangeLock.unlock();
    }
}

Notice how the method now throws InterruptedException. We must either do that or catch the exception, because it is checked and is thrown by await(). However, we cannot sensibly catch the exception because we do not know in this method how the thread should be terminated. The Javadoc comment has been changed to show this.

Finally, we must rewrite the deposit method by making it call signalAll()..

public void deposit(int amount) {
    balanceChangeLock.lock();
    try {
        System.out.print("Depositing " + amount);
        int newBalance = balance + amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
        sufficientFunds.signalAll();
    } finally {
        balanceChangeLock.unlock();
    }
}

Conditions with synchronized methods

Just as every object has a built-in lock, so also every one of those locks has a built-in condition. It is used in a similar way to the conditions described above, but instead of using await() and signalAll() from the Condition interface you use wait() and notifyAll() from the Object class.

Summary

Notes

Different kinds of classes

You are already used to using public classes. Each has to be in its own file, and the filename has to match the class name. Here are some brief notes on other kinds.

Extra non-public classes in a file: Suppose you have a file containing a public class. You can also add other class definitions after the public class. They cannot themselves be public (because their names don't match the filename), but they are accessible throught the package containing the file. Warning - if the package has two of these with the same name, there can be ambiguity.

Inner classes are defined inside the definition of another class. For example,

public class C {
    :
    :
    //now here is the inner class
    private static class D {
        :
        :
    }
}

They can be private or public, just like fields and methods.

Static inner classes behave more or less like other classes.

For non-static inner classes, each instance is attached to an instance of the outer class. This means that the methods in the inner class can access the fields in the outer class.

Anonymous inner classes are often useful for defining action listeners and run objects. There were some examples in last week's notes. You create a single instance by saying "new" and then the definition of the anonymous class.