Whether it is fair or not fair lock, lock their implementation is dependent on AbstractQueuedSynchronizer, it provides a based on fifo queue implementation block the locks and the framework of synchronizers. Characteristics are as follows

  • State is represented only by an int. For ReentrantLock, it is the number of times the lock is held by the thread. When the number is 0, the lock is not held. When the number is positive, it is the number of times the lock is held
  • Exclusive mode (default) and shared mode are supported. In exclusive mode, acquiring a lock already owned by another thread will only fail, while in shared mode, multiple threads can succeed.

The lock () principle

AcquireQueued (addWaiter(Node.exclusive), arG) is executed when ReentrantLock fails to acquire the lock

private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Create a node that stores the current thread and the mode in which the lock is held. backup to full enq on failure Node pred = tail;if(pred ! = null) { node.prev = pred;if(compareAndSetTail(pred, node)) {//CAS sets the new node to the end of the queue if the current tail node has not been changed by other threads.returnnode; } } enq(node); // First team entryreturn node;
}
Copy the code

If the queue fails to get, add a waiting Node to the queue


private Node enq(final Node node) {
    for(;;) {// The CAS mechanism is used to implement lock-free operations, so you need to perform this operation until the CAS succeeds.if(t == null) {// Initialization occurs when the queue is created for the first time. The advantage of this is that when there is less contention, these operations will not actually occur and performance will be betterif (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                returnt; }}}}Copy the code

As you can see, joining the queue is to insert a new thread from the end of the queue. After joining the queue, it starts to try again and again until the lock is successfully acquired

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for(;;) { final Node p = node.predecessor(); // Execute the previous node of the current node firstif(p == head && tryAcquire(arG)) {// If the previous node of the current node is head, the thread that waits first will be processed firstsetHead(node); 
                p.next = null; // helpGC, which frees the reference of the current thread in the queue, is also known as' unqueue ''failed = false; Return interrupted; } / / execution here shows that there is competition, there is more than one thread is waiting for a lock if (shouldParkAfterFailedAcquire (p, node) && parkAndCheckInterrupt ()) / / in the interrupt for the current thread, when awakened, Continue the loop // If the thread is interrupted, set the interrupt flag, as opposed to doAcquireInterruptibly, which throws an exception directly, This is why lockInterruptibly throws an interrupt = true; } } finally { if (failed) cancelAcquire(node); }}Copy the code

As can be seen from the above, no matter whether the lock is a fair lock or an unfair lock, as long as the lock is placed in the wait queue, the execution is still the first to wait. The unfair lock is reflected in that the new thread ignores the already waiting thread. Therefore, fairness is reflected in the fact that the thread participating in the lock grab for the first time will wait for the thread already in the waiting queue. Unfair does not mean that the thread is randomly selected from the queue already waiting

ShouldParkAfterFailedAcquire source code is as follows

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; // Check the wait status of the previous nodeif(ws == node.signal) // We have tried to get the lock, so we can parkreturn true;
    if (ws > 0) {   
        do{// Remove all canceled threads from the queue node.prev = pred = pred.prev; }while (pred.waitStatus > 0);
        pred.next = node;
    } else{// The wait state of the previous node of the current thread must be 0 or PROGATE. This means that the current thread can try again to acquire the lock before park, which means that the previous Node may have just acquired the SIGNAL compareAndSetWaitStatus(pred, ws, Node.signal); }return false;
}

Copy the code

WaitStatus: indicates the waiting status. There are five types

  • SIGNAL:, indicating that its predecessor needs to execute unparking;
  • CANCELLED: Threads saved by the current node have been CANCELLED due to timeout or interruption;
  • CONDITION: The file is in the CONDITION queue and await is performed;
  • PROPAGATE: A shared lock needs to PROPAGATE the release signal to other nodes
  • 0: the state is not in the preceding 4. It may be that the signal has just been obtained and its value is 0, or it may be a newly created head node

ParkAndCheckInterrupt is primarily the park current thread

private final boolean parkAndCheckInterrupt() {// If no permission is obtained, the thread is blocked, and the unblocked state is as follows: //1 a thread called the unpark method on this thread //2 a thread interrupted this thread //3 This method returns for no reason. Based on this, the call must determine the condition of park, and when it returns, To set the interrupt state locksupport. park(this); // Returns the interrupted status of the threadreturn Thread.interrupted();
}
Copy the code

At this point lock() is done

Unlock () principle

When an UNLOCK is executed, ReentrentLock executes the corresponding Release

public final boolean release(int arg) {
    if(tryRelease(arg)) {tryRelease(arg) = head;if(h ! = null && h.waitStatus ! = 0) unparkSuccessor(h); //h.waitStatus == 0 indicates that the park has not been executed, so unpark is not requiredreturn true;
    }
    return false;
}
Copy the code

If the release succeeds, that is, all the locks held by the current thread have been released, then the unparksucceeded can be executed. The source code shows that unpark starts at the head, combining the principles of Lock, AQS itself is a first-in, first-out (FIFO) antecedent

private void unparkSuccessor(Node node) {
     int ws = node.waitStatus;
    if(ws < 0) compareAndSetWaitStatus(node, ws, 0); Node s = node.next; // It is possible that the thread has been cancelled, so it is possible to traverse the end of the thread to the last thread that has not been cancelledif (s == null || s.waitStatus > 0) {
        s = null;
        for(Node t = tail; t ! = null && t ! = node; t = t.prev)if(t.waitStatus <= 0) s = t; // Make sure the thread is not cancelled}if(s ! = null) LockSupport.unpark(s.thread); // restore thread}Copy the code

So unlock() ends

Lock and UNLOCK

  • Lock is essentially going to get the lock, get it, execute the logic down, otherwise put the current thread into sync queue, and then execute park
  • Unlock releases all the locks of the current thread, unpark the first thread to enter the sync queue, and complete the lock requirement for that thread

The principle of await

public final void await() throws InterruptedException {
    if(Thread.interrupted()) throw new InterruptedException(); // Add a new waiter to the condition queuewaitStatus will be marked as CONDITION Node Node = addConditionWaiter(); Int savedState = fullyRelease(node); int interruptMode = 0;while(! IsOnSyncQueue (node)) {// If the current thread is not in the lock queue, sleep it, when another thread is unlocking, unpark it, wake it up, and if it is in the SYN queue, proceed. Locksupport.park (this); locksupport.park (this);if((interruptMode = checkInterruptWhileWaiting(node)) ! = 0)break; // The thread is interrupted while waiting, exit} // the lock is contested again, equivalent to the lock operationif(acquireQueued(node, savedState) && interruptMode ! Returns interruptMode = REINTERRUPT; returns interruptMode = REINTERRUPT; returns interruptMode = interruptMode; returns interruptMode = REINTERRUPT; returns interruptMode = interruptMode; returns interruptMode = interruptMode;if(node.nextWaiter ! Waiters() = null) // Clear non-condition waiters (work as a non-condition unlinkCancelledWaiters(), while signal has a close operation that sets Conditon threads to non-condition unlinkCancelledWaiters();if(interruptMode ! = 0) reportInterruptAfterWait(interruptMode) reportInterruptAfterWait(interruptMode) }Copy the code

IsOnSyncQueue source code is as follows

final boolean isOnSyncQueue(Node node) {
    if(node. WaitStatus = = node. CONDITION | | node. The prev = = null) / / the node itself is invoked the await method, or not in the queue for locks, in which a [if there must be a front-facing node]return false; 
    if(node.next ! = null) // If the current node has the next node, then it must have performed enQ, i.e. acquired the lockreturn true; // If the CAS fails, node.rev may not exist, so it needs to be iterated from beginning to endreturn findNodeFromTail(node); 
}
Copy the code

CheckInterruptWhileWaiting source as follows

private int checkInterruptWhileWaiting(Node node) {
    return Thread.interrupted() ?
        (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
        0;
}
final boolean transferAfterCancelledWait(Node node) {
    if(compareAndSetWaitStatus(node, node.condition, 0)) {// The thread interrupts to retrieve the lock and set itwaitStatus is 0 so that subsequent threads can clear enq(node) from the Condition queue;return true;
    }
    while(! IsOnSyncQueue (node)) // If CAS fails, as long as the current node is not in SyncQueue, it spins and yields thread.yield () each time;return false;
}
Copy the code

As you can see, await is releasing the lock that the thread already has, putting iton a Conditon queue, and then blocking. Upon awakening, the lock is reacquired and threads in the Condition queue are cleared. At this point the await execution ends

The principle of singnal

public final void signal() {
    if(! IsHeldExclusively ()) / / only the current thread holds a lock, in order to release the throw new IllegalMonitorStateException (); Node first = firstWaiter;if(first ! = null)doSignal(first); Condition node} private void (condition node)doSignal(Node first) {
    do {
        if ( (firstWaiter = first.nextWaiter) == null)
            lastWaiter = null;
        first.nextWaiter = null;
    } while(! transferForSignal(first) && (first = firstWaiter) ! = null); } // Sync queue final Boolean transferForSignal(Node Node) {if(! compareAndSetWaitStatus(node, Node.CONDITION, 0))return false; //CAS sets the wait state to 0. Int ws = p.waitStatus; // Add the new node to the sync queue and return the original tail node.if(ws > 0 || ! CompareAndSetWaitStatus (p, ws, Node. SIGNAL)) / / reference shouldParkAfterFailedAcquire LockSupport. Unpark (Node. Thread); // If the previous node thread of the current node has been canceled, or the previous node thread of the current node has been canceledwaitIf Status fails to be set to SIGNAL, the current thread is immediately woken upreturn true;
}
Copy the code

As you can see, the most critical information for Signal is to remove the CONDITION state from the wait queue and add the thread to the SYNC queue, ending signal

Await and signal

  • Await: throw the current thread into the CONDITION queue, release all the locks it previously acquired in the SYNC queue, and wait park again.
  • Signal: Gets the head element of the Coedition queue, which releases the thread that entered the CONDITION queue first, puts it into the SYNC queue, and then unpark

Await unpark signal. If it is found to be in sync queue, try again to obtain the lock. If it succeeds, it becomes the lock owner

Note that only the first thread to enter the SYNC queue can attempt to acquire the lock