Feature

In concurrent programming, exclusion refers to any technique that dynamically locks certain blocks of code so multiple threads can't corrupt their shared resources in ways that can cause integrity problems. In Java, exclusion has meant using the synchronized keyword against a method or block of code to control access to an object's lock.

Even though synchronization is a simple and concise way of controlling access to critical code, there are some limitations:

• While a thread is trying to acquire a lock, it can't be interrupted or timed-out.
• Each lock can only test against a single implicit condition using the wait() and notify() methods, which doesn't give developers much flexibility when trying to react to particular program states.

Starting with J2SE 5.0 there's another way of protecting a code block from concurrent access - the Lock interface and its implementations, the ReentrantLock and ReentrantReadWriteLock classes. These classes overcome the limitations of the synchronized keyword and give developers some useful new features to work with. For example:

• Threads can poll objects for existing locks held by other threads before trying to acquire a lock themselves. Locks can also specify timeouts, during which they can be interrupted.
• Now an object represents a lock. As an object, the lock can be stored, passed around, or discarded, meaning multiple objects can share the same lock, or one object can have multiple locks.
• A lock object can have multiple condition objects so it's possible to target individual threads or groups of threads.

Despite the power of these new features, they complement rather than replace the existing low-level concurrency primitives such as synchronized. So this article walks through the mechanics of using the Lock interface implementations and offers some guidelines for when they can best be used.

Exclusion Pre-Version 5.0
Prior to J2SE 5.0 the usual way of achieving exclusion was to apply the synchronized keyword against a method or block of code.

synchronized(someObject) {
      // work with object state
}

Any thread that wants to execute an object's synchronized code first has to acquire the object's lock. If the lock is already under the control of another thread, then the seeking thread goes into a blocked state and tries to acquire the lock at a later time. When the lock is eventually acquired, the code in the synchronized method or block is executed, and the lock is automatically released on exit, whether this occurs normally or through an exception.

As well as protecting certain sections of code from concurrent access, Java allows threads to actively cooperate towards a common goal by using the waiting and notification mechanism. For example, in the normal course of execution, a thread may have to wait for some condition to occur before it can continue, such as a variable reaching a certain value. Instead of wasting CPU cycles and retaining its exclusive object lock waiting for the right conditions, a thread can voluntarily step aside by calling wait(), a method of the base class object. The thread gives up its exclusive object lock and enters a waiting state. Only when another thread calls the notify() or notifyAll() methods, indicating conditions have changed, will the original thread try to re-acquire the lock and test the condition again.

public synchronized void someMethod() throws InterruptedException {
    while(!someCondition)
       wait();

    // work with object state
    notifyAll();
}

Using the synchronized keyword and the waiting and notification mechanism are simple ways of performing concurrent programming that are also platform-neutral and cause only a modest performance hit in the case of uncontended locks. (An uncontended lock means no other threads attempt to acquire an object's lock while another thread holds it. If threads have to compete to acquire a popular object's lock, more code is executed at the virtual machine level and performance degrades).

Exclusion in J2SE 5.0
Before diving into the details of the new concurrent utilities in J2SE 5.0, they should be put into some context. When using threads, developers need to consider some design issues that normally don't figure as prominently in sequential programming:

• Safety: means periodically locking certain sections of code so contending threads don't corrupt an object's state.
• Liveness: means ensuring that a program makes gradual progress towards some goal. In concurrent programs this progress can be affected by threads contending for the right to execute synchronized blocks of code, waiting for certain conditions to become true, or getting a slot in the execution schedule. While it's normal for concurrent programs to block occasionally because of these factors, long-term or permanent blockages need to be identified and prevented.
• Performance: means ensuring that each invoked method executes as soon as practicable.

Effective use of threads means balancing these design considerations, and the concurrent utilities in J2SE 5.0 can help. In contrast to the existing low-level concurrency primitives, these new tools are utilities in the java.util.concurrent package. Just as the Collections framework provides concrete implementations of commonly used data structures, the new concurrency utilities provide concrete implementations of commonly used concurrent tools.

Safety
Whereas the synchronized keyword provides implicit locking, the Lock interface and its implementations make locking explicit. The ReentrantLock and ReentrantReadWriteLock offer the same locking and memory semantics as the existing primitives but provide more features for developers. (The locks are called re-entrant because a thread can repeatedly acquire a lock that it already owns. The lock keeps track of these acquisitions and the tread must call unlock() for each one to release the lock fully.)

Listings 1 and 2 show an example of the ReentrantLock in action. This application models a fundamental double-entry bookkeeping requirement: a valid transaction must consist of a debit and a credit for the same amount. Unless this transaction happens atomically, the financial integrity of any system in which it's used is questionable. The run() method in Listing 2 performs a loop that transfers random amounts of money between a small number of accounts, which are modelled as array elements. After each transfer, the list of accounts is displayed along with the grand total of the money in the system; as long as the grand total remains the same, we can be sure that the transactions are happening atomically. Almost as important as this atomicity, transfers can only be made from accounts that have enough money.

In the transfer() method of Listing 2, the lock() and unlock() methods define the scope of the lock, which can be a single line, a few lines, or may equally span multiple methods and objects. Notice the location of the call to the unlock() method. The implicit locking provided by the synchronized keyword takes care of the acquisition and, most importantly, the release of object locks: when a synchronized method or block exits, either through normal execution or an exception, any locks are automatically released. There's no such protection when using the explicit locking of the Lock implementations. The usual idiom is to immediately follow the call to lock() with a try/finally block, with the lock being released in the finally clause. This guarantees that lock releases won't be forgotten.

ReentrantLock and ReentrantReadWriteLock constructors can take an optional fairness parameter. When this parameter is set to true and there's contention for an object's lock, the lock will be granted to the thread that's been waiting the longest. If the parameter is set to false or omitted the lock is granted to whichever thread tries to acquire it when it's next free, regardless of how many other threads may be waiting. Because of the overhead involved in this kind of positive discrimination, setting the fairness parameter to true will have a noticeable performance impact so that fair locks won't have the same throughput as unfair. For this reason, the fairness parameter should always be set to false or omitted unless there's a requirement that threads be served in a first-created, first-out order in which case there are dedicated data structures that can do this better.

In common with pre-J2SE 5.0 locking, the new locking utilities can conditionally suspend execution at certain times until an application's environment is right to carry on. Previously, lock objects were associated only with single conditions; now, there's no limit. This makes it possible to send wake-up notifications to specific groups of waiting threads rather than a broadcast reveille.

Because object's wait(), notify(), and notifyAll() methods are final and can't be overridden, the new lock utilities use await(), signal(), and signalAll() to do the same things. As a general rule, a call to await() should always be inside a while-loop, as shown in Listing 2, rather than an if-statement since there's no guarantee that the condition will be true when the thread is next notified. It's also a good practice to put the while-loop immediately after the call to lock() with no statements in between because any threads entering the locked code will execute these statements before hitting the while-loop and possibly cause side effects.

Liveness
As mentioned previously, liveness means that a program will do something...eventually. That is, its threads won't become so tangled that they are deadlocked and cause the program to hang. In general, programs may become deadlocked when they use a threading model that contains the following three conditions:

• Mutual exclusion: only one process or thread may use a resource at a time.
• Hold-and-wait: a process or thread may hold allocated resources while waiting to acquire others.
• No pre-emption: no resource can be forcibly removed from a process or thread that holds it.

The Java threading model contains all three conditions. So, it may happen that one thread acquires resource A and then tries to acquire resource B and another thread may already be holding resource B and is, in turn, trying to acquire resource A. This situation is called a circular wait: each thread holds at least one resource needed by another thread. Because each thread has exclusive control of the resources it holds and neither can be forced to give up this control, they are deadlocked.