StampedLock, the artifact to solve thread hunger, deserves it!

StampedLock, the artifact to solve thread hunger, deserves it!

Preface

The introduction of StampedLock in JDK 1.8 can be understood as an enhancement of ReentrantReadWriteLock in some aspects. A new mode called Optimistic Reading is added on the basis of the original read-write lock. This mode does not lock, so it will not block threads, and will have higher throughput and higher performance. Concurrent programming practical notes are also worth looking at.

Let s take a look at what StampedLock brings to us...

  • With ReentrantReadWriteLock, why introduce StampedLock?
  • What is optimistic reading?
  • How does StampedLock solve the problem of thread "starvation" when it is difficult for the writer thread to acquire the lock in the concurrent scenario of more reading and less writing?
  • What kind of scene is used?
  • Implementation principle analysis, is it realized through AQS or something else?

characteristic

It was originally designed as an internal tool class to develop other thread-safe components to improve system performance, and the programming model is also more complicated than ReentrantReadWriteLock, so inexplicable problems such as deadlock or thread safety are prone to occur if it is not used well.

3.access data modes :

  • Writing (exclusive write lock): The writeLock method will block the thread waiting for exclusive access. It can be analogous to the write lock mode of ReentrantReadWriteLock. At the same time, there is only one writer thread to acquire the lock resource;
  • Reading (pessimistic read lock): The readLock method allows multiple threads to acquire a pessimistic read lock at the same time. The pessimistic read lock and the exclusive write lock are mutually exclusive, and are shared with optimistic reads.
  • Optimistic Reading (optimistic reading): Need to pay attention to here, it is optimistic reading, and there is no lock. That is, there will be no CAS mechanism and no blocking threads. TryOptimisticRead will return a non-zero postmark (Stamp) only when it is not currently in Writing mode. If there is no write mode thread acquiring lock after acquiring optimistic read, the method validate returns true, allowing multiple threads to acquire optimistic read and read locks . At the same time, a writer thread is allowed to acquire a write lock .

Supports mutual conversion between read and write locks

ReentrantReadWriteLock can be downgraded to a read lock after a thread acquires a write lock, but not vice versa.

StampedLock provides the function of mutual conversion between read lock and write lock, making this class support more application scenarios.

Precautions

  1. StampedLock is a non-reentrant lock. If the current thread has acquired the write lock, it will deadlock if it is acquired again;
  2. Does not support the Conditon condition to wait for the thread;
  3. After the write lock and pessimistic read lock of StampedLock are successfully locked, a stamp will be returned; then when unlocking, this stamp needs to be passed in.

Explain the performance improvement brought by optimistic reading in detail

So why is the performance of StampedLock better than ReentrantReadWriteLock?

The key lies in the optimistic read provided by StampedLock. We know that ReentrantReadWriteLock supports multiple threads to acquire read locks at the same time, but when multiple threads read at the same time, all write threads are blocked.

The optimistic read of StampedLock allows one write thread to acquire the write lock, so it will not cause all the write threads to block, that is, when there is more reading and less writing, the writer thread has the opportunity to acquire the write lock, reducing the problem of thread starvation and greatly improving throughput .

You may have questions here. If multiple optimistic reads and one pre-thread are allowed to enter critical resource operations at the same time, what should be done if the read data may be wrong?

Yes, optimistic reading does not guarantee that the data read is the latest, so when reading the data to a local variable, you need to verify whether it has been modified by the writing thread through lock.validate(stamp). If it is modified, you need to be pessimistic Read the lock, and then re-read the data to the local variable.

At the same time, because optimistic reading is not a lock, there is no context switching caused by thread wakeup and blocking, and the performance is better.

In fact, it is similar to the "optimistic lock" of the database, and its realization idea is very simple. Let's take an example of a database.

A numeric version number field version is added to the product_doc table of the production order. Each time the product_doc table is updated, the version field is incremented by 1.

select id,..., version from product_doc ID = WHERE 123 duplicated code

The update is performed only when the version matches the update.

update product_doc set version = version + 1 ,... ID = WHERE 123 and Version = . 5 duplicated code

The optimistic lock of the database is to find out the version when querying, and use the version field to verify when updating. If they are equal, the data has not been modified and the data read is safe.

The version here is similar to the Stamp of StampedLock.

Example of use

Imitate to write one that saves the user id and user name data in the shared variable idMap, and provides the put method to add data, the get method to obtain the data, and putIfNotExist to obtain the data from the map first, if not, simulate the query data from the database and put it in the map in.

public  class  CacheStampedLock  {      /**      * Shared variable data      */     private final  Map <Integer,  String > idMap =  new  HashMap<>();     private final StampedLock lock =  new  StampedLock();     /**      * Add data, exclusive mode      */     public  void  put ( Integer key,  String  value )  {         long stamp = lock.writeLock();         try  {             idMap.put(key, value);         }  finally  {             lock.unlockWrite(stamp);         }     }     /**      * Read data, read-only method      */     public  String  get ( Integer key )  {          //1. Try to read data through optimistic read mode, non-blocking         long stamp = lock.tryOptimisticRead();         //2. Read the data to the current thread stack         String  currentValue = idMap.get(key);          //3. Verify whether it has been modified by other threads, true means it has not been modified, otherwise you need to add a pessimistic read lock         if  (!lock. validate(stamp)) {              //4. On the pessimistic read lock, and re-read the data to the current thread local variables             stamp = lock.readLock();             try  {                 currentValue = idMap.get(key);             }  finally  {                 lock.unlockRead(stamp);             }         }         //5. If the verification is passed, the data will be returned directly         return  currentValue;     }     /**      * If the data does not exist, read from the database and add it to the map, and use the lock upgrade      *  @param  key      *  @param  value can be understood as the data read from the database, assuming it will not be null      *  @return      */     public  String  putIfNotExist ( Integer key,  String  value )  {          //Obtain the read lock, or directly call the get method to use optimistic reading         long stamp = lock.readLock();         String  currentValue = idMap.get(key);          //If the cache is empty, try to write the lock to read data from the database and write to the cache         try  {              while  (Objects.isNull(currentValue)) {                  //Try to upgrade the write lock                 long wl = lock.tryConvertToWriteLock(stamp);                 //If it is not 0, the write lock is successfully upgraded                 if  (wl != 0L) {                      //Simulate reading data from the database and write it to the cache                     stamp = wl;                     currentValue = value;                     idMap.put(key, currentValue);                     break ;                 }  else  {                      //Upgrade failed, release the read lock and write lock added before, try again through the loop                     lock.unlockRead(stamp);                     stamp = lock.writeLock();                 }             }         }  finally  {              //release the last lock             lock.unlock(stamp);         }         return  currentValue;     } } Copy code

In the above example of use, the get() and putIfNotExist() methods need to be paid attention to. The first one uses optimistic reading to make reading and writing can be executed concurrently, and the second is programming that uses a read lock to convert to a write lock. The model first queries the cache, and when it does not exist, reads data from the database and adds it to the cache.

When using optimistic reading, you must write in accordance with a fixed template, otherwise it is easy to cause bugs. Let's summarize the template of the optimistic reading programming model:

public  void  optimisticRead ()  {      //1. Obtain version information in non-blocking optimistic read mode     long stamp = lock.tryOptimisticRead();     //2. Copy shared data to the thread local stack     copyVaraibale2ThreadMemory();     //3. Verify whether the data read in optimistic read mode has been modified     if  (!lock.validate(stamp)) {          //3.1 Verification fails, read lock         stamp = lock.readLock();         try  {              //3.2 Copy shared variable data to local variable             copyVaraibale2ThreadMemory();         }  finally  {              //release the read lock             lock.unlockRead(stamp);         }     }     //3.3 The verification is passed, and the data of the thread local stack is used for logical operations     useThreadMemoryVarables(); } Copy code

Usage scenarios and precautions

For the high-concurrency scenarios with more reads and less writes, the performance of StampedLock is very good. The optimistic read mode solves the problem of "starvation" of the write thread. We can use StampedLock instead of ReentrantReadWriteLock, but it should be noted that the function of StampedLock is only When using a subset of ReadWriteLock , there are still a few things to pay attention to.

  1. StampedLock is a non-reentrant lock, you must pay attention to it during use;
  2. Both pessimistic read and write locks do not support the condition variable Conditon, you need to pay attention when you need this feature;
  3. If the thread is blocked on the readLock() or writeLock() of StampedLock, calling the interrupt() method of the blocked thread at this time will cause the CPU to surge. Therefore, you must not call interrupt operations when using StampedLock. If you need to support interrupt functions, you must use interruptible pessimistic read lock readLockInterruptibly() and write lock writeLockInterruptibly() . This rule must be remembered clearly.

Principle analysis

We found that it is not like other locks by defining internal classes to inherit AbstractQueuedSynchronizer abstract class and then subclasses to implement template methods to achieve synchronization logic. But the realization idea is still similar, the CLH queue is still used to manage threads, and the state of the lock is identified by the synchronization state value state.

A lot of variables are defined inside. The purpose of these variables is the same as ReentrantReadWriteLock. The state is divided into bits, and the state variables are manipulated to distinguish the synchronization state through bit operations.

For example, if the eighth bit of the write lock is 1, it means the write lock, and the read lock uses bits 0-7, so under normal circumstances, the number of threads that acquire the read lock is 1-126. After exceeding, the readerOverflow int variable will be used to save the excess Threads.

Spin optimization

Certain optimizations are also made to multi-core CPUs. NCPU obtains the number of cores. When the number of cores exceeds 1, the retry of the thread acquiring lock and the retry of enqueuing money all spin operations. 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. The nodes waiting in the queue are simpler than AQS. There are only three states:

  • 0: initial state;
  • -1: waiting;
  • cancel;

There is also a field, cowait, which points to a stack through this field to save the reader thread. The structure is shown in the figure

At the same time, two variables are defined to point 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 code

Another point to note is cowait, which saves all read node data and uses the header interpolation method.

When the read and write threads compete to form a waiting queue, the data is shown in the following figure:

Acquire 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 code

Acquire the write lock. If the acquisition fails, the node will be built and put into the queue, and the thread will be blocked at the same time. When you need to pay attention, this method does not respond to the interrupt. If you need to interrupt, you need to call writeLockInterruptibly(). Otherwise, it will cause high CPU usage.

(s = state) & ABITS indicates that the read lock and write lock are not used, then directly execute U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) CAS operation will set the eighth bit to 1, indicating that the write lock is occupied success. If CAS fails, acquireWrite(false, 0L) is called to join the waiting queue, and the thread is blocked at the same time.

In addition, the acquireWrite(false, 0L) method is very complicated, using a lot of spin operations, such as spinning into a queue.

Acquire a 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 code

Key steps to obtain a 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 flag by U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))CAS Acquired the read lock successfully.

Otherwise, call acquireRead(false, 0L) to try to acquire the read lock using spin, and enter the waiting queue if it fails to acquire it.

acquireRead

When the A thread acquires the write lock and the B thread acquires the read lock, call the acquireRead method, it will join the blocking queue and block the B thread. The method is still very complicated inside, and the general process is as follows:

  1. If the write lock is not occupied, it will immediately try to acquire the read lock, and the CAS will return directly if the status is changed to the flag successfully.
  2. If the write lock is occupied, the current thread is packaged as a WNode read node and inserted into the waiting queue. If it is a writing thread node, put it directly into the end of the queue, otherwise put it into the stack pointed to by the WNode cowait of the read thread specially stored at the end of the queue . The stack structure is to insert data in a header insertion method, and finally wake up the read node, starting from the top of the stack.

Release 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. I want to set the waiting state of the head node to 0 to indicate that the subsequent node is about to wake up.
  2. After waking up the subsequent node to acquire the lock through CAS, if it is a reading node, all reading nodes of the stack pointed to by the cowait lock will be awakened.

Release the read lock

unlockRead(long stamp) If the stamp passed in is consistent with the stamp held by the lock, the non-exclusive lock is released. The internal main method is to modify the state successfully through spin + CAS. Before modifying the state, it is judged whether it exceeds the limit of the number of read threads. If it is less than the limit, modify the state synchronization state through CAS, and then call the release method to wake up the successor node of whead.

Release write lock

unlockWrite(long stamp) If the passed stamp is consistent with the stamp held by the lock, the write lock is released, whead is not empty, and the current node status status! = 0 then call the release method to wake up the subsequent node threads of the head node.

summary

StampedLock cannot completely replace ReentrantReadWriteLock. Because of the optimistic read mode in the scenario of more reads and less writes, a write thread is allowed to acquire a write lock, which solves the problem of write thread starvation and greatly improves throughput.

When using optimistic reading, you need to pay attention to writing according to the programming model template, otherwise it is easy to cause deadlock or unexpected thread safety issues.

It is not a reentrant lock and does not support the condition variable Conditon. And when the thread is blocked on readLock() or writeLock(), calling the interrupt() method of the blocked thread at this time will cause the CPU to surge. If you need to interrupt the thread scenario, you must pay attention to calling **pessimistic read lock readLockInterruptibly() and write lock writeLockInterruptibly(). **In order for you to apply what you have learned, the editor here has compiled 123 real interview questions for concurrent programming . You can Let's fight it.

In addition, the rules for waking up threads are similar to AQS. The head node is awakened first. The difference is that when the node awakened by StampedLock is a reading node, all reading nodes of the stack pointed to by the cowait lock of this reading node will be awakened, but the order of waking up and inserting in contrast.