Deep Interpretation of the ReentrantLock Bottom Source

Catalog

  • Introduction to ReentrantLock

  • Fundamental knowledge paving

    • state property
    • Thread Holder Properties
    • Queue usage in ReentrantLock
  • Demo&Principle Analysis

    • Fair lock() method

    • Demo

    • Vernacular principles (interview dictation)

    • Detailed Principle

    • Summary of knowledge points

      • Summary of Life Track of FIFO Chain List

      • Summary of life trajectory of waitStatus attribute
    • unLock() method

    • Vernacular principles (interview dictation)
    • Detailed Principle

    • Fair lock() method

    • Demo
    • Vernacular principles (interview dictation)
    • Detailed Principle

    • lockInterruptibly() method

    • Demo
    • Vernacular principles (interview dictation)
    • Detailed Principle

    • tryLock() method

    • Demo
    • Vernacular principles (interview dictation)
    • Detailed Principle

    • tryLock(long timeout, TimeUnit unit) method

    • Demo
    • Vernacular principles (interview dictation)
    • Detailed Principle
  • Summary of interview questions

  • ReentrantLock Full Chinese Comment Runnable Code Download

Introduction to ReentrantLock

Re-entrainable locks in jdk concurrent packages are based on AQS (AbstractQueuedSynchronized), which has two implementations: fair locks (the order of locks on threads is entirely based on the order in which methods are called) and unfair locks (the order of locks on threads is not entirely based on the order in which methods are called).

ReentrantLock provides a variety of API s: fair/unfair Lock-lock() method, timed release lock-tryLock(long timeout, TimeUnit unit) method, interrupt interrupt blocking thread throws an InterruptedException exception, tryLock() returned directly from a failure to acquire a lock

This article is based on the open-jdk 1.8 explanation

Fundamental knowledge paving

state property

    //Synchronization status identification    
    private volatile int state;

A state of 0 indicates that no thread currently holds a lock; a state of 1 indicates that a thread holds a lock; and a state greater than 1 indicates the number of times a lock has been reentrated by the current thread because ReentrantLock is reentrant.

With volatile, the visibility of the state property value is guaranteed (visibility is the property that always guarantees the latest value when the property value is obtained).

Thread Holder Properties

    //Current Thread Holder Identity
    private transient Thread exclusiveOwnerThread;

This property is of type Thread and identifies the thread currently holding the lock.

Queue usage in ReentrantLock

The queue in ReentrantLock is FIFO. What is the data structure of this queue in order to achieve a fair lock, ensure the locking order of threads, and also store elements?

In ReentrantLock, a Node class is defined to represent threads as well as components of the chain table. The prev attribute of Node points to the previous node (representing the previous thread entering the queue), and the next attribute points to the next node (representing the next thread entering the queue), which forms a singleChain lists; AQS also maintains the head and tail attributes of the Node type, which are null by default, representing the head and end nodes respectively. These two attributes make it easy to get the head and end nodes in subsequent logic to make logical processing and judgment.

The following are the core properties of the Node class:

    //Point to the previous node   
    volatile Node prev; 

    //Point to the next node   
    volatile Node next; 

    //Pointing to the current node represents a thread    
    volatile Thread thread; 

    /*
        Wait state, for the ReentrantLock method, has three values, why is it for?
      Since this property is inherited from AQS and is used by other concurrent packages, ReentrantLock only partially uses it
        What are the values and meanings for ReentrantLock?
      0:Initialize default or invalid state, i.e. member variable definition int type defaults to 0, or indicates unlocked
      -1(SIGNAL):Marking the thread represented by the current node requires the thread of the next node to wake up after releasing the lock, identifying whether to wake up with the current value
      1(CANCELLED):The thread waiting in the synchronization queue did not end properly (an interrupt exception or other unpredictable exception occurred), and was marked as cancelled
     */
    volatile int waitStatus; 

Demo&Principle Analysis

Unfair lock() method

Demo

    public void testReentrantLock() {    
     //Multiple threads use the same ReentrantLock object with the same lock
      Lock lock = new ReentrantLock();      
      lock.lock();  
      System.out.println("Handle");
      lock.unlock();    
    }

Vernacular principles (interview dictation)

Initialize by calling the ReentrantLock parameterless constructor, which is implemented by default with an unfair lock; call the lock method:

Step 1, Preempt Lock

  1. When entering the lock method, call the cas method to preempt the lock (change the state from 0 to 1), regardless of whether or not a thread is queued

    1. If the modification is successful, update the current thread holder property to the current thread

    2. If the modification is unsuccessful, determine if the current thread holder is the current thread, but before that it is possible for other threads to release the lock and the state changes to 0, so let's also check the value of the state

      1. If 0, call the cas method again to try to lock, regardless of whether or not a thread is queued

        1. If the lock is successful, modify the current thread holder property to return the lock success
        2. Enter join queue process if lock fails
      2. If the state is not zero, determine if the thread holder is the current thread

        1. If the current thread, add a state to 1, increment the number of entries, and return to lock success
        2. Enter the join queue process if it is not the current thread

Step 2: Failed to preempt lock and join queue

  1. Initialize the Node node representing the current thread to determine whether the chain list is initialized by determining whether the tail node is null
    1. If the chain table is not initialized, a node of type Node that does not represent any thread is constructed as the head node, and the cas method is called to assign to the head and tail variables. In this case, the chain table has only one node, that is, the head node is the end node.
    2. If the list of chains has been initialized, assign the prev attribute of the node to the end of the previous list of chains, assign the next attribute of the end of the previous list to the node, and assign the tail variable to the node

Step 3. After joining the queue, spin 1 to 2 times to try to acquire the lock. If the lock is no longer available, the thread is blocked until it is waked up and the lock is successfully acquired

  1. Determines whether the prev attribute of the node (the previous node) is a head variable (the head node)
    1. If it is a header node, try to acquire the lock again
      1. If the lock is acquired successfully, set the current node to the head variable (the head node), and assign the next attribute of the old head node to null in order to speed up the GC's old head node
      2. If acquiring a lock is unsuccessful, try blocking the thread
  2. If it is not a header node or the acquisition of a lock fails, change the waitStatus of the prev node of the node node from the default value of 0 to -1 using the cas method, marking that the thread represented by the current node needs to wake up the thread of the next node after releasing the lock
  3. Then when the node's prev node waitStatus value is -1, the LockSupport.park(this) method is called to block the current thread (which is blocked indefinitely) after which an unlock operation can be called from the previous node thread or wake up by calling the interrupt method on the current thread (note here that even ifWake up by the front node, or possibly because of unfair lock implementation logic, after waking up, the lock is acquired by other threads. If the interrupt method wakes up and temporarily clears the current interrupt state, spin again for the third step of logic
  4. Restore interrupt state after successful lock
  5. Return Lock Success

Interrupt(); Calling the interrupt() method of another thread in one thread will only set that thread to interrupt state, not really interrupt the thread. After deciding whether the thread is interrupt or not, the developer will define how to handle the interrupt thread and will throw InterruptedExceptio in generalN Exception

isInterrupted(boolean ClearInterrupted); returns whether it is in an interrupt state, ClearInterrupted is true, the interrupt state is cleared, and vice versa, the interrupt state is preserved

Detailed Principle

Before reading the detailed principles, read against the source code to enhance your understanding (a link to run code downloads with Chinese comments is included at the end of this article)

After entering the lock method, call the cas method to preempt the lock (change the state from 0 to 1), regardless of whether there are threads queuing; if the modification is successful, update the current thread holder property to the current thread; if the modification is unsuccessful, call the acquire method;

    final void lock() {    
        //Use cas atomic method directly, if state is 0 then change to 1 instead of queuing in FIFO queue    
        if (compareAndSetState(0, 1))        
            //If the lock succeeds, modify the lock holder to the current thread object and the lock succeeds              
            setExclusiveOwnerThread(Thread.currentThread());   
        else        
            //If it fails, the following logic is executed (including logic to determine whether a thread is reentry, to try locking again, to block a thread, to be waked up to acquire a lock, and so on)   
           acquire(1);
    }

After entering the acquire method, try to acquire the lock again. If the acquire fails again, initialize the node representing the current thread, join the queue and block until it is awakened (the reason to attempt two acquisition actions here is to give full play to the unfair lock performance advantage)

    public final void acquire(int arg) {
        // 1.tryAcquire: Try locking again, true: Identity lock succeeded; false: Identity lock failed
        if (!tryAcquire(arg) &&
                /*
                 2.addWaiter: Encapsulate threads as nodes and place them in FIFO queues;
                 3.acquireQueued: 
                 Spin to acquire the lock and block the thread if another attempt to acquire the lock fails;
                 Wait for the previous thread in the queue to unlock, wake up the thread, and acquire the lock successfully
                 */
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            //Set the state of the thread to interrupt (what this code does in acquireQueued)
            selfInterrupt();
    }

After entering 1.tryAcquire, if the wireless process holds a lock at this time, try to acquire the lock again: 1. If acquisition fails, enter the queue; 2. Otherwise, return to acquire success; if a thread holds a lock, determine if it is the current thread that holds the lock: 1. If it is, increase the number of entries; 2. If it is not, enter the queue

    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);
    }

    final boolean nonfairTryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        //If no thread currently holds a lock, try to acquire the lock again. After acquiring the lock successfully, modify the current lock holder and return to the lock successfully
        int c = getState();
        if (c == 0) {
            if (compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);
                return true;
            }
        }
        //If the current lock is held by the current thread, the number of entries is accumulated and the lock is returned successfully
        else if (current == getExclusiveOwnerThread()) {
            //Assignments are made using operations that do not support atomicity because only threads that currently have locks can modify this state, so no other thread modifications will occur
            int nextc = c + acquires;
            if (nextc < 0) // overflow
                throw new Error("Maximum lock count exceeded");
            setState(nextc);
            return true;
        }
        return false;
    }

After entering 2.addWaiter, create a node representing the current thread and append the end of the list

    /**
     * Description: Initialize the node and append the end of the chain
     *
     * @param mode Identifying whether the node of the current thread is in exclusive or shared mode does not make sense for code logic
     * @return Node representing the current thread
     */
    private Node addWaiter(Node mode) {
        //Initialize the object NOde in the list, representing the current thread
        Node node = new Node(Thread.currentThread(), mode);

        Node pred = tail;
        //If the chain list is initialized (the last node is not empty), place the current node directly behind the end node's back interface
        if (pred != null) {
            //Assign the prev attribute of the node to the end of the previous list of chains
            node.prev = pred;
            //  Using the atomic method, the tail variable is assigned to a node
            // (Note: Only the variables that record the tail nodes are modified here, not the associations between the linked list nodes)
            if (compareAndSetTail(pred, node)) {//#1
                //Assigning the next attribute of the end node of the previous list to the node node (the cas atom method is not used here because all other threads that want to modify the next attribute of t must successfully get t, and t is only possible if the thread that successfully executes compareAndSetTail(t, node) is at that point in time when T represents the end nodeOwned)
                pred.next = node;
                return node;
            }
        }
        //If the list has not been initialized or because of intense lock competition, the compareAndSetTail execution at #1 fails, and the list will be initialized or spinned until the compareAndSetTail execution succeeds.
        enq(node);
        return node;
    }
    /**
     * If the list has not been initialized or because of intense lock competition, the compareAndSetTail execution at #1 fails, and the list will be initialized or spinned until the compareAndSetTail execution succeeds.
     */
    private Node enq(final Node node) {
        for (; ; ) {
            Node t = tail;
        //If the chain list is not initialized (the trailing node variable is empty), initialization is required
        if (t == null) { // Must initialize #2
            //Initialize node (does not represent any thread) as head variable
            if (compareAndSetHead(new Node()))
                //Chain list with only one node, head is tail
                tail = head;
        } else {
            //There are two things that will get here:
            // 1. The list has been initialized in another thread, but the competing execution of compareAndSetTail failed in this thread
            // 2. The chain list is not initialized when the current thread executes the addWaiter method, but it is initialized by other threads when the #2 code above is executed
            //Assign the prev attribute of the node to the end of the previous list of chains
            node.prev = t;
            //Attempt to modify tail variable to current thread node again, spin to change until successful
            if (compareAndSetTail(t, node)) {
                // Assign the next attribute of the end node of the previous list to the node node
                t.next = node;
                return t;
            }
        }
    }

After entering 3.acquireQueued, the spin attempts to acquire the lock once or twice, and if the lock is no longer available, the thread is blocked until it is successfully acquired by wakeup

  • The remaining 70% of the content, add my WeChat, send 49.9 yuan red envelope can be viewed, if the above content has met your needs, appreciate it, you can also yo!
  • If there are technical blindnesses or unclear descriptions, inform me that they will be modified in time
  • After paying to read, if you find the source code explanation error, let me know, the situation is true, after modifying the article, return 10%/article
  • Personal mailbox: ningw1@126.com, note caption when adding WeChat

Tags: Programming Attribute JDK

Posted on Wed, 11 Sep 2019 10:19:54 -0700 by mxicoders