AQS source code analysis

ReentrantLock Underlying principle

One 、AQS brief introduction

• abstract queue synchronizer AbstractQueuedSynchronizer abbreviation AQS, It is the basic component of synchronizer ,JUC The underlying implementation of various locks depends on AQS

1.1 Member variables

• state Indicates the lock status
  • The value is 0 No one holds the lock （ In a free state ）,int Type defaults to 0
  • Greater than 0 Indicates that a thread holds the lock
  • In case of Lock reentry Then value +1
• head and tail Each represents a point to the queue Head node and Tail node Of The pointer

  • AQS The queue in is First in first out bidirectional linked list

    • Be careful ： The head node in the queue is not the node to acquire the lock , Just space occupying furnishings , The node that really wants to acquire the lock is the second node , The second node becomes the head node after acquiring the lock
• If a thread does not acquire a lock, it needs to enter the queue and wait
  • The thread holding the lock must not be in the queue （ Remember the conclusion first , Analyze the reason in the source code ）

1.2 Node node

• Each in the queue Node The node consists of four parts
  • Front pointer 、 The back pointer 、 Current thread 、 The waiting state of the current thread
• about WaitStatus Enumerated values , Record the of the current thread Wait state ,int Type. The default value is 0
  • CANCELLED （1） Indicates that the thread has been canceled
  • SIGNAL （-1） Indicates that the thread needs to be awakened , In a waiting state
  • CONDITION （-2） Indicates that the thread is waiting in the condition queue
  • PROPAGATE （-3） Indicates that other nodes need to be notified when releasing shared resources

1.3 Inheritance relationships

• AbstractQueuedSynchronizer Inherited from AbstractOwnableSynchronizer

  

• exclusiveOwnerThread At present Lock thread

  

Two 、 Get lock source code analysis

• Before the formal analysis , Need to know ReentrantLock There is a queue in , Threads that can't get the lock will enter the queue

  

• This queue inherits AQS, in other words ReentrantLock Contains AQS queue

  

Official source code analysis ：

1. Get into lock Method

   

2. Continue to enter lock Method

   

3. Select the implementation of fair lock

   

4. Get into acquire Method

   The parameter value is fixed to 1, Indicates an attempt to AQS Properties in state Change it to 1（ Lock ）

   

5. Get into tryAcquire Method

   

6. Select the method of fair lock rewriting

   

   The implementation class must override tryAcquire Method , Otherwise, an exception that does not support the operation will be thrown

   

7. First, get the thread currently trying to lock , Then enter getState Method

   

8. return state Value , This is the case 0（ There is no thread lock yet ）

   

9. getState Method returns 0, Judge that the lock is free , Get into if Code block , perform hasQueuedPredecessors Method

   hasQueuedPredecessors Method is used to determine whether the current thread needs to wait in the queue

   here , Maybe you have doubts , At this point, it has been determined that this thread can be locked , Directly through CAS Just lock it , Why judge whether you need to queue or not ？（ View 2 、1 answer ）

   

10. hasQueuedPredecessors Method returns false, Express You don't need to join the queue and wait

    
    • At this time, the values of all three are null,return The first judgment of returns false, The entire method returns false

11. The source code is returned to section 9 Step , namely tryAcquire Method , Get into setExclusiveOwnerThread Method

    

12. Successfully set the locked thread to the current thread

    

13. Return the source code to section 11 Step ,tryAcquire Method returns true, The source code is returned to 5 Step , namely acquire Method

    

14. The source code continues to return , Until the first step calls lock method , The code continues to run down , Indicates that the locking is successful

Conclusion ：

• A single thread or multiple threads do not compete In alternation ,ReentrantLock stay JDK level You can solve the synchronization problem , It will not involve the call of the underlying interface of the operating system

• Multiple threads do not compete and alternate execution will not use the queue , Just modify state Value

• JDK1.6 Before synchronized Lock 、 The lock release operating system needs to switch to the kernel state , And call the underlying interface in the operating system , The operation is relatively heavyweight ,ReentrantLock Lighter than it

• JDK1.6 Yes synchronized After optimization （ Biased locking 、 Lightweight lock ）, about Single thread 、 Multithreading does not compete Can also be in JDK The layer is locked 、 Unlock operation , The performance of the two is almost the same

summary ：

In the locking process, first judge state Value , If 0, Then judge whether to join the queue , If you don't need to , take state Value is modified to 1, And change the locked thread to the current thread , Locking success

2.1 Why judge whether you need to enter the queue ？

• Why? tryAcquire Method has determined that this thread can be locked , You have to decide whether you need to queue up ？

  
  • If t1 For the lock , here t2 Attempt to lock failed , Will enter the queue , At some point t1 Finished executing the code , Release the lock ,state The value of becomes 0, Right now t3 Attempt to acquire lock , Judge state The value of is 0, If you pass immediately CAS Lock ,t3 It will be better than t2 Get the lock first , Do not meet the characteristics of fairness

• For unfair locks

  • If the current state The value is 0, be Try locking directly , Without judging whether you need to join the queue

    

3、 ... and 、 Lock Competition source code analysis

Lock thread t1 The lock hasn't been released yet , There are other threads t2 To try to lock , There is competition

1. t2 Try to lock , Consistent with the above source code process , To tryACquire Method

   problem ：ReentrantLock How to reflect the of lock reentry ？（ Look at three 、1 answer ）

   

2. Return the source code to the upper layer acquire Method

   perform addWaiter Method , Queue threads that cannot acquire locks

   

3. perform enq Method

   

4. analysis enq Method

   enq Method to create the head and tail nodes of the queue , Set the parameter node as the tail node , And form a two-way linked list with the head node ：

   

   • You need to specify the in the queue at this time head and tail Values are null

   • Node t = tail; Assignment result t by null

   • Get into if Sentence judgment , Create a Thread is null Null node for value , And set it as the head node of the queue （ In the head node of the queue Thread Value is always null）

     

   • tail = head; This indicates that the head node also becomes the tail node

     

   • Back to the source code , Will not enter the else in , Again into the cycle , Judge that at this time t Not empty ,t It's the head node （ Tail node ）, Get into else in

     

   • take contain t2 Thread Node node The previous node of is set as the head node , adopt CAS Action sets the tail node to contain t2 Thread Node node , The next node of the header node is set to contain t2 Thread Node node （ Double linked list ）, Pictured ：

     

   • here contain t2 Thread Node node Team success , Become the tail node

5. Return the source code to the next level addWaiter, Returns the... That becomes the tail node at this time contain t2 Thread Node node

   

6. Return the source code to the next level acquire Method , perform acquireQueued Method , Parameter is contain t2 Thread Node node ( Tail node ) and 1

   

7. here t2 Thread has been queued , But he has to spin to judge whether he can get the lock , Because it's possible t1 In the process of joining the team, he released the lock ,t2 There is no need to block ; If the spin still doesn't get the lock , So you're going to have to t2 Blocking （ Joining the team is not blocking ）

   Be careful ： about t3 threads , The node before it in the queue is t2 node , Out of the principle of fairness , In any case, it won't be t3 Gets the lock , therefore t3 Can't spin , Only the thread corresponding to the second node will spin

8. Yes acquireQueued Method analysis

   The thread corresponding to the second node Spin twice Backward entry blocking state , Wait for the thread to be released to wake up , Become the head node of the queue （ Head of the node Thread To be set to null）, The thread corresponding to the second node successfully obtains the lock . The original first node is out of the queue , By GC Garbage collection ：

   

   • final Node p = node.predecessor(); p Become contain t2 Thread Node node Previous node of , Now it's Thread by null The head node of

   • if (p == head && tryAcquire(arg)) The first condition is satisfied , The second condition is similar to the previous analysis , Try to spin once to get the lock , Suppose the acquisition fails at this time

     • It can be seen that , Only the second node will spin , The third node won't spin

   • Into the second if block , call shouldParkAfterFailedAcquire , The first parameter represents the header node , The second parameter represents the tail node （ contain t2 Thread Node node ）

     private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
             
         
         int ws = pred.waitStatus; // Head of the node status The value is int Type default 0
         
         if (ws == Node.SIGNAL) return true; // Do not enter ,SIGNAL The value is -1
         
         if (ws > 0) {
              // Do not enter 
     
             do {
             
                 node.prev = pred = pred.prev;
             } while (pred.waitStatus > 0);
             pred.next = node;
             
         } else {
              // Get into 
     
             // take node Previous node of （ Head node ） Of status It is amended as follows -1, Indicates a waiting state 
             // Note not to modify t2 Threads node Node status
             compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
         }
         
         return false; // return false
     }
     

   • Return the source code to the next level , Keep going into the cycle

     

   • On the second cycle , hypothesis if In block , Another spin attempt to get the lock still didn't get the lock , Enter again shouldParkAfterFailedAcquire Method

     private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
             
         
         int ws = pred.waitStatus; // Head of the node status The value is -1
         
         if (ws == Node.SIGNAL) return true; // Get into , return true
         
         // Omit the rest .....
     }
     

   • At this point, there is a small problem , Why did you enter... For the first time shouldParkAfterFailedAcquire When the method is used , Not directly ws==0 Just go back to true, You have to assign more values （ It is amended as follows -1） Well ？（ Look at three 、2 answer ）

   • Get into parkAndCheckInterrupt Method

     

   • parkAndCheckInterrupt Method , call park Method take t2 Thread blocking

     private final boolean parkAndCheckInterrupt() {
             
         LockSupport.park(this); // Blocking t2 Threads 
         
         // The following code cannot be executed , Until another thread executes unpark Method wake up t2, Will execute down return sentence 
         
         return Thread.interrupted(); 
     }
     

   • Suppose that at this time, the locking thread Lock released , And awakened t2,t2 perform return Thread.interrupted(); return fasle

   • parkAndCheckInterrupt Method returns false, Keep going into the cycle

     

   • Go to the first if sentence , Attempt to acquire lock succeeded , Get into setHead Method

9. setHead Methods to analyze

   

   • Take the second node as the head node

   • In the second node Thread Be set to null（t2 Now hold the lock , The thread holding the lock must not be in the queue ）

   • The pointer of the second node to the first node becomes null, Pictured ：

     

10. Jump out of setHead Method , Back to the top , Keep going down

    

    • Change the pointer from the first node to the second node to null, The first node does not have any points at this time , By GC Garbage collection

    • renturn false,t2 Acquire the lock , The code continues to return , until lock Method , Keep going down

      

3.1 Embodiment of lock reentry

• When a thread executes to tryAcquire When the method is used , There is one if conditional , Compare the thread trying to acquire the lock with the thread holding the lock , If the same , On the other hand state Perform the operation of adding one , Indicates lock reentry

3.2 Why modify it twice waitStatus Value ？

• Why did you enter... For the first time shouldParkAfterFailedAcquire When the method is used , Not directly ws==0 Just go back to true To block , You have to assign more values ？
  • For one more spin （ The second node spins twice ）
    • Delay call park Time for ,park It will involve interface calls at the operating system level , It's a heavyweight lock , Consumption of resources
  • state Each value of corresponds to a different state

3.3 Interrupt when thread is blocked

If t2 The thread is shown below 1 The contents of the box are shown in , call park After method blocking , Interrupted by another thread , Then this method continues down , return true, The operation process is shown in the figure below ：

Return after interrupt true Why , You can refer to another article of the blogger , Delivery address ：interrupt、interrupted 、isInterrupted difference

You can find , When a thread is in a waiting queue , Cannot process external interrupt requests （ The thread is shown in the figure above 4 The box interrupts itself ）, Only after the thread gets the lock , To handle external requests .

3.4 The third thread joins the queue

• t3 The situation after the thread joins the queue is shown in the following figure

  

• Combined with the previous source code, we can find , After each thread joins the queue status Values are 0,status The value of will be changed by the next thread joining the queue to -1, Not that you will status Is changed to -1, reason ：

  • Calling park Before , There is no modification status Value ,park after , Thread blocking , Naturally, you can't modify it yourself status Value
  • If in park I modified it myself before status Value , If there is an exception , May lead to park Execution failure , Cannot block

Four 、 Unlock source code analysis

Get into ：

Get into ：

Back off , If the lock does not re-enter, then tryRelease The return value of the method is true：

If the waitStatus Values are not for 0, It means that a node is blocked after it , Need to be awakened （ In the header node waitStatus If the value of is -1, He needs to wake up the next node ）：

// Parameters node Indicates the header node , This method is to wake up head Next node of , Let it spin to get a lock 
private void unparkSuccessor(Node node) {
    

    // here head Our mission has been completed , Just a placeholder virtual node , It needs to be status Set as 0, Will not affect the judgment of other functions 
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
    
        s = null;
        
        // Search forward from the end of the queue , Find out except head The front most outside the node and waitStatus Value less than or equal to 0d
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    
    // After waking up, a blocked node spins to obtain a lock 
    if (s != null)
        LockSupport.unpark(s.thread);
}

4.1 Why look for nodes from back to front ？

One way to unlock is to wake up head Next node of , Let it spin to get a lock , namely unparkSuccessor Method . In the wake-up process of this method , Is to search forward from the tail node of the queue , Why not search backwards from the beginning ？

answer ：

In the process of competing for locks , Will execute a enq() Method , This method creates the head and tail nodes of the queue , Set the parameter node as the tail node , And form a two-way linked list with the head node ：

In execution if(compareAndSetTail(t, node)) when ,cas It's atomic manipulation , cas After success ,tail Point to the head node （tail Of prev Pointer in cas It has been established before the operation ）, A two-way linked list has not yet been formed .

When executed if The content in the code block , It's not an atomic operation , At this point, if other threads call unpark Method （ The header node has not been next Point to tail）, You can't traverse the complete queue from scratch , And looking forward from the back .