Click “like” to see, form a habit, wechat search [Three prince Aobing] follow this fool who seems to have something

This article has been included in GitHub github.com/JavaFamily, there are a line of big factory interview complete test points, materials, resume template, and my life program.

preface

In multithreaded development, the synchronized keyword and reentrant lock are most commonly used to control thread synchronization. In JDK8, a new weapon, the StampedLock, was introduced. What is it? The word Stamp means a postmark. So what does that mean here? Fool, see the breakdown below.

Faced with the problem of critical area resource management, there are generally two sets of ideas:

The first is to use a pessimistic strategy. The pessimist thinks that every time I access a shared variable in a critical section, someone will always conflict with me, so I must lock the entire object and unlock it after I have accessed it.

However, optimists on the contrary believe that although the shared variables in the critical area will conflict, the conflict should be a small probability event, and in most cases, it will not happen. Therefore, I can first access it. If there is no conflict after I run out of data, then my operation is successful. If I’m done and someone conflicts, I either try again or switch to a pessimistic strategy.

It’s not hard to see from this that reentrant locking and synchronized are typically pessimistic strategies. As you might have guessed, StampedLock provides a tool for optimistic locking, and is therefore an important complement to reentrant locking.

Basic use of StampedLock

The Documentation for StampedLock provides a good example of how to use StampedLock quickly. So let me take a look at this example, and it’s all explained in the comments.

To clarify what the validate() method means, the function signature looks like this:

public boolean validate(long stamp)
Copy the code

Its acceptance argument is the postmark returned by the last lock operation. If the lock was not applied for before validate() was called, it returns true. This means that the shared data protected by the lock has not been modified, so the previous read operation is guaranteed to ensure data integrity and consistency.

If, on the other hand, a write lock was successfully applied for before validate(), this indicates that the previous read and write operations conflict and the program needs to retry or upgrade to a pessimistic lock.

And reentrant locking

As you can see from the examples above, StampedLock is much more complex than locking, and the code is not as clean as it used to be.

So why do we still use it?

The most fundamental reason is to improve performance! In general, the performance of this optimistic lock is several times faster than a normal reentrant lock, and the performance difference increases as the number of threads increases.

In short, StampedLock’s performance in massively concurrent scenarios is to roll over reentrers and read-write locks.

But after all, nothing in the world is perfect, and StampedLock is not perfect. Its disadvantages are as follows:

  1. Coding is cumbersome, and if optimistic reading is used, conflicting scenarios should be handled by the application itself
  2. It is non-reentrant, and if you accidentally call it twice in the same thread, your world is clean…
  3. It does not support wait/notify

If none of the above is a problem for you, THEN I believe StampedLock should be your first choice.

Internal data structure

To help you better understand StampedLock, here is a brief introduction to its internal implementation and data structure.

In StampedLock, there is a queue that holds threads waiting on the lock. The queue is a linked list whose element is an object called WNode:

When there are several threads waiting in the queue, the entire queue might look like this:

In addition to this wait queue, another particularly important field in StampedLock is long State, which is a 64-bit integer that StampedLock uses very cleverly.

The initial value of state is:

private static final int LG_READERS = 7;
private static final long WBIT  = 1L << LG_READERS;
private static final long ORIGIN = WBIT << 1;
Copy the code

That is… Too much in front of 0001, 0000, 0000 (0, do not write, fill 64 ~), why don’t you do the initial value 0 here? Because 0 has a special meaning, a non-zero number was chosen to avoid conflicts.

If there is a write lock, set the 7th bit to 1… 0001, 1000, 0000, plus WBIT.

Each time the write lock is released, it increments by 1, but instead of adding state directly, it removes the last byte and uses only the first 7 bytes for statistics. Therefore, when the write lock is released, state becomes:… 0010 0000 0000 0000… 0010, 1000, 0000, and so on.

Why record the number of times the write lock is released?

This is because the state judgment of the entire state is based on the CAS operation. However, normal CAS operations may encounter ABA problems. If the number of times is not recorded, then when the write lock is released, the request is obtained, and then released, we will not be able to determine whether the data has been written. When “release -> apply -> release” occurs, the CAS operation can check the data changes and determine that the write operation has occurred. As an optimistic lock, the CAS operation can accurately determine that the conflict has occurred, and the rest is left to the application to resolve the conflict. Therefore, the number of locks released is recorded in order to accurately monitor thread conflicts.

Seven bits of the remaining byte of state are used to record the number of threads that read the lock. Since there are only seven bits, only 126 are recorded. See RFULL in the code below. If it does, the excess is logged in the readerOverflow field.

    private static final long WBIT  = 1L << LG_READERS;
    private static final long RBITS = WBIT - 1L;
    private static final long RFULL = RBITS - 1L;
    private transient int readerOverflow;
Copy the code

To summarize, the structure of the state variable is as follows:

Write lock request and release

Now that you’ve looked at StampedLock’s internal data structure, let’s look at applying and releasing write locks! First is the write lock request:

    public long writeLock(a) {
        long s, next;  
        return ((((s = state) & ABITS) == 0L &&  // If there is no read/write lock, set the write lock flag
                 U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
                // If you write a lock successfully within the scope next, or if you fail, enter acquireWrite().
                next : acquireWrite(false.0L));
    }
Copy the code

If the CAS state fails, the write lock application failed, and acquireWrite() is invoked to apply or wait. AcquireWrite () does a few things in general:

  1. The team
    1. If the head is equal to the tailwtail == whead, means it’s almost my turn, so spin wait, grab the end
    2. ifwtail==nullIf no queue is initialized, initialize the queue
    3. If there are other waiting nodes in the queue, then you have to join the queue and wait
  2. Block and wait
    1. If the head node is equal to the front node(h = whead) == p)“That means it’s my turn, too, spinning and waiting for the scramble
    2. Otherwise wake up the reader thread in the header
    3. If the lock cannot be preempted, park() the current thread

Simply put, the acquireWrite() function is used to scramble locks, its return value is the postmark of the current lock state, and acquireWrite() uses a lot of spin retries to improve lock performance, so its code looks a bit arcane.

UnlockWrite () is passed in as the postmark from which the lock was applied:

    public void unlockWrite(long stamp) {
        WNode h;
        // Check whether the lock status is normal
        if(state ! = stamp || (stamp & WBIT) ==0L)
            throw new IllegalMonitorStateException();
        // Set the flag bit of state to 0, which also increases the number of locks released
        state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
        // The header is not empty, try to wake up subsequent threads
        if((h = whead) ! =null&& h.status ! =0)
            // Wake up (unpark) the next thread
            release(h);
    }
Copy the code

Read lock request and release

The code to obtain the read lock is as follows:

    public long readLock(a) {
        long s = state, next;  
        // If there is no write lock in the queue and the number of reader threads does not exceed 126, the lock is acquired directly and the number of reader threads is increased by 1
        return ((whead == wtail && (s & ABITS) < RFULL &&
                 U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
                // If the scramble fails, enter acquireRead() to scramble or wait
                next : acquireRead(false.0L));
    }
Copy the code

The implementation of acquireRead() is quite complex and can be broken down into several steps:

In short, it’s spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin, spin.

Here is how to release the read lock:

StampedLock pessimistic read full CPU issues

StampedLock is a great thing, but because it’s so complex, it does have a few hiccups. The following example demonstrates the CPU usage of StampedLock pessimistic locks:

public class StampedLockTest {
    public static void main(String[] args) throws InterruptedException {
        final StampedLock lock = new StampedLock();
        Thread t1 = new Thread(() -> {
            // Get the write lock
            lock.writeLock();
            // The simulator blocks and waits for other resources
            LockSupport.park();
        });
        t1.start();
        // Make sure t1 gets the write lock
        Thread.sleep(100);
        Thread t2 = new Thread(() -> {
            // Block in pessimistic read lock
            lock.readLock();
        });
        t2.start();
        // ensure t2 blocks read lock
        Thread.sleep(100);
        // Interrupt thread T2, which causes the CPU of thread T2 to spiket2.interrupt(); t2.join(); }}Copy the code

In the above code, after the interruption of T2, the CPU usage of T2 is 100% saturated. At this point, T2 is blocking on the readLock() function, in other words, StampedLock’s read locks might fill up the CPU after being interrupted. What is the reason for this? The mechanical fool must have figured it out because there was too much spin in StampedLock! Yes, your guess is correct.

Specific reasons are as follows:

If there are no interrupts, the thread blocking on readLock() will wait in park() after a few spins, and once in park() wait, it will not consume CPU. The park() function, however, has a feature that if the thread is interrupted, park() will return immediately. Even if it does not return, it will not throw you any exceptions. Originally, you wanted the unpark() thread to start when the lock was ready, but now when the lock was not ready, you interrupt it and park() returns, but after all, the lock was not ready, so it spins again.

All the way around, we get to park(), but unfortunately, the thread’s interrupt flag stays open, park() stops blocking, and the next spin starts. The endless spin doesn’t stop, so the CPU is full.

To solve this problem, essentially inside StampedLock, when Park () returns, you need to determine that the interrupt is marked as and do the right thing, such as exit, throw an exception, or clean up the interrupt bit.

Unfortunately, at least in JDK8, there is no such treatment. Thus, the CPU overloads after interrupting readLock(), as shown above. Please pay attention.

Write in the last

Today, we took a closer look at the use and main implementation ideas of StampedLock, an important complement to reentrant and read-write locks.

It provides an optimistic locking strategy and is a different kind of locking implementation. StampedLock is, of course, a little more difficult to program than in-lock and read-write locks, but it’s a performance multiplier.

Here are some tips for you. If your application has a controllable number of threads, and the competition is not too fierce, then you can directly use simple synchronized, reentrant lock, read and write lock; If your application is threaded, competitive, and performance-sensitive, you need to take the trouble to use StampedLock, which is more complex, to increase the throughput of your application.

Note that StampedLock is not reentrant and should not be deadlocked by a single thread. StampedLock does not have a wait/notification mechanism, so if you must use StampedLock, you will have to bypass it.

Do the little fools have a deeper understanding of this underdog? Take a wave in the comments section: Get Stronger

I’m Aobing, and the more you know, the more you don’t know, and I’ll see you next time.

This article is constantly updated. You can search “Santaizi Aobing” on wechat and read it for the first time. Reply [Information] There are the interview materials and resume templates for first-line big factories prepared by me.