Book Reading: Java Concurrency in Practice, Chapter 13

ReentrantLock

The Lock interface in Java offers a choice of unconidtional, polled, timed, and interruptible lock acquisition, and all lock and unlock operations are explicit. ReentrantLock implements Lock, providing the same mutual exclusion and memory-visibility gurantees 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.

Why create a locking mechanism that is so similar to intrinsic locking? Intrinsic locking works fine in most cases but has some functional limitations, for example:

• It 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.
• It must be released in the same block of code in which they are acquired.

A canonical form for using a Lock is as below:

Lock lock = new ReentrantLock();
lock.lock();
try {
    // Do something...
} finally {
    lock.unlock();
}

Note the lock must be released in a finally block, otherwise it will never be released if the guarded code were to throw a exception. So it is more dangerous than intrinsic lock because it doesn’t automatically clean up the lock when control leaves the guarded block.

Polled and timed lock acquistion

The timed and polled lock-acquisition modes provided by tryLock allow more sophisticated error recovery than unconditional acquisition. Using it lets yout 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. Example:

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

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

The program uses tryLock to attempt both locks, but back off and retry if they cannot both be acquired. Note this try-wait-acquire pattern can result in livelock problem, which is a risk with some algorithm that detect and recover from deadlock. If more than one processes take action, the deadlock detection algorithm can be repeatly triggered. The states of processes involved in the livelock constantly change with regard to one another, no progress will be made. Livelock is similar to deadlock, the most important difference is that the threads are not blocked, instead they will try to respond to each other continuously. So in this example, it is possible that several threads are trying to acquire the lock at the same time and all back offs, that is why we need to add a random component to reduce the likelihood of livelock.

Timed locks are also useful in implementing activities that manage a time 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.

Interruptible lock acquisition

The interruptible lock acquistion allows locking to be used within cancellable activities. The lockInterruptibly method allows you to try to acquire a lock while remaining responsive to interruption. An example of usage:

public boolean lockInterruptiblyExample() throws InterruptedException {
    lock.lockInterruptibly();
    try {
        // Do something...
    } finally {
        lock.unlock();
    }
}

The usage is pretty similar with lock(), the key differences are:

1. If the current thread is already interrupted when calling lockInterruptibly, it won’t acquire the lock, and throws InterruptedException.
2. If the current thread is interrupted when acquiring the lock, it won’t acquire the lock, and throws InterruptedException.

Note this is different when interrupting a thread that already acquired the lock, you need to handle the lock releasing logic carefully since it is currently held by the thread.

Fairness

The ReentrantLock constructor offers choice of two faireness options: create a non-fair lock (the default) or a fair lock. The differnces are:

1. Threads acquire a fair lock in the order in which they requested it.
2. A nonfair lock permits barging: threads requesting a lock can jump ahead of the queue of waiting threads if the lock happens to be available when it is requested.

When it comes to locking, fairness has significant performance cost because of the overhead of suspending and resuming threads. In practice, a statistical fairness guarantee–promising that a blocked thread will eventually acquire the lock–is often good enough, and is far less expensive to deliver. In most cases, the performance benefits of nonfair locks outweight the benefits of fair queueing. Don’t pay for fairness if you don’t need it.

Fair locks tend to work best when they are held for a relatively long time or when the mean time between lock requests is relatively long. In these cases, the condition under which barging provides a throughput advantage–when the lock is unheld but a thread is currently waking up to claim it–is less likely to hold.

Like the default ReentrantLock, intrinsic locking offers no deterministic fairness guarantees, but the statistical faireness guarantees of most locking implementations are good enough for almost all situations.

ReentrantReadWriteLock

ReentrantLock implements a standard mutual exclusion lock: at most one thread at a time can hold a ReentrantLock. But mutual exclusion is frequently a stronger locking discipline than needed to preserve data integrity, and thus limits concurrency more than necessary. Mutual exclusion is a conservative locking strategy that prevents writer/writer and writer/reader overlap, but also prevents reader/reader overlap. In many cases, data structures are “read-mostly”–they are mutable and are sometimes modified, but most access involve only reading. In these cases, it would be nice to relax the locking requirements to allow multiple readers to access the data structure at once. As long as each thread is guaranteed an update-to-date view of the data and no other thread modifies the data while the readers are viewing it, there will be no problems. This is what read-write locks allow: a resource can be accessed by multiple readers or single writer at a time, but not both.

To read data guarded by a ReadWriteLock you must first acquire the read lock, and to modify data guarded by a ReadWriteLock you must first acquire the write lock:

public interface ReadWriteLock {
    Lock readLock();
    Lock writeLock();
}

In practice, read-write locks can improve performance for frequently accessed read-mostly data structures on multiprocessor system; under other conditions they perform slightly worse than exclusive locks due to their greater complexity.

The interaction between the read and write locks allows for a number of possible implementations. Some of the implementation options for a ReadWriteLock are:

1. Release preference. When a writer releases the write lock and both readers and writers are queued up, who should be given performance–readers, writers, or whoever asked first?

2. Reader barging. If the lock is held by readers but there are waiting writters, should newly arriving readers be granted immediate access, or should they wait behind the writers? Allowing readers to barge ahead of writers enhances concurrency but runs the risk of starving writers.

3. Reentrancy. Are the read and write locks reentrant?

4. Downgarding. If a thread holds the write lock, can it acquire the read lock without releasing the write lock? This would let a writer “downgrade” to a read lock without letting other writers modify the guarded resouce in the meantime.

5. Upgrading. Can a read lock be upgraded to a wirter lock in preference to other waiting readers or writers? Most read-write lock implementations do not support upgrading, because without an explicit upgrade operation it is deadlock prone. For example, there are two readers reading the data simultaneously since we don’t block multiple readers. And they both attempt to upgrade to a writer lock, they will wait for the release of the reader lock of each other, which causes a deadlock.

ReentrantReadWriteLock provides reentrant locking semantics for both locks and it can be constrcuted as nonfair (the default) or fair. With a fair lock, preference is given to the thread that has been waiting the longest; if the lock is held by readers and a thread reqeusts the write lock, no more readers are allowed to acquire the read lock until the writer has been serviced and releases the write lock. With a nonfair lock, the order in which threads are granted access is unspecified. Downgrading from writer to reader is permitted; upgrading from reader to writer is not.