Skip to content
Upgradable read-write locks for Java
Java
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
archive
code
documentation
LICENSE.txt
README.md

README.md

Concurrent-Locks

This project provides additional Lock implementations for Java, extending the base functionality and performance provided by the JDK.

ReentrantReadWriteUpdateLock

The ReentrantReadWriteUpdateLock provided in this project, is like the ReentrantReadWriteLock counterpart in the JDK, but in addition to providing a read lock and a write lock, it provides a third option: an update lock.

Unlike the JDK, this efficiently supports read-before-write data access patterns.

Background - JDK ReentrantReadWriteLock

The ReentrantReadWriteLock in the JDK classifies threads as needing to read-without-write, write-without-read, or write-before-read. Threads can obtain the read lock, or the write lock, and if they have the write lock, they can downgrade it to a read lock. But the key limitation is that it does not support read-before-write: threads which hold a read lock cannot upgrade it to a write lock. Thus the JDK ReentrantReadWriteLock does not support read-before-write access patterns efficiently.

Read-before-write is common. Imagine a document (or a resource) where most requests are to read data, but also occasionally the document might need to be updated, which involves reading it in, performing some analysis and alterations to it, then writing out a new version. An efficient lock implementation would minimize the amount of time for which reading threads are blocked, while the document is being updated.

The only way to provide safe access to the document while it is being updated like this using the ReentrantReadWriteLock of the JDK, is for a thread which might update the document (a "writing thread") to do so in three steps:

  1. Acquire the write lock, and only then read the document
  2. Hold the write lock while analyzing and generating a new version of the document
  3. Hold the write lock while writing out the new version

If the writing thread did not acquire any lock before it got to step 3, and it tried to acquire the write lock only at step 3, then a race condition is possible with other threads doing the same thing, because at step 3 there would be no guarantee that the version each thread had read at step 1 had not already been overwritten with another version by another thread. Performing a write in this case, would be susceptible to the lost update problem, where one thread overwrites changes made by another thread.

If the writing thread acquired a read lock at step 1, it would be guaranteed that the version of the document it read had not been modified by other threads by the time it got to step 3, but at step 3 it would be unable to acquire the write lock because the JDK ReentrantReadWriteLock does not allow the read lock to be upgraded to a write lock.

So the only solution with the the JDK ReentrantReadWriteLock, is for the writing thread to hold the write lock all for three steps of the process, which prevents concurrent read access by other threads for the entire duration, which is needless for steps 1 & 2.

The following table shows the situations in which a conventional Read-Write lock can needlessly block reading threads in applications with read-before-write access patterns. The extended periods for which reads are blocked, of course will be felt most severely in applications in which reading and writing are long-running operations, in applications where document access has relatively high latency (e.g. across a network), or in applications with high levels of concurrency.

Read-before-write access pattern with conventional Read-Write lock

Step Concurrent reads allowed?
1. Acquire write lock and read data NO
2. Holding write lock, perform computations on the data NO
3. If new data needs to be written, holding write lock, write new data NO
4. Release write lock YES

ReentrantReadWriteUpdateLock Overview

The ReentrantReadWriteUpdateLock in this project provides a third type of lock, an update lock. An update lock is an intermediate type of lock between a read lock and a write lock. Like the write lock, only one thread can acquire an update lock at a time. But like a read lock, it allows read access to the thread which holds it, and concurrently to other threads which hold regular read locks.

The key feature is that the update lock can be upgraded from its read-only status, to a write lock. Thus it supports read-before-write access patterns efficiently. Also the write lock can be downgraded again to an update lock, supporting write-before-read access patterns efficiently.

The following table shows the situations in which the Read-Write-Update lock provided in this project can increase concurrency in applications with read-before-write access patterns. It should also be noted that if the writing thread determines that the document does not need to be updated after all, then it does not upgrade to a write lock and so concurrent reads will not be blocked at all.

Read-before-write access pattern with Read-Write-Update lock

Step Concurrent reads allowed?
1. Acquire update lock and read data YES
2. Holding update lock, perform computations on the data YES
3. If new data needs to be written, upgrade to write lock, write new data NO
4. Release write lock, optionally release update lock YES

Example Usage - Writing Threads

final ReadWriteUpdateLock readWriteUpdateLock = new ReentrantReadWriteUpdateLock();

public void updateDocumentIfNecessary() {
    readWriteUpdateLock.updateLock().lock(); // allows other readers, blocks others from acquiring update or write locks
    try {
        // STEP 1: Read in the document...
        Document currentDocument = readInDocument();
        // Decide if document actually needs to be updated...
        if (shouldUpdate(currentDocument)) {
            // STEP 2: Generate a new version of the document...
            Document newVersion = generateNewVersion(currentDocument);
            // STEP 3: Write out new version...
            readWriteUpdateLock.writeLock().lock(); // upgrade to the write lock, at this point blocks other readers
            try {
                writeOutDocument(newVersion);
            }
            finally {
                readWriteUpdateLock.writeLock().unlock(); // downgrade back to update lock
            }
        }
    }
    finally {
        readWriteUpdateLock.updateLock().unlock(); // release update lock
    }
}

Example Usage - Reading Threads

public Document readDocument() {
    readWriteUpdateLock.readLock().lock(); // blocks others from acquiring write lock
    try {
        return readInDocument();
    }
    finally {
        readWriteUpdateLock.readLock().unlock();
    }
}

Supported Lock Acquisition Paths

Lock Type Associated Permissions Permitted acquisitions Permitted downgrades Prohibited
Read • Read (shared) • None → Read
• Read → Read (reentrant)
• Read → None • Read → Update
• Read → Write
Update • Read (shared) • None → Update
• Update → Update (reentrant)
• Write → Update (reentrant)
• Update → None • Update → Read
Write • Read (exclusive)
• Write (exclusive)
• None → Write
• Update → Write
• Write → Write (reentrant)
• Write → Update
• Write → None
• Write → Read

CompositeLock

A lock spanning a group of backing locks. When locked CompositeLock locks all backing locks. When unlocked, it unlocks all backing locks.

Ensures that either all backing locks are acquired, or no backing locks are acquired, by applying roll back logic such that failure to acquire any one lock, causes all locks already acquired to be unlocked.

Lock acquisition methods which take timeouts, are implemented such that the timeout is applied across the acquisition of all locks.

Locks are unlocked in the reverse of the order in which the were acquired.

Utilities

The Locks class provides utility methods which mimic the JDK java.util.concurrent.locks.Lock API, but instead apply those operations on groups of backing locks.

Provides methods:
  • lockAll(Iterable<L> locks)
  • lockInterruptiblyAll(Iterable<L> locks)
  • tryLockAll(Iterable<L> locks)
  • tryLockAll(long time, TimeUnit unit, Iterable<L> locks)
  • unlockAll(Iterable<L> locks)

Usage in Maven and Non-Maven Projects

Concurrent-Locks is in Maven Central, and can be added to a Maven project as follows:

<dependency>
    <groupId>com.googlecode.concurrent-locks</groupId>
    <artifactId>concurrent-locks</artifactId>
    <version>1.0.0</version>
</dependency>

For non-Maven projects, the library can be downloaded directly from Maven Central here.

Project Status

  • Development of the library is complete, and all code has 100% test coverage
  • The completed library has been deployed to Maven central as version 1.0.0
  • There are no known bugs
  • For a technical discussion of locks in this project, see the thread on the JDK concurrency-interest mailing list
  • API JavaDocs are available here

Report any bugs/feature requests in the Issues tab.
For support please use the Discussion Group, not direct email to the developers.

You can’t perform that action at this time.