ReentrantLock实现原理

ReentrantLock，意译过来就是可重入锁，即同一线程对锁的再次获取并不会发生阻塞。

ReentrantLock是什么

什么是ReentrantLock？官方文档是描述的：

/**
 * A reentrant mutual exclusion {@link Lock} with the same basic
 * behavior and semantics as the implicit monitor lock accessed using
 * {@code synchronized} methods and statements, but with extended
 * capabilities.
 *
 * <p>A {@code ReentrantLock} is <em>owned</em> by the thread last
 * successfully locking, but not yet unlocking it. A thread invoking
 * {@code lock} will return, successfully acquiring the lock, when
 * the lock is not owned by another thread. The method will return
 * immediately if the current thread already owns the lock. This can
 * be checked using methods {@link #isHeldByCurrentThread}, and {@link
 * #getHoldCount}.
 *
 * <p>The constructor for this class accepts an optional
 * <em>fairness</em> parameter.  When set {@code true}, under
 * contention, locks favor granting access to the longest-waiting
 * thread.  Otherwise this lock does not guarantee any particular
 * access order.  Programs using fair locks accessed by many threads
 * may display lower overall throughput (i.e., are slower; often much
 * slower) than those using the default setting, but have smaller
 * variances in times to obtain locks and guarantee lack of
 * starvation. Note however, that fairness of locks does not guarantee
 * fairness of thread scheduling. Thus, one of many threads using a
 * fair lock may obtain it multiple times in succession while other
 * active threads are not progressing and not currently holding the
 * lock.
 * Also note that the untimed {@link #tryLock()} method does not
 * honor the fairness setting. It will succeed if the lock
 * is available even if other threads are waiting.
 *
 * <p>It is recommended practice to <em>always</em> immediately
 * follow a call to {@code lock} with a {@code try} block, most
 * typically in a before/after construction such as:
 *
 *  <pre> {@code
 * class X {
 *   private final ReentrantLock lock = new ReentrantLock();
 *   // ...
 *
 *   public void m() {
 *     lock.lock();  // block until condition holds
 *     try {
 *       // ... method body
 *     } finally {
 *       lock.unlock()
 *     }
 *   }
 * }}</pre>
 *
 * <p>In addition to implementing the {@link Lock} interface, this
 * class defines a number of {@code public} and {@code protected}
 * methods for inspecting the state of the lock.  Some of these
 * methods are only useful for instrumentation and monitoring.
 *
 * <p>Serialization of this class behaves in the same way as built-in
 * locks: a deserialized lock is in the unlocked state, regardless of
 * its state when serialized.
 *
 * <p>This lock supports a maximum of 2147483647 recursive locks by
 * the same thread. Attempts to exceed this limit result in
 * {@link Error} throws from locking methods.
 *
 * @since 1.5
 * @author Doug Lea
 */
public class ReentrantLock implements Lock, java.io.Serializable {
}

这里笔者大概列出了几点：

1. ReentrantLock是一个可重入的排他锁。
2. ReentrantLock支持公平策略和非公平策略（默认）。
3. ReentrantLock在反序列化时会被设置为非锁定状态（无论序列化时处于什么状态）。
4. ReentrantLock支持最大的可重入次数为2147483647（int型整数最大值），如果超过这个值会抛出异常。

总的来说，ReentrantLock就是一种支持公平策略和非公平策略的可重入排它锁。

ReentrantLock具有与监听器锁（即synchronized）相同的行为和语义（除此之外还存在额外的扩展能力）。

ReentrantLock的使用

ReentrantLock继承自Lock接口，Lock接口作为JDK中显式锁的抽象提供了相比于synchronized更灵活的锁能力，不过带来更多灵活性的代价则是需要使用者手动释放锁。

阻塞加锁

在ReentrantLock中提供了一个具有与监听器锁（即synchronized）相同加锁语义的方法，即Lock#lock。Lock#lock会以阻塞方式获取锁，如果锁获取失败则进入阻塞状态，直到锁获取成功。在使用上我们应该通过如下语法使用Lock:

    // 当锁定和解锁发生在不同的作用域时，必须注意确保持有锁时执行的所有代码都受到 try-finally 或 try-catch 的保护，以确保在必要时释放锁。
    Lock l = ...;
    l.lock();
    try {
        // access the resource protected by this lock
    } finally {
        l.unlock();
    }    

关于Lock实现，它应该与监视器锁（synchronized）具有相同的内存同步语义，即：Lock实现的加锁操作（Lock#lock）和解锁操作（Lock#unlock）应该与监视器锁（synchronized）的加解锁操作具有相同的内存同步效果。另外，如果Lock实现中提供了与隐式监听器锁（synchronized）完全不一样的行为和语义，例如顺序性的保证、不可重入性、死锁检测等，则必须在文档上对这些行为和语义进行记录和说明。

扩展功能

对于加锁部分ReentrantLock除了提供传统的Lock#lock方法外，还提供了更多附加功能的方法（synchronized所没有的能力），具体如下所示：

• tryLock()

  tryLock()以非阻塞的方式试图获取锁，即当锁获取成功立刻返回true，否则立刻返回false。一般会通过如下用法使用tryLock()，以确保锁被获取时是处于未被锁定状态，并在获取失败后不会释放锁。

  Lock lock = ...;
  if (lock.tryLock()) {
      try {
          // manipulate protected state
      } finally {
          lock.unlock();
      }
  } else {
      // perform alternative actions
  } 
  

• tryLock(long, TimeUnit)

  tryLock(long time, TimeUnit unit)以可超时可中断的阻塞方式获取锁，即在给定等待时间内无中断的情况下获取处于空闲状态的锁，如果获取成功立刻返回true；如果获取失败则停止线程调度并进入阻塞状态，直到发生以下三件事：

  • 线程获取锁成功，并返回true
  • 线程在进入阻塞前或后（Thread#interrupt）发生了中断，并抛出异常InterruptedException并清理当前线程的中断状态（如锁支持在获取中被中断）
  • 线程阻塞超过指定等待时间，并返回false（如果超时间小于等于0，这个方法将不会进行等待）。

• lockInterruptibly()

  lockInterruptibly()以可中断的阻塞方式获取锁，即如果锁获取失败则进入阻塞状态，直到发生中断（Thread#interrupt）或锁获取成功。

  关于中断：如果当前线程在进入这个方法时就存在中断状态，或者在锁获取过程中发生中断了（Thread#interrupt），将会抛出异常InterruptedException并清理当前线程的中断状态。

另外，ReentrantLock还支持条件等待，即持有锁的线程让出锁给其他线程执行相应的逻辑，并进入等待状态（不持有锁）直到条件符合后再次被唤醒（持有锁）。在ReentrantLock中可通过newCondition方法创建并返回一个绑定了Lock实例的Condition对象用于执行条件等待，即通过调用Condition#await方法进入条件等待；通过调用Condition#signal方法将线程从条件等待中唤醒。

对于Condition，线程必须在持有锁情况下才能调用Condition#await和Condition#signal方法。另外，线程会在进入条件等待时将锁原子性释放；在条件等待返回之前重新获取锁。

使用例子

一般来说，在并发情况下访问共享资源就需要用到ReentrantLock了。比如说，在单机情况下统计访问人数时可通过ReentrantLock来保护共享变量count。

/**
 * 书店
 */
public class ShopMall{

    // 默认非公平锁
    private final static Lock lock = new ReentrantLock();

    /**
     * 书店访问人数
     */
    private static Integer count = 0;

    /**
     * 模拟访问书店
     */
    public void view(){
        doBefore();
        doView();
    }

    /**
     *  前置处理
     * 
     *  官方推荐lock使用格式，防止发生其他不可预期的事情导致死锁
     *  public void m() {
     *      lock.lock();  // block until condition holds
     *      try {
     *          // ... method body
     *      } finally {
     *          lock.unlock()
     *      }
     *  }
     */
    public void doBefore(){
        lock.lock();
        try{
            // 此处count++并非原子性操作，所以需要加锁保证其原子性
            count++; 
        }finally{
            lock.unlock();
        }
    }
}

当然，我们也可以通过ReentrantLock#tryLock加锁，在获取锁失败后会立刻失败，而不是阻塞等待。此方法可用于防止同一个客户端一次并发了两次请求导致数据出现重复。

除此之外，在共享资源不足的情况下我们还可以通过条件等待的方式使得访问线程进入阻塞状态，并在资源补充完成后继续访问。

/**
 * 书店
 */
public class ShopMall{

    // 默认非公平锁
    private final static Lock lock = new ReentrantLock();

    // 等待条件：如果书本库存不存在进入等待状态
    private final static Condition waitCondition = lock.newCondition();

    // 库存数量
    private static Integer inventory = 100;

    /**
     * 模拟买书
     */
    public void purchase(){
        lock.lock();
        try{
            enqueue();
            doPurchase();
        }finally{
            lock.unlock();   
        }
    }

    /**
     * 排队
     */
    private void enqueue(){
        while(inventory <= 0){
            waitCondition.await();
        }
    }

    /**
     * 添加库存
     */
    public void addInventory(){
        lock.lock();
        try{
            inventory++;
            if(inventory > 0){
                waitCondition.signal();
            }
        }finally{
            lock.unlock();
        }
    }
}

这里需要注意，在默认实现中Condition#awit和Condition#signal的使用需要持有相关联的Lock。而如果在Condition的具体实现类中并没有这样的限制，我们也可以在不持有相关联Lock的情况下进行调用。

使用总结

方法	描述
lock	以阻塞方式获取锁，即如果锁获取失败则进入阻塞状态，直到锁获取成功。
lockInterruptibly	以可中断的阻塞方式获取锁，即如果锁获取失败则进入阻塞状态，直到发生中断或锁获取成功。
tryLock	以非阻塞的方式试图获取锁，即当锁获取成功立刻返回true，否则立刻返回false。
tryLock(long time, TimeUnit unit)	以可超时可中断的阻塞方式获取锁，即当锁获取成功立刻返回true，否则进入阻塞状态直到发生中断、发生等待超时或锁获取成功。
unlock	释放锁的持有。在Lock的实现类通常会添加对锁释放的限制，典型的做法是只有锁持有者才能释放锁，如果违反了限制则会抛出一个未检查异常。

关于Lock与synchronized的差异

1. synchronized仅提供了阻塞的方式获取锁，而Lock则提供了更广泛更灵活的锁操作（阻塞、非阻塞和超时等）。
2. synchronized仅支持关联一个条件等待对象，而Lock则支持同时关联多个条件等待对象（Condotion）。
3. synchronized需与对象的隐式监听器锁关联，并必须以代码块的形式来对锁获取和释放，而Lock则不需要。
4. synchronized获取和释放的执行顺序是相反的、执行作用域是相同的，而Lock则不需要。

虽然synchronized作用域机制使得使用监视器锁编程变得更加容易，并有助于避免许多涉及锁的常见编程错误，但在某些情况下，我们需要以更灵活的方式使用锁，例如一些并发访问数据结构的算法需要使用锁链：你先获取节点A的锁，然后节点B，然后释放A，获取C，然后释放B并获得D。对于这种情况则需要使用Lock的相关实现来解决（允许在不同范围内获取和释放锁、允许以任何顺序获取和释放多个锁）。

Lock实例只是一个普通的对象，它也可以作为synchronized语句的目标对象，因为获取Lock实例的监听器锁与调用Lock实例中任何的锁获取方法没有特殊的关系，但是建议不要以这种方式使用Lock实例以避免混淆。

更多关于Lock的详情可阅读：Lock接口

ReentrantLock的实现原理

AQS

在Java中ReentrantLock是基于AQS实现的，而所谓AQS（即，AbstractQueuedSynchronizer）是JDK提供给我们用于实现阻塞锁的框架。关于AQS的实现原理主要分为两部分：

1. 通过一个原子变量state来确定锁的状态（例如：1表示锁定，0表示释放）。
2. 通过一个FIFO队列存储获取锁失败的线程以实现阻塞等待的效果。

即，在AQS中通过原子变量state实现锁语义，FIFO队列实现阻塞效果。但对于使用者的我们是不需要太过关注其中的实现原理，而只需要对锁的获取与释放语义进行定义即可，具体方法如下所示：

方法	描述
tryAcquire	表示在排他模式(EXCLUSIVE)下去获取资源，如果返回true表示获取成功，否则表示获取失败。其中，在方法的实现中我们应该判断当前是否能在独占模式获取资源。
tryRelease	表示在排他模式(EXCLUSIVE)下去释放资源，如果返回true表示全部释放成功，否则表示释放失败或者部分释放。
tryAcquireShared	表示在共享模式(SHARED)下去去获取资源，如果返回大于0表示获取成功并且其后继节点也可能成功获取资源；如果返回等于0表示获取成功但其后继节点不能再成功获取资源了；如果返回小于0则表示获取失败。其中，在方法的实现中我们应该判断当前是否能够在共享模式下获取资源。
tryReleaseShared	表示在共享模式(SHARED)下去释放资源，如果返回true表示释放成功，否则表示释放失败。
isHeldExclusively	表示资源是否被独占地持有，如果返回true表示被独占持有，否则表示没有被独占持有。

即，当要实现独占语义时需要实现tryAcquire、tryRelease和isHeldExclusively；当要实现共享语义时则需要实现tryAcquireShared和tryReleaseShared。

最终，我们就可以在实现类中使用以下方法了：

方法	描述
tryAcquire	表示在排他模式(EXCLUSIVE)下去获取资源，如果返回true表示获取成功，否则表示获取失败。
tryRelease	表示在排他模式(EXCLUSIVE)下去释放资源，如果返回true表示全部释放成功，否则表示释放失败或者部分释放。
tryAcquireShared	表示在共享模式(SHARED)下去去获取资源，如果返回大于0表示获取成功并且其后继节点也可能成功获取资源；如果返回等于0表示获取成功但其后继节点不能再成功获取资源了；如果返回小于0则表示获取失败。
tryReleaseShared	表示在共享模式(SHARED)下去释放资源，如果返回true表示释放成功，否则表示释放失败。
isHeldExclusively	表示资源是否被独占地持有，如果返回true表示被独占持有，否则表示没有被独占持有。
acquire	表示在排他模式(EXCLUSIVE)下去获取资源，如果获取失败会陷入阻塞（进入等待队列）直到获取成功。
acquireInterruptibly	表示在排他模式(EXCLUSIVE)下去获取资源，获取失败会陷入阻塞（进入等待队列）直到获取成功或中断抛出异常。
tryAcquireNanos	表示在排他模式(EXCLUSIVE)下在规定时间内去获取资源，获取失败会陷入阻塞（进入等待队列）直到获取成功或中断抛出异常，其中如果在规定时间内获取成功会返回true，超时则返回false。
release	表示在排他模式(EXCLUSIVE)下去释放资源，如果释放成功返回true，否则返回false。
acquireShared	表示在共享模式(SHARED)下去获取资源，获取失败会陷入阻塞（进入等待队列）直到获取成功（与排他模式相比，此方法可以让多个线程同时获取到资源）。
acquireSharedInterruptibly	表示在共享模式(SHARED)下去获取资源，获取失败会陷入阻塞（进入等待队列）直到获取成功或中断抛出异常（与排他模式相比，此方法可以让多个线程同时获取到资源）。
tryAcquireSharedNanos	表示在共享模式(SHARED)下去获取资源，获取失败会陷入阻塞（进入等待队列）直到获取成功或中断抛出异常，其中如果在规定时间内获取成功会返回true，超时则返回false。（与排他模式相比，此方法可以让多个线程同时获取到资源）。
releaseShared	表示在共享模式(SHARED)下去释放资源，如果释放成功返回true，否则返回false。

如果需要更深入学习AQS的话可以阅读笔者之前的文章《什么是AQS》

在了解完AQS后，接下来我们再来看ReentrantLock是如何基于AQS实现的。

ReentrantLock

虽然说ReentrantLock是基于AQS实现的，但是在ReentrantLock上并没有直接继承AQS，而是继承自JDK显式锁的抽象接口类Lock，然后再将相应的方法执行委托给了继承自AQS的内部类Sync来实现。

ReentrantLock通过继承Lock并将相关执行委托AQS的方式是贯彻了“基于接口编程”的设计模式。对于ReentrantLock的实现者直接将其与AQS进行硬编码是一种糟糕的设计，因为AQS仅仅是作为阻塞锁的一种实现方式，在未来版本或者定制版本中还可能存在其它的实现方式。而通过继承Lock来实现ReentrantLock则完美地将接口与实现进行分离，以此来降低耦合性、提高扩展性和可维护性（使用者无需关注和依赖于特定的实现）。

因为ReentrantLock可分为公平锁（FairSync）和非公平锁（NonfairSync），所以它会在Lock中采用可配置的方式进行实现，即通过构造参数选择并构建出公平锁（FairSync）和非公平锁（NonfairSync），然后将其赋值给成员变量Sync（默认会选择和构建非公平锁NonfairSync）：

public class ReentrantLock implements Lock, java.io.Serializable {
    /** Synchronizer providing all implementation mechanics */
    private final Sync sync;
    
    /**
     * Creates an instance of {@code ReentrantLock}.
     * This is equivalent to using {@code ReentrantLock(false)}.
     */
    public ReentrantLock() {
        sync = new NonfairSync();
    }

    /**
     * Creates an instance of {@code ReentrantLock} with the
     * given fairness policy.
     *
     * @param fair {@code true} if this lock should use a fair ordering policy
     */
    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }
}

然后在之后关于ReentrantLock的所有操作都委托给成员变量sync:

public class ReentrantLock implements Lock, java.io.Serializable {
    public void lock() { sync.lock(); } 
    public void lockInterruptibly() throws InterruptedException { sync.acquireInterruptibly(1); }
    public boolean tryLock() { return sync.nonfairTryAcquire(1); }
    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(timeout));
    }
    public void unlock() { sync.release(1); }
    public Condition newCondition() { return sync.newCondition(); }
    // ...
}

其中Sync类是通过（继承）AQS来实现的，在AQS中如果实现类是排他模式（ReentrantLock属于排他模式）则只需要实现tryAcquire、tryRelease和isHeldExclusively方法。然而，因为公平锁和非公平锁之间的区别仅仅是在tryAcquire的实现中存在差别，所以在Sync实现中将tryAcquire的实现下放到子类FairSync和NonfairSync中，下面我们先来看看Sync：

/**
 * Base of synchronization control for this lock. Subclassed
 * into fair and nonfair versions below. Uses AQS state to
 * represent the number of holds on the lock.
 */
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();

    // ...nonfairTryAcquire

    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
    // ...
}

在类Sync中仅仅实现了通用的两个方法，分别是tryRelease和isHeldExclusively，其中方法的实现并不难理解，这里就不再细讲了，我们只需要注意实现中的两个关键点：

1. 锁获取与释放线程的一致性。通过Thread.currentThread() != getExclusiveOwnerThread()实现只有获取锁的线程才能释放锁，这一点也是线程安全的一个保证，避免被其他线程解锁了。
2. 锁获取的可重入性。因为ReentrantLock是可重入锁，锁定状态的state值可能大于等于1，所以只有state==0时才算成功释放锁。

另外根据AQS的定义，因为ReentrantLock需要用到AQS的ConditionObject，所以需要实现isHeldExclusively。此方法用于保证只有持有排他锁的情况下才能进入条件队列等待，而此处是通过语句getExclusiveOwnerThread() == Thread.currentThread()来实现的。

接下来，我们再来看看在FairSync和NonfairSync上是如何实现tryAcquire的（为了便于理解，笔者在不影响逻辑的情况下简单改写了一下tryAcquire方法）：

• 非公平策略NonfairSync

  /**
  * Sync object for non-fair locks
  */
  static final class NonfairSync extends Sync {
  
      /**
       * Performs non-fair tryLock.  tryAcquire is implemented in
       * subclasses, but both need nonfair try for trylock method.
       */
      protected final boolean tryAcquire(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;
      }
  }
  

  在NonfairSync#tryAcquire方法中存在两个关键的判断，分别是非公平式获取锁和可重入式获取锁。下面笔者将整个执行流程整理了出来：

  1. 判断当前锁是否处于空闲状态，如果是则通过CAS机制获取锁，否则执行第2步（非公平式获取锁）。
  2. 判断持有锁的线程是否与当前线程相同，如果是则增加持有锁的数量，否则返回false表示获取失败（可重入式获取锁）。

  在tryAcquire的定义并没有对等待队列中是否存在元素进行判断，所以即使在等待队列中存在等待时间很长节点（线程），当前进入线程也有机会获取到锁，即非公平策略。

  这里我们深入一步看看acquire方法的具体逻辑：

  public abstract class AbstractQueuedSynchronizer
      extends AbstractOwnableSynchronizer
      implements java.io.Serializable {
      
      public final void acquire(int arg) {
          if (!tryAcquire(arg) &&
              acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
              selfInterrupt();
      }
  }
  

  在acquire方法中首先会调用了tryAcquire方法来获取锁，如果失败则执行acquireQueued方法插入到等待队列中进行等待，直到锁获取成功。

• 公平策略FairSync

  /**
   * Sync object for fair locks
   */
  static final class FairSync extends Sync {
  
      /**
       * 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)) {
                  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;
      }
  }
  

  与NonfairSync#tryAcquire方法相同，在FairSync#tryAcquire方法中采用了几乎一样的判断逻辑，只不过是在获取锁时加上了节点（线程）是否等待时间最长的判断，即：

  1. 判断当前锁是否处于空闲状态并且当前线程是否等待时间最长（通过!hasQueuedPredecessors()表达式判断），如果是则通过CAS机制获取锁，否则执行第2步（公平式获取锁）。
  2. 判断持有锁的线程是否与当前线程相同，如果是则增加持有锁的数量，否则返回false表示获取失败（可重入式获取锁）。

  hasQueuedPredecessors方法用于查看等待队列中是否存在比当前节点（线程）等待时间长的等待节点（线程），即是否存在等待节点（线程）位于当前节点（线程）的前面。换句话说，只有当前线程前面没有线程正在等待时才尝试获取锁，否则进入到队列中进行等待。最终通过这样的方式就实现了公平策略。

总结

至此，本文从如何使用到如何实现两个角度分别对ReentrantLock进行了分析。简单来说，ReentrantLock是可重入的排它锁，通过它我们可以线程安全地访问共享资源，其主要是通过原子变量+FIFO队列实现的。