cool hit counter AbstractQueuedSynchronizer super detailed principle analysis_Intefrankly

AbstractQueuedSynchronizer super detailed principle analysis


Today we will study and learnAbstractQueuedSynchronizerkind of Related Principles,java.util.concurrent Many classes in the package rely on this class to provide queue-based synchronizers, such as the commonly usedReentranLockSemaphore harmonyCountDownLatch etc.

To make it easier to understand, we take a paragraph that usesReentranLock of Code as an example, explainReentranLockThe method of each method regardingAQS The use of.

ReentranLock example

We all know that.ReentranLock of Locking behavior harmonySynchronized resemble, All are re-entry-ready of lock up, But both of The implementation is indeed completely different of, We will also explain laterSynchronized The principle of. beyond,Synchronized of Blocking cannot be interrupted, but (not)ReentrantLock provides interruptible of blockage . The following code isReentranLock functions, and we'll explain the principles behind their implementation in this order.

ReentrantLock lock = new ReentrantLock();
lock.lock();
lock.unlock();

Fair and non-fair locks

ReentranLock There are fair and non-fair locks, and the difference between the two is whether access to the lock is related to the queuing order. We all know that if a lock is held by another thread, then the other thread that applied for the lock will be hung up waiting and added to the waiting queue. Theoretically, the first call tolock The function is hung up waiting for of Threads should be in the waiting queue of front end, post-call of Right at the back of the line.。 in case this time, The lock is released., Need to notify waiting threads to try to get a lock again, A fair lock will allow the first to enter the queue of Threads get locks。 Whereas a non-fair lock wakes up all threads, Let them try to get the lock again, So it may lead to later of The thread gets the lock first, then it is non-equitable。

public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

We will findFairSync harmonyNonfairSync Both inheritedSync class, whileSync of The parent class isAbstractQueuedSynchronizer (subsequently referred to asAQS ). neverthelessAQS of The constructor is empty of, There is no operation。

later of Source Code Analysis, in case Not specifically stated, It means fair lock.。

lock operation

ReentranLock oflock The function is shown below, directly Calledsync oflock function. that is CalledFairSync oflock function.

    //ReentranLock
    public void lock() {
        sync.lock();
    }
    //FairSync
    final void lock() {
         // Called AQS's acquire function, which is one of the key functions
        acquire(1);
    }

We'll get down to business.AQS (statistics) correlation of The source code was analyzed,acquire function of The effect is to get only one thread in the same time period of measure word, This quantity is the abstraction of lock concept。 Let's analyze the code first, You'll slowly understand it. of connotation。

public final void acquire(int arg) {
	// tryAcquire First try to get" lock up", Acquired without going into the follow-up process
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
         //addWaiter is to create a node for the current thread and add it to the wait queue
         //acquireQueued is to continue trying to acquire a lock after the thread has already joined the waiting queue.
        selfInterrupt();
}

tryAcquireaddWaiter harmonyacquireQueued All are very important functions, so let's learn them in turn and understand what they do.

 Variables in the //AQS class.
private volatile int state;
 //This is the implementation of FairSync, not implemented in AQS, subclasses implement this function according to their needs
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
     // Get the state variable in AQS, representing the lock of the abstract concept.
    int c = getState();
     if (c == 0) { //value is 0, then the current exclusive variable is not yet occupied by a thread
         // If there is no first thread waiting on the current blocking queue, the UnfairSync implementation here is inconsistent
        if (!hasQueuedPredecessors() && 
            compareAndSetState(0, acquires)) {
             //successful cas, then the current thread gets ownership of the variable, i.e., successful locking
            setExclusiveOwnerThread(current);
             // setExclusiveOwnerThread sets this thread to be the exclusive variable owner thread
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
         // If the thread has taken ownership of the exclusive variable, then according to reentrancy
         //principle, add 1 to the state value, indicating multiple locks
         // Since the lock has been acquired, the code will only be executed by one thread at a time, so there is no need to
         // Perform any parallel processing
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
     // None of the above, indicating a lock acquisition failure
    return false;
}

From the above code we can see thattryAcquire It's trying to get that thread-exclusive variablestate . The value of state indicates its status: if it is 0, then no thread is currently exclusive to this variable; if not, then there is already a thread exclusive to this variable, which means that a thread has already acquired the lock. But this time make another determination to see if the current thread acquired this lock itself, and if so, increase the value of state.

ReentranLock gets the lock

There are a few points to note here, the first beingcompareAndSetState function. This is the use ofCAS Operation to setstatevalue, and the state value is set tovolatile modifier, By doing these two things to ensure that the modificationsstate of Values do not present multi-threading problems。 And then there's Fair and non-fair locks of Differentiation issues, (located) atUnfairSync ofnonfairTryAcquire function does not have the same of Position call onhasQueuedPredecessors to determine if there are already threads currently queued up to get a lock.

in casetryAcquire return totrue , then the lock was acquired successfully; if false is returned, then the lock was not acquired and needs to be added to the blocking wait queue. We'll look at it belowaddWaiter of Related Operations。

Blocking queue for waiting locks

The current thread information will be saved of Node added to waiting queue of The related functions involve lock-free queues of Related Algorithms, Since theAQS in just adds the node to the end of the queue, use to of The lock-free algorithm is also relatively simple。 truly of lock-free queue of The algorithm we wait until the analysisConcurrentSkippedListMap When the lecture is being given.

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Let's try it first using the quick entry method, in case failures, The more complete of Enrollment algorithm.
    // Only if necessary of Only in the case of more complex and time-consuming of algorithm, That is, optimism. of attitudinal
     Node pred = tail;  //Column tail pointer
    if (pred != null) {
        node.prev = pred; // steps1: this node of The forward pointer points totail
         if (compareAndSetTail(pred, node){ //step 2:cas points the tail pointer to the node
            pred.next = node;// step Three: in case results, Let the old column tail node ofnext Pointer to this node.
            return node;
        }
    }
     //cas fails, or enq is called when pred == null
    enq(node);
    return node;
}
private Node enq(final Node node) {
    for (;;) { //cas lock-free algorithm of standardizedfor cycle, non-stop of attempt
        Node t = tail;
         if (t == null) { //initialize
            if (compareAndSetHead(new Node())) 
              // Needs attention of behead It's a sentry. of role, It doesn't mean that someone is going to get a lock of thread node
                tail = head;
        } else {
            // harmonyaddWaiter consistent, But with the outside of infinite loop, non-stop of attempt, spin lock
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

By callingaddWaiter function.AQS Having added the current thread to the waiting queue, but not yet blocking the execution of the current thread, let's next analyzeacquireQueued function.

Waiting for a queue node to operate

Since operations that enter a blocking state reduce the efficiency of execution, theAQS Every effort is made to avoid threads trying to acquire exclusive variables from entering a blocking state. So, after the thread is added to the waiting queue, theacquireQueued A for loop will be executed, each time determining whether the current node should get this variable (at the head of the queue now). If it should not be fetched or fails on another attempt to fetch, then callshouldParkAfterFailedAcquire Determining whether you should enter a blocking state。 in case Before the current node of The node has gone into a blocking state, Then it can be decided that it is impossible for the current node to acquire the lock, To preventCPU non-stop of executefor cycle, consumeCPU sources, invokeparkAndCheckInterrupt function to enter the blocking state.

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) { // Always perform, Until the lock is acquired, return to.
            final Node p = node.predecessor(); 
            //node of The precursors arehead, would indicate that,node is going to get the lock of Next Node.
            if (p == head && tryAcquire(arg)) { // So try again to get the exclusive variable
                 setHead(node);  // If the result, then set yourself as head
                p.next = null; // help GC
                failed = false;
                return interrupted;
                // this time, It's not in the blocking state yet., So directly return tofalse, Indicates that no interrupt call is requiredselfInterrupt function
            }
             // Determine if you want to enter the blocking state. If `shouldParkAfterFailedAcquire`
            // return totrue, Indicates the need to enter blocking
             // call parkAndCheckInterrupt; otherwise it means it can try to get the lock again and continue with the for loop
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                // invokeparkAndCheckInterrupt carry out blocking, then (afterwards) return to Is the interrupt state
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL) // The previous node is waiting for the exclusive variable to be released of notices, consequently, The current node can block
        return true;
    if (ws > 0) { // The previous node is in a position to cancel the acquisition of exclusive variables of statuses, consequently, You can skip it.
        // return tofalse
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        // Put the previous node of The status is set tosignal, return tofalse,
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}
private final boolean parkAndCheckInterrupt() {
     LockSupport.park(this);  // Pass the AQS object in itself
    return Thread.interrupted();
}

Blocking and disruption

From the above analysis, we know thatAQS By callingLockSupport ofpark method to perform blocking of the current process of operations。 indeed, here of Blocking is when a thread stops executing of connotation, By calling this one function. The thread goes into a blocking state, above-mentioned oflock The operation also blocks, waiting for an interrupt or in case the exclusive variable is released.

public static void park(Object blocker) {
    Thread t = Thread.currentThread();
     setBlocker(t, blocker);// set the blocking object, used to record who is blocking the thread, used for thread monitoring and analysis tools to locate
     UNSAFE.park(false, 0L);// Let the current thread no longer be scheduled by the thread, that is, the current thread is no longer executed.
    setBlocker(t, null);
}

About interruptions of Related Knowledge, We'll talk later., Just keep going alongAQS of masterstroke, Take a look at releasing exclusive variables of Let's do it。

ReentrantLock does not get blocked, join queue

unlock operation

together withlock operate similarly.unlock The operation invokes theAQS ofrelase Methods, parameters and callsacquire When it's the same, it's 1.

public final boolean release(int arg) {
    if (tryRelease(arg)) { 
     //Releasing exclusive variables starts by subtracting the value of status by 1, because it is added by 1 when acquiring
        Node h = head;
        if (h != null && h.waitStatus != 0)
             unparkSuccessor(h);// wake up the successor node of head
        return true;
    }
    return false;
}

From the above code, it is clear that release is the first call totryRelease to release exclusive variables。 in case succeed, Then check to see if there is a waiting lock of Block the thread, in case Yes, Just callunparkSuccessor to wake them up.

protected final boolean tryRelease(int releases) {
     // Since only one thread can get the exclusive first variable, all operations do not need to consider multiple threads
    int c = getState() - releases; 
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
     if (c == 0) { //If it equals 0, then the lock should be released, otherwise it means the current thread has multiple lock operations.
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

We can see thattryRelease middle of Logic also reflects reentrentable locks of conception, Only untilstate of have a value of0 time, That means the lock is really released.。 So the exclusive variablestate The value of represents the presence or absence of a lock. properstate=0 When indicates that the lock is not possessed, no in indicates that the current lock is possessed.

private void unparkSuccessor(Node node) {
    .....
     // generally speaking, Need to wake up of Threads arehead of Next Node, But in case It gets the lock of The operation was canceled, Or at the nodenull time
     // Just continue to traverse back, The first one was found not canceled of The successor node.
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        LockSupport.unpark(s.thread);
}

Calledunpark After the method is performedlock The operation is blocked of The thread reverts to a running state, will be executed againacquireQueued middle of boundlessfor Loop of operations, Try to get the lock again。

ReentrantLock releases the lock and notifies the blocking thread to resume execution

postscript

concernAQS harmonyReentrantLock of The analysis is almost over。 I have to say, I saw it for the first timeAQS of It was a shock, It used to be thoughtSynchronized harmonyReentrantLock of The principle of implementation is the same of, All rely onjava virtual machine of Function Implementation of。 Didn't think there wasAQS Such a big behindBoss I'm trying to help.。 Learned the class of principle, We're right about itJUC of Many classes of Analysis is much simpler。 furthermore,AQS involvedCAS The algorithms for operations and lock-free queues also provide the basis for learning other lock-free algorithms. knowledge of The ocean is infinite of yes!


Recommended>>
1、Atom Editor Configuration
2、How do you learn a new skill
3、How to submit code to github using gitshell
4、Just now Xiaomi and Baidu reach deep partnership AI will become a necessity for IoT
5、Analyzing how programmers can choose the right offer for their career plan

    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号