ReentrantLock实现原理分析

一、锁设计猜想 1.1 设计目的

满足线程的互斥特性
意味着同一个时刻，只允许一个线程进入到加锁的代码中。多线程环境下，线程的顺序访问。

1.2 设计过程猜想

• 一定会涉及到锁的抢占，需要有一个标记来实现互斥。 全局变量（0，1)。
• 抢占到了锁，怎么处理(不需要处理)。
• 没抢占到锁，怎么处理
  　a、需要等待（让处于排队中的线程，如果没有抢占到锁，则直接先阻塞->释放CPU资源）。
  　　wait/notify(线程通信的机制，无法指定唤醒某个线程)
  　　LockSupport.park/unpark（阻塞一个指定的线程，唤醒一个指定的线程）
  　　Condition
  　b、需要排队（允许有N个线程被阻塞，此时线程处于活跃状态)。
  　　通过一个数据结构，把这N个排队的线程存储起来。
• 抢占到锁的释放过程，如何处理
  　LockSupport.unpark() -> 唤醒处于队列中的指定线程。
• 锁抢占的公平性（是否允许插队)
  　公平
  　非公平
  

二、锁实现源码分析 2.1 公平锁和非公平锁

公平锁

final void lock() {
  acquire(1); //抢占1把锁.
}
public final void acquire(int arg) {  -> AQS里面的方法
  if (!tryAcquire(arg) &&
    acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}
protected final boolean tryAcquire(int acquires) {
  final Thread current = Thread.currentThread();
  int c = getState();
  if (c == 0) { //表示无锁状态
    if (!hasQueuedPredecessors() &&
      compareAndSetState(0, acquires)) { //CAS（#Lock） -> 原子 *** 作| 实现互斥的判断
      setExclusiveOwnerThread(current); //把获得锁的线程保存到exclusiveOwnerThread中
      return true;
   }
 }
  //如果当前获得锁的线程和当前抢占锁的线程是同一个，表示重入
  else if (current == getExclusiveOwnerThread()) {
    int nextc = c + acquires; //增加重入次数.
    if (nextc < 0)
      throw new Error("Maximum lock count exceeded");
    setState(nextc); //保存state
    return true;
 }
  return false;
}

非公平锁

final void lock() {
  //不管当前AQS队列中是否有排队的情况，先去插队
  if (compareAndSetState(0, 1)) //返回false表示抢占锁失败
    setExclusiveOwnerThread(Thread.currentThread());
  else
    acquire(1);
}
public final void acquire(int arg) {  --AQS
  if (!tryAcquire(arg) &&
    acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
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) {
    //hasQueuedPredecessors
    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;
}

2.2 加入队列并进行自旋等待

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

acquireQueued(addWaiter(Node.EXCLUSIVE), arg)

• addWaiter(Node.EXCLUSIVE) -> 添加一个互斥锁的节点
• acquireQueued() -> 自旋锁和阻塞的 *** 作

private Node addWaiter(Node mode) {
  //把当前线程封装成一个Node节点。
  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;
}
private Node enq(final Node node) {
for (;;) {//自旋
    Node t = tail;
    if (t == null) { // Must initialize
      //初始化一个head节点
      if (compareAndSetHead(new Node()))
        tail = head;
   } else {
      node.prev = t;
      if (compareAndSetTail(t, node)) {
        t.next = node;
        return t;
     }
   }
 }
}

//node表示当前来抢占锁的线程，有可能是ThreadB、 ThreadC。。
final boolean acquireQueued(final Node node, int arg) {
  boolean failed = true;
  try {
    boolean interrupted = false;
    for (;;) { //自旋
     
      //begin ->尝试去获得锁(如果是非公平锁)
      final Node p = node.predecessor();
      if (p == head && tryAcquire(arg)) { //如果返回true，则不需要等待，直接返
回。
        setHead(node);
        p.next = null; // help GC
        failed = false;
        return interrupted;
     }
      //end
      //否则，让线程去阻塞(park)
      if (shouldParkAfterFailedAcquire(p, node) &&
        parkAndCheckInterrupt()) //LockSupport.park
        interrupted = true;
   }
 } finally {
    if (failed)
      cancelAcquire(node);
 }
}

//ThreadB、 ThreadC、ThreadD、ThreadE -> 都会阻塞在下面这个代码的位置.
private final boolean parkAndCheckInterrupt() {
  LockSupport.park(this);  //被唤醒. (interrupt()->)
  return Thread.interrupted(); //中断状态（是否因为中断被唤醒的.）
}

2.3 unlock

public final boolean release(int arg) {
  if (tryRelease(arg)) {
    Node h = head; //得到当前AQS队列中的head节点。
    if (h != null && h.waitStatus != 0) //head节点不为空
      unparkSuccessor(h); //
    return true;
 }
  return false;
}

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0) //表示可以唤醒状态
      compareAndSetWaitStatus(node, ws, 0); //恢复成0
    Node s = node.next;
    if (s == null || s.waitStatus > 0) { //说明ThreadB这个线程可能已经被销毁，或
者出现异常...
      s = null;
      //从tail -> head进行遍历.
      for (Node t = tail; t != null && t != node; t = t.prev)
        if (t.waitStatus <= 0) //查找到小于等于0的节点
          s = t;
   }
    if (s != null)
      LockSupport.unpark(s.thread);  //封装在Node中的被阻塞的线程。ThreadB、ThreadC。
 }