The introduction

If you ask an Android student, please simply say the basic idea of Java AQS, then there are not less than half of the students may be meng state 😨.

What is it? What is AQS? I haven’t heard of 🙃.

Sure, it’s not too much of a surprise if you haven’t heard of it before, but if you’ve studied Concurrency in Java in depth, you’ll probably know about locks. As an ambitious young person, you’ll probably be wondering, “Why lock can sync?” At this time, we must also see the shadow of AQS.

From a technical point of view, when we talk about ReentrantLock, it’s not hard to talk about AQS.

If you don’t know, this article may help.

This article isJava Concurrent SeriesThe first paper:

  • Analyses the synchronized the underlying implementation | Java related to lock
  • A simple, from already to AQS | Java

background

Before we can understand a technology, we need to understand why the technology is happening and what it can do for us.

AbstractQueuedSynchronizer AQS full name, when jdk1.5 to join, is the foundation of the whole JUC, we all use most of the synchronizer are now based on AQS, its performance compared with the commonly used synchronized to a certain extent, improve a lot, Doug Lea, the master of concurrency who built it, expects it to be the basis for most synchronization requirements.

So what are the reasons for AQS? Is the AQS just there to improve performance, or is the wheel of the AQS to be repeated just for performance?

To explain this problem, we should first consider that synchronized was the most common method of synchronization before it appeared. Synchronized could not solve deadlocks, because when it applied for resources, if it failed to apply, the thread would immediately go into a blocked state after the end of the spin. In order to solve this problem, we needed a new solution.

If we have to rewrite to design a tool to solve the above problems, how to design, AQS provides the following solution?

  • Support response interrupts.synchronizedOnce blocked, it cannot be interrupted. However, if the blocked thread can respond to the interrupt signal, it can be woken up. So you’re breaking the inpreemption condition.
  • Timeout is supported. If the thread does not acquire the lock for a period of time, instead of entering a blocking state, it returns an error, then the thread has a chance to release the lock it once held, which can also break the non-preemption condition.
  • Non-blocking get lock. If an attempt to acquire the lock fails and the thread does not block but returns, the thread has a chance to release the lock it once held. This also breaks the non-preemption condition.

The background content source above (modified) is binarylei

What is AQS?

Abstract queue synchronizer AbstractQueuedSynchronizer, is used for a basic framework of numerous synchronous components, internal use the CLH queue lock.

If you haven’t seen this before, this sentence may sound a little confusing, but before you try to figure out how it works, let’s have an idea in mind:

This is the basic framework that you’re going to use to build locks

Some people say that AQS is just a tool class, and it is. But its importance in concurrent programming might be better described as a framework.

1. Introduction to AQS basic theory

The main use of AQS is inheritance, that is, the subclass inherits AQS to implement its abstract method to manage state, internal use of an INT member variable state to represent the synchronization state, and through a FIFO(first-in, first-out) queue to complete the queuing work of threads.

In terms of implementation, it is generally recommended that subclasses be defined as static internal classes (like Sync in ReentrantLock). AQS itself does not implement any synchronization interface, but only defines several methods for obtaining and releasing synchronization state for use by custom synchronization components. Synchronizers can support exclusive acquisition of synchronization state. Shared access to synchronization state is also supported, which is how synchronization components built into the JDK work.

The overview

Describe the workflow:

Each time a resource is requested, it is first added to the CLH queue, and state+1, and the queue is in the cycle traversal stage (when state=0, it means that the resource is not occupied). During the queue cycle, if the requested shared resource is idle, the thread of the current resource request is set as a valid worker thread. Set locked to true to indicate that the node is occupied, and subsequent nodes (i.e. threads that need to acquire resources) remain in spin wait state. I continuously check whether the previous node’s locaked is false. If false, the resource is idle and I try to obtain the resource.

Template method pattern

If you look at the ReentrantLock source code, you will find that, except for the original lock() method provided by ReentrantLock itself, the rest of the method resolution, that is, the core method calls within the ReentrantLock, all call AQS related methods.

And NonfairSync implements some of AQS methods, such as tryAcquire(), to provide concrete implementation logic.

This design is called the template method pattern:

In other words, it can be summarized as follows: for a design, we define the concrete implementation logic in advance for the methods that are not easy to change, and give some concrete implementation to external implementation. And this similar method according to our logic needs, packaged into several general method call combination, for external call.

  • For the outside, it itself does not know the concrete implementation of my inside;
  • Externally, several specific methods are required to implement their own corresponding unique logic;

The advantage is that we encapsulate the immutable, extend only the mutable, and extract the common code for easy maintenance.

CLH queue lock

CLH queue lock is a kind of extensible, high performance, fair spin lock based on linked list. The thread applying for resources spins only on the local variable. It continuously rotates the state of the precursor node, and terminates the spin if the precursor releases the lock.

When a thread needs to acquire a lock, it creates a QNode with locked set to true to obtain the lock and myPred to reference its precursor.

The complete process is as follows:

  1. Suppose thread A wants to get A resource by making itself the tail of the queue and getting A reference to its precursor nodemyPredAnd constantly spin judgment on the parent node reference.

  1. When another thread B also needs to acquire the lock, the same process is performed, as shown below (qnode-b) :

  1. When a thread wants to release a lock, set the current node to False.

    The subsequent node is spinning, and if its prenode is false, the prenode has released the lock, so it can acquire the lock itself and release the current prenode reference for GC collection.

The whole process is shown in the figure above. The advantage of CLH queue lock is low space complexity. If there are N threads and L locks, and each thread acquires only one lock each time, the storage space required by CLH queue lock is O(L+ N),n threads have N nodes, and L locks have L tail.

The CLH queue lock implementation method in AQS is a variant implementation compared with the above method. Compared with ordinary CLH queue lock, the implementation method in AQS has made relevant optimization, for example, the thread will not continue to retry, but will block after the relevant number of retries. Wait for the wake up call.

AQS related methods

Template method

When we implement our custom synchronous component, the template methods provided by the synchronizer will be invoked. The relevant methods are as follows:

The template methods provided by the above template method synchronizer fall into three categories:

  1. Exclusive get and release synchronization state
  2. Shared get and release
  3. Synchronization status and query the status of waiting threads in the synchronization queue.

Rewritable methods

A method to access or modify synchronization state

In a custom synchronization component framework, the abstract AQS method must change the synchronization state during implementation. In this case, three methods provided by the synchronizer are required to operate, because they can ensure that the state changes are safe:

  • getState()

    Gets the current synchronization status

  • setState(newState:Int)

    Set the current synchronization status

  • compareAndSetState(expect:Int,update:Int)

    CAS is used to set the current state. This method ensures atomicity of the state setting.

2. From ReentrantLock to AQS

Have not seen AQS, ReentrantLock always should understand some point, there is a saying that know brother is like brother, so we start with it, beat around the corner.

The paper

Describe the background to ReentrantLock:

We all know that the synchronized keyword is used for locking, but this locking can have a significant impact on performance because threads must be in a wait state to acquire resources, with no additional attempt mechanism. So in jdk1.5, Java provided ReentrantLock as an alternative to synchronized.

ReentrantLoack features ReentrantLoack, interruptible, limitable, fair lock, and unfair lock.

Simple use of ReentrantLock:

val lock = ReentrantLock()
lock.lock() / / lock
// Business logic
lock.unlock()  / / release
Copy the code

Relationship with AQS

Now, you might look at this and say, well, what does that have to do with AQS? Take a look at the picture below:

Already have an abstract class internal Sync inherited AbstractQueuedSynchronizer, the default constructor and instantiate the NonfairSync class subclasses (Sync). For external, only focus on the lock and unlock method, but the inside is actually called the AbstractQueuedSynchronizer method.

Process analysis

ReentrantLock uses AQS in its ReentrantLock application.

For ease of understanding, our entire process uses NonfairSync, the pseudo-source code for unfair locks (there is not much difference between fair and unfair).

lock()

Start with the locking method as follows:

class NonfairSync. ->

   fun lock(a) -> {
  
      👉 1. if (compareAndSetState(0.1))
            👉 2. setExclusiveOwnerThread(Thread.currentThread())
            else👇 acquire (1) // Get in exclusive mode
 
       
       fun acquire(arg:Int=1)- > {// Trying to get && Adds the current thread to the wait queue and keeps trying to get the previous node via CAS
         👉 3.  if(! TryAcquire (arg) && 👉4.  acquireQueued(addWaiter(Node.EXCLUSIVE), arg) )
         
Copy the code
1.compareAndSetState

This method means to attempt to acquire the lock, and the internal operation is as follows: if the current state value is equal to the expected value, the synchronization state is set atomically to the given update value.

In other words, we estimate the current value to be 0, that is, we estimate that there are no threads currently occupying the resource. If we find that the actual value to be operated on is really 0, that is, the current resource is not occupied by other threads, then we update it to 1, indicating that the current resource is occupied.

And there is an int variable state inside AQS, whose function is to represent the current lock state.

private volatile int state;
Copy the code

If a thread successfully attempts to acquire the lock, what if the same thread tries again? We call it lock reentrant, so how do we do that? Can’t I get another lock on my own? It is impossible to generate two locks for one resource that are occupied by the same thread. Outrageous! So what to do?

This is where the setExclusiveOwnerThread method comes in, and let’s look at its implementation.

2.setExclusiveOwnerThread
protected final void setExclusiveOwnerThread(Thread thread) - {
        exclusiveOwnerThread = thread
Copy the code

Inside is set the current thread object, and this’ exclusiveOwnerThread ‘is another variable of AQS, representing the current thread that owns the lock. So where does this work? Let’s look at the following method.

3.tryAcquire

The pseudo-code for this method, which means that the lock is acquired unfairly, is as follows:

 
 fun tryAcquire(acquires:Int=1) -> {
    👇
     fun nonfairTryAcquire(acquires):Boolean- > {valCurrent = Current thread objectval c = getState()
     1. 👉 if(c== 0 && compareAndSetState(0, acquires)) 
    	       setExclusiveOwnerThread(current)
    		     return true
    	 
     2. 👉 else if(current= current thread object in AQS) State += acquires held in AQSreturn true
    	   
           return  false

Copy the code

When nonfairTryAcquire is called to acquire the lock, the internal operation is simple: first get the current thread object and the state value stored in the current AQS,

  1. If the current state is 0 and passescompareAndSetStateMethod attempt to modifystateSuccess means that the current resource is not occupied by threads, and then the thread that currently owns the lock is set as its own.
  2. If the thread currently occupying the resource is itself, then yesAQSIn thestate+1, and returns true, indicating that the current thread successfully acquired the lock.

If return false, the current thread failed to acquire the lock.

Why is state+1 required for the same thread when the lock is acquired?

We all know that with ReentrantLock, we release the lock and call unLock, so that’s where we start.

4.acquireQueued

This method acquires the lock in an endless loop, with the following internal code:

 fun acquireQueued(node:Node, arg:Int=1):Boolean- > {// Whether the resource has been successfully obtained
    var failed = true
    try {
      	// Whether the waiting process is interrupted
        val interrupted = false
      	// Start the spin, or get the lock,
        while (true) {
            valP = previous node// If the previous node is the head node and the state was successfully changed, the current thread has acquired the lock
            if (p == head && tryAcquire(arg)) {
              	// Set a new header
                setHead(node)
              	// Set the previous header to null for GC collection
                p.next = null // help GC
                failed = false
                return interrupted
            }
          	// called when the lock fails to be obtained
          	// If the current thread is blocked and has been interrupted, modify the interrupted flag
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true}}finally {
        if (failed)
            cancelAcquire(node)
    }
}
Copy the code
conclusion

When we call lock() (using an unfair lock as an example), internally we first attempt to modify the state variable held in AQS atomically:

  1. If the modification is successful, it indicates that the current resources are not occupied by threads, and the lock is successfully obtainedAQSIn theexclusiveOwnerThreadUpdate to the current thread object, so that later lock reentry directly returns a successful lock acquisition.
  2. Is called if the initial modification failsacquireMethod to obtain the lock. The method internally tries to acquire the lock once, adds the current thread to the wait queue, and then passesCASThe way you keep spinning, keep gettingThe parent nodeNode, ifThe parent nodeNode isThe head head nodeIs displayed, indicating that the current node isThe queue firstIf the lock is obtained successfully, the queue head node is updated to the current node and the parent node of the current traversal is removed. If the lock fails to be acquired, the precursor node is used to determine whether the current thread is blocked. If the current thread has been interrupted, the flag bit is updated and the loop is suspended until it is awakened.

After reading the simple analysis of lock() method, do you feel that you are on the wrong car? It is just a simple process analysis. If you follow it closely, the details are still very deep, which may not be the whole overview of this article, we just need to know the general process.

unLock()

   1.👇
   fun unLock(a)- > {2.👇
       fun release(arg:Int=1):Boolean- > {// If -tryrelease - is true, the waiting queue will be woken up, that is, another thread will acquire the lock.
      	     👉   if (tryRelease(arg))
            		    ...
          			   unparkSuccessor(h)
      
           3.👇
           fun tryRelease(arg=1):Boolean-> {c = AQS state variable -arg..if (c == 0) { 
                    // Set the thread held in AQS to NULL
                    setExclusiveOwnerThread(null)  
             				return true}.. setState(c) ..Copy the code

As mentioned above, unLock method is called in the following order. When unLock method is called to release the lock, relase method is actually called inside, and tryRelease method is called inside. The state variable in AQS -arg(1) is used inside. If c=0, it indicates that there are no threads currently occupying the resource and wakes up the waiting queue, that is, other threads start acquiring the lock.

Go through the train of thought (not fair locking)

When we call the lock method, we first try to modify the state variable value within AQS atomically. If the current state value is consistent with the expected value, we update the variable value of the internal STATE of AQS to 1, and assign the reference of the current thread object to AQS.

If the attempt to modify the state variable fails, acquire(xx) is called to acquire the lock, add itself to the current wait queue inside the method, and keep spinning with CAS to try to get whether the previous node of the parent node is equal to the head node. If the previous node is equal to the head node and the current state variable is successfully modified, it means that the current thread has acquired the lock. Then, the current node is set as the head node and its previous node is removed. Of course, AQS does a lot of work on this, and it does not keep repeating the retry operation. After a spin, it stops in a thread interrupt and cancels the current attempt.

By going through the source code for ReentrantLock, we have an overview of the process and the specific responsibilities of the corresponding methods, which will play some important roles in our understanding of AQS. And customizing your own reentrant lock would also help.

3. Write a reentrant lock using AQS

Reentrant of the lock

When a thread calls a method or an object that has acquired a lock and then calls the specified method again, the lock is reentrant. In general, when we re-enter, we will determine whether the current thread has acquired the lock. If so, we will modify the synchronization state, that is, state+1 in AQS. Why do we need state+1, because we need minus 1 to release the lock.

The specific code is as follows:

4. AQS in our daily life

To tell the truth, not using AQS, will not affect any development, now in Android development, all kinds of thread related tool library, Rx, coroutines, is to reduce the development difficulty, but as the foundation, we should understand some of the underlying design idea, when you may one day want to define the rules of a particular thread tools, All of these things that seem to be of little practical use to us will come in handy.

The study of anything, there is a why?

When you’re trying to figure out why synchronized is a lock, or why ReentrantLock is ReentrantLock, these obscure things are the only entry points.

Illustrations address

  • Processon-aqs framework analysis
  • Processon-clh queue lock analysis

Thank you

  • Enjoy learning classroom – AQS analysis -Mark
  • Principle of lock – AQS source analysis: synchronized why to repeat the wheel

About me

Hello, I’m Petterp, an Android engineer training in Didu.

If you find this article valuable to you, please feel free to visit 👏🏻 and follow me on Github.

If you feel bad after reading, also welcome to leave a message to me.