The introduction

This article is the first source class analysis of the article, first say why I read the source code?

  1. After all, there is no secret in the source code, you want the principle of source code it has;
  2. The people who write the source code are very skilled, and you can see the art of their code design. Read thousands of books, line thousands of miles, the same truth, read more source code, always from quantitative change to qualitative change, finally write excellent code.

Say again oneself look source code method:

  1. Be sure to remember the purpose of their own source ah!! Comrades, this really is too important, when I used at first to see the source code, was the first just want to look A certain way (hypothesis is A method) of the source code, and then found A method call the B method, and go to the B method, method and call C B, like dolls endless, finally took A long time did not understand A method, in self-doubt.
  2. Look at the source code to know the whole and then part of the first, a main road through, and then slowly refined, “do not know the true face of Lushan, only edge born in this mountain”, the ancients honestly do not deceive me;
  3. To learn to give up, yes you read the right, to learn to give up, as long as it is not important things, don’t understand it doesn’t matter, let go, don’t be obsessed, after all, time is precious, there is no need to die on it, do this not cost-effective business;
  4. Or you will forget to take notes, good, no matter what kind of form is, to take notes, I am really feeling significantly less memory, but also may be to face more every day now, time is more fragmented, so take notes allows you to quickly recall how do you understand the knowledge point somewhere;
  5. Finish notes also have to review the past to learn new, otherwise they will turn over the book ma Dongmei, interview Sun Honglei;
  6. Look at the source code to learn to ask yourself questions, and then look at the source code is how to solve, don’t be led by the source code, this will be reflected in the article;
  7. Don’t be impatient, the source code is written by the big guy, I don’t understand this again and again is very normal, to tell the truth today to speak this part of the source code I also read many times, just barely can see, so meet don’t understand when tell yourself: steady, we can win.

Above is some of their own experience, talent and learning, a lot of advice, temporarily did not have the message function, interested can pay attention to the public number plus my micro channel mutual discussion, nonsense not to say, directly open dry.

ReentrantLock (synchronized) ReentrantLock (synchronized) ReentrantLock (ReentrantLock) Contracted out in Java and Java. Util. Occupy important position in the concurrent AbstractQueuedSynchronizer (queue synchronizer), then respectively introduces the response of interrupts and does not respond already how respectively on the basis of AQS, Finally, the similarities and differences between synchronized and ReentrantLock are compared.

Template method design patterns

Before the introduction of AQS, we first introduce a design pattern, the template method design pattern, this kind of design mode, the abstract parent class will first define one or more template structure and some basic method, but is not specific to the behavior of the structure, so subclasses through the way of inheritance under the premise of without changing the template structure, to achieve a specific behavior, That leaves a lot to your imagination.

In summary:

  1. The parent class is an abstract class;
  2. Template methods typically use final declarations to prevent subclass overrides from changing the template structure;
  3. Subclasses are implemented by inheritance.

The above text may be a little abstract, but the code is easy to understand.

There is a template method that lives a day, and some basic methods are implemented:

public abstract class NormalTemplate {
    // Define the template method and declare it final
    public final void day(a) {// Define your day
        Get up / /
        wakeup();
        / / breakfast
        breakfast();
        // Get to work by car
        transportation();
        / / work
        work();
    }
    // Basic method
    public void wakeup(a) {
        System.out.println("Struggle to get up at 6:00.");
    }

    public void breakfast(a) {
        System.out.println("Milk and bread...");
    }
    
    public void transportation(a) {
        System.out.println("Crowded into the skeptical subway...");
    }
    
    // Work freely
    protected abstract void work(a);
}
Copy the code

To redefine what a happy day looks like, subclass the template as follows:

public class HappyTemplate extends NormalTemplate {
    @Override
    public void wakeup(a) {
        System.out.println("Wake up naturally...");
    }
    @Override
    public void transportation(a) {
        System.out.println("Never get stuck in traffic on my favorite scooter.");
    }
    @Override
    protected void work(a) {
        System.out.println("Work? What is a job?");
    }
    public static void main(String[] args) {
        HappyTemplate happy = newHappyTemplate(); happy.day(); }}Copy the code

The result is as follows:

Except for breakfast, everything is covered by subclasses, and the template pattern is actually quite simple, so you should have an idea of the design pattern by now.

AQS and ReentrantLock principle analysis

AQS defines some template methods and some basic methods, and then develops various synchronization components based on AQS, such as ReentrantLock. This awareness is very important. This is the above reading source method, first look at the whole. When I first read ReentrantLock, I didn’t understand this, and then I would jump back and forth to AQS in ReentrantLock.

ReentrantLock is different from synchronized, which is a JDK level lock that blocks/wakes up threads, and a JVM level lock that blocks/wakes up threads. So there are two questions:

  1. sinceReentrantLockIs based on the AQS template, then this template isReentrantLockWhat does it define?
  2. sinceReentrantLockIs a lock that blocks/wakes up threads, so what characteristics should such a lock have?

This is the above see source code sixth, to look at the source code with a problem.

A lock that blocks/wakes up threads should have at least the following elements:

  1. Need to have a variable to represent the current lock state, at least at least occupied and idle two states, at the same time since it is to control the concurrency of multithreading, so is not at least to ensure that this variable multithreading concurrency safety, can not be some threads appear to be occupied, some threads appear to be idle;
  2. If the lock is occupied, at least know who is holding it, that is, keep track of the thread currently holding the lock;
  3. If a lock fails and needs to block threads, there must always be a place to store them, and the data structure must be thread-safe;
  4. Now that blocking/waking is involved, who does the work?

With these problems, go to the AQS source code to see how it is implemented, in particular, this article is based on JDK1.8 source code analysis.

First answer the above question, how is it solved in AQS:

  1. For locks, AQS uses a volatile variable with an integer. I’m sure you don’t need to explain how volatile is, if you don’t already know how

The article has even been analyzed from the hardware level, if you have not seen it, there will be more harvest, here will not expand to say; (2) for holding a thread record locks, in AQS superclass AbstractOwnableSynchronizer have a variable exclusiveOwnerThread to record, is a set of medium, the feeling of die, die, but mainly captures the template method design pattern, is clear; 3. For the queue storing blocked threads, AQS defines a queue named CLH, which is actually the first letter of the name of the three big guys (Craig, Landin, and Hagersten). As for the guarantee of thread safety, CAS is adopted, and its underlying structure is bidirectional linked list. The blocked threads are encapsulated as nodes of the linked list. The head node points to the head of the list, and the tail node points to the tail of the list. To join a queue, add a node to the tail node and CAS the tail node. To exit the queue is to CAS the head and move the CAS back; Head = tail = null; head = tail = null; head = tail = null; The process is as follows:

4. How is blocking/waking done? Here the park()/unpark() primitives are used, but these are native methods that are encapsulated in Java through the LockSupport utility class; Analysis of thesycnhronizedThe park()/unpark() operation primitives can wake up precisely, which wait()/notify() does not.

Part of the code is shown as follows:

public abstract class AbstractOwnableSynchronizer
    implements java.io.Serializable {

    /** * The current owner of exclusive mode synchronization. */
    private transient Thread exclusiveOwnerThread;        
        
}

public abstract class AbstractQueuedSynchronizer
    extends AbstractOwnableSynchronizer
    implements java.io.Serializable {
    // Omit some code
    /** * The synchronization state. */
    private volatile int state; 
    
    / / CLH node
    static final class Node {
        static final Node SHARED = new Node();
        
        static final Node EXCLUSIVE = null;
        
        // Wait state
        static final int CANCELLED =  1;
        static final int SIGNAL    = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;
        volatile int waitStatus;

        // The precursor node
        volatile Node prev;
        / / the subsequent section
        volatile Node next;
        
        volatile Thread thread;
       
        Node nextWaiter;
        
        final boolean isShared(a) {
            return nextWaiter == SHARED;
        }
        
        final Node predecessor(a) throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }
        
        // Get the lock!! This is a template method!!
        public final void acquire(int arg) {
        if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }// Release the lock!! This is a template method!!
        public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if(h ! =null&& h.waitStatus ! =0)
                unparkSuccessor(h);
            return true;
        }
        return false; }}Copy the code

Next, we will analyze how ReentrantLock is implemented based on AQS:

To use ReentrantLock first, you must construct a concrete object instance, so let’s look at the constructor:

/** No argument constructor */
public ReentrantLock(a) {
    sync = new NonfairSync();
}

/** A constructor with a fair policy */
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}
Copy the code

ReentrantLock can be divided into fair lock and unfair lock according to different fair policies. The default is unfair lock. ReentrantLock can be divided into fair lock and unfair lock. What is fair and unfair will be specified when locking.

As you can see from the constructor, the result of the construction is a sync object, on which all subsequent locking and unlocking will be based.

/ / lock
public void lock(a) {
    sync.lock();
}

/ / releases the lock
public void unlock(a) {
    sync.release(1);
}
Copy the code

So what is such an important object? That’s right, it’s a subclass of AQS.

abstract static class Sync extends AbstractQueuedSynchronizer {
    // Some code
    
    abstract void lock(a);// Abstract methods
    
    final boolean nonfairTryAcquire(int acquires) {...// The reasons for the length, to avoid repetition, will be analyzed in detail below
    }

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

Due to space constraints, this article only posted part of the source code, from the above analysis, we know that FairSync represents a fair lock class, NonfairSync represents an unfair lock class. Let’s look at these two classes:

// Unfair lock
static final class NonfairSync extends Sync {
   // Some code
    final void lock(a) {
        if (compareAndSetState(0.1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1); // Call the AQS template method
    }

    protected final boolean tryAcquire(int acquires) {
        returnnonfairTryAcquire(acquires); }}/ / fair lock
static final class FairSync extends Sync {
    // Some code
    final void lock(a) {
        acquire(1);
    }
    protected final boolean tryAcquire(int acquires) {...// Space is limited to avoid duplication. This method will be analyzed in detail below}}Copy the code

ReentrantLock: ReentrantLock: ReentrantLock: ReentrantLock

Overall:

ReentrantLock implements unfair and fair locking by inheriting AQS from the internal abstract class Sync and then implementing Sync from the internal class NonfairSync and FairSync. In NonfairSync and FairSync, the locking behavior of the internal abstract class Sync is materialized, and the template method in AQS is called to realize the locking logic.

Partial (unlock details) :

Unfair lock and lock:

final void lock(a) {
    if (compareAndSetState(0.1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1); // Call the AQS template method
}
Copy the code

If it succeeds, it sets itself as the exclusive lock thread. If it fails, it calls the template method acquire(1) in AQS. In fact, this is the first place where locks are unfair, i.e. the thread that comes first doesn’t necessarily get the lock first.

So how is fairness reflected in fair lock?

Fair lock lock:

final void lock(a) {
    acquire(1);// Call the AQS template method
}
Copy the code

It can be seen from the source, will not go to grab the lock, but directly call AQS template method acquire(1).

Acquire (1) template method in AQS is as follows:

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

Overall analysis logic:

The locking logic of the template consists of the following two parts:

  1. Through the firsttryAcquire(arg)Method try to lock;
  2. If the lock failsacquireQueued(addWaiter(Node.EXCLUSIVE), arg)Method to put the thread into the CLH queue, if successful due to&&It’s gonna short-circuit, cause the backacquireQueued(addWaiter(Node.EXCLUSIVE), arg)If the method does not execute, it is not added to the blocking queue.

Concrete implementation:

In NonfairSync, say the first part tryAcquire(ARG) :

// The implementation of NonfairSync
protected final boolean tryAcquire(int acquires) {
    return nonfairTryAcquire(acquires);
}
Copy the code

The tryAcquire(arg) method in NonfairSync is an empty shell, and the actual call is the nonfairTryAcquire(acquires) method in Sync as follows:

    // methods in Sync
final boolean nonfairTryAcquire(int acquires) {
    // Get the current thread
    final Thread current = Thread.currentThread();
    int c = getState(); // Get the current lock status
    if (c == 0) { // If no one holds the lock, the CAS attempts to acquire the lock
        if (compareAndSetState(0, acquires)) {
            ExclusiveOwnerThread set to the current thread
            setExclusiveOwnerThread(current); 
            return true; }}// If the lock is already held, determine whether it is held by the current thread
    else if (current == getExclusiveOwnerThread()) {
        // If held by the current thread, the state variable is accumulated
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);// Modify the state variable
        return true;
    }
    // If the lock is held by another thread, the lock fails and false is returned
    return false;
}
Copy the code

This logic is relatively simple, but also relatively easy to understand, I have detailed comments in the code, we must be able to understand. But there is a key point here: when no one owns the lock, the unfair lock will directly start grabbing the lock through CAS, which is also the second aspect of unfairness!! .

How to ensure fairness in the fair lock? The lock code of the fair lock is as follows:

/ / fair lock
protected final boolean tryAcquire(int acquires) {
   // Get the current thread
   final Thread current = Thread.currentThread();
   int c = getState();// Get the current lock status
   if (c == 0) { // Determine if you are the head node when no one holds the lock
                   // If so, try using CAS to lock
       if(! hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
           ExclusiveOwnerThread set to the current thread
           setExclusiveOwnerThread(current);
           return true; }}// If the lock is already held, determine whether it is held by the current thread
   else if (current == getExclusiveOwnerThread()) {
       // If held by the current thread, the state variable is accumulated
       int nextc = c + acquires;
       if (nextc < 0)
           throw new Error("Maximum lock count exceeded");
       setState(nextc);// Modify the state variable
       return true;
   }
   // If the lock is held by another thread, the lock fails and false is returned
   return false;
}
Copy the code

From the source can be seen, the overall framework and non-fair lock almost, the only difference is, when no one holds the lock, will judge the current queue through hasqueuedToraise () to other threads, no will grab the lock, what is fair, this is fair.

 public final boolean hasQueuedPredecessors(a) {
    // The correctness of this depends on head being initialized
    // before tail and on head.next being accurate if the current
    // thread is first in queue.
    Node t = tail; 
    Node h = head;
    Node s;
    returnh ! = t && ((s = h.next) ==null|| s.thread ! = Thread.currentThread()); }Copy the code

Having covered the first part of the template approach, let’s look at the second part: AcquireQueued (addWaiter(Node.exclusive), arG) if the lock fails, place the thread in the CLH queue and block.

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    if(pred ! =null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}
Copy the code

The thread is first stored as a Node through the Node constructor, and then the tail Node in the underlying bidirectional list is assigned to the temporary variable pred. If the tail node is not empty, the node is inserted into the tail of the queue through CAS. If the tail node is empty, the enq(node) method is executed: this method initializes the queue, creates an empty node, and spins until the node is successfully added to the tail of the queue.

private Node enq(final Node node) {
    for (;;) { // equivalent to while(true)
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node())) // Create an empty Node
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                returnt; }}}}Copy the code

You should be able to understand the above process by looking at CLH queue initialization.

Note that addWaiter(Node.exclusive) simply adds a thread object to the end of the CLH queue and does not block the thread, so the thread blocks by acquireQueued(…). Method.

Next, analyze acquireQueued(…) Method to perform thread blocking. First on the source code, as follows:

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            // Get the precursor of the current node
            final Node p = node.predecessor();
            // Wake up if you are at the head of the queue
            // the previous Node is an empty Node pointed to by head
            if (p == head && tryAcquire(arg)) {
                // The thread exits the queue and moves the head pointer back one position.
                // Set node to empty, so head still points to an empty node
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())// Call park to block itself
                interrupted = true; }}finally {
        if(failed) cancelAcquire(node); }}Copy the code

I’ve commented some of the above code, but let’s look at the function itself:

First, there’s a for(;;) in the code. Loop, so the moment the function returns is the moment the lock was taken;

Second, this function has a return value, which is a Boolean variable. What does that mean? The return variable is interrupted, which means interrupted, and while lock does not respond to interrupts, it records that no other thread has sent interrupt signals to it during the time it was blocked. Return true if yes, false if no;

When true is returned, selfInterrupt() is called based on this return value and sends itself an interrupt signal, setting its own interrupt flag bit to true. This is done because it did not respond promptly to interrupt signals from other threads during the block and now compensates for the response.

//AQS template method
public final void acquire(int arg) {
    if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }static void selfInterrupt(a) {
    Thread.currentThread().interrupt();
}
Copy the code

A thread calls the park() function to block itself and stay there until it is woken up by another thread, thus locking itself.

private final boolean parkAndCheckInterrupt(a) {
    LockSupport.park(this);// Block the thread
    return Thread.interrupted();
}
Copy the code

The park() function returns two cases:

  1. Other thread callsunpark(Thread t), accurate awakening;
  2. Other thread callst.interrupt()Because theLockSupport.park(t)Is responsive to interrupts.

After being interrupted, check whether Thread. Interrupted () has been interrupted. Return false if case 1; Return true in case 2.

Since lockSupport.park (t) will respond to an interrupt, acquireQueued(…) When awakened, if it finds itself at the head of the queue, it tries to get the lock. If it fails, it blocks itself again, repeating the process until it gets the lock and exits the function.

Therefore, the lock process of fair lock and unfair lock has been analyzed.

The following analysis unlock:

/ / first
//Sync
public void unlock(a) {
    sync.release(1);
}

// Then call the AQS template method

//AQS
public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if(h ! =null&& h.waitStatus ! =0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

/ / in the end

// The implementation of Sync
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if(Thread.currentThread() ! = getExclusiveOwnerThread())// Only the owner of the lock is eligible to release the lock; otherwise, an exception is thrown
     throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {// Every tryRelease(1), state-1,
    // The lock is not fully released until it is reduced to 0
     free = true;
     setExclusiveOwnerThread(null);
    }
    setState(c);// CAS is not used because the lock is mutually exclusive
             Call set directly to change the lock state
    return free;
}
Copy the code

Overall:

First, look at the unlock logic stipulated in the AQS template method as a whole, which is also divided into two parts:

  1. calltryRelease(...)Method unlock;
  2. callunparkSuccessor(h)Method to wake up a successor in the queue.

Because of the exclusivity of locks, fair locks and unfair release locks are the same and simpler.

Locks that respond to interrupts — lockInterruptibly analysis

The lock analyzed above does not respond immediately when a thread interrupts. Instead, it records the interrupt signal and compensates for the interrupt when the block is complete. So there is also a direct response to interrupt lock, directly on the source code:

/ / already
public void lockInterruptibly(a) throws InterruptedException {
  sync.acquireInterruptibly(1);
}
Copy the code

The acquireInterruptibly(1) method is also called through sync. This method is implemented in AQS as follows:

public final void acquireInterruptibly(int arg)
        throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    if(! tryAcquire(arg)) doAcquireInterruptibly(arg); }Copy the code

Which tryAcquire (…). The doAcquireInterruptibly method is implemented by FairSync and NonfairSync.

private void doAcquireInterruptibly(int arg)
    throws InterruptedException {
    final Node node = addWaiter(Node.EXCLUSIVE);
    boolean failed = true;
    try {
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                // Throw an interrupt exception
                throw newInterruptedException(); }}finally {
        if(failed) cancelAcquire(node); }}Copy the code

Guys, that looks a lot like code that doesn’t respond to interrupts, see the difference? When an interrupt signal is received, parkAndCheckInterrupt(…) The for method returns true, indicating an interrupt signal, no longer blocks, throws an exception, and breaks out of the for loop. Thus achieving the purpose of interruption.

Contrast between synchronized and ReentrantLock

Similarities:

  1. Can be used for thread synchronization;
  2. Both are reentrant locks
  3. Both have unfair locks

Difference:

  1. ReentrantLock responds to interrupts, but synchronized does not.
  2. ReentrantLock can wait out of time, but synchronized cannot.
  3. ReentrantLock can have fair locks, but synchronized does not.
  4. Both ReentrantLock and lock release require display invocation, while synchronized does not require display lock release.
  5. ReentrantLock provides a richer API for obtaining lock status;
  6. ReentrantLock is internally locked based on the queue synchronizer in AQS, while synchronized is locked by locking objects or classes.

Use:

The usage of synchronized has been analyzed in detail in the previous article, here only lists the use of lock, the code is as follows:

private static Lock lock = new ReentrantLock();
public static int lockValue = 0;

public static void increaseLock(a) {
    try {
        lock.lock();
        lockValue++;
    } catch (Exception ex) {

    } finally{ lock.unlock(); }}Copy the code

At this point, the content of this article is almost over, based on my own experience, when you understand AQS and ReentrantLock, it is important to keep in mind the template method design pattern, so that it is much clearer, so that you do not have a very confusing feeling.

For fair lock and fair lock flow chart, due to space constraints, not here to show, want to get the original hd map, please pay attention to the public number: Xiao said and reply to AQS.

reference

Java concurrency principle implementation Yu Chunlong