Reentrantlock

Reentrantlock实现了Lock接口，Lock接口时Java定义的锁的规范，Reentrantlock基于AbstractQueuedSynchronizer（简称aqs）实现的，拥有Synchronized关键字的所有功能，同时还拥有锁中断，公平锁与非公平锁（synchronized只能是非公平锁）

STATE

state是AQS的一个属性，初始值为0，线程在尝试获取锁是，通过cas将state的值从0改为1，若修改成功，则获取锁，否则添加到clh队列中，同时state还记录了重入的状态，每重入一次，state则加1

CLH

什么是CLH

CLH全称是Craig、Landin and Hagersten 队列，是单向链表实现的队列，**申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱节点释放了锁就结束自旋。**AQS实现的是一个双向链表实现的队列，属于CLH的变体，后面还是简称clh，结构如下图

AQS为什么要采用双向链表

因为原本的CLH只需要通过自旋获取上一个节点的状态，而上一个节点无需获取下一个节点的状态，所以单向即可实现，而AQS的实现是涉及到挂起的，挂起的线程必须通过上一个节点的线程唤醒，所以上一个线程需要获取到下一个节点的线程，故AQS实现的是双向链表
因为Reentrantlock中，线程获取锁的过程中可以中断，中断后的线程需要从列表中溢出，使用双向列表，可以直接将上一个节点指向下一个节点，以及将下一个节点指向上一个节点，避免了遍历列表带来的开销
Reentrantlock，线程加入队列中时，需要判断前置节点，如果前置节点是head，则直接竞争锁，如果前置节点不是head，则判断前置节点线程状态，确保前置节点线程状态正常，避免异常线程影响整体执行

公平锁与非公平锁

ReentranLock的公平锁与非公平锁通过FairSync与NonfairSync实现，两者都继承Sync

abstract static class Sync extends AbstractQueuedSynchronizer {
     private static final long serialVersionUID = -5179523762034025860L;

     /**
      * Performs {@link Lock#lock}. The main reason for subclassing
      * is to allow fast path for nonfair version.
      */
     abstract void lock();

     /**
      * Performs non-fair tryLock.  tryAcquire is implemented in
      * subclasses, but both need nonfair try for trylock method.
      */
     final boolean nonfairTryAcquire(int acquires) {
         final Thread current = Thread.currentThread();
         int c = getState();
         if (c == 0) {
             if (compareAndSetState(0, acquires)) {//非公平锁在这里是直接竞争
                 setExclusiveOwnerThread(current);
                 return true;
             }
         }
         else if (current == getExclusiveOwnerThread()) {
             int nextc = c + acquires;
             if (nextc < 0) // overflow
                 throw new Error("Maximum lock count exceeded");
             setState(nextc);
             return true;
         }
         return false;
     }

     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);
         return free;
     }

     protected final boolean isHeldExclusively() {
         // While we must in general read state before owner,
         // we don't need to do so to check if current thread is owner
         return getExclusiveOwnerThread() == Thread.currentThread();
     }

     final ConditionObject newCondition() {
         return new ConditionObject();
     }

     // Methods relayed from outer class

     final Thread getOwner() {
         return getState() == 0 ? null : getExclusiveOwnerThread();
     }

     final int getHoldCount() {
         return isHeldExclusively() ? getState() : 0;
     }

     final boolean isLocked() {
         return getState() != 0;
     }

     /**
      * Reconstitutes the instance from a stream (that is, deserializes it).
      */
     private void readObject(java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
         setState(0); // reset to unlocked state
     }
 }

static final class NonfairSync extends Sync {
    private static final long serialVersionUID = 7316153563782823691L;

    /**
     * Performs lock.  Try immediate barge, backing up to normal
     * acquire on failure.
     */
    final void lock() {
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1);
    }

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

static final class FairSync extends Sync {
     private static final long serialVersionUID = -3000897897090466540L;

     final void lock() {
         acquire(1);
     }

     /**
      * Fair version of tryAcquire.  Don't grant access unless
      * recursive call or no waiters or is first.
      */
     protected final boolean tryAcquire(int acquires) {
         final Thread current = Thread.currentThread();
         int c = getState();
         if (c == 0) {
             if (!hasQueuedPredecessors() &&
                 compareAndSetState(0, acquires)) {//公平锁在这里要先通过hasQueuedPredecessors方法判断该节点前置节点是否是head
                 setExclusiveOwnerThread(current);
                 return true;
             }
         }
         else if (current == getExclusiveOwnerThread()) {
             int nextc = c + acquires;
             if (nextc < 0)
                 throw new Error("Maximum lock count exceeded");
             setState(nextc);
             return true;
         }
         return false;
     }
 }

public final boolean hasQueuedPredecessors() {
    // 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; // Read fields in reverse initialization order
    Node h = head;
    Node s;
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

公平锁和非公平锁的区别就在上述代码，非公平锁在获取锁之前，会先尝试将state设为0以获取锁。公平锁在尝试获取锁的时候是先判断队列中没有节点，没有节点则尝试获取锁，否则加入队列，而非公平锁在尝试获取锁时，不需要管队列有没有节点，直接尝试获取锁，获取失败再加入队列，所以非公平锁在调用lock方法时，在真正加入队列之前，会比公平锁多两次竞争的机会

非公平锁因为有多个线程同时竞争，效率比公平锁高，而公平锁可以避免线程因为长期竞争不到锁，而发生线程饥饿，ReentrantLock的非公平锁不是绝对的非公平，首次竞争失败后的线程还是要加入到队列中，按照公平锁的逻辑获取锁

读锁和写锁

读写锁由java.util.concurrent.locks.ReentrantReadWriteLock实现的，读写锁的意义并不是字面上的控制某个属性的读写，而是指锁本身的权限

1
2
3

ReentrantReadWriteLock reentrantReadWriteLock = new ReentrantReadWriteLock();
ReentrantReadWriteLock.ReadLock readLock = reentrantReadWriteLock.readLock();
ReentrantReadWriteLock.WriteLock writeLock = reentrantReadWriteLock.writeLock();

读锁和写锁有以下特点

读锁可以多个线程进入，但是如果有线程进入读锁代码，其他线程就无法进入写锁的代码
如果写锁被线程持有，那读锁就无法被线程持有
总结起来就是，读锁和写锁互斥，写锁与写锁互斥，读锁与读锁不互斥（前提读锁和写锁属于同一个ReentrantReadWriteLock）

可中断锁

可中断的锁原理就是在进入方法的方法以及排队过程中判断线程的状态，如果已中断则退出排队并抛出中断错误，退出锁竞争，并且用户可自己通过检测异常实现线程中断

超时获取

超时获取在排队过程通过时间判断是否已经超出预期，如果超出预期，退出排队并抛出中断异常，实现退出锁竞争

等待与唤醒

ReentrantLock的等待与唤醒是通过实现Condition完成的，主要逻辑是内部维护了一个链表，每次有线程使用await方法，就加入队列（加入队列实际逻辑比较复杂），调用signal的时候换默认唤醒链表头部的节点

主要是通过一下两个方法

public final void await() throws InterruptedException {
if (Thread.interrupted())
    throw new InterruptedException();
Node node = addConditionWaiter();
int savedState = fullyRelease(node);
int interruptMode = 0;
while (!isOnSyncQueue(node)) {
    LockSupport.park(this);
    if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
        break;
}
if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
    interruptMode = REINTERRUPT;
if (node.nextWaiter != null) // clean up if cancelled
    unlinkCancelledWaiters();
if (interruptMode != 0)
    reportInterruptAfterWait(interruptMode);
}

await对标于Object.wait，等待的作用

public final void signal() {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    Node first = firstWaiter;
    if (first != null)
        doSignal(first);
}

signal对标于Object.notify，唤醒的作用，signalAll对标Object.notifyAll

ReentrantLock lock方法

这里以非公平锁为例介绍lock方法完整流程

final void lock() {
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

非公平锁先通过compareAndSetState尝试获取锁，这是一个cas方法，获取失败后再调用acquire方法

public final void acquire(int arg) {
if (!tryAcquire(arg) &&
    acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}

acquire方法中，先通过tryAcquire方法尝试获取一次锁，获取失败后，加入队列排队，如果获取成功，则跳出判断（如果成功，!tryAcquire(arg)为false，那么会直接跳出判断）

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

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

这两个方法就是尝试获取锁的主要代码了，基本逻辑就是先判断state的值，如果等于0就尝试竞争，否则判断是否是重入锁

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

这个方法是再队列中排队的逻辑，主要是判断上一个节点是不是head，然后判断是否进行park（阻塞）操作，和Synchronized的阻塞是一样的，都是调用操作系统的方法

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */
        return true;
    if (ws > 0) {
        /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

这个方法主要是判断是否进行park操作，如果当前节点之前的节点存在waitStatus大于0（即waitStatus为CANCELLED），就得先将之前的节点剔除掉，然后返回false，在acquireQueued方法中循环到下一次再进行判断

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);
    return Thread.interrupted();
}

这个方法就是调用park方法阻塞线程（最终调用的是sun.misc.Unsafe#park（本地方法）），并且在被唤醒后返回线程中断状态

private void cancelAcquire(Node node) {
if (node == null)
    return;

node.thread = null;

Node pred = node.prev;
while (pred.waitStatus > 0)
node.prev = pred = pred.prev;

Node predNext = pred.next;

node.waitStatus = Node.CANCELLED;

if (node == tail && compareAndSetTail(node, pred)) {
    compareAndSetNext(pred, predNext, null);
} else {
    int ws;
    if (pred != head &&
        ((ws = pred.waitStatus) == Node.SIGNAL ||
         (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
        pred.thread != null) {
        Node next = node.next;
        if (next != null && next.waitStatus <= 0)
            compareAndSetNext(pred, predNext, next);
    } else {
        unparkSuccessor(node);
    }

    node.next = node; // help GC
}
}

这个方法就是取消获取，基本逻辑就是将当前节点的上一个节点向下的指针指向当前节点的下一个节点，但是向上的指针不变，并将当前节点置为CANCELLED，这样下一个节点在获取锁时会将当前节点剔除掉

ReentrantLock unLock方法

1
2
3

public void unlock() {
    sync.release(1);
}

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

realease方法中主要就是判断是否释放锁成功，成功就唤醒head的下一个节点，让下一个节点重新竞争

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);
return free;
}

tryRelease主要是判断是否是重入锁退出，如果是则state减一，返回false，如果不是，则返回true

private void unparkSuccessor(Node node) {

int ws = node.waitStatus;
if (ws < 0)
    compareAndSetWaitStatus(node, ws, 0);

Node s = node.next;
if (s == null || s.waitStatus > 0) {
    s = null;
    for (Node t = tail; t != null && t != node; t = t.prev)
    if (t.waitStatus <= 0)
        s = t;
}
if (s != null)
    LockSupport.unpark(s.thread);
}

unparkSuccessor主要是唤醒下一个线程，如果下一个线程已经取消掉了，则从tail一直往前推，直到不满足循环要求，退出循环（这个地方不是找到正常的节点就退出循环，而是要到不满足（t != null && t != node）的时候（即找到当前节点下一个正常的节点）才退出循环），如果这个时候找到正常的节点了就唤醒，没有就直接返回

Java Reentrantlock