A simple AbstractQueuedSynchronizer

There are feelings, there are dry goods, wechat search [three prince Ao bing] pay attention to the programmer who has a little bit of things.

This article has been included in GitHub github.com/JavaFamily, there are a line of large factory interview complete test sites, information and my series of articles.

In Java multithreaded programming, ReentrantLock and Semaphore are two extremely important concurrency control tools. Most readers should be familiar with their use (if you are not sure, please take out your book and browse).

But are you familiar with the details of the implementation of reentry locks and semaphores? I’m going to take you through the implementation.

First, here’s an important class diagram to illustrate the relationship between the three:

You can see that the reentrant lock and semaphore in its own internal, implements a AbstractQueuedSynchronizer subclass, the name of the subclass is Sync. This Sync class is the core implementation of reentrant locks and semaphores. Subclass code is less in Sync, the core algorithm are provided by the AbstractQueuedSynchronizer. Therefore, it can be said that, as long as everybody understand AbstractQueuedSynchronizer, clearly know reentrant lock and semaphore implementation principle.

You must know about AbstractQueuedSynchronizer

Before it is entered AbstractQueuedSynchronizer, and some basic knowledge need to everybody know, in this way can we better understand AbstractQueuedSynchronizer implementation.

Permission-based multithreaded control

To control multiple threads accessing a shared resource, we need to issue a license to each thread accessing the shared interval. A thread must be licensed to enter the shared range activity. When a thread leaves the shared interval after completing its work, it must return the license to ensure that subsequent threads can obtain the license properly. If permissions run out, threads must wait while they enter the shared interval. This is the basic idea that governs multithreaded parallelism.

For example, a large group of children go to a playground to ride the ferris wheel, and only 20 children can sit on the ferris wheel. But 100 kids showed up. So the number of permits is going to be 20. That means only 20 kids can ride the ferris wheel at a time. The rest have to wait in line. Only when the child on the ferris wheel is out of control can other children play on it.

So using permissions to control thread behavior is pretty much the same thing as queuing up to ride the Ferris wheel.

Exclusive and shared locks

The second important concept is exclusive and shared locks. As the name implies, in exclusive mode, only one thread can access a shared variable, whereas in shared mode, multiple threads can access it simultaneously. Simply put, reentrant locking is exclusive; Semaphores are shared.

In the words of ferris wheel, exclusive lock means that although I have 20 seats here, the children can only get on one by one. What about the extra seats? You can either leave them empty or let the only child on the ferris wheel change his seat wherever he wants. And the shared lock is the normal way to open the ferris wheel.

LockSupport

LockSupport can be thought of as a utility class. It simply suspends and continues the thread of execution. Its common apis are as follows:

  • Public static void park() : Suspends the current thread if no license is available
  • Public static void unpark(Thread Thread) : Gives Thread an available license to continue executing

Since the word park means to stop, the park() function here means to pause the thread. Unpark (), on the other hand, lets the thread continue.

Note that LockSupport is itself a permit-based implementation. To understand this, see the following code:

LockSupport.unpark(Thread.currentThread());
LockSupport.park();
Copy the code

Can you guess, after park(), whether the current thread stops or can continue execution?

The answer is: yes. That’s because unpark() is executed before park(), which releases a license, meaning that the current thread has an available license. Park () does not block threads with available permissions.

To sum up, the execution of park() and unpark() has nothing to do with the order in which they are called. This is important because in a multi-threaded environment, it is often difficult to guarantee the order of function calls (all executed concurrently in different threads), so this permission-based approach maximizes error prevention.

A classic example of the opposite of park() and unpark() is Thread.resume() and thread.suspend ().

Look at the following code:

Thread.currentThread().resume();
Thread.currentThread().suspend();
Copy the code

Let the thread resume execution first, and then suspend the thread. This is very similar to the park() example above, but the results are quite different. In this case, the current thread is stuck.

Therefore, using park() and unpark() is our preferred option. In AbstractQueuedSynchronizer, it was also used the LockSupport park () and unpark () operation to control the running state of the thread.

AbstractQueuedSynchronizer internal data structure

Well, that’s all for the basics. Now, let’s cut to the chase: first look at the AbstractQueuedSynchronizer internal data structures.

Inside the AbstractQueuedSynchronizer, there is a queue, we call it the synchronization waiting queue. It is used to save threads waiting on the lock(waiting due to the lock() operation). In addition, in order to maintain wait in the waiting thread on the Condition variable, AbstractQueuedSynchronizer and need to maintain a Condition variable waiting queue, that by the Condition. Await () caused by blocked thread.

Because a single reentrant lock can generate multiple condition variable objects, a single reentrant lock can have multiple condition variables waiting in queues. In effect, a wait list is maintained inside each condition variable object. Its logical structure is as follows:

The following class diagram shows the implementation at the code level:

As you can see, both synchronous and conditional wait queues use the same Node class as the Node of the linked list. For synchronous wait queues, Node contains prev, the last element of the list, next, and thread objects. For conditional variable wait queues, nextWaiter is also used to represent the next node waiting in the conditional variable queue.

Another important member of the Node Node is waitStatus, which represents the status of the Node in the queue:

  • CANCELLED: indicates that the thread CANCELLED the wait. A cancellation may occur if an exception occurs while the lock is being acquired, such as an interrupt exception or a timeout during the wait.
  • SIGNAL: indicates that subsequent nodes need to be woken up.
  • CONDITION: The thread waits in the CONDITION variable queue.
  • PROPAGATE: PROPAGATE unconditionally in the shared mode releaseShared state. Earlier JDKS did not have this state, and at first glance it seems redundant. This state was introduced to address bug 6801020 where concurrent release of shared locks causes threads to hang. (as the JDK gets better, its code gets harder to understand :(like our own engineering code, the more bugs we fix, the more obscure the details become.)
  • 0: initial state

CANCELLED=1, SIGNAL=-1, CONDITION=-2, PROPAGATE=-3. In a specific implementation, the CANCELLED status can be determined simply by releasing waitStatus which is less than or equal to 0.

Exclusive lock

Understanding the basic implementation of AbstractQueuedSynchronizer ideas and data structure, then let’s have a look at its implementation details. First, let’s look at the implementation of exclusive locks. A reentrant lock is a typical exclusive lock.

Request a lock

Here is the code for requesting permission for an exclusive lock:

public final void acquire(int arg) {
    // Try to obtain the license, arg is the number of licenses. For reentrant locks, one is requested at a time.
    if(! tryAcquire(arg) &&// If tryAcquire fails, add the current thread to the synchronous wait queue using addWaiter()
    // Then continue trying to acquire the lock
    acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}
Copy the code

Take a look at the tryAcquire() function. This function attempts to obtain a license. For AbstractQueuedSynchronizer, it is an unrealized of abstract function.

The implementation is in a subclass. In the reentrant lock, read and write lock, semaphore implementation, have their own implementation.

If tryAcquire() succeeds, acquire() returns success directly. If this fails, add the current thread to the synchronous wait queue with addWaiter().

The acquireQueued() function is then used to request the lock on a thread that is already in the queue. As you can see from the name, node must be a node that is already in the queue. Its function is to request a license for a Node that is already in the queue.

This is a function you should look at because it is used both in the normal lock() method and in await() of conditional variables.

Conditional variable wait

If condition.await () is called, the thread will also wait, and here is the implementation:

The Condition object’s signal() notification

Signal () is a FIFO in a conditional wait queue, starting with the first node:

Release () releases the lock

Releasing exclusive locks is simple

public final boolean release(int arg) {
    TryRelease () is an abstract method with a subclass implementation like tryAcquire()
    if (tryRelease(arg)) {
        Node h = head;
        if(h ! =null&& h.waitStatus ! =0)
            // Wake up a waiting thread from the queue (skip if CANCEL is encountered)
            unparkSuccessor(h);
            return true;
    }
    return false;
}
Copy the code

A Shared lock

Shared locks are slightly more complex to implement than exclusive locks. And that makes sense. Because the exclusive locking scenario is simple, single in, single out, while shared locking is different. Maybe N goes in and M goes out, which is a little bit more difficult to deal with. But their core ideas are the same. Some typical applications of shared locks are: semaphores, write locks in read/write locks.

Get a shared lock

In order to achieve a Shared lock, in AbstractQueuedSynchronizer, have a special set against a Shared lock method.

Get the shared lock using the acquireShared() method:

Releasing a Shared Lock

The code to release the shared lock is as follows:

public final boolean releaseShared(int arg) {
    //tryReleaseShared() attempts to release permissions, which is an abstract method that needs to be implemented in a subclass
    if (tryReleaseShared(arg)) {
        // This function is already present in the above code, which is to wake up the thread and set the propagation state
        doReleaseShared();
        return true;
    }
    return false;
}
Copy the code

Write the last words

AbstractQueuedSynchronizer is a more complex implementation, to fully understand the details still need to slowly understand.

This article also can have the effect of a topic, will AbstractQueuedSynchronizer design thoughts, the core data structure is the core code to show you. Hope to understand AbstractQueuedSynchronizer implementation, as well as understand the reentrant lock, semaphore, read-write lock has certain help.

The multithreaded series is still on the way, and if you have a deeper understanding of this class, you can post it in the comments section: Get Stronger

I’m Aobing, the more you know, the more you don’t know, thank you for your talent: likes, favorites and comments, we’ll see you next time!

This article is constantly updated. You can search “Santaizi Aobing” on wechat and read it for the first time. Reply [Information] There are the interview materials and resume templates for first-line big factories prepared by me.