ReentrantLock 实现原理

面试中遇到“ ReentrantLock 实现原理？”这个问题，我们应该怎么回答？是否直接就开始介绍 AQS, CLH 队列，这些高大上的词语。这样的回答会给面试官两个不好的印象：

• 问题回答没有逻辑，没有解释 ReentrantLock 与 AQS 等关系。
• 有死记硬背没有自己理解之嫌。

因此在这里提供一个回答问题的思路：按照功能介绍，需求分析，需求实现，源码实现，实现总结，共5步进行回答。这样有什么好处呢？

• 回答具有逻辑。按照使用到原理顺序回答问题，符合人的思维逻辑。
• 有自己的思考。在需求实现一节里详细介绍了如果自己来实现这些功能，会是怎么样的。
• 易于记忆。先是介绍怎么使用（功能介绍），然后是列举 ReentrantLock 类的方法和这些方法具有什么性质（需求分析），接下来是实现这些方法和功能（需求实现），最后是 JDK 怎么实现这些方法和功能的（源码实现）。

1.功能简介

1.1 ReentrantLock 是什么？

ReentrantLock 是一个可重入互斥锁，是 Lock 接口的实现类，是控制线程之间同步访问共享资源的一种方式。

1.2 为什么要使用 ReentrantLock？

ReentrantLock 用来保证线程安全。线程安全是在多线程并发访问共享资源时，通过同步机制协调各线程执行，来确保得到正确结果。

1.3 什么时候使用 ReentrantLock？

在需要控制线程之间同步访问共享资源时使用 Lock，但是只有以上需求时，我们完全可以使用 synchronized，没有必要使用 ReentrantLock。因此，当还有下面需求时才考虑使用 ReentrantLock ：

• 阻塞可中断；当阻塞等待获取锁时，线程中断，可以中断阻塞。
• 公平锁；公平锁是指按照线程访问锁的先后顺序获取锁，synchronized 是非公平锁，所以要使用公平锁只能使用 ReentrantLock。
• 选择性通知（唤醒）；多线程有等待/通知（wait，notify/notifyAll）功能，但是“通知“只能随机唤醒线程，而使用 ReentrantLock Condition 可以唤醒指定线程。

1.4 怎么使用ReentrantLock？

• 1.获取锁释放锁例子

  Lock l = ...;
  l.lock();
  try {
    // access the resource protected by this lock
  } finally {
    l.unlock();
  }}
  

• 2.阻塞可中断例子

  Lock l = ...;
  try {
    l.lockInterruptibly();
    try {
      // access the resource protected by this lock
    } finally {
      l.unlock();
    }}
  } catch (InterruptedException e){
    // 中断后处理
  }
  

• 3.公平锁例子

  Lock l = new ReentransLock(true);
  

• 4.选择性通知
  假设我们有一个支持put和take方法的有界缓冲区。如果尝试在空缓冲区上执行take，那么线程将阻塞，直到某个项可用为止；如果试图在已满的缓冲区上执行put，那么线程将阻塞，直到有可用的空间为止。我们希望在单独的等待集中保持等待put线程和take线程，这样我们就可以使用优化，即当缓冲区中的项或空间变为可用时，一次只通知一个线程。这可以使用两个Condition实例来实现。

  public class BoundedBuffer {
  final Lock lock = new ReentrantLock();
  final Condition notFull  = lock.newCondition();
  final Condition notEmpty = lock.newCondition();
  
      final Object[] items = new Object[100];
      int putptr, takeptr, count;
  
      public void put(Object x) throws InterruptedException {
          lock.lock();
          try {
              while (count == items.length)
                  notFull.await();
              items[putptr] = x;
              if (++putptr == items.length) putptr = 0;
              ++count;
              notEmpty.signal();
          } finally {
              lock.unlock();
          }
      }
  
      public Object take() throws InterruptedException {
          lock.lock();
          try {
              while (count == 0)
                  notEmpty.await();
              Object x = items[takeptr];
              if (++takeptr == items.length) takeptr = 0;
              --count;
              notFull.signal();
              return x;
          } finally {
              lock.unlock();
          }
      }
  }
  

2.需求分析

我们根据 ReentrantLock 定义的方法，将这些方法具有的特性进行分析，并拆分为每个小的需求点，通过实现小的需求点，并组合，最终实现 ReentrantLock 的功能。这样做可以降低实现难度，也可以简化实现原理。

• 构造函数
  • 公平锁，线程按照申请锁的顺序获取锁，先进先出。
  • 非公平锁，不是申请锁的顺序获取锁，可能最后申请锁反而先获取锁。
• lock()
  • 有阻塞获取锁，当能获取到锁时，方法返回；当不能获取到锁时，线程等待（阻塞）直到获取到锁。它功能可以分解为：无阻塞获取锁+阻塞。
  • 可重入，获取到锁的线程可以多次获取到锁。
• lockInterruptibly()
  • 有阻塞获取锁。
  • 可重入。
  • 阻塞可中断，线程等待（阻塞）获取锁期间，可以中断等待。
• tryLock()
  • 无阻塞获取锁，当不能获取到锁时，方法返回false，没有阻塞的状态。
  • 可重入。
• tryLock(long, TimeUnit)
  • 有阻塞（一段时间）获取锁，当能获取到锁时，方法返回；当不能获取到锁时，线程等待（阻塞）一段时间，当过了这个时间还没能获取到锁，将中断阻塞。
  • 可重入。
  • 阻塞可中断。
• unlock()
  • 释放锁。
  • 解除阻塞，通知其他线程解除阻塞，尝试获取锁。
• newCondition()

3.需求实现

根据需求分析，探讨实现每个需求的原理。

• 公平锁
  使用线程安全队列按照线程执行 lock 方法的先后顺序添加进队列。

• 非公平锁
  随机让阻塞线程获取锁。

• 无阻塞获取锁
  使用 int state 变量作为锁状态的标志，0表示没有线程占用锁，1表示有线程占用锁。获取锁的伪码如下：

  private int state;
  public boolean tryLock(){
    if state == 0
      state = 1;
      return true;
    else
      return false;
  }
  

  这样会有两个问题：

  • 1.判断 state==0 and state=1是非原子操作（执行两步）会有线程安全问题。
  • 2.state 会出现一个线程修改时，另一个线程无法获取到最新值的情况，即存在可见性问题。

  解决办法：

  • 1.unsafe.compareAndSwapInt(this, stateOffset, 0, 1)，CAS 保证原子性。
  • 2.private volatile int state，volatile 保证可见性。

  所以最终伪码：

  private volatile int state;
  public boolean tryLock(){
    return unsafe.compareAndSwapInt(this, stateOffset, 0, 1);
  }
  

• 阻塞
  有5种方法实现阻塞：

  • while(time>0)这种方法占用 CPU 资源，不推荐。
  • Object.wait(timeout)需配合 synchronized 使用，不推荐。
  • Thread.join实现较为复杂，不推荐。
  • Thread.sleep实现较为复杂，不推荐。
  • UNSAFE.park(false, 0) LockSupport.park()推荐。

• 可重入
  使用 Thread exclusiveOwnerThread变量存当前占用锁的线程，当线程再次获取锁时，将 state++。伪码如下：

  private volatile int state;
  private transient Thread exclusiveOwnerThread;
  if (current == exclusiveOwnerThread) {
    state ++;
    return true;
  }
  

• 阻塞指定时间
  在实现“互斥---一直阻塞”时，已经列举5种方法，并且推荐UNSAFE.park(false, 0) LockSupport.park()。所以为保持实现方法统一，推荐使用：

  • UNSAFE.park(false, nanos)
  • LockSupport.parkNanos(blocker, nanos)
  • LockSupport.parkUntil(blocker, deadline)

• 解锁
  只有持有锁的线程才能释放锁，当释放锁时state--，伪码如下：

  private volatile int state;
  public void unlock() {
    if (current == exclusiveOwnerThread) {
      state --;
    }
  }
  

• 解除阻塞
  解除阻塞和实现阻塞方法对应，方法如下：

  • UNSAFE.unpark(thread)
  • LockSupport.unpark(thread)

• 响应中断
  线程中断时调用 Thread.interrupt() ，LockSupport.park() 会响应中断，解除阻塞。

• newCondition
  先不考虑，比较复杂，需单独写一篇文章。

4.源码实现

通过阅读源码，分析上面列出的需求，来分析源码是怎么实现需求的。

• 公平锁
  CLH，线程安全的双向链表。

• 非公平锁
  非公平锁执行 lock 方法时立刻尝试获取锁，而不是像公平锁一样进行排队。

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

• 无阻塞获取锁
  CAS方式获取锁，unsafe.compareAndSwapInt(this, stateOffset, expect, update)

• 阻塞
  LockSupport.park()

• 可重入
  获取锁的持有线程，与当前线程比较，判断是否相等，相等即可获取锁，并且修改 state。state=0表示没有线程获取锁；state=num表示线程获取锁的次数为num，释放锁时需要释放num次。

  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;
  }
  

• 阻塞指定时间
  LockSupport.parkNanos(this, nanosTimeout)

• 解锁
  解锁需要做如下步骤：

  • state -= releases；
  • setExclusiveOwnerThread(null)。

  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;
  }
  

• 解除阻塞
  按照 CHL 队列顺序，通知下一个线程解除阻塞 LockSupport.unpark(s.thread);。

• 响应中断
  源码实现与需求实现一致。线程中断时调用 Thread.interrupt() ，LockSupport.park() 会响应中断，解除阻塞。

• newCondition
  先不考虑，比较复杂，需单独写一篇文章。

5.实现总结

本文按照，功能介绍，需求分析，需求实现，源码实现顺序讲解，介绍了 ReentrantLock 的使用、功能、实现。本文写了很多内容，如果可以用一句话介绍实现原理：
ReentrantLock 是使用链表、park、CAS、volatile 等方法实现的一个互斥且可重入的锁。

建议面试时遇到xxx原理一类的问题按照使用-原理来回答问题，这样我们可以给面试官留下不仅会使用而且还知道原理的印象。