Lock and ReentrantLock

The Lock interface, shown in Listing 13.1, defines a number of abstract locking operations. Unlike intrinsic locking, Lock offers a choice of unconditional, polled, timed, and interruptible lock acquisition, and all lock and unlock operations are explicit. Lock implementations must provide the same memory-visibility semantics as intrinsic locks, but can differ in their locking semantics, scheduling algorithms, ordering guarantees, and performance characteristics. (Lock.newCondition is covered in Chapter 14.)

Listing 13.1. Lock Interface.

public interface Lock {
 void lock();
 void lockInterruptibly() throws InterruptedException;
 boolean tryLock();
 boolean tryLock(long timeout, TimeUnit unit)
 throws InterruptedException;
 void unlock();
 Condition newCondition();
}

ReentrantLock implements Lock, providing the same mutual exclusion and memory-visibility guarantees as synchronized. Acquiring a ReentrantLock has the same memory semantics as entering a synchronized block, and releasing a ReentrantLock has the same memory semantics as exiting a synchronized block. (Memory visibility is covered in Section 3.1 and in Chapter 16.) And, like synchronized, ReentrantLock offers reentrant locking semantics (see Section 2.3.2). ReentrantLock supports all of the lock-acquisition modes defined by Lock, providing more flexibility for dealing with lock unavailability than does synchronized.

Why create a new locking mechanism that is so similar to intrinsic locking? Intrinsic locking works fine in most situations but has some functional limitationsit is not possible to interrupt a thread waiting to acquire a lock, or to attempt to acquire a lock without being willing to wait for it forever. Intrinsic locks also must be released in the same block of code in which they are acquired; this simplifies coding and interacts nicely with exception handling, but makes non-blockstructured locking disciplines impossible. None of these are reasons to abandon synchronized, but in some cases a more flexible locking mechanism offers better liveness or performance.

Listing 13.2 shows the canonical form for using a Lock. This idiomis somewhat more complicated than using intrinsic locks: the lock must be released in a finally block. Otherwise, the lock would never be released if the guarded code were to throw an exception. When using locking, you must also consider what happens if an exception is thrown out of the try block; if it is possible for the object to be left in an inconsistent state, additional TRy-catch or TRy-finally blocks may be needed. (You should always consider the effect of exceptions when using any form of locking, including intrinsic locking.)

Failing to use finally to release a Lock is a ticking time bomb. When it goes off, you will have a hard time tracking down its origin as there will be no record of where or when the Lock should have been released. This is one reason not to use ReentrantLock as a blanket substitute for synchronized: it is more "dangerous" because it doesn't automatically clean up the lock when control leaves the guarded block. While remembering to release the lock from a finally block is not all that difficult, it is also not impossible to forget.[1]

[1] FindBugs has an "unreleased lock" detector identifying when a Lock is not released in all code paths out of the block in which it was acquired.

Listing 13.2. Guarding Object State Using ReentrantLock.

Lock lock = new ReentrantLock();
...
lock.lock();
try {
 // update object state
 // catch exceptions and restore invariants if necessary
} finally {
 lock.unlock();
}

13.1.1. Polled and Timed Lock Acquisition

The timed and polled lock-acqusition modes provided by TRyLock allow more sophisticated error recovery than unconditional acquisition. With intrinsic locks, a deadlock is fatalthe only way to recover is to restart the application, and the only defense is to construct your program so that inconsistent lock ordering is impossible. Timed and polled locking offer another option: probabalistic deadlock avoidance.

Using timed or polled lock acquisition (TRyLock) lets you regain control if you cannot acquire all the required locks, release the ones you did acquire, and try again (or at least log the failure and do something else). Listing 13.3 shows an alternate way of addressing the dynamic ordering deadlock from Section 10.1.2: use TRyLock to attempt to acquire both locks, but back off and retry if they cannot both be acquired. The sleep time has a fixed component and a random component to reduce the likelihood of livelock. If the locks cannot be acquired within the specified time, transferMoney returns a failure status so that the operation can fail gracefully. (See [CPJ 2.5.1.2] and [CPJ 2.5.1.3] for more examples of using polled locks for deadlock avoidance.)

Timed locks are also useful in implementing activities that manage a time budget (see Section 6.3.7). When an activity with a time budget calls a blocking method, it can supply a timeout corresponding to the remaining time in the budget. This lets activities terminate early if they cannot deliver a result within the desired time. With intrinsic locks, there is no way to cancel a lock acquisition once it is started, so intrinsic locks put the ability to implement time-budgeted activities at risk.

The travel portal example in Listing 6.17 on page 134 creates a separate task for each car-rental company from which it was soliciting bids. Soliciting a bid probably involves some sort of network-based request mechanism, such as a web service request. But soliciting a bid might also require exclusive access to a scarce resource, such as a direct communications line to the company.

We saw one way to ensure serialized access to a resource in Section 9.5: a single-threaded executor. Another approach is to use an exclusive lock to guard access to the resource. The code in Listing 13.4 tries to send a message on a shared communications line guarded by a Lock, but fails gracefully if it cannot do so within its time budget. The timed TRyLock makes it practical to incorporate exclusive locking into such a time-limited activity.

13.1.2. Interruptible Lock Acquisition

Just as timed lock acquisition allows exclusive locking to be used within timelimited activities, interruptible lock acquisition allows locking to be used within cancellable activities. Section 7.1.6 identified several mechanisms, such as acquiring an intrinsic lock, that are not responsive to interruption. These noninterruptible blocking mechanisms complicate the implementation of cancellable tasks. The lockInterruptibly method allows you to try to acquire a lock while remaining responsive to interruption, and its inclusion in Lock avoids creating another category of non-interruptible blocking mechanisms.

Listing 13.3. Avoiding Lock-ordering Deadlock Using trylock.

public boolean transferMoney(Account fromAcct,
 Account toAcct,
 DollarAmount amount,
 long timeout,
 TimeUnit unit)
 throws InsufficientFundsException, InterruptedException {
 long fixedDelay = getFixedDelayComponentNanos(timeout, unit);
 long randMod = getRandomDelayModulusNanos(timeout, unit);
 long stopTime = System.nanoTime() + unit.toNanos(timeout);

 while (true) {
 if (fromAcct.lock.tryLock()) {
 try {
 if (toAcct.lock.tryLock()) {
 try {
 if (fromAcct.getBalance().compareTo(amount)
 < 0)
 throw new InsufficientFundsException();
 else {
 fromAcct.debit(amount);
 toAcct.credit(amount);
 return true;
 }
 } finally {
 toAcct.lock.unlock();
 }
 }
 } finally {
 fromAcct.lock.unlock();
 }
 }
 if (System.nanoTime() < stopTime)
 return false;
 NANOSECONDS.sleep(fixedDelay + rnd.nextLong() % randMod);
 }
}

Listing 13.4. Locking with a Time Budget.

public boolean trySendOnSharedLine(String message,
 long timeout, TimeUnit unit)
 throws InterruptedException {
 long nanosToLock = unit.toNanos(timeout)
 - estimatedNanosToSend(message);
 if (!lock.tryLock(nanosToLock, NANOSECONDS))
 return false;
 try {
 return sendOnSharedLine(message);
 } finally {
 lock.unlock();
 }
}

The canonical structure of interruptible lock acquisition is slightly more complicated than normal lock acquisition, as two TRy blocks are needed. (If the interruptible lock acquisition can throw InterruptedException, the standard try-finally locking idiom works.) Listing 13.5 uses lockInterruptibly to implement sendOnSharedLine from Listing 13.4 so that we can call it from a cancellable task. The timed TRyLock is also responsive to interruption and so can be used when you need both timed and interruptible lock acquisition.

Listing 13.5. Interruptible Lock Acquisition.

public boolean sendOnSharedLine(String message)
 throws InterruptedException {
 lock.lockInterruptibly();
 try {
 return cancellableSendOnSharedLine(message);
 } finally {
 lock.unlock();
 }
}

private boolean cancellableSendOnSharedLine(String message)
 throws InterruptedException { ... }

13.1.3. Non-block-structured Locking

With intrinsic locks, acquire-release pairs are block-structureda lock is always released in the same basic block in which it was acquired, regardless of how control exits the block. Automatic lock release simplifies analysis and prevents potential coding errors, but sometimes a more flexible locking discipline is needed.

In Chapter 11, we saw how reducing lock granularity can enhance scalability. Lock striping allows different hash chains in a hash-based collection to use different locks. We can apply a similar principle to reduce locking granularity in a linked list by using a separate lock for each link node, allowing different threads to operate independently on different portions of the list. The lock for a given node guards the link pointers and the data stored in that node, so when traversing or modifying the list we must hold the lock on one node until we acquire the lock on the next node; only then can we release the lock on the first node. An example of this technique, called hand-over-hand locking or lock coupling, appears in [CPJ 2.5.1.4].

Performance Considerations