Don't go! Here is a note: picture and text to explain AQS, let's have a look at the source code of AQS (long text)

Preface

AbstractQueuedSynchronizer Abstract queue synchronizer , abbreviation AQS . Is in JUC A very important basic component of the package ,JUC The concurrent lock under the package ReentrantLock CountDownLatch And so on AQS Realized . So I want to further study the underlying principle of locking , It's very necessary to know AQS Principle .

official account ：liuzhihangs, Record the skills in work study 、 Development and source notes ; From time to time to share some of the life experience . You are welcome to guide ！

Introduce

Let's take a look at AQS Class diagram structure of , And source code annotations , There is a certain general understanding, and then start from the source code , Step by step, study its underlying principles .

" Source code comments

Provides implementation of blocking locks and associated synchronizers relying on first in first out （FIFO） Waiting in line （ Semaphore , Events, etc. ） Framework . This class is designed for most of the AQS The synchronizer uses atomic variables to represent states （state）. Subclasses must define protected Method to modify this state, And define state The specific meaning of value in an object is acquired or released. Consider these , Other methods in this class can implement all queuing and blocking mechanisms . Subclasses can keep other state fields , But you can only use the method getState 、setState and compareAndSetState Update in atomic form state .

A subclass should be defined as a non-public internal auxiliary class used to implement the synchronization performance of its enclosing class . class AbstractQueuedSynchronizer No synchronization interface is implemented . contrary , It defines some methods , Such as acquireInterruptibly It is possible to call the appropriate implementation of its public methods through specific locks and related synchronizers .

This class supports exclusive mode and shared mode . In exclusive mode , Other threads cannot get success , Sharing mode can （ But not necessarily ） To be successful . This kind of thing is not “ understand ”, In a mechanical sense, these differences are , When sharing mode is successful , The next waiting thread （ If there is ） It must also be determined whether it can access . Threads share the same wait in different modes FIFO queue . Usually , Implementation subclasses support only one of these patterns , But it's possible to use both modes at the same time , for example ReadWriteLock . Shared only patterns do not need to define subclasses of methods that support unused patterns .

This class defines nested classes AbstractQueuedSynchronizer.ConditionObject , Can be used as a Condition Implemented by subclasses , And use isHeldExclusively Method indicates whether the current thread is exclusive ,release()、 getState() acquire() Methods are used to manipulate state Atomic variable .

This class provides a way to check and monitor internal queues , And conditional objects like methods . Use synchronization mechanisms for them as needed .

To use this class as a basis for synchronization , The following methods need to be redefined , If you use , By checking and or modifying getState 、setState or compareAndSetState Method ：

tryAcquire
tryRelease
tryAcquireShared
tryReleaseShared
isHeldExclusively

"

The general impression can be drawn from the above notes ：

1. Internally, it depends on first in, first out （FIFO） Waiting in line .
2. There is state Indicates status information .state Value can only be used getState 、setState and compareAndSetState Methods are updated atomically .
3. Support exclusive mode and shared mode , But what kind of pattern should be supported by subclass implementation .
4. nesting AbstractQueuedSynchronizer.ConditionObject It can be used as Condition Implemented by subclasses .
5. Subclasses need to be redefined tryAcquire、tryRelease、tryAcquireShared、tryReleaseShared、isHeldExclusively Method .

Queue node Node

Node node , Contains the following elements ：

Elements	meaning
prev	Last node
next	Next node
thread	Hold thread
waitStatus	Node status
nextWaiter	The next one is in CONDITION Nodes of state

The combination of waiting queues is as follows ：

Here is the waiting queue node Node attribute ：

static final class Node {
    //  Nodes are sharing tags waiting in mode 
    static final Node SHARED = new Node();
    //  Flag indicating that the node is waiting in exclusive mode 
    static final Node EXCLUSIVE = null;

    //  Indicates that the thread has been canceled 
    static final int CANCELLED =  1;
    //  Indicates that subsequent threads need to wake up 
    static final int SIGNAL    = -1;
    //  Indicates that the thread is waiting for the condition 
    static final int CONDITION = -2;
    //  Indicate next time acquireShared It should be transmitted unconditionally 
    static final int PROPAGATE = -3;
    
    /**
     *  Status field , Use only the following values 
     * SIGNAL -1 ： When the current node is released or cancelled , must  unpark  His subsequent nodes .
     * CANCELLED 1 ： Because of the timeout （timeout） Or interrupt （interrupt）, The node is cancelled . The node will never leave this state . especially , Threads with cancellation nodes will never block again .
     * CONDITION -2 ： The node is currently in the conditional queue .  But it won't be used as a synchronization queue node , Until the transfer , The transition state will be set to  0 .
     * PROPAGATE -3 ：releaseShared  It should be propagated to other nodes . 
     * 0： Are not 
     *  Values are expressed in numbers to simplify the use of , Most of the time you can check symbols （ Is it greater than 0） To simplify use 
     */
    volatile int waitStatus;

    //  Last node 
    volatile Node prev;

    //  Next node 
    volatile Node next;

    //  Nodes hold threads 
    volatile Thread thread;

    //  Link to the next wait condition node , Or special value sharing 
    Node nextWaiter;

    //  Whether the node is in   Sharing status   yes ,  return  true
    final boolean isShared() {
        return nextWaiter == SHARED;
    }

    //  Go back to the previous node ,  When using   The previous node cannot be empty 
    final Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null)
            throw new NullPointerException();
        else
            return p;
    }

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

stay Node Nodes need to focus on waitStatus

1. The default state is 0;
2. waitStatus > 0 (CANCELLED 1) Indicates that the node timed out or interrupted , Need to be removed from the queue ;
3. waitStatus = -1 SIGNAL The status of the previous node of the current thread is SIGNAL, The current thread needs to be blocked （unpark）;
4. waitStatus = -2 CONDITION -2 ： The node is currently in the conditional queue ;
5. waitStatus = -3 PROPAGATE -3 ：releaseShared It should be propagated to other nodes , Use in shared lock mode .

To understand the Node After the structure of , Learn more about AQS structure , And start with the common methods , Gradually understand the specific implementation logic .

AbstractQueuedSynchronizer

public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable {

    //  Waiting for the head of the queue , Delay initialization .  In addition to initialization , It is only by means of setHead modify .  Be careful ： If the head exists , Its waitStatus Promise it won't be  CANCELLED  state 
    private transient volatile Node head;

    //  Wait for the end of the queue , Delay initialization .  Only in modifying the passing method ENQ Add a new node and wait .
    private transient volatile Node tail;

    //  sync  
    private volatile int state;

    //  To obtain state 
    protected final int getState() {
        return state;
    }

    //  Set the status value 
    protected final void setState(int newState) {
        state = newState;
    }

    //  Atoms update state values 
    protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

}

stay AQS The main parameters are ：

Parameters	meaning
head	Wait for the queue header
tail	Wait for the end of the queue
state	sync

We can learn from the notes that , stay AQS There are mainly two operation modes in this system , Namely ： Exclusive mode 、 Sharing mode , The source code is analyzed from two different angles .

operation	meaning
acquire	Get in exclusive mode , Ignore interrupt . By calling at least once tryAcquire , Return on success . otherwise , Thread queuing , It may be repeatedly seized and unsealed , call tryAcquire Until we succeed . This method can be used to implement methods Lock.lock .
release	Release in exclusive mode . By dredging one or more threads , If you realize tryRelease return true. This method can be used to implement methods Lock.unlock .
acquireShared	Get in shared mode , Ignore interrupt . Through at least one first call tryAcquireShared , Return on success . otherwise , Thread queuing , It may be repeatedly seized and unsealed , call tryAcquireShared Until we succeed .
releaseShared	Release in shared mode . By dredging one or more threads , If you realize tryReleaseShared return true.

Both shared mode and exclusive mode are used in this addWaiter Method , Create the queue node for the current thread and pattern .

Exclusive mode

Get exclusive resources acquire

public final void acquire(int arg) {
    // tryAcquire  Try to get  state, If the acquisition fails, it will be added to the queue 
    if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

In exclusive mode, an attempt is made to acquire state, When the acquisition fails acquireQueued(addWaiter(Node.EXCLUSIVE), arg).

1. tryAcquire(arg), Try to get state This is implemented by the subclass itself , Different subclasses have different logic , This will explain when introducing subclass code .
2. obtain state After failure , Will be carried out in acquireQueued(addWaiter(Node.EXCLUSIVE), arg), This code can be split into two pieces ：addWaiter(Node.EXCLUSIVE),acquireQueued(node, arg).
3. addWaiter(Node.EXCLUSIVE) The current newly created node is returned .
4. acquireQueued(node, arg) Thread failed to acquire lock , Use addWaiter(Node.EXCLUSIVE) Put in the waiting line , and acquireQueued(node, arg) Using a loop , Keep trying to get resources for the nodes in the queue , Until success or interruption .

There are three steps to get resources ：

1. Try to get resources
2. Queue entry
3. Outgoing queue

Try to get resources tryAcquire(arg), Implemented by subclasses , Then we will start to analyze separately Queue entry 、 Outgoing queue .

Queue entry ：addWaiter(Node.EXCLUSIVE)

Use addWaiter(Node.EXCLUSIVE) Method inserts the node into the queue , Steps are as follows ：

1. Create a node based on the pattern passed in
2. Determine whether the tail node exists , If it doesn't exist, you need to use enq(node) Method initializes the node , Existence is direct Try Insert the tail .
3. Try Insert the tail with CAS Insert , Prevent concurrency , If the insertion fails , Would call enq(node) Spin until you insert .

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    //  Locate at the end of the queue  node
    Node pred = tail;
    if (pred != null) {
        //  The previous node of the new node   Point to the tail node 
        node.prev = pred;
        //  Use  CAS  Set tail node ,tail  If it is equal to  pred  Then update to  node
        if (compareAndSetTail(pred, node)) {
            //  If the update is successful, it will  pred  The next node of points to  node
            pred.next = node;
            return node;
        }
    }
    //  Tail node not initialized , Failure or competition , The spin 
    enq(node);
    return node;
}

/**
 * tailOffset  That is, member variables  tail  Value 
 *  This is equivalent to ： Compare  tail  The value of and  expect  Is the value of equal ,  If it is equal, it will be updated to  update
 */
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}
private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        //  The tail node is empty   The header node needs to be initialized , At this point, the head and tail nodes are 
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            //  Not empty   Loop assignment 
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

After reading the code and comments, it must be a little fuzzy , Now let's illustrate it step by step .

Because according to Whether the initial tail node is empty There are two cases , Here we use two pictures ：

1. The first is the first time you add a node , here head Will delay initialization ;
2. The second picture shows an existing queue , Insert nodes ;
3. Pay attention to the code ,enq Method returns The last node before ;
4. addWaiter Method The return is The newly created node currently inserted .

After the node is added to the queue , Returns the current node , The next step is to call the method acquireQueued(addWaiter(Node.EXCLUSIVE), arg) Keep getting resources .

Outgoing queue ：acquireQueued(addWaiter(Node.EXCLUSIVE), arg)

The method will try to get resources through the loop , Until success . The code is as follows ：

final boolean acquireQueued(final Node node, int arg) {
    //  Whether or not to get resources 
    boolean failed = true;
    try {
        //  Interrupt state 
        boolean interrupted = false;
        //  Infinite loop 
        for (;;) {
            //  The node before the current node 
            final Node p = node.predecessor();
            //  The previous node is the head node ,  Description the current node is   Head of the node  next  That's the real first data node  （ because  head  It's a virtual node ）
            //  And then try to get resources 
            if (p == head && tryAcquire(arg)) {
                //  After success   Point the head pointer to the current node 
                setHead(node); 
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // p  It's not a head node ,  perhaps   The head node failed to get the resource  （ It is preempted by other nodes under unfair circumstances ） 
            //  Judge  node  Is it going to be blocked ,
            if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

1. Continuously obtain whether the previous node of this node is head, because head It's a virtual node , If the previous node of the current node is head node , Then the current node is The first data node ;
2. The first data node keeps getting resources , To be successful , Will head Point to the current node ;
3. The current node is not a head node , perhaps tryAcquire(arg) Failure （ Failure may be unfair lock ）. At this time, it is necessary to determine the state of the previous node Whether the current node should be blocked （ Whether the state of the previous node is SIGNAL）.

/**
 *  According to the state of the last node , Determine whether the current thread should be blocked 
 * SIGNAL -1 ： When the current node is released or cancelled , must  unpark  His subsequent nodes .
 * CANCELLED 1 ： Because of the timeout （timeout） Or interrupt （interrupt）, The node is cancelled . The node will never leave this state . especially , Threads with cancellation nodes will never block again .
 * CONDITION -2 ： The node is currently in the conditional queue .  But it won't be used as a synchronization queue node , Until the transfer , The transition state will be set to  0 .
 * PROPAGATE -3 ：releaseShared  It should be propagated to other nodes . 
 * 0： Are not 
 *
 */
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    //  The waiting state of the previous node 
    int ws = pred.waitStatus;
    //  The previous node needs  unpark  Subsequent nodes 
    if (ws == Node.SIGNAL)
        return true;
    //  The current node is in cancel state 
    if (ws > 0) {
        do {
            //  Remove the canceled node from the queue 
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        //  Set the previous node to  SIGNAL  state 
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

stay shouldParkAfterFailedAcquire In the method , Will judge the state of the previous node , At the same time, cancel the invalid nodes in front of the current node in the queue .

Keep reading Outgoing queue acquireQueued Method , Found a finally Will judge the state and execute cancelAcquire(node); , That is, the red square below the flow chart above .

cancelAcquire(Node node)

final boolean acquireQueued(final Node node, int arg) {
    //  Whether or not to get resources 
    boolean failed = true;
    try {
        //  Omit 
        //  stay  finally  The current node will be set to cancel state 
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}


private void cancelAcquire(Node node) {
    //  Node does not exist   Go straight back to 
    if (node == null)
        return;

    //  Disassociate node from thread 
    node.thread = null;

    // Skip nodes that have been canceled , Get the valid node before the current node 
    Node pred = node.prev;
    while (pred.waitStatus > 0)
        node.prev = pred = pred.prev;

    //  Get the next node of the valid node before the current node 
    Node predNext = pred.next;

    //  The current node is set to cancel 
    node.waitStatus = Node.CANCELLED;

    //  If the current node is the tail node , The last node is set to be valid , And will  predNext  Set to null 
    if (node == tail && compareAndSetTail(node, pred)) {
        compareAndSetNext(pred, predNext, null);
    } else {
        int ws;
        // pred  It's not a head node (node  Last valid node of   No  head) && （ pred The state of is  SIGNAL ||  pred  Is set to  SIGNAL  success  ） && pred  Binding thread of is not empty 
        if (pred != head && 
        ((ws = pred.waitStatus) == Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && 
        pred.thread != null) {
            //  The successor node of the current node 
            Node next = node.next;
            //  The subsequent node is not empty   And   The state is valid   take  pred  Of   The successor node is set to   The successor node of the current node 
            if (next != null && next.waitStatus <= 0)
                compareAndSetNext(pred, predNext, next);
        } else {
            // node  Last valid node of   yes  head,  Or something else   Wake up the next valid node of the current node 
            unparkSuccessor(node);
        }

        node.next = node; // help GC
    }
}

private void unparkSuccessor(Node node) {

    //  Determine the current node status 
    int ws = node.waitStatus;
    if (ws < 0)
        //  Update the node status to  0 
        compareAndSetWaitStatus(node, ws, 0);

    //  Next node ,  Generally, the next node should be the node that needs to wake up , That is to issue a certificate .
    Node s = node.next;
    //  Greater than  0  CANCELLED ：  Thread canceled 
    //  But it's possible   The subsequent nodes   Empty or cancelled .
    if (s == null || s.waitStatus > 0) {
        s = null;
        //  Start traversing from the tail node , Until it reaches  t.waitStatus <= 0  The node of 
        //  It doesn't stop when you locate it , Will continue to execute , It's equivalent to finding the first node that needs to wake up 
        // t.waitStatus <= 0 ： SIGNAL（ -1  Subsequent threads need to release ） 
        //                     CONDITION （ -2  Thread is waiting for condition ） 
        //                     PROPAGATE （ -3 releaseShared  It should be propagated to other nodes ）
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    //  Locate the node that needs to wake up   Conduct  unpark
    if (s != null)
        LockSupport.unpark(s.thread);
}

Process analysis ：

1. Invalid node found for current node pred;
2. If the current node is the tail node , The last node is set to be valid , And will predNext Set to null ;
3. pred It's not a head node && （ pred The state of is SIGNAL || pred Is set to SIGNAL success ） && pred Binding thread of is not empty ;
4. Other situations .

Here are the pictures ：

Q: You can see from the picture that , It's just the operation next The pointer , But there was no operation prev The pointer , Why is that ？

A: stay Outgoing queue ：acquireQueued(addWaiter(Node.EXCLUSIVE), arg) In the method ,shouldParkAfterFailedAcquire Method will determine the state of the previous node , At the same time, cancel the invalid nodes in front of the current node in the queue . The previous invalid node will be removed , This is also to prevent pointing to a node that has been removed . At the same time guarantee prev The stability of the , It is beneficial to learn from tail Start traversing the list , This one is in unparkSuccessor(node); You can also see the list from back to front .

Q: unparkSuccessor(Node node) Why traverse back and forth ？

A:

stay addWaiter(Node.EXCLUSIVE) When inserting a new node , It uses The tail interpolation , Look at the red box part , It may not have pointed to next.

Q: node.next = node; This leads to head It's not pointing to the latest node , The list is broken ？
A： acquireQueued Method introduction , There's a cycle in it , Will continue to try to acquire resources , After success, it will be set to head. And in shouldParkAfterFailedAcquire Will also clear the invalid nodes in front of the current node .

Free exclusive resources release

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

Release in exclusive mode . By releasing one or more threads , If you realize tryRelease return true. This method can be used to implement methods Lock.unlock .

1. tryRelease(arg) Operations release resources , It is also implemented by subclasses , The subclass will be explained later . return true The resource is no longer held by thread , Other nodes can try to get ;
2. Release successful , And head != null && h.waitStatus != 0, Will continue to execute unparkSuccessor(h);
3. This one will see as long as tryRelease(arg) The operation released resources successfully , Whether the execution is successful or not , Will return to true,unparkSuccessor(h) It's equivalent to just additional operations .

Sharing mode

Get shared resources acquireShared

public final void acquireShared(int arg) {
    //  Less than  0  Indicates that the resource acquisition failed 
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

private void doAcquireShared(int arg) {
    //  Add to node   Here is the shared node 
    final Node node = addWaiter(Node.SHARED);
    //  Depending on whether you get the resources   Decide if you need to cancel 
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            //  Go back to the previous node 
            final Node p = node.predecessor();
            if (p == head) {
                //  Try to get shared resources again 
                int r = tryAcquireShared(arg);
                //  Show success 
                if (r >= 0) {
                    //  Set the current node as the head node   And try to wake up the following nodes 
                    setHeadAndPropagate(node, r);
                    //  Release the head node  GC  Will recycle 
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

1. tryAcquireShared(arg), Try to get resources , This is implemented by subclasses ;

2. The return value is divided into 3 Kind of ：

   1. Less than 0: It means failure ;
   2. be equal to 0: Indicates that the shared mode has successfully obtained resources , However, subsequent nodes cannot succeed in shared mode ;
   3. Greater than 0: Indicates that the shared mode has successfully obtained resources , Subsequent nodes may also succeed in sharing mode , under these circumstances , Subsequent waiting threads must check availability .
3. After failure, you will use doAcquireShared(arg); Keep getting resources ;
4. final Node node = addWaiter(Node.SHARED); Nodes are also created ;
5. In the loop, judge the previous node continuously if it is head, Then try to get resources ;
6. In the shared mode, you will use setHeadAndPropagate(node, r); Set the head node , At the same time, wake up the subsequent nodes .

Set the head node , And propagate to wake up subsequent nodes

// node  Is the current node 
// propagate  yes   The first step  tryAcquireShared  The return value of   When you come in  >=0
//  Greater than  0:  Indicates that the shared mode has successfully obtained resources , Subsequent nodes may also succeed in sharing mode , under these circumstances , Subsequent waiting threads must check availability .
private void setHeadAndPropagate(Node node, int propagate) {
    //  Record the current head node 
    Node h = head; // Record old head for check below
    //  Set incoming  node  Is the head node 
    setHead(node);
    //  Judge the condition , Wake up subsequent nodes 
    // propagate > 0  There are follow-up resources 
    // h == null  The old head node   Because the front  addWaiter,  It won't be empty , It should be to prevent  h.waitStatus < 0  How to write a null pointer 
    // (h = head) == null  Current   Head node , Judge the state again 
    // waitStatus < 0  Subsequent nodes need to be awakened 
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        //  The subsequent nodes are shared , You need to wake up 
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

doReleaseShared() Free up shared resources

private void doReleaseShared() {
    //  loop 
    for (;;) {
        //  Start from scratch 
        Node h = head;
        //  Determines if the queue is empty , It's just initialized 
        if (h != null && h != tail) {
            int ws = h.waitStatus;
            // SIGNAL（ -1  Subsequent threads need to release ）
            if (ws == Node.SIGNAL) {
                //  Update the wait status to  0  If you fail , Cycle 
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            // loop to recheck cases
                //  Wake up subsequent nodes ,  At the same time, set the current node to   Cancel 
                unparkSuccessor(h);
            }
            //  If the state is  0  The status will be updated to  PROPAGATE
            // PROPAGATE （ -3 releaseShared  It should be propagated to other nodes ）
            else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;                // loop on failed CAS
        }
        //  Determine whether the head node has changed , There are changes   It's because of competition , Another thread got the lock , It will continue to loop 
        //  There's no change. It's over 
        if (h == head)                   // loop if head changed
            break;
    }
}

1. Start from the beginning , If h != null && h != tail Indicates that the queue is not empty or has just been initialized ;
2. The node status is SIGNAL（ -1 ） Indicates that subsequent threads need to release ;
3. Changes the current node state , Wake up subsequent nodes after success , Failure continues to cycle ;
4. If the node state is 0 Then update to PROPAGATE, Will propagate the State .

Free up shared resources releaseShared

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        //  Free up shared resources 
        doReleaseShared();
        return true;
    }
    return false;
}

Release in shared mode . By releasing one or more threads , If you realize tryReleaseShared return true.

summary

Q: AQS What is it ？
A: AQS Internal provides a first in, first out （FIFO） Two way waiting queue , Internal dependence Node Realization , And provided in Exclusive mode and Sharing mode The public way to get in and out of the queue under . And about status information state Is implemented by subclasses .tryAcquire、tryRelease、tryAcquireShared、tryReleaseShared The operation of getting resources is defined and implemented by subclasses . and AQS Provides the related operations after the subclass gets the resources , Including nodes Node In and out of the queue , Spin, get resources, etc .

Q: AQS How to operate after failure to obtain resources ？
A: After the thread fails to get resources , It's going to be in the waiting queue , In the queue, there will be constant attempts to get resources （ The spin ）, Indicates that the thread just enters the waiting state , You can still get resources again later .

Q: AQS What is the data structure of the waiting queue ？
A: CLH First in, first out of variants （FIFO） Two way waiting queue .（CLH Lock is a spin lock . To ensure that there is no hunger . Fairness in providing first come, first served . It is a kind of extensible based on linked list 、 High performance 、 Fair spin lock , The application thread spins only on local variables , It constantly polls the status of its predecessors , If you find that the precursor releases the lock, the spin ends .）

Q: AQS How the nodes in the waiting queue get and release resources ？
A: May have a look Exclusive mode The narrative process in , Sort through the code .

This paper starts from Exclusive mode and Sharing mode To introduce the AQS Basic logic , And through the source code and drawing to understand the basic ideas . But there is no introduction to the business logic that needs to be implemented by subclasses . This will be introduced later ReentrantLock、CountDownLatch And so on .