An overview of

The introduction of StampedLock in JDK 1.8 can be interpreted as an enhancement to ReentrantReadWriteLock in some ways, adding a mode called Optimistic Reading to the original read and write lock. This mode does not lock, so it does not block threads, resulting in higher throughput and better performance.

Take a look at what StampedLock brings to the table…

  • With ReentrantReadWriteLock, why introduce StampedLock?
  • What is optimistic reading?
  • How does StampedLock solve the thread hunger problem that writer threads cannot acquire locks in concurrent scenarios with too many reads and too few writes?
  • What kind of scenarios are used?
  • Implementation principle analysis, is it through AQS or something else?

features

It is designed as an internal tool class for developing other thread-safe components to improve system performance, and its programming model is more complex than ReentrantReadWriteLock, so it is prone to deadlocks and thread-safe problems.

Three data access modes:

  • Writing: The writeLock method blocks threads waiting for exclusive access. It is similar to ReentrantReadWriteLock, in which only one thread obtains lock resources at a time.
  • Reading (pessimistic readLock) : a readLock method that allows multiple threads to acquire pessimistic read locks at the same time. Pessimistic read locks are mutually exclusive with exclusive write locks and are shared with optimistic reads.
  • Optimistic Reading: Note that this is Optimistic Reading, not locked. There will be no CAS mechanism and no blocking threads. TryOptimisticRead returns a non-zero Stamp only if the tryOptimisticRead is not currently in Writing mode. If no write-mode thread has acquired the lock after the tryOptimisticRead has been acquired, the validate method returns true, allowing multiple threads to acquire the optimistic read and lock. It also allows a writer thread to acquire a write lock.

Support read/write lock conversion

ReentrantReadWriteLock A thread that has acquired a write lock can be degraded to a read lock, but not vice versa.

StampedLock supports the conversion between read locks and write locks, making StampedLock applicable to more application scenarios.

Matters needing attention

  1. StampedLock is a non-reentrant lock. If the current thread has already acquired the write lock, it will be deadlocked if it acquires it again.
  2. Both do not support Conditon conditions that will wait for threads;
  3. StampedLock write locks and pessimistic read locks return a stamp after being successfully locked. Then when unlocking, you need to pass in the stamp.

Explain the performance benefits of optimistic reading

So why is StampedLock performing better than ReentrantReadWriteLock?

The key is the optimistic read provided by StampedLock. We know that ReentrantReadWriteLock allows multiple threads to acquire the read lock at the same time, but when multiple threads read at the same time, all writer threads are blocked.

StampedLock’s optimistic read allows one writer thread to acquire the write lock, so it does not block all writer threads. That is, when there are too many reads and too few writes, the writer thread has the opportunity to acquire the write lock, reducing thread hunger and greatly improving throughput.

If you allow multiple optimistic reads and one thread to enter a critical resource operation at the same time, what if the read data may be wrong?

Yes, optimistic reading cannot guarantee that the data read is the latest, so when the data is read to the local variable, it needs to check whether it has been modified by the writer thread through lock.validate(stamp). If it has been modified, it needs to attach pessimistic read lock, and then read the data to the local variable again.

And because optimistic reads are not locks, they perform better without context switches caused by thread wake up and blocking.

In fact, with the database “optimistic lock” has the same wonderful, its implementation idea is very simple. Let’s take an example of a database.

Add a numeric version number field version to product_doc, increment version by 1 each time product_doc is updated.

Select id,... , version from product_doc where ID = 123Copy the code

Updates are performed only if version is matched at update time.

update product_doc
set version = version + 1,...
where id = 123 and version = 5
Copy the code

Optimistic locking of the database is to check version during query and verify version field during update. If the data is equal, it indicates that the data has not been modified and the data read is safe.

The version here is similar to StampedLock’s Stamp.

Use the sample

Mock write saves the user ID and user name data in the shared variable idMap, and provides the PUT method to add data, get method to get data, and putIfNotExist method to get data from the map. If not, simulate querying data from the database and putting the data into the map.

Public class CacheStampedLock {/** * Sharing variable data */ private final Map<Integer, String> idMap = new HashMap<>(); private final StampedLock lock = new StampedLock(); /** * Public void put(Integer key, String value) {long stamp = lock.writeLock(); try { idMap.put(key, value); } finally { lock.unlockWrite(stamp); Public String get(Integer key) {// 1. Long stamp = lock.tryOptimisticRead(); long stamp = lock.tryOptimisticRead(); String currentValue = idmap.get (key); // 3. Check whether it has been modified by other threads. True indicates that it has not been modified; otherwise, add pessimistic read lock if (! Stamp = lock.readLock(); stamp = lock.validate(); stamp = lock.readLock(); try { currentValue = idMap.get(key); } finally { lock.unlockRead(stamp); }} // 5. If the check passes, return currentValue; } /** * If the data does not exist, add the data from the database to the map. * @return */ public String putIfNotExist(Integer key, String value) { Long stamp = lock.readLock(); String currentValue = idMap.get(key); Try {while (objects.isNULL (currentValue)) {// Try to upgrade the write lock long wl = lock.tryConvertToWriteLock(stamp); If (wl! Stamp = wl; // stamp = wl; currentValue = value; idMap.put(key, currentValue); break; } else {// update failed, release read lock and write lock, repeat loop lock.unlockRead(stamp); stamp = lock.writeLock(); }}} finally {// release the last lock lock.unlock(stamp); } return currentValue; }}Copy the code

In the example above, the get() and putIfNotExist() methods need to be noticed. The first one uses optimistic reads so that reads and writes can be executed concurrently. The second one uses a programming model that converts read locks to write locks, queries the cache first, reads data from the database when it does not exist and adds it to the cache.

When using optimistic reading, we must write according to the fixed template, otherwise it is easy to bug, we summarize the template of optimistic reading programming model:

public void optimisticRead() { // 1. Long stamp = Lock. tryOptimisticRead(); / / 2. The copy Shared data to the thread local stack copyVaraibale2ThreadMemory (); // 3. Check whether the data read in optimistic read mode has been modified. Lock. validate(stamp)) {stamp = lock.readLock(); Try {/ 3.2 / copy Shared variable data to a local variable copyVaraibale2ThreadMemory (); } finally {// release read lock lock.unlockRead(stamp); UseThreadMemoryVarables (); useThreadMemoryVarables(); }Copy the code

Usage scenarios and precautions

StampedLock performs well in high-concurrency scenarios with too many reads and too few writes. The problem of writer thread hunger is solved by optimistic read mode. We can use StampedLock to replace ReentrantReadWriteLock. However, it is important to note that StampedLock’s functionality is only a subset of ReadWriteLock. There are a few things to be aware of when using StampedLock.

  1. StampedLock is a non-reentrant lock. Use StampedLock carefully.
  2. Pessimistic read and write locks do not support the conditional variable Conditon, so be careful when you need this feature.
  3. If a thread blocks on StampedLock’s readLock() or writeLock(), calling interrupt() on that blocking thread will cause a CPU spike. Therefore, do not call interrupt operations when using StampedLock. If you want to support interrupt functions, always use the interruptible pessimistic read lock readLockInterruptibly() and write lock writeLockInterruptibly(). This rule must be kept in mind.

The principle of analysis

We find that it is not like other lock by defining the inner class inheritance AbstractQueuedSynchronizer abstract classes and subclasses implement template method to realize the synchronization logic. However, the implementation idea is still similar, CLH queue is still used to manage threads, by synchronizing the state value state to identify the lock state.

Many variables are defined internally. The purpose of these variables is the same as that of ReentrantReadWriteLock. The state is shred by bit.

For example, if the write lock uses the eighth bit 1, it indicates that the write lock uses the eighth bit 1, and the read lock uses the 0-7 bit. Therefore, generally the number of threads that acquire the read lock is 1-126. After the number exceeds, the readerOverflow int variable will be used to save the number of threads that exceed the number.

Spin optimization

The multi-core CPU is also optimized to obtain the number of cores. When the number of cores exceeds 1, the thread will have spin operation for lock retries and queue money retries. It is mainly judged by some internally defined variables, as shown in the figure.

Waiting queue

The nodes of the queue are defined by WNode, as shown in the figure above. Nodes waiting for queues are simpler than AQS, with only three states:

  • 0: initial state.
  • -1: waiting.
  • Cancel;

There is also a field, cowait, that points to a stack to hold the reader thread. The structure is shown in the figure

Two variables are defined to refer to the head node and the tail node respectively.

/** Head of CLH queue */
private transient volatile WNode whead;
/** Tail (last) of CLH queue */
private transient volatile WNode wtail;
Copy the code

Another important point to note is cowait, which holds all read node data using a header interpolation method.

When read-write threads compete to form a wait queue, the data is shown below:

Access to write lock

public long writeLock() {
    long s, next;  // bypass acquireWrite in fully unlocked case only
    return ((((s = state) & ABITS) == 0L &&
             U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
            next : acquireWrite(false, 0L));
}
Copy the code

This method does not respond to interrupts. Call writeLockInterruptibly() if an interrupt is required. Otherwise, high CPU usage may occur.

(s = state) & ABITS indicates that the read lock and write lock are not in use, so directly execute U.compareAndSwapLong(this, state, S, next = S + WBIT)) CAS operation to set the eighth bit to 1, indicating that the write lock is occupied successfully. If CAS fails, call acquireWrite(false, 0L) to join the queue and block the thread.

The acquireWrite(false, 0L) method is complex, using lots of spin operations such as auto-queuing.

Access to read lock

public long readLock() {
    long s = state, next;  // bypass acquireRead on common uncontended case
    return ((whead == wtail && (s & ABITS) < RFULL &&
             U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
            next : acquireRead(false, 0L));
}
Copy the code

Obtain key steps of the read lock

(whead == wtail && (s & ABITS) < RFULL If the queue is empty and the number of read lock threads does not exceed the limit, Modify the STATE identifier to obtain read lock successfully through U.compareAndSwapLong(this, STATE, S, next = S + RUNIT) CAS.

Otherwise, acquireRead(false, 0L) is called to attempt to acquire the read lock using spin, failing which, the lock is queued.

acquireRead

When thread A acquires the write lock and thread B acquires the read lock, the acquireRead method is called, and it joins the blocking queue and blocks thread B. The method is still very complicated internally, and the general process is as follows:

  1. If the write lock is not occupied, the system immediately attempts to obtain the read lock. If the CAS status is changed successfully, the system returns.
  2. If the write lock is occupied, the current thread is wrapped as a WNode read node and inserted into the wait queue. If it is a writer-thread node, it goes directly to the end of the queue, otherwise it goes to the stack pointed to by WNode Cowait, the reader thread, at the end of the queue. The stack structure is a header insertion method to insert data and finally wake up the read node, starting from the top of the stack.

Release the lock

Whether unlockRead releases the read lock or unlockWrite releases the write lock, the overall process is basically through CAS operation. After the state is successfully modified, the release method is called to wake up the subsequent node threads of the head node of the waiting queue.

  1. You want to set the wait state of the head node to 0 to indicate that the successor node is about to wake up.
  2. Wake up The subsequent node obtains the lock through CAS, and if it is a read node, wakes up all the read nodes of the stack to which the COwait lock points.

Release read lock

UnlockRead (Long stamp) If the stamp passed in is the same as the one held by the lock, the non-exclusive lock will be released. Internally, the state is successfully modified through spin + CAS. Before modifying the state, it determines whether the number of read threads exceeds the limit. If it is less than the limit, change the state synchronization through CAS, and then call the release method to wake up the whead successor.

Release the write lock

UnlockWrite (Long stamp) If the stamp passed is the same as that held by the lock, the write lock is released, the WHEad is not empty, and the current node status is status! If = 0, the release method is called to wake up the subsequent node threads of the header.

conclusion

StampedLock cannot completely replace ReentrantReadWriteLock. The optimistic read mode allows a writer thread to acquire the write lock in a scenario where there are many reads and few writes, thus solving the problem of writer thread hunger and greatly improving throughput.

When using optimistic reads, you need to be careful to follow the programming model template, otherwise you can easily create deadlocks or unexpected thread-safety issues.

It is not a reentrant lock and does not support the condition variable Conditon. And when a thread blocks on readLock() or writeLock(), calling interrupt() on that blocking thread causes the CPU to spike. Be aware of calling the pessimistic read lock readLockInterruptibly() and the write lock writeLockInterruptibly() if thread interruption scenarios are required.

In addition, the thread awakening rule is similar to AQS, that is, the head node is awakened first. The difference is that when StampedLock awakens a read node, all read nodes of the stack pointed to by the cowait lock of the read node will be awakened, but the order of awakening is opposite to that of insertion.

Three things to watch ❤️

If you find this article helpful, I’d like to invite you to do three small favors for me:

  1. Like, forward, have your “like and comment”, is the motivation of my creation.

  2. Follow the public account “Java rotten pigskin” and share original knowledge from time to time.

  3. Also look forward to the follow-up article ing🚀

  4. [666] Scan the code to obtain the learning materials package