形形色色的锁

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

锁有哪些种类

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

  • 乐观锁
乐观锁示意

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

  • 悲观锁
悲观锁示意

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

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

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

熟悉的陌生人——synchronized

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

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

  1. 偏向锁(biased lock)
  2. 轻量锁 (lightweight lock)
  3. 重量锁 (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还是会频繁发生,况且基于这种原理的锁,竞争完全依赖操作系统的线程调度,没法做到公平,有可能会出现饿死的现象。于是解决这个问题的关键,是要引入排队机制。

CHL

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

CLHLock本身就是一个队列,它的特点是:

  • 在前一个线程的节点上进行自旋
  • 使用隐式链表,每个节点中仅仅包含一个标记位,没有向后的引用
  • 为了避免操作引用引起的同步,使用ThreadLocal来保存指向节点的引用,进一步提升了效率。
CHL链表
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架构图:

SMP

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

NUMA

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

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

答案是肯定的,这就是MCS队列:

MCS

MCS与CLH队列有三点不同:

  • 使用显示链表,每个节点包含向下一个节点的引用
  • 每个线程在自己的节点上自旋
  • 解锁也需要一次CAS操作
MCS链表
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:

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

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

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

其次说说Atomic系列(AtomicInteger等)的注意事项:

  1. 用在需要同步读写操作这种情况下,比如CAS类型的compareAndSet()或者对CAS的封装getAndSet()、getAndIncrement()等方法
  2. 如果仅仅是并发写和读,不必用AtomicXXX直接使用volatile关键字即可,因为java中的赋值操作本身就是原子的,你看AtomicInteger中的set和get不也没有加什么同步逻辑么
  3. 虽然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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

Java研发方向如何准备BAT技术面试

背景: 最近BAT等各大互联网巨头们的校招陆陆续续都准备开始了,可能对于在校的大多数学生来说,不知道如何正确衡量自己掌握的技术,更不知道BAT这...

1.5K4
来自专栏Java Web

模仿天猫实战【SSM版】——后台开发

3436
来自专栏Phoenix的Android之旅

Dagger2 Android应用:@Component和@Module

这部分会介绍一下DI的主要概念,包括Component,Module,但不涉及和Android有关的具体代码。

1332
来自专栏Java学习网

Java初学人员的注意事项

Java中J2SE J2EE J2ME的区别 多数编程语言都有预选编译好的类库以支持各种特定的功能,在Java中,类库以包(package)的形式提...

2348
来自专栏Android相关

IjkPlayer初始化过程

最近调研做视频秒开,使用B站开源的ijkplayer作为播放器。ijkplayer基于ffmpeg的播放器。

2771
来自专栏企鹅号快讯

Java 9 逆天的十大新特性

在介绍 Java 9 之前,我们先来看看 Java 成立到现在的所有版本。 1990 年初,最初被命名为 Oak; 1995 年 5 月 23 日,Java 语...

2295
来自专栏JackieZheng

Java豆瓣电影爬虫——小爬虫成长记(附源码)

  以前也用过爬虫,比如使用nutch爬取指定种子,基于爬到的数据做搜索,还大致看过一些源码。当然,nutch对于爬虫考虑的是十分全面和细致的。每当看到屏幕上唰...

36711
来自专栏美团技术团队

Android热更新方案Robust

美团•大众点评是中国最大的O2O交易平台,目前已拥有近6亿用户,合作各类商户达432万,订单峰值突破1150万单。美团App是平台主要的入口之一,O2O交易场景...

4149
来自专栏BaronTalk

在Android项目中使用Java8

前言 在过去的文章中我介绍过Java8的一些新特性,包括: Java8新特性第1章(Lambda表达式) Java8新特性第2章(接口默认方法) Java8新特...

3076
来自专栏机器学习从入门到成神

Java 进阶面试问题列表

1061

扫码关注云+社区

领取腾讯云代金券