AQS is J.U.C bag under a framework that is used to realize all kinds of locks and other sync framework, such as already, Semophare, CyclicBarrier, CountDownLatch, etc.

AQS data structure (unordered list garbled, normal in editor)

  • CLH queue

  • AQS is through a CLH queue to achieve thread blocking, wake up.

  • The queue is a bidirectional linked list, with each node representing a thread and each node having two Pointers, prev and Next.

  • The node also has a waitStatus int that represents the current state of the thread. contains

  • cancelled

  • signal

  • condition

  • propagate

  • If acquire fails, a new thread is wrapped as a Node and placed at the end of the linked list.

  • If the previous thread releases successfully, it wakes up the next thread, the next node of the head. Head itself is a virtual node.

  • state

  • State property, int, Volitile modifier. Used to represent resources

  • For example,

  • ReentrantLock

  • 0 means the lock is not held by any thread

  • A value greater than 0 indicates that the lock is held by a thread, and the number of times the lock is held

  • CountDownLatch

  • The countDown method subtracts state by one

  • Await blocks until state is reduced to 0

ReentrantLock

Below we combine ReentrantLock to specific analysis of AQS related source code

Lock execution process

1. The lock method actually calls acquire method, acquire code is as follows:

public final void acquire(int arg) { if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code

First tryAcquire once. If it succeeds, the lock is successfully acquired. If this fails, it is wrapped as a Node tail and inserted at the end of the CLH queue, and the Node is acquireQueued (the acquireQueued method is described below).

2. The tryAcquire method is the logic we need to implement:

Take unfair locks as an example:

        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;
        }
Copy the code

First, we determine whether the current lock is held, if not, through CAS set to hold state, and set this thread to hold thread, return true, indicating that the lock is successful; If the current lock is already held by the current thread, state is added, representing reentrant +1, and true is returned, indicating that the lock succeeded. Otherwise, the current lock is held by another thread. If false is returned, the lock failed.

3.acquireQueued

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

Within the for loop, the current thread (the thread of Node) is eligible to proceed with tryAcquire logic if the node’s precursor is a head node, i.e. node is the first non-virtual node (head is a virtual node). If acquire succeeds, the node will be set as head, and the thread and prev of the node will be set to null, making it also a virtual node, keeping the head virtual node characteristics.

If the node precursor is not a head, the current thread (that is, the node thread) will be suspended if the condition is met.

At this point, the whole Lock (acquire) process ends.

In simple terms, first try once and return if successful; If the node fails, it is placed at the end of the queue and continues to try, but only if the current node is the first non-virtual node is it really eligible to run tryAcquire. This place will hang up to avoid idling. When the holding thread is released, subsequent nodes are awakened (as described in the release logic below).

Execution logic of UNLOCK

1.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; } protected final boolean tryRelease(int releases) { int c = getState() - releases; if (Thread.currentThread() ! = getExclusiveOwnerThread()) throw new IllegalMonitorStateException(); boolean free = false; if (c == 0) { free = true; setExclusiveOwnerThread(null); } setState(c); return free; }Copy the code

Since ReentrantLock is reentrant, tryRelease will return false if it only reduces the number of reentrants and does not actually release the resource. True will only be returned if the resource is fully freed, i.e. state goes to 0.

In the release method, the threads of the unparksucceeded (head) of the head are awakened only when tryRelease returns true, that is, when the current thread (the one that called unlock, the one that got the lock) actually frees the resources. The awakened thread executes the acquireQueued logic analyzed earlier, attempting to acquire the resource (if it is the first non-virtual node).

From this and the tryAcquire method in acquireQueued, CLH queue-managed threads acquire resources on a first-come-first-served basis, which is fair.