形形色色的锁

原创

wiizhang

发布于 2018-09-13 16:24:06

8200

发布于 2018-09-13 16:24:06

文章被收录于专栏：企鹅FM企鹅FM

java中有各种同步机制，尤其是JDK1.5以后引入Lock后，衍生出各种功能不一的锁，比如ReentrantLock、Semaphore、CountDownLatch等等。本文便从浅入深，聊聊这些锁背后的概念和机制。

锁有哪些种类

首先从概念上讲，锁大致可以分为两类：

乐观锁

乐观锁顾名思义，态度总是很积极，认为很有可能能够竞争成功，比如自旋锁，第一个线程竞争成功，自然很开心，但后面的线程就要不断循环等待直到锁被释放。这种机制构成了一种忙等待。

悲观锁

悲观锁则相反，它假定锁是很有可能拿不到的，于是每个线程仅仅尝试一次，拿到就很开心，拿不到就把自己挂起，直到持有临界资源的线程释放后，才会唤醒一个等待中的线程。这样构成了阻塞等待。

从刚才的两种等待过程可以推测出，忙等待的效率应该更高一些，因为少了线程的挂起和唤醒（会导致内核态和用户态切换），但对于整个系统而言，阻塞等待显然更加受欢迎，毕竟空转是一种浪费，且排队使用cpu的线程还有很多

于是在java的世界里面，虚拟机很人性，它不会因为一个进程的锁太多而影响到其他进程的心情，于是自旋锁的个数上限被控制了起来，并根据当前系统运行情况动态调整这个值，当超过上限后，自旋锁会升级为阻塞锁（当然是直接挂起了呗）

熟悉的陌生人——synchronized

synchronized关键字相信java程序员一定不会陌生，因为简单易用，无需创建对象，是多线程同步的首选。

然而说到synchronized背后的机制，估计就知之者寥寥了。其实synchronized之所以难以一言蔽之，因为它是用极其复杂的过程换来了一个简单的调用形式，这个过程包含了三种概念：

偏向锁（biased lock）
轻量锁（lightweight lock）
重量锁（heavyweight lock）

为了介绍这三种锁的含义，首先必须啰嗦几句jvm中对象的表示形式

JVM中每个对象都有一个对象头（Object header），普通对象头的长度为两个字，数组对象头的长度为三个字（JVM内存字长等于虚拟机位数，32位虚拟机即32位一字，64位亦然），其构成如下所示：

重点在于这个MarkWord上，它记录了这个对象相关的很多信息:

于是第一行最后有一个tag标记（2个bit）位用来标记一个对象的锁状态。既然是两位，显然不止两种状态，下面会进一步介绍

简单说说进入synchronized的过程：

我们知道synchronized是针对对象来操作的，于是要对一个对象上锁:

第一步会在当前线程的线程栈中生成一条锁记录（lock record），这条记录的内容就是当前MarkWord的内容拷贝，此时若对象没有被锁住的话tag值就是01代表有资源
第二步就是尝试将这条锁记录的地址写入到MarkWord中的lock record address。这一步是关键，因为可能会出现三种情况:

1.当前没有线程竞争 2.有线程在竞争且抢先一步拿到了该锁 3.当前线程重入这把锁
于是这里写入必须保证原子性，依赖的是系统提供的原子操作Compare-And-Swap（以下简称CAS）
这步CAS的比较值就是tag的初始值01，如果设置成功tag就变为00，证明自己是第一个，于是顺利拿到了轻量锁，此时同步将lock record的地址写入。如果设置不成功查看下若tag为00，则代表此锁已经有主，取出lock record address和当前线程栈中对应的record做对比，如果发现有，则代表是锁重入，也算成功，直接写lock record address（因为是栈结构，所以最终肯定能还原）。但是如果在当先线程栈中找不到这样一条记录，那就说明此锁是其他线程拥有，这时就要把轻量锁升级为重量锁，将Tag状态改为10，并生成一个Monitor对象（重量锁对象），再将MarkWord中Monitor address的值改为该Monitor对象的地址。最后将当前线程塞入该Monitor的等待队列中。

接下来，说说解锁过程：

解锁时依然是CAS修改tag值，如果比较00成功，则写入01，同步将lock record中的值还原写回到该对象的MarkWord中。
CAS失败，检查tag值如果是10，则表明这段时间已经有其他线程经竞争过该锁，且升级为了重量锁，那么就要去Monitor的等待队列中唤醒一个线程去重新竞争锁。
当发生锁重入时，会对一个Object在线程栈中生成多个lock record，每当退出一个synchronized代码块便解锁一次，并弹出一个lock record。

说了这么多好像漏掉了谁，貌似偏向锁还没出场呢。留意下刚才提到的锁重入的情况，系统允许同一个线程重入一个对象的锁，但是每次重入都需要完成固定的步骤，以轻量锁为例，如果重入每次最少要消耗一个CAS操作和额外的几条指令，而偏向锁就是为了解决这种问题而生。

（CAS会产生多大开销？这个和CPU的cache一致性有关，CAS会强迫cache失效，导致重新从内存中加载该值）

获取偏向锁时与轻量锁最大的差别在于，在MarkWord中写入的不是lock record的地址，而是当前线程的ID，同时tag标记始终保持01且置位偏向标记位，于是下次重入时，如发偏向标记被置且lock address的值与当前线程ID相同，则直接算获取锁成功。不相同说明有不同线程竞争锁，这时候要先将偏向锁撤销（revoke）为轻量锁，再升级为重量锁。
偏向锁的释放不需要做任何事情，这也就意味着加过偏向锁的MarkValue会一直保留偏向锁的状态，因此即便同一个线程持续不断地加锁解锁，也是没有开销的。如果有不同线程竞争锁，这时候要先将偏向锁撤销（revoke）为轻量锁，再升级为重量锁

当然上述过程只是简要介绍了synchronized的流程，具体实现还会更加复杂一些，比如在hotspot的实现中synchronized也用到了自旋锁，在进入等待队列前，其实会自旋一小段时间，如果发现期间锁被释放则立即获取锁，这看起来对于正在队列中等待的其他线程稍显不公，不过这样做的好处是可以提高系统整体吞吐率。

自旋锁

什么是自旋锁呢？要想弄明白自旋锁，首先要理清一个概念，究竟什么是CAS（CopmareAndSwap）？为了揭开它的神秘面纱，先从我们熟悉的Java层的AtomicReference类开始吧：

public final V getAndSet(V newValue) {
    while (true) {
        V x = get();
        if (compareAndSet(x, newValue))
            return x;
    }
}

通过观察这个getAndSet方法，其思路就是while死循环，直到compareAndSet成功为止。再看看compareAndSet是如何实现的呢？

public final boolean compareAndSet(V expect, V update) {
    return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}

原来是利用了sun.misc.Unsafe库中的native方法提供了C++层面的CAS原子操作，继续刨根问底，看看unsafe.cpp写了什么：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

再继续找找Atomic::cmpxchg函数：

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

最后终于看到一行关键代码cmpxchg指令，跟到这里也就差不多到头了，这是汇编语言对机器原子操作的封装。语法：cmpxchg dest , r ，这条指令首先将dest指向的值与累加寄存器（这里就是eax）的值相比较，如果相等，那么久把寄存器r中的值赋值给dest指向的内存。注意这句指令到前面有一个LOCK_IF_MP的宏，它其实是提供一个汇编指令的lock前缀，用来保证这一步操作的原子性。也就是说最终CAS的原子性由硬件保证，这也是C++/Java各种锁得以实现的根基！

知道了以上这些，我们其实不难实现一个简单的自旋锁，仍然使用AtomicBoolean就行：

public class SpinLock {

    private AtomicBoolean sign =new AtomicBoolean(false);

    public void lock() {
        while(!sign.compareAndSet(false, true)) {}
    }

    public void unlock () {
        sign.set(false);
    }
}

不过自旋锁真的就这十几行代码就搞定了吗？

显然，这个例子仅仅为了示意，真正在java中使用自旋锁，还是需要使用系统中那些实现了AbstractQueuedSynchronizer抽象类的锁。这个SpinLock本质上是一个TAS（Test and Set）锁，它逻辑非常简单清晰，可惜就是性能低下，我们来分析下原因：

在第二部分讲解synchronized关键字时提到偏向锁能避免锁重入时CAS操作带来的开销，如果我们的自旋锁，每次循环都进行CAS操作，那就会不断地令CPU二级缓存时效，性能可想。于是一种改进版本TAS锁就被设计出来：

public class TTASLock {

    private AtomicBoolean sign =new AtomicBoolean(false);

    public void lock() {

        while(true) {

            while(sign.get()) {}
            if(sign.compareAndSet(false, true)) {

                break;
            }

        }
    }

    public void unlock () {
        sign.set(false);
    }
}

这种解决方案相对于TAS锁有了缓解，把自旋放在了get操作上，但是当多个线程竞争的情况下，CAS还是会频繁发生，况且基于这种原理的锁，竞争完全依赖操作系统的线程调度，没法做到公平，有可能会出现饿死的现象。于是解决这个问题的关键，是要引入排队机制。

假设有一个如上形式的队列，每个节点对应一个线程，保证FIFO，每次只有队头的线程持有锁，后一个节点在前一个节点的一个成员变量上自旋，只有竞争进入队列的节点调用一次CAS将自己设为队尾，如此一来，大大减少了CAS操作的次数，这样的队列有个学名叫CLH队列，由Craig, Landin, Hagersten这三个人的名字缩写得来，当然实现了CLH的锁就称之为CLH Lock。

CLHLock本身就是一个队列，它的特点是：

在前一个线程的节点上进行自旋
使用隐式链表，每个节点中仅仅包含一个标记位，没有向后的引用
为了避免操作引用引起的同步，使用ThreadLocal来保存指向节点的引用，进一步提升了效率。

public class CLHLock implements Lock {

         AtomicReference<QNode> tail;
         ThreadLocal<QNode> myPred;
         ThreadLocal<QNode> myNode;

         public CLHLock() {
                   tail = new AtomicReference<QNode>(new QNode());
                   myNode = new ThreadLocal<QNode>() {
                            protected QNode initialValue() {
                                     return new QNode();
                            }
                   };

                   myPred = new ThreadLocal<QNode>() {
                            protected QNode initialValue() {
                                     return null;
                            }
                  };

         }


         @Override
         public void lock() {
                   QNode qnode = myNode.get();
                   qnode.locked = true;
                   QNode pred = tail.getAndSet(qnode);
                   myPred.set(pred);
                   while (pred.locked) {

                   }

         }


         @Override
         public void unlock() {
                   QNode qnode = myNode.get();
                   qnode.locked = false;
                   myNode.set(myPred.get());

         }

     class QNode {
          public volatile boolean locked;
     }

}

看到这里，发现问题又来了，总是在前一个node上自旋，效率就是一定最高吗？

说到这里又必须扯上硬件了，在CPU多核的时代，不得不提到SMP(Symmetric Multi-Processor)架构，它将多个处理器与一个集中的存储器相连。在SMP模式下，所有处理器都可以访问同一个系统物理存储器，这就意味着SMP系统只运行操作系统的一个拷贝。因此SMP系统有时也被称为一致存储器访问（UMA）结构体系。

SMP架构图：

显然这一架构的缺点就是随着处理器个数增多，对共享资源（总线、内存）的争用会变得激烈，为了解决这一问题，Linux上采取了NUMA（Non-Uniform Memory Access Architecture）架构：

查阅资料了解到：NUMA系统的结点通常是由一组CPU和本地内存组成，有的结点可能还有I/O子系统。由于每个结点都有自己的本地内存，因此全系统的内存在物理上是分布的，每个结点访问本地内存和访问其它结点的远地内存的延迟不同。

所以如果在NUMA架构下，如果自旋锁选择CLH队列，一定会导致频繁访问远地内存，这不是我们所乐见，那么有可能在本地节点上自旋吗？

答案是肯定的，这就是MCS队列：

MCS与CLH队列有三点不同：

使用显示链表，每个节点包含向下一个节点的引用
每个线程在自己的节点上自旋
解锁也需要一次CAS操作

public class MCSLock implements Lock {
         AtomicReference<QNode> tail;
         ThreadLocal<QNode> myNode;
 
         public MCSLock () {
                   tail = new AtomicReference<QNode>(null);
                   myNode = new ThreadLocal<QNode>() {
                            protected QNode initialValue() {
                                     return new QNode();
                            }
                   };
         }

         @Override
         public void lock() {
                   QNode qnode = myNode.get();
                   QNode pred = tail.getAndSet(qnode);
                   if (pred != null) {
                            qnode.locked = true;
                            pred.next = qnode;
                            // wait until predecessor gives up the lock
                            while (qnode.locked) {

                            }
                   }
         }
 
         @Override
         public void unlock() {
                   QNode qnode = myNode.get();
                   if (qnode.next == null) {
                            if (tail.compareAndSet(qnode, null))
                                     return;
                            // wait until predecessor fills in its next field
                            while (qnode.next == null) {

                            }
                   }
                   qnode.next.locked = false;
                   qnode.next = null;
         }

         class QNode {
                   volatile boolean locked = false;
                   QNode next = null;
         }

}

至于什么时候要用MCS锁，这个要看系统是否支持NUMA，不过对于应用层大可不必为了这两种锁孰是孰非过于纠结，因为它们的效率已经比较高了，况且jvm的支持者们也在不断探寻更加高效的处理方式，这里就顺带列举下hotspot中对于自旋的一些优化策略：

如果平均负载小于CPUs则一直自旋
如果有超过(CPUs/2)个线程正在自旋，则后来线程直接阻塞
如果正在自旋的线程发现Owner发生了变化则延迟自旋时间（自旋计数）或进入阻塞
如果CPU处于节电模式则停止自旋
自旋时间的最坏情况是CPU的存储延迟（CPU A存储了一个数据，到CPU B得知这个数据直接的时间差）自旋时会适当放弃线程优先级之间的差异

各种锁的使用总结

首先总结一下synchronized的使用，虽然说synchronized从单个进程角度上讲效率上不是最优的，但是它有利于整个系统的平衡，也不会轻易让系统的自旋锁个数突破上限，所以既然java的设计者为synchronized做了这么多工作，本意还是希望多去使用它。于是在以下场景里面可以优先考虑使用synchronized：

在线程的实时性要求不是很高时
同步逻辑简单清晰，没有额外的条件
同步块逻辑本身不会频繁进出

synchronized作为一个java 关键字，本身由native实现，已经进行过诸多优化，而且编译器本身也会对同步逻辑进一步优化，所以正常使用时，大可不必担心效率问题，当然我们书写同步块时也是需要注意以下事项：

对数据集合进行同步，最好优选ConcurrentLinkedQueue一类的同步库，性能会更高
尽量不要在循环体内部进入同步块，即避免频繁进出同步块
在保证第2点的前提下，尽量缩小同步块的范围，如果可以，尽量避免将整个方法同步
务必选择final或者static final类型的对象进行同步，避免因为同步的对象发生改变而产生不可预知的后果

其次说说Atomic系列（AtomicInteger等）的注意事项：

用在需要同步读写操作这种情况下，比如CAS类型的compareAndSet()或者对CAS的封装getAndSet()、getAndIncrement()等方法
如果仅仅是并发写和读，不必用AtomicXXX直接使用volatile关键字即可，因为java中的赋值操作本身就是原子的，你看AtomicInteger中的set和get不也没有加什么同步逻辑么
虽然Atomic性能比synchronized要高出几倍，但也千万别自作聪明的在一个Atomic类型变量上自旋，这个是效率极低的做法

最后来看看CountDownLatch、Semaphore、ReentrantMutex和ReentrantLock这些锁的使用。它们都是在synchronized或者某种自旋锁上的封装，比如CountDownLatch提供了一个线程与多个线程同步的能力，ReentrantLock同时提供了公平和非公平两种互斥锁，具体使用哪种看需要而定。当然如果只是想用java Object 的wait和notify，我建议用Android源码中的ConditionVariable代替，它在其上做了一层封装，避免了几个容易犯的错误

参考资料：

synchronized机制：
http://www.majin163.com/2014/03/17/synchronized1/
http://www.majin163.com/2014/03/17/synchronized2/
CLH队列讲解：
http://blog.csdn.net/aesop_wubo/article/details/7533186
MCS队列讲解：
http://blog.csdn.net/aesop_wubo/article/details/7538934

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java