ReentrantLock source code analysis

Scan the qr code below or search the wechat official account, cainiao Feiyafei, you can follow the wechat official account, read more Spring source code analysis and Java concurrent programming articles.

The problem

Here are two questions to consider before reading this article

1.How does ReentrantLock implement locking at the Java level (not the JVM level)?
2.What is a fair lock? What is an unfair lock?

Introduction to the

LockIs an interface in the JUC package that defines lock acquisition, lock release, and lock-related methods.ReentrantLockIs a concrete implementation class of the Lock interface that acquires the Lock exclusively and reentrantly. There are two concepts here,reentrantandexclusive. Reentrant means that the same thread can acquire the lock more than once. Exclusive means that only one thread can acquire the lock at a time.
ReentrantLockThe implementation of locks can be divided into two categories, respectivelyFair lockandNot fair lock, respectively by two inner classes in the ReentrantLock classFairSyncandNonfairSyncTo implement. FiarSync NonfairSync and inherited the Sync, and Sync class inherits AbstractQueuedSynchronizer (AQS) class, so already is ultimately rely on AQS to realize locking. For more information about AQS, please refer to the following two articles.
Design principle of queue synchronizer (AQS)
Queue synchronizer (AQS) source code analysis
ReentrantLock has two constructors, one with no arguments and one with arguments. When an object is created using the no-argument constructor, an unfair lock is created. In the parameter constructor, you can pass in a variable of type Boolean. If true is passed, the lock is fair; if false, the lock is unfair.

/**
 * Creates an instance of {@code ReentrantLock}.
 * This is equivalent to using {@code ReentrantLock(false)}.
 */
public ReentrantLock(a) {
    sync = new NonfairSync();
}

/**
 * Creates an instance of {@code ReentrantLock} with the
 * given fairness policy.
 *
 * @param fair {@code true} if this lock should use a fair ordering policy
 */
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}
Copy the code

Fair lock

When true is passed into the constructor of a ReentrantLock, a fair lock is created. Fair locklock()andunlock()Method implementations are made by the FairSync classlock()andrelease()Method (where the release() method is defined in AQS).

public static void main(String[] args) {
    ReentrantLock lock = new ReentrantLock(true);
    try{
        lock.lock();
        System.out.println("Hello World");
    }finally{ lock.unlock(); }}Copy the code

Acquiring a lock

When lock.lock() is called, the fairsync.lock () method is called, and the fairsync.lock () method calls acquire() in AQS.

static final class FairSync extends Sync {
    final void lock(a) {
        // Call acquire() to get the synchronization status
        acquire(1); }}Copy the code

In the acquire() method of AQS, the tryAcquire() method of the subclass will be called first. At this time, since we create a fair lock, the tryAcquire() method of the FairSync class will be called. For details on acquire(), see queue Synchronizer (AQS) source code analysis.
The tryAcquire() method acquires the synchronization state (that is, the lock). If the current thread successfully acquires the lock, it increments the synchronization state in the AQS by one and returns true. If the lock is not acquired, it returns false. The source code for the tryAcquire() method on the FairSync class is shown below.

protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        (In AQS, state is equivalent to the lock. If the thread can successfully modify state, then it has acquired the lock.)
        int c = getState();
        if (c == 0) {
            // If c equals 0, no thread has acquired the lock

            /** * there may be multiple threads executing at the same time, all of which satisfy the condition c==0. * In the if condition, the hasqueuedToraise () method is first called to determine whether a thread is already queuing in the queue. This method returns true to indicate that a thread is queuing and false to indicate that no thread is queuing. Hasqueuedtoraise () returns true, indicating that a thread is queued, * at this point! Hasqueuedtoraise () == false, the ifcondition is false due to the && operator's short circuit, and the if statement is not entered. The tryAcquire() method returns false * * the second case: Hasqueuedtoraise () returns false, indicating that no threads are queued * at this time! 24 hasqueuedToraise () == true, then a&&, CompareAndSetState () is a CAS method that changes the value of the state field. The result of the compareAndSetState() method is divided into two cases * the ith case: When the CAS is successfully modified, the state field returns true, and the if condition is true, and the if statement is entered, indicating that the current thread has acquired the lock. The final tryAcquire() method returns true * case II: If the CAS fails to modify the state field, another thread has acquired the lock at that moment, the if condition is false, and the if block is not entered, and the tryAcquire() method returns false. * /
            if(! hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
                // The current thread successfully changed the value of the state field, which means that the current thread acquired the lock, then set the owner of the lock in the AQS to the current thread, and return true.
                setExclusiveOwnerThread(current);
                return true; }}// If c = 0, the lock has been acquired by the current thread
        else if (current == getExclusiveOwnerThread()) {
            // If it is the current thread, then the value of state is increased by 1, which is the reentrant of the lock
            int nextc = c + acquires;
            if (nextc < 0)
                throw new Error("Maximum lock count exceeded");
            // Because only one thread must have acquired the lock, only the thread that acquired the lock will execute this line of code, so you can directly call setState(nexTC) to change the value of state. There is no thread-safety issue here.
            setState(nextc);
            // Then return true to indicate that the current thread has acquired the lock
            return true;
        }
        // If state is not equal to 0 and the current thread is equal to the thread that has acquired the lock, return false to indicate that the current thread did not acquire the lock
        return false; }}Copy the code

In the tryAcquire() method, the synchronization state is determined to be 0.
1.If it equals 0, it means that no thread currently holds the lock, which is called firsthasQueuedPredecessors()The tryAcquire() method checks if there are any threads in the queue waiting to acquire the lock. If a thread is queued, the current thread will fail to acquire the lock (because AQS is designed using FIFO, you cannot jump the queue if someone is queued). If there are no threads queued in the synchronization queue, then let the current thread CAS state. If the setting succeeds, the lock is currently acquired and returns true. If CAS fails, the lock was snatched by another thread at that instant, the current thread failed to acquire the lock, and false is returned.
2.If it is not equal to 0, it means that some thread has acquired the lock, then it will determine whether the current thread is equal to the thread that already holds the lock (The getExclusiveOwnerThread() method returns the thread that already holds the lock), if they are equal, then state is incremented by 1. This is called a reentrant lock, which allows the same thread to acquire the lock more than once.
3.If state is not equal to 0 and the current thread is not equal to the thread holding the lock, false is returned indicating that the current thread failed to acquire the lock.
In this way, the logic of fair lock acquisition is implemented through the tryAcquire() method of the FairSync class. The logic of the tryAcquire() method is different in different lock implementations. For example, in an unfair lock, the code logic of NonfairSync’s tryAcquire() method is different from that of FairSync’s tryAcquire() method. When a thread attempts a CAS operation on state, it does not determine whether a thread is queuing on the synchronous queue (that is, it does not call the HasqueuedBoomon () method).
The hasqueuedProsper () method is used to determine whether a thread is queued on a synchronous queue and returns true if it is, false if it is not. The source code is as follows, and the method is explained in detail in the posted code snippet (to understand this method, you need to have a certain understanding of the design principles of AQS, you can read this article: Queue Synchronizer (AQS) Design principles).

public final boolean hasQueuedPredecessors(a) {
    Node t = tail; // Read fields in reverse initialization order
    Node h = head;
    Node s;

    /** * This method checks whether a thread is queued in the queue. It returns true if there are threads queued, and false if there are no threads queued. * first: the queue has not been initialized, head = null, tail = null, threads do not need to queue. * 2: The enq() method uses tail = head as the first step, and sets the Node represented by the current thread to tail as the second step. In the enq() method, tail = head as the first step, and tail as the second step. So there is a possibility that tail = head exists at the moment between the two steps *. For all threads, there is no need to queue * when h! = t result is true, then determine ((s = h.n ext) = = null | | s.t hread! CurrentThread () == null * * if (s = h.next) == null * * if (s = h.next) == null * * If (s = h.next) == null If s == null, the second node is null. = t, * shows that at this point has been the second thread into the queue, but it hasn't come yet and will be the next head node pointer pointing to modify, so this thread thread need to queue, because * | | operation cause of short circuit when (s = h.n ext) = = null result is true, The following judgment is not entered, and hasqueuedboomtoraise () returns true, indicating that the thread needs to queue. * when s is not null, s.read! It determines whether the Thread in node s is not equal to the currentThread. If it is not, hasqueuedboomtoraise () returns true, indicating that the currentThread needs to be queued. * Because when the second node is not the current thread, it means that the current thread should be at least third in the queue, so it needs to queue. * if the threads in a s nodes is equal to the current thread, it means that the current thread is ranked second in the queue (has access to lock the thread) was the first one, the threads are not need to queue, * because might have access to lock the thread in the moment the release of the lock, then ranked second in the queue for thread also lined what oh, Just try to get the lock. * * * * /

    returnh ! = t && ((s = h.next) ==null|| s.thread ! = Thread.currentThread()); }Copy the code

Release the lock

When the lock.unlock() method is called to release the lock, the release() method of AQS is called. If the lock is released successfully, the value of the state variable in AQS is reduced to 0. In the release() method, the tryRelease() method is called and then the unparksucceeded () method is called to wake up a thread in the synchronization queue waiting to acquire the lock. The logic of the tryRelease() method is implemented by subclasses, with different implementations for different locks. For ReentrantLock, however, the logic for releasing a fair lock is the same as that for an unfair lock, calling the tryRelease() method of Sync.
The AQS release() method source code is as follows.

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        // When the lock is released successfully, other threads in the synchronization queue need to be woken up
        Node h = head;
        / / when waitStatus! If =0, there are other threads in the synchronization queue waiting to acquire the lock
        if(h ! =null&& h.waitStatus ! =0)
            // Wake up the next thread in the synchronization queue that can try to acquire the lock
            unparkSuccessor(h);
        return true;
    }
    return false;
}
Copy the code

The source and code for the tryRelease() method of the Sync class are commented below.

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    // Determine if the current thread is the thread holding the lock, if not, throw an exception
    if(Thread.currentThread() ! = getExclusiveOwnerThread())throw new IllegalMonitorStateException();
    // Since the previous step confirmed that the current thread holds the lock, it must be thread-safe when changing state
    boolean free = false;
    // If state=0, the lock will be released completely.
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}
Copy the code

TryRelease () returns a successful lock release. TryRelease () returns true only if the synchronization state variable has been reduced to 0, and false otherwise. If the lock has been re-entered multiple times, tryRelease() will be called multiple times. If tryRelease() returns true, the lock has been released. If tryRelease() returns true, the lock has been released. Call the unparksucceeded () method to wake up the next thread in the synchronization queue nearest the head node that is eligible for the lock. Why is it closest to the head? Because AQS guarantees FIFO. Why is it qualified? Because the status of some threads in the synchronization queue is cancelled, i.e. the Node Node waitStatus=1, this thread cannot be woken up to grab the lock. In addition, this is just to wake up the thread to try to acquire the lock, there is no guarantee that it will be acquired. The method used to wake up a thread isLockSupport.unpark().
The source code and comments for the unparksucceeded () method are below.

private void unparkSuccessor(Node node) {
    /* * If status is negative (i.e., possibly needing signal) try * to clear in anticipation of signalling. It is OK if this * fails or if status is changed by waiting thread. */
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    /* * Thread to unpark is held in successor, which is normally * just the next node. But if cancelled or apparently null, * traverse backwards from tail to find the actual * non-cancelled successor. */
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        /** * The thread on which the lock is placed in the synchronization queue may have been cancelled, and the waitStatus of the node in the synchronization queue is 1 *. The second node in the synchronization queue should be woken up, but if the thread of the second node is cancelled, it cannot be woken up at this time. * The third node should be judged, and if the third node is also cancelled, then the next node should be judged until the first time there is a node that has not been cancelled. If both are cancelled, then s==null, so no threads are awakened */
        for(Node t = tail; t ! =null&& t ! = node; t = t.prev)if (t.waitStatus <= 0)
                s = t;
    }
    if(s ! =null)
        LockSupport.unpark(s.thread);
}
Copy the code

Not fair lock

An unfair lock is created when false is passed in the no-parameter constructor of ReentrantLock or in the parameter constructor. The implementation of an unfair lock is implemented by the NonfairSync class. The acquisition logic of an unfair lock is slightly different from that of a fair lock, and the lock release is exactly the same.

Acquiring a lock

Acquiring an unfair lock starts with a call to the lock() method of the NonfairSync class. An unfair lock does not determine whether there is a queue in the synchronization queue. Instead, it directly attempts to change the state variable to 1. If the change succeeds, the thread has acquired the lock, and the lock() method ends. If the change fails, call AQS acquire() again to try to acquire the lock.

static final class NonfairSync extends Sync {
    
    final void lock(a) {
        If AQS acquire() fails, go to acquire()
        if (compareAndSetState(0.1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1); }}Copy the code

When the acquire() method of AQS is called, the tryAcquire() method of the AQS subclass is called in the acquire() method, in which case the tryAcquire() method of the NonfairSync class is called. The source code is as follows.

protected final boolean tryAcquire(int acquires) {
    // Call nonfairTryAcquire()
    return nonfairTryAcquire(acquires);
}
Copy the code

NonfairSync’s tryAcquire() method calls the nonfairTryAcquire() method.

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // It differs from fair locking in that fair determines whether there is a queue in the synchronization queue before CAS operation.
        / /! hasQueuedPredecessors()
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true; }}else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
Copy the code

You can see that the logic of the nonfairTryAcquire() method is very similar to the logic of the FairSync tryAcquire() method, with the only difference being whenc == 0When,An unfair lock does not determine whether there is a queue in the synchronization queue, butdirectlyCall the CAS method to set the value of state.A fair lock determines whether there is a queue in the synchronization queueIf no one is queuing, the CAS method is called to set the value of state. That is, the unfair lock is not calledhasQueuedPredecessors()Methods. The rest of the logic, fair and unfair locking logic is the same.

Release the lock

The release logic for an unfair lock is the same as that for a fair lock, which ends with a call to the tryRelease() method of Sync.

conclusion

This article mainly introduces how to passReentrantLockTo create fair and unfair locks, using the default no-argument constructor to create unfair locks; When created using the parameter constructor, an unfair lock is created if false is passed as the argument, and a fair lock is created if true is passed.
The class of the synchronous component that implements fair locking isFairSync, the class of the synchronous component that implements unfair locking isNonfairSync, which are subclasses of queue synchronizer AQS.
By analyzing FairSync and NonfairSync classes respectivelytryAcquire()Methods: The process of acquiring fair lock and unfair lock is analyzed. At the same time, by comparing the implementation codes of the two, it is found that the unfair lock will not judge whether there are threads queuing in the synchronization queue when acquiring the lock, but will directly try to modify the value of state, while the fair lock will first judge whether there are threads queuing in the synchronization queue when acquiring the lock, and will try to modify the value of state if there are no threads queuing.
A fair lock releases the lock using the same logic as a non-male lock.
Finally, answer the two questions at the beginning of the article.
1.How does ReentrantLock implement locking at the Java level (non-JVM implementation)?
Already the class byCombine a synchronization component, Sync, to implement the lock, the synchronization component inherits AQS and rewrites the tryAcquire(), tryRelease() and other methods in AQS. Finally, the lock logic is actually implemented through AQS and the rewritten tryAcquire(), tryRelease() and other methods. ReentrantLock implements the lock in the same way that other types of locks are implemented under JUC packages, by combining a custom synchronization component that inherits AQS and then overwriting some of the methods in AQS to implement a custom lock. This synchronization component is typically defined as an inner class.
2.What is a fair lock? What is an unfair lock?
byFairSyncThe lock implemented by the synchronization component is a fair lock. The principle of acquiring the lock is that the thread waiting for the longest time in the synchronization queue acquires the lock, so it is called a fair lock. byNonfairSyncThe lock implemented by the synchronization component is unfair. The principle of acquiring the lock is that when the thread outside the synchronization queue tries to acquire the lock, it will not judge whether there is a thread in the queue. Instead, it will grab the lock and walk away.

Related to recommend

See the Bean creation process from the source code
The Spring source code series container startup process
In the Spring! The most! The most! Important afterprocessor! No one!!
@ Import and @ EnableXXX
Write a Redis/Spring integration plug-in by hand
Why should dynamic proxies in the JDK be implemented based on interfaces and not inheritance?
FactoryBean – one of Spring’s extension points
How the @autowired annotation works
The practical application of the one-time policy design pattern
How does Spring address loop dependencies
Pipe program: the cornerstone of concurrent programming
Learn the implementation principle of CAS
Unsafe class source code interpretation and usage scenarios
Design principle of queue synchronizer (AQS)
Queue synchronizer (AQS) source code analysis

The problem

Introduction to the

Fair lock

Acquiring a lock

Release the lock

Not fair lock

Acquiring a lock

Release the lock

conclusion

Related to recommend

Related Posts

LoadRunner- Summary (III)

Bit operation and SQL implementation

Gracefully add comments when using JPA for automatic table building