distributedlock

概述

本文主要内容为分析锁的逻辑结构、JVM中锁的实现，以及自己所设计的一种基于redis的分布式锁。

锁的简介

锁的定义

In computer science, a lock or mutex (from mutual exclusion) is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy。 —wiki

渣翻：在计算机科学中，锁（互斥量）是一种多线程环境中用于限制资源访问的同步机制，通常代表着并发中的一种互斥访问策略。

锁的种类

计算机中有许多种锁，最常见的的便是读写锁和可重入锁。

简单锁：资源只能被一个线程持有、加锁、与修改；其他线程对于该资源的加锁和操作必须等待持有锁的线程释放之后才能进行。
可重入锁：持有锁资源的线程可以重复的在资源上进行加锁操作，通常持有锁的线程将资源上所有的锁都释放后其他线程才能加锁并访问该资源。
读写锁：读写锁通常分为读锁和写锁，当资源被某线程以写锁模式占有时，其他线程均不能访问该资源；当资源被某线程以读锁模式占有时，其他线程可以对该资源加读锁进行读操作，但不能对该资源加写锁执行写操作。

JVM中锁的实现

Java中常用的锁有两种：synchronized关键字与java.util.concurrent.ReentrantLock.它们都是可重入的排他锁，后者实现时参考了前者的设计。我们这里主要讨论前者，即JVM中自带的锁。 synchronized所实现的锁是一种独占的可重入锁，它还包含了许多优化所带来的新特性。

独占锁

锁资源在某一时刻内只能被某一个线程所占有，这样的结构被称为独占锁，独占锁是锁的最基本表现形式。由于锁涉及到多个线程之间的同步，通常会借用用多个线程同时可见的一片内存空间来实现。这片内存空间通常有两种状态：

free: 表明锁资源没有被任何线程所占有
locked：锁资源已被某线程所占有当一个线程运行到临界区时，它会首先去检查约定的内存空间状态，如果为free，那么就把这里置为locked，标明临界区已经被某线程所占有，其他线程看到locked标志后就不会再向下执行，达到排他运行的目的。

在实现锁的时候，请注意这里的两个要点：

内存区域对所有线程可见。由于JVM内存模型的限制，这里的内存区域通常需要加上一点额外的处理才能保证其”可见”。关于JVM内存模型以及可见性的讨论，请查阅volatile关键字。
查看并设置内存空间这一个过程必须是原子操作。设想这样一种场景：1.线程A查看共享内存空间，此时锁的状态为free；2.线程B查看共享内存空间，此时锁的状态也为free（线程A还没来得及上锁）；3.线程A将锁空间状态置为locked，执行临界区代码；4.线程B将锁空间状态置为locked，也执行临界区代码。此时线程A与线程B都在执行临界区的代码，锁的功能就失效了。因此，查看并修改这一个过程必须要保证原子性。具体实现请参考CAS（CompareAndSwap）

可重入锁

当线程申请锁资源时，如果发现锁资源已经被持有，且持有者为自己会发生什么？设想一下，如果我们并未记录锁资源被谁所持有，仅简单记录锁定/未锁定状态。当上述情况发生时，线程会发现锁不可用（lock状态），因此它会将自己置于等待状态，等待线程自己释放锁资源！这样，单个线程就形成了一个死锁闭环。所以，在实际的实现中锁都是可重入的，通常的实现方式为：当持有锁的线程再次申请同一锁资源时，线程不会阻塞，仅是重入计数+1；当线程释放锁资源时，线程不会立即释放锁资源，而是不断减少重入计数，当锁资源重入计数减为0时，线程才会将整个锁资源释放，供其他线程使用。

可重入锁所实现的关键在于判断锁资源当前被哪个线程所占有。也就是说，锁资源在被线程锁定的时候，它应记录下占有它的线程。修改锁资源的状态与记录锁资源被哪个线程所占有应绑定在一起作为一个原子操作，如果这两个操作相互独立的话，就可能造成锁定状态与持有锁的线程记录不一致的情况，造成严重的并发问题。因此JVM中线程在获取锁资源时，直接将自己的唯一标识放到共享存储区中，通过判断替换是否成功确认自己是否获取到了锁资源。这样，通过查看锁资源处的记录线程就知道当前是由哪个线程持有该锁。

线程对于同一个锁资源的重入次数通常放在线程内部而非多个线程的共享区域。原因如下：

重入次数只对当前持有锁资源的线程有意义，对于其他线程没有意义；其他线程只需要判断锁资源是否被占用即可确定自己接下来是否需要进入临界区，无需关心重入次数。
对于共享区域的修改需要考虑数据的可见性、多个线程之间的同步等问题，编码难度与系统开销往往比线程独占更高。

线程等待

当线程申请锁资源失败时，通常需要其暂停工作，等待资源可用时继续向下执行。线程的等待通常有两种方式：自旋等待与阻塞等待。

自旋等待：线程使用while(!trylock())不断循环尝试获取锁，直到获取资源后继续往后执行。优点：响应时间快，线程不会进入阻塞状态，不涉及线程切换。缺点：占用系统资源多。当线程进入自旋状态时，通常会占用某个CPU（核）100%的资源，此时该CPU无法做任何其他操作。
阻塞等待：线程进入阻塞状态，释放CPU资源，待锁资源释放时系统唤醒线程。此时线程将再次重试获取锁资源，根据获取情况继续向后执行。优点：CPU资源释放出来，可供其他线程使用。缺点：线程阻塞/唤醒存在时间消耗，对于锁资源状态变化的响应较自旋等待情况更慢。

通常情况下，自旋等待由于其良好的响应速度，不涉及线程切换的优点，适用于较少竞争、且每个线程持有锁资源时间不长的情况。在这种情况下如果使用阻塞等待，可能线程正在进入阻塞的过程中时，锁资源就由不可用变为可用状态了，线程还得再慢悠悠地从阻塞状态切换为运行态，整个过程耗时过长，锁资源没有得到充分利用。同样的，如果在线程通常长时间占用锁的情况下时采用自旋等待，将导致系统CPU资源迅速被耗尽，系统除了等待无法做任何其他工作。

公平锁与非公平锁

根据等待线程的不同唤醒方式，锁可以分为公平锁与非公平锁：

公平锁：当多个线程同时等待锁资源时，系统将严格按照线程进入等待状态的次序进行唤醒。
非公平锁：当多个线程同时等待锁资源时，系统不一定严格按照线程进入等待状态的次序进行唤醒。

通常来说，非公平锁的效率比公平锁要高。但是将可能导致某些线程（通常是优先级较低的线程）始终无法获取到锁资源，造成线程的”饥饿”状态。具体的取舍由用户自己决定。

锁的实现

作为一种通用的同步工具，所有锁的核心语义是相通的。JVM中的Lock接口中有多种获取锁的方法：

lock():无中断、无限等待锁资源
lockInterruptibly()：在获取锁等待的过程中可中断，无限等待锁资源
tryLock():无阻塞，仅尝试获取锁资源
tryLock(long time, TimeUnit unit):最多等待一段时间锁资源，可中断

这四种不同的调用方式基本可涵盖所有的应用场景，我们将从这4种不同的调用方式中分析JVM中锁的实现原理。

tryLock

tryLock在四种调用方式中实现起来最简单，因为它仅涉及到上一章我们所讨论的独占与可重入，没有涉及到锁实现中的难点：等待队列，就更谈不上公平锁与非公平锁了。在AbstractQueuedSynchronizer中，Doug Lea大师使用一个int类型变量用于标识当前对象的状态，即上一章我们所讨论的共享的内存空间。该值的声明含有volatile关键字，因此对于所有线程都是可见的；而且对于其的所有赋值操作均以CAS方式实现，保证对其的写操作是原子的。(TIPS：CAS操作存在ABA问题，为何这里没有考虑？如果我们把A当做无锁状态，当任一线程将其置为B状态后，由于Lock机制，仅有持有锁的线程在释放所有锁资源后才能将其置为A状态。) 同时，在AbstractQueuedSynchronizer的父类AbstractOwnableSynchronizer中，exclusiveOwnerThread属性用于存储持有当前锁资源的线程，这个属性就是我们实现可重入的关键。（TIPS：exclusiveOwnerThread未使用synchronized或volatile关键字修饰，它的可见性必须由代码保证。当获取锁资源时，线程必须先修改状态值，再修改exclusiveOwnerThread状态；当释放锁资源时，线程必须先修改exclusiveOwnerThread状态，再修改状态值。由于状态值的volatile属性，内存屏障将保证exclusiveOwnerThread的happens-before，即可见性）

if(compareAndSwap(state-free, state-lock)) {
    exclusiveOwnerThread = currentOwnerThread;
    reentrantCount = 1;
    return true;
} else if (exclusiveOwnerThread == currentOwnerThread) {
    reentrantCount += 1;
    return true;
}
return false;

tryLockWithTimeOut

其他的lock调用方式在tryLock的基础上增加了同步等待等功能。使用tryLockWithTimeOut时，线程在获取锁资源失败的情况下将阻塞等待一段时间，在此期间可通过Thread.interrupt中断线程的等待行为。如果在设定等待时间内获取到锁资源，方法将立即返回成功，否则将返回失败。多个线程同时等待一个锁资源时，为了避免过多的线程切换开销、防止部分线程长时间饥饿，通常会采用队列的方式将等待线程组织起来，按照等待的次序依次获取锁资源。（非公平锁并不保证严格按照等待次序获得锁资源）线程获取锁资源时，如果线程获取锁资源失败，就在等待队列的末尾添加一个节点，代表自己正在排队等待锁资源释放；接着按照预设的逻辑进行等待。当线程释放锁资源时，如果等待队列中有线程存在，则唤醒下一个等待的线程。等待队列的第一个问题是：对于释放锁资源的唤醒信号，应由释放锁资源的线程’推送’给下一个等待线程还是由等待线程自己去获取？假设采用推送的模式，此时线程A与线程B都需要独占锁资源才能向下继续执行，它们各自执行情况如下：

线程A尝试并成功获取锁资源
线程B尝试获取锁资源失败
线程A释放锁资源，检查等待队列，其中无等待节点，不用’推送’唤醒信号
线程B将自己放入等待队列，等待线程A向自己’推送’唤醒信号

线程B将进入等待状态，无法正确得到唤醒，因为唤醒信号的到来发生在线程B监听之前，导致信号丢失。如果采用线程主动’获取’的则可避免该问题的发生：线程进入等待队列后，不断监听前一个节点的状态，如果前一个节点从持有锁资源的状态变为未持有，线程就会再次尝试获取锁资源，重复上述流程。前一个节点状态改变记录不会丢失，只需在线程进入阻塞状态前再check一次就可以避免信号丢失的情况发生。（但是由于check与进入阻塞状态不是原子操作，因此之间仍然可能导致唤醒操作发生在阻塞之前，但是概率很小，这里就不考虑了）

由于阻塞状态的线程无法将自己唤醒，因此线程释放锁资源时必须承担将后续线程唤醒的任务。

等待队列的第二个问题：如何实现等待线程的可中断性？当等待线程接收到中断信号后，应将其从等待队列中移除，后一个节点的线程应监听中断线程的前一个节点，否则无法被正常唤醒。将节点从队列（链表）中取出的操作非常简单，但也存在上面的问题：这个操作应由中断线程来处理还是后续等待节点线程处理？参考上面的分析，如果由中断线程执行摘出操作，当中断线程在等待队列的末尾，且刚好此时有一个线程正要将自己’挂’在中断线程的节点上时，将会导致后续线程始终无法被唤醒。因此，当等待线程接收到中断信号时，只需将自己节点中的状态置为cancelled即可；当后续线程被唤醒时，再将这些cancelled的节点从队列中摘除出去。