An overview of the

Concurrency locks in Java are roughly divided into implicit locks and explicit locks. Implicit locking is the most commonly used synchronized keyword. Explicit locking mainly contains two interfaces: Lock and ReadWriteLock, main implementation class already and ReentrantReadWriteLock respectively, these two classes are based on AQS (AbstractQueuedSynchronizer). Other places refer to CAS as locks, and CAS play an important role in many concurrency related classes, including AQS.

It’s easy to understand the nature and limitations of synchronized and AQS. Therefore, this article will focus on the principles and will not go into too much use and features.

conception

The following are some conceptual explanations of locks. These are descriptions of the properties of locks, not implementations.

Pessimistic locks and optimistic locks

Pessimistic locks are the same as exclusive locks and assume that a conflict will occur, so acquiring the lock will block other waiting threads. The advantage of doing this is that it is simple and safe, but both suspended and resumed threads need to go into kernel mode, which incurs a significant performance overhead. Pessimistic locks are synchronized. In the real world, however, most of the time there is no conflict. Pessimistic locks can cause a lot of waste. Optimistic locking, on the other hand, assumes that no conflicts will occur, and attempts to perform an operation first, failing to perform other operations (typically repeated retries). This lock does not block other threads, does not involve context switching, and has low performance overhead. The representative implementation is CAS.

Fair locks and unfair locks

Fair lock means that each thread checks whether there are queued threads before locking and obtains the lock in the queued order. An unfair lock refers to a thread that attempts to obtain the lock without considering the queuing problem before adding the lock. If it fails to obtain the lock, it will queue up at the end of the queue. It is worth noting that in the implementation of AQS, once a thread is queued, even if the lock is unfair, the thread must queue.

Reentrant and non-reentrant locks

If a thread has acquired a lock, it can access all blocks of code that are locked by the lock. Non-reentrant locks are the opposite.

The Synchronized keyword

Synchronized is an exclusive lock. When you modify static methods, you lock class objects, such as Object.class. When you modify a non-static method, you lock the object, which is this. When you modify a method block, you lock the objects in parentheses. Each object has a lock and a wait queue. The lock can only be held by one thread. Other threads that need the lock must block the wait. After the lock is released, the object will fetch one from the queue and wake up. It is not determined which thread to wake up, so fairness is not guaranteed.

Class and object locks

Synchronized modifies static methods by locking class objects, such as Object.class. When you modify a non-static method, you lock the object, which is this. Multiple threads can execute the same synchronized instance method at the same time, as long as they access different objects.

Synchronized locks objects rather than codes. As long as access is made to synchronized methods of the same object, even different codes will be synchronized sequential access.

In addition, it should be noted that synchronized methods do not prevent non-synchronized methods from being executed at the same time, so you generally need to add synchronized to all methods that access a variable when protecting it.

Realize the principle of

Synchronized is implemented based on Java object headers and the Monitor mechanism.

Java object head

An object contains three parts in memory: object header, instance data, and alignment padding. The Java object header contains two parts:

• Class Metadata Address type pointer. A pointer to the metadata of the storage class. The virtual machine uses this pointer to find out which class instance it is.
• Mark Word (Mark field). Store some runtime data for the object itself. Including hash code, GC generation age, lock status flags and so on.

Monitor

The Mark Word has a field pointing to a Monitor object. Monitor records information such as the thread holding the lock and the queue of waiting threads. Each object has a lock and a wait queue, which is implemented here. Monitor objects are implemented in C++. There are three key fields:

• _owner Records the thread that currently holds the lock
• _EntryList is a queue that records all threads blocking for locks
• _WaitSet is also a queue for threads that have called wait() and have not yet been notified.

Monitor operates as follows:

1. When multiple threads compete for locks, they enter the EntryList queue first. The thread that successfully competes is marked as Owner. Other threads continue to block and wait in this queue.
2. If the Owner thread calls wait(), it releases the object lock and enters the WaitSet to be awakened. The Owner is left empty, and the threads in the EntryList again compete for the lock.
3. If the Owner thread finishes executing, the lock is released, the Owner is empty, and the threads in the EntryList compete for the lock again.

JVM handling of synchronized

How does a virtual machine associate synchronized with monitor? There are two cases:

• If you are synchronizing a code block, the monitorenter directive is directly preceded by the synchronized block and the Monitorexit directive is followed by the synchronized block. This is called display synchronization.
• If a method is synchronized, the virtual machine sets the ACC_SYNCHRONIZED flag for the method. The JVM uses this flag to determine if the method is synchronous when called.

JVM optimization for Synchronized

Synchronized is a heavyweight lock and has been optimized by the virtual machine due to its high consumption.

Spin-locking and adaptive spin

In many applications, the lock state lasts only a short time, and it is not worth suspending the recovery thread for this time. We can have the waiting thread execute a loop a certain number of times to acquire the lock. This technique, called spin-locking, saves the system switching threads, but still hogs the processor. In JDK1.4.2, the number of selectable times can be controlled by a parameter. JDK 1.6 also introduced adaptive spin locks, which are not limited by the number of spins on the same lock, but by the time of the previous spin on the lock and the state of the lock owner.

Lock elimination

When the virtual machine is running, a locked piece of code that cannot possibly contain shared data is cleared.

Lock coarsening

When the virtual machine detects a string of fragmented operations that lock the same object, it extends the lock outside the entire operation sequence. Such as the append operation for StringBuffer.

Lightweight lock

For the vast majority of locks, there is no contention for the entire synchronization cycle. If there is no competition, lightweight locks can avoid the mutex overhead using CAS operations.

Biased locking

The core idea of biased locking is that if a thread acquires a lock, then the lock goes into biased mode. When the thread requests the lock again, it can acquire the lock without any synchronization operation.

CAS

Operating model

CAS is short for compare and swap, compare and swap. It refers to an operation mechanism, not a specific class or method. This operation is wrapped on the Java platform. In the Unsafe class, the calling code looks like this:

unsafe.compareAndSwapInt(this, valueOffset, expect, update);
Copy the code

It takes three parameters, the memory location V, the old expected value A, and the new value B. The operation reads A value from A memory location and compares it with the expected value A. If equal, change the value of this memory location to the new value B, returning true. If not, it conflicts with another thread, and returns false without making any changes.

This mechanism avoids concurrent collisions without blocking other threads and is much better than exclusive locks. CAS is used heavily in Java atomic classes and concurrent packages.

Retry mechanism (cyclic CAS)

There are many articles that say that CAS operations fail and retry until they succeed, which is a loose statement.

First, CAS itself does not implement a post-failure processing mechanism. It only returns a Boolean value for success or failure, leaving it up to the caller. But the most common way to do this is retry.

Second, it’s easy to misunderstand this sentence as a recomparison and exchange. When it actually fails, the original value has already been modified, and if you don’t change the expected value, no comparison will fail. The new value also needs to be modified.

Therefore, the correct method is to use an infinite loop to perform the CAS operation. On success, the loop ends and returns. On failure, the value is read from memory again and the new value is calculated, and then CAS is called. Take a look at AtomicInteger source code to understand everything:

public final int incrementAndGet () {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            returnnext; }}Copy the code

The underlying implementation

CAS consists of three steps: read – compare – modify. The comparison is to check whether there is a conflict. If no conflict is detected, other threads can modify the value, then the CORRECTNESS of CAS still cannot be guaranteed. So the key is to ensure atomicity of the comparison-modify two-step operation.

The underlying CAS is accomplished by invoking the CPU instruction set CMPXCHG, which is the compare and Exchange instruction in x86 and Intel architectures. In the case of multiple cores, this instruction can not guarantee atomicity, need to be preceded by the LOCK instruction. The LOCK instruction ensures that a CPU core has an exclusive memory area during operation. So how does this work?

In the processor, there are generally two ways to achieve this effect: bus locks and cache locks. In a multi-core processor architecture, the CPU core does not have direct access to memory, but is unified through a bus access. A bus lock locks the bus so that other cores cannot access memory. This approach is too costly and causes other cores to stop working. A cache lock does not lock the bus, but only a portion of memory. When a CPU core reads data from a memory region into its cache, it locks the memory region corresponding to the cache. During the lock, other cores cannot manipulate this memory region.

This is how CAS implements atomicity for comparison and swap operations. Note that CAS only guarantees atomicity of operations, not visibility of variables, so the volatile keyword is required.

ABA problem

As mentioned above, CAS guarantees atomicity for comparison and interchange. However, other cores can still change this value between reading and starting the comparison. CAS can tell if the core changes A to B. But if the core changes A to B and then changes back to A. CAS will assume that the value has not changed and proceed. This is not consistent with the actual situation. The solution is to add a version number.

ReentrantLock

ReentrantLock uses code to implement the same semantics as synchronized, including reentrancy, memory visibility, and race conditions. Compared to synchronized, it has the following benefits:

• Lock acquisition is supported in a non-blocking manner
• Can respond to interrupts
• Can time
• Fair and unfair locks are supported

The basic usage is as follows:

public class Counter {
    private final Lock lock = new ReentrantLock();
    private volatile int count;

    public void incr() {
        lock.lock();
        try {
            count++;
        } finally {
            lock.unlock();
        }
    }

    public int getCount() {
        returncount; }}Copy the code

ReentrantLock has two internal classes, FairSync and NoFairSync, that correspond to fair and unfair locks. They all inherit from Sync. Sync in turn inherits from AQS.

AQS

AQS full name AbstractQueuedSynchronizer. There are two important members of AQS:

• The member variable state. Used to indicate the current state of the lock. The volatile modifier ensures memory consistency. Meanwhile, all operations on state are performed using CAS. A state of 0 means that no thread is holding the lock, and the thread that holds the lock increments state by one and decays state by one when it releases the lock. Multiple hold releases add and subtract multiple times.
• There is also a bidirectional linked list, where each node except the head node records information about the thread, representing a waiting thread. This is a linked list of FIFOs.

The following code to ReentrantLock unfair lock to see the principle of AQS.

Request a lock

There are three possibilities when requesting a lock:

1. If no thread holds the lock, the request succeeds and the current thread directly acquires the lock.
2. If the current thread already holds the lock, then CAS is used to increment the state value by 1 to indicate that it has applied for the lock again. When releasing the lock, the value is reduced by 1. That’s the implementation of reentrancy.
3. If another thread holds the lock, it adds itself to the wait queue.

final void lock() {
    if (compareAndSetState(0, 1))   
        setExclusiveOwnerThread(Thread.currentThread()); // If no thread holds the lock, the lock is acquired directly, corresponding to case 1else
        acquire(1);
}

public final void acquire(int arg) {
    if(! AcquireQueued (addWaiter(node.exclusive), arg)) // Add thread to queue Case 3 selfInterrupt(); }Copy the code

Create a Node Node and join the linked list

If there is no lock contention, then the wait queue is entered. Queues have a head node by default and do not contain thread information. In case 3 above, addWaiter creates a Node that holds a reference to the current thread and is added to the end of the linked list. There is also a member variable, waitStatus, which represents the wait state of the thread, with an initial value of 0. There are two more values we need to focus on:

• CANCELLED, ‘1’ means’ I don’t want the lock ‘, please move me out.
• SINGAL, with a value of -1, indicates that the next node is pending, not the current node.

Meanwhile, the operations added to the end of the list use the CAS+ infinite loop pattern, which is typical. Take a look:

Node node = new Node(mode);
for (;;) {
    Node oldTail = tail;
    if(oldTail ! = null) { U.putObject(node, Node.PREV, oldTail);if (compareAndSetTail(oldTail, node)) {
            oldTail.next = node;
            returnnode; }}else{ initializeSyncQueue(); }}Copy the code

As you can see, the CAS method is called in an infinite loop. If multiple threads call this method at the same time, only one thread executes successfully in each loop, and the other threads enter the next loop and call again. N threads will loop N times. This implements the concurrency model in lock-free mode.

Hang wait for

• If the previous node to this node was the head node, it tries to acquire the lock again, removes it and returns. If not, proceed to the next step;
• Determine the waitStatus of the previous node, return true if it is SINGAL, and call locksupport.park () to suspend the thread;
• CANCELLED, the previous node is removed;
• If it is any other value, the previous node’s waitStatus is marked as SINGAL and the next loop is entered.

As you can see, a thread has at most two chances to suspend the wait before it can compete.

final boolean acquireQueued(final Node node, int arg) {
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true; } } catch (Throwable t) { cancelAcquire(node); throw t; }}Copy the code

Release the lock

• Call tryRelease, which is implemented by subclasses. The implementation is very simple. If the current thread is the thread holding the lock, subtract state by one. If state is greater than 0, the current thread still holds the lock, and returns false. If 0, no thread holds the lock, return true, and proceed to the next step.
• If the head node’s waitStatus is not equal to 0, call locksupport.unpark () to wake up its next node. The next node to the head node is the first thread in the wait queue, reflecting the FIRST-in-first-out nature of AQS. In addition, even if the lock is unfair, after entering the queue, you still have to do it in order.

public final boolean release(int arg) {
    if(tryRelease(arg)) {// Subtract state from 1 Node h = head;if(h ! = null && h.waitStatus ! = 0) unparkSuccessor(h);return true;
    }
    return false;
}

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        node.compareAndSetWaitStatus(ws, 0);
        
    Node s = node.next;
    if (s == null || s.waitStatus > 0) { 
        s = null;
        for(Node p = tail; p ! = node && p ! = null; p = p.prev)if (p.waitStatus <= 0)
                s = p;
    }
    if(s ! = null) // Wake up the first waiting thread locksupport.unpark (s.read); }Copy the code

How is fair locking implemented

The above analysis is unfair locks, but what about fair locks? It is simple to determine if there are threads waiting in the wait queue before competing for locks.

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if(! Hasqueuedtoraise () && compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);
            return true; }}...return false;
}
Copy the code

ReentrantReadWriteLock ReentrantReadWriteLock

Read/write lock mechanism

After understanding ReentrantLock and AQS, it’s easy to understand read and write locks. A read-write lock has a read lock and a write lock, corresponding to the read operation and lock operation respectively. The lock features are as follows:

• Only one thread can acquire the write lock. A write lock is acquired only when no thread holds any lock.
• If a thread is holding a write lock, no other thread can acquire any lock.
• When no thread holds the write lock, multiple threads can acquire the read lock.

The lock feature guarantees concurrent reads, which greatly improves efficiency and is very useful in practical development. So how to achieve it in detail?

Realize the principle of

Read/write locks have two locks, but actually only one wait queue.

• When acquiring a write lock, ensure that no thread holds the lock.
• When a write lock is released, the first thread in the queue is woken up, possibly by a read lock or a write lock.
• When obtaining a read lock, check whether the write lock is held first.
• After obtaining the read lock successfully, the thread waiting for the read lock in the queue will wake up one by one to know the location of the thread waiting for the write lock.
• When releasing read locks, check the number of read locks. If the number is 0, wake up the next thread in the queue. Otherwise, no operation is performed.

The resources

Java CAS principle analysis

Check out ReentrantLock and AQS implementation principles

In-depth understanding of Java concurrency implementation principles of Synchronized

Explicit locking/thinking logic of computer programs