Analysis of ReentrantLock lock and unlock

Analysis of the principle of ReentrantLock

Speaking of ReentrantLock, we all know that it is a reentrant mutex based on AQS (AbstractQueuedSynchronizer).

If we want to analyze ReentrantLock, we have to start with AbstractQueuedSynchronizer.

Analysis of AbstractQueuedSynchronizer

AbstractQueuedSynchronizer has an internal class Node, and the underlying layer maintains a doubly linked list to form a queue. That is our AQS queue. When we fail to acquire the lock, the thread will be put into this queue and wake up when waiting for other threads to release the lock.

The entire locking process of ReentrantLock revolves around the state attribute. When the state field is greater than 0, it means that the current resource is locked, and the value of the state represents the number of reentries of the thread currently holding the lock. When the state is 0, the threads in the queue can compete for it through a series of CAS operations this lock.

public abstract class AbstractQueuedSynchronizer
    extends AbstractOwnableSynchronizer
    implements java.io.Serializable {<!-- -->
    
    static final class Node {<!-- -->
// wait state
        volatile int waitStatus;

// previous node
        volatile Node prev;

        // next node
        volatile Node next;

        //current node thread
        volatile Thread thread;
        
        //head pointer
        private transient volatile Node head;

       // tail pointer
        private transient volatile Node tail;

        //reentry times
        private volatile int state;

        }
   }

Sync

Sync is the abstract internal class of ReentrantLock, which inherits AQS. The main function of ReentrantLock depends on this internal class Sync. He defines a generic template for acquiring and releasing locks. And defines the unfair acquisition lock method.

abstract static class Sync extends AbstractQueuedSynchronizer {<!-- -->
    private static final long serialVersionUID = -5179523762034025860L;
    
    //Unfair lock acquisition method
    final boolean nonfairTryAcquire(int acquires) {<!-- -->
            final Thread current = Thread. currentThread();
            int c = getState();
            if (c == 0) {<!-- -->
                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;
        }
}

Sync has two sons, NoFairSync (unfair lock) and FairSync (fair lock). The main function of ReentrantLock is realized through these two implementation classes.

NoFairSync (unfair lock)

Acquiring lock process

  1. Try to use CAS to lock
    final void lock() {<!-- -->
        //Try to use CAS to lock
        if (compareAndSetState(0, 1))
            //The lock is successful, and the current resource lock thread is set as the current thread
            setExclusiveOwnerThread(Thread. currentThread());
        else
        //Failed to lock, follow the lock process defined by the parent class Sync
            acquire(1);
    }
    
  2. If the CAS lock fails, follow the lock process defined by Sync
    public final void acquire(int arg) {<!-- -->
    // try to lock
        if (!tryAcquire(arg) & amp; & amp;
        //Failed to lock, put the current thread at the end of the AQS queue
        //And judge whether the current thread is ranked first in the AQS queue, if so, try to acquire the lock again, if not, find the previous available thread, and suspend the current thread
            acquireQueued(addWaiter(Node. EXCLUSIVE), arg))
            selfInterrupt();
    }
    
  3. tryAcquire is unfairly locked, using the nonfairTryAcquire() method defined by the parent class Sync
    protected final boolean tryAcquire(int acquires) {<!-- -->
    //nonfairTryAcquire() defined by the parent class Sync
        return nonfairTryAcquire(acquires);
    }
    
    protected final boolean nonfairTryAcquire(int acquires) {<!-- -->
        // get the current thread
            final Thread current = Thread. currentThread();
            // get state value
            int c = getState();
            //If the state is 0, it means it can be locked
            if (c == 0) {<!-- -->
            //Use CAS to set state from 0 to 1
                if (compareAndSetState(0, acquires)) {<!-- -->
                    //If the CAS lock is successful, set the thread holding the lock resource as the current thread
                    setExclusiveOwnerThread(current);
                    //return lock successfully
                    return true;
                }
            }
            //If the lock fails, determine whether the thread holding the lock resource is the current thread
            //If yes, start the lock reentry operation
            //If not, give up reentrancy
            else if (current == getExclusiveOwnerThread()) {<!-- -->
                //state + 1
                int nextc = c + acquires;
                // Exceeded the reentry limit, throwing an exception
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                //set state = state + 1
                setState(nextc);
                //return lock successfully
                return true;
            }
            //Otherwise, return lock failure
            return false;
        }
    
  4. addWaiter(Node.EXCLUSIVE) If the lock acquisition fails, add the current thread to the end of the AQS queue
    //If the lock fails, add the current thread to the end of the AQS queue
        private Node addWaiter(Node mode) {<!-- -->
        Node node = new Node(Thread. currentThread(), mode);
        //Get AQS tail node
        Node pred = tail;
        if (pred != null) {<!-- -->
            // Point the previous node of the current thread to the original tail
            node.prev = pred;
            //Use the CAS method to point the pointer of the original tail node to the new thread just now
            if (compareAndSetTail(pred, node)) {<!-- -->
                pred.next = node;
                return node;
            }
        }
        //If using CAS to set the current thread to the end of AQS fails, execute this method
        enq(node);
        return node;
    }
    
    //Use an infinite loop until the current thread is successfully set to the end of the queue before jumping out of the loop
    private Node enq(final Node node) {<!-- -->
        for (;;) {<!-- -->
            // Get the tail pointer
            Node t = tail;
            //If the tail pointer is null, it proves that AQS is an empty queue and needs to be initialized
            if (t == null) {<!-- -->
                //Create a node and set it as the head pointer
                if (compareAndSetHead(new Node()))
                    // tail pointer points to head pointer
                    tail = head;
            } else {<!-- -->//If the tail pointer is not null, set the current thread to the end of the queue
                node.prev = t;
                if (compareAndSetTail(t, node)) {<!-- -->
                    t.next = node;
                    return t;
                }
            }
        }
    }
    
  5. acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) Determine whether the current thread is in front of AQS, if so, try to acquire the lock again, if not, find the waiting thread in front of AQS, and suspend itself
    //Judge whether the current thread is the first in the AQS queue
    //If so, re-acquire the lock
    //If not, suspend the current thread
    final boolean acquireQueued(final Node node, int arg) {<!-- -->
        //Acquiring lock failed flag
        boolean failed = true;
        try {<!-- -->
            //interrupt flag
            boolean interrupted = false;
            //Infinite loop: If the thread is the node in front of AQS, you can try to acquire the lock, if not, go from back to front until you find an active thread node, and then hang yourself
            for (;;) {<!-- -->
                // Get the previous node of the current thread
                final Node p = node. predecessor();
                //If the previous node of the current thread is head, it proves that the current thread is at the head of AQS, and try to acquire the lock again
                if (p == head & amp; & amp; tryAcquire(arg)) {<!-- -->
                    //Obtain the lock successfully, the next step...
                    //Set the current thread as the head node
                    setHead(node);
                    //Release the object for garbage collection
                    p.next = null; // help GC
                    //Get the lock successfully
                    failed = false;
                    return interrupted;
                }
                //Failed to acquire the lock, determine whether it should be suspended
                if (shouldParkAfterFailedAcquire(p, node) & amp; & amp;
    // suspend the thread
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {<!-- -->
            if (failed)
                cancelAcquire(node);
        }
    }
    
    / / Determine whether the current thread should be suspended
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {<!-- -->
        //Get the status of the previous node of the current thread
            int ws = pred.waitStatus;
        //If the previous thread is also in the waiting state, return true and the current thread can be suspended
            if (ws == Node. SIGNAL)
                return true;
        //If the previous thread is in the cancel state, then it has been traversing forward for a long time until the thread with the state less than 0 is obtained
            if (ws > 0) {<!-- -->
                do {<!-- -->
                    node.prev = pred = pred.prev;
                } while (pred.waitStatus > 0);
                pred.next = node;
            } else {<!-- -->
                //Set the status of the found thread to wait (-1)
                compareAndSetWaitStatus(pred, ws, Node. SIGNAL);
            }
            return false;
        }
    \t
    //Call the park() method to suspend the thread
        private final boolean parkAndCheckInterrupt() {<!-- -->
            LockSupport. park(this);
            return Thread. interrupted();
        }
    

FairSync (fair lock)

The difference between fair lock and unfair lock:

  1. The unfair lock will use CAS to try to acquire the lock as soon as it enters the lock method, and the acquire() method will be called only when the lock fails to be acquired, while the fair lock directly calls the acquire() method

    //Unfair lock
    final void lock() {<!-- -->
        //Use CAS once by default
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread. currentThread());
        else
            acquire(1);
    }
    
    // fair lock
    final void lock() {<!-- -->
        / / Directly call the common method of acquiring the lock
            acquire(1);
    }
    
  2. Unfair lock does not judge whether there is queuing phenomenon in the AQS queue in the acquire() method of acquiring the lock. Regardless of whether the current thread exists in the AQS queue, it can compete for the lock. The fair lock will first call the hasQueuedPredecessors() method to check whether there is queuing in the queue. If there is queuing, the current thread will be stored at the end of the AQS queue, and then try to acquire the lock

    //Unfair lock
    final boolean nonfairTryAcquire(int acquires) {<!-- -->
                final Thread current = Thread. currentThread();
                int c = getState();
                if (c == 0) {<!-- -->
                   //The acquisition lock method does not judge whether there is a queuing phenomenon in the AQS queue, no matter whether the current thread exists in the AQS queue, it can compete for the lock
                    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;
            }
    
    // fair lock
    protected final boolean tryAcquire(int acquires) {<!-- -->
                final Thread current = Thread. currentThread();
                int c = getState();
                if (c == 0) {<!-- -->
                //First call the hasQueuedPredecessors() method to check whether there is a queue in the queue
                    if (!hasQueuedPredecessors() & amp; & amp;
                        compareAndSetState(0, acquires)) {<!-- -->
                        setExclusiveOwnerThread(current);
                        return true;
                    }
                }
                else if (current == getExclusiveOwnerThread()) {<!-- -->
                    int nextc = c + acquires;
                    if (nextc < 0)
                        throw new Error("Maximum lock count exceeded");
                    setState(nextc);
                    return true;
                }
                return false;
            }
        }
    

Unlock process unlock()

Both fair lock and unfair lock unlocking use the same code, and both use the release() method of AQS to unlock.

public void unlock() {<!-- -->
    sync. release(1);
}

release() process

public final boolean release(int arg) {<!-- -->
    //try to unlock
    if (tryRelease(arg)) {<!-- -->
        Node h = head;
        //Unlocking is successful, if the state of the head node !=0, it means that AQS still has queuing threads, and the subsequent threads need to be woken up
        if (h != null & amp; & amp; h.waitStatus != 0)
            //Find the thread closest to the head node from back to front to wake up and prepare to grab the lock
            unparkSuccessor(h);
        return true;
    }
    return false;
}
  1. Release the lock tryRelease()

    //Try to release the lock
    protected final boolean tryRelease(int releases) {<!-- -->
        //state-1
        int c = getState() - releases;
        //If the current thread != holds the lock thread, an exception is thrown
        if (Thread. currentThread() != getExclusiveOwnerThread())
            throw new IllegalMonitorStateException();
        //Release resources successful mark falg
        boolean free = false;
        //c == 0 means state == 0 means releasing resources successfully
        if (c == 0) {<!-- -->
            free = true;
            //The thread holding the lock is set to null
            setExclusiveOwnerThread(null);
        }
        //state = state - 1 wait for next reentry -1
        setState(c);
        return free;
    }
    
  2. The lock is successfully released and wakes up other waiting threads in AQS

    private void unparkSuccessor(Node node) {<!-- -->
        // Get the state of the head node
        int ws = node.waitStatus;
        //If the head node state > 0 then set the state of the head node to 0
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);
    //Get the next node of the head node
        Node s = node. next;
        //Find the thread closest to the head node to wake up
        //If the state of the next node > 0, it means that the next thread has given up acquiring the lock
        if (s == null || s.waitStatus > 0) {<!-- -->
            s = null;
            //Search from the back to the front of the AQS to find the thread closest to the head node
            for (Node t = tail; t != null & amp; & amp; t != node; t = t.prev)
                if (t. waitStatus <= 0)
                    s = t;
        }
        // perform wakeup operation
        if (s != null)
            LockSupport. unpark(s. thread);
    }