并发编程系列之一:锁的意义

12月 23rd, 2013

 

背景

 

C/C++语言的并发程序(Concurrent Programming)设计,一直是一个比较困难的话题。很多朋友都会尝试使用多线程编程,但是却很难保证自己所写的多线程程序的正确性。多线程程序,如果涉及到对共享资源的并发读写,就会产生资源争用(Data Race)。解决资源争用,最直接的想法是引入锁,对并发读写的数据进行保护(更高级的则包括无锁编程—— Lock Free Programming)。但是,锁又有很多种类,例如:自旋锁(Spinlock)、互斥锁(Mutex)、读写锁(Read-Write-Lock)等等。这么多的锁,每种锁有什么特点?对应哪些不同的使用场景?使用过程中需要注意哪些事项?各自分别有哪些不足之处?都是困扰程序员的一个个问题。

 

甚至,一个最基本的问题:为什么锁就能够用来保护共享资源?锁真正蕴含的意义有哪些?我相信很多使用过各种锁的程序员,都不一定能够完全正确的回答出来。

 

有鉴于此,本人希望将自己近10年数据库内核研发,所积累下的并发编程的经验记录下来,形成一个系列的文章,分享给大家。这个系列,个人打算对其命名为 #并发编程系列# ,作为此系列开篇的文章,本文将从一个简单的并发编程的例子出发,引出锁真正蕴含的意义

 

一个测试用例

 

并发程序处理中,面临的一个最简单,也是最常见的共享资源的争用,就是针对一个全局变量进行并发的更新和读取。这个全局变量,可以是一个全局计数器,统计某个事件在多线程中发生的次数;或者是一个全局递增序列,每个线程需要获取属于其的唯一标识。诸如此类,多个线程,针对一个全局变量的并发读写,是十分常见的。如下图所示:

global count ++

此用例中,N个线程,并发更新一个全局变量。让我们先来看一个简单的测试,全局变量global_count没有任何保护,此时会发生什么?

 

测试场景:500个线程,每个线程做10000次global_count++操作,主线程首先将global_count初始化为0,然后等待这500线程运行结束。待500个线程运行结束之后,由于每个线程都做了10000次global_count++,那么可以确定,最后的global_count取值应该是5000000。事实是这样吗?根据此测试场景,撰写测试代码,每个线程做的都是同样的事,代码很简单:

threadaddfunc

主线程等待所有500个线程结束之后,进行判断,若global_count不等于5000000,则打印出当前global_count的取值。运行结果如下:

通过上图,可以发现,global_count并不是每次都等于5000000,很大的几率,global_count要小于5000000。多线程对一个全局变量进行++操作,并不能保证最终得到的结果的正确性。究其内部原因,是因为++操作并不是一个原子操作(Atomic Operation),而是对应至少3条汇编语句,考虑如下两个线程的 ++ 操作并发:

线程1,2,分别读取了global_count的当前值,分别加1后写出。线程2的写覆盖了线程1的写,最后导致两次 ++ 操作,实际上却对global_count只加了1次。

 

如何解决此问题,相信大家都有很多方法,例如:将global_count声明为原子变量(C++ 11标准支持)。但是此文,并不打算使用原子变量,而是将global_count的++操作,通过Spinlock保护起来。一个全局的Spinlock,500个线程,在++操作前,需要获取Spinlock,然后进行global_count的++操作,完成后释放Spinlock。对应的每个线程代码修改如下:

global_count++ with spinlock

主线程,仍旧是同样的逻辑,等待所有的500个线程执行结束之后,判断global_count取值是否等于5000000,如果不相等,则打印出来。此时,同样执行此测试程序,没有任何一条数据打印出来,每一个循环,都满足global_count等于5000000。通过引入了Spinlock,完美了解决上面的问题。

 

为什么引入了Spinlock保护之后,多线程针对全局变量的并发读写所带来的问题就解决了?此问题,恰好引入了锁意义的剖析。

 

锁的意义

 

在分析锁的意义前,先来简单看看Spinlock的功能:Spinlock是一把互斥锁,同一时间,只能有一个线程持有Spinlock锁,而所有其他的线程,处于等待Spinlock锁。当持有Spinlock的线程放锁之后,所有等待获取Spinlock的线程一起争抢,一个Lucky的线程,抢到这把锁,大部分Unlucky的线程,只能继续等待下一次抢锁的机会。

 

由此来说,在spinlock锁保护下的代码片段,同一时间只能有一个线程(获得Spinlock的线程)能够执行,而其他的线程,在获取spinlock之前,不可进入spinlock锁保护下的代码片段进行执行。前面的测试用例,由于spinlock保护了global_count++的代码,因此global_count++操作,同时只能有一个线程执行,不可能出现前面提到的两线程并发修改global_count变量出现的问题。How Perfect!!!注:在spinlock加锁之前,以及spinlock放锁之后的代码段,可以由多线程并发执行。)

spinlock

但是,故事到此就完了吗?我相信对于大部分程序员来说,或者是之前的我来说,认为故事到此就结束了。已经成功的使用了一个Spinlock,来保护全局变量的并发读写,保证了并发访问的正确性。

 

但是(又是这个该死的但是),故事并未结束,这个案子也还没有了结。有一定经验的C/C++程序员,或者是曾经看过我写过的一个PPT:《CPU Cache and Memory Ordering——并发程序设计入门》,以及一篇博客:《C/C++ Volatile关键词深度剖析》,的朋友来说,应该都知道这个故事还有一个点没有挖掘:内存模型(Memory Model),无论是程序语言(如:C/C++,Java),或者是CPU(如:Intel X86,Power PC,ARM),都有所谓的内存模型。

 

简单来说,内存模型规定了一种内存操作可见的顺序。为了提高程序运行的效率,编译器可能会对你写的程序进行重写,执行顺序调整等等,同样,CPU也会对其执行的汇编执行进行顺序的调整,这就是所谓的乱序执行。最基本的四种乱序行为,包含:LoadLoad乱序;LoadStore乱序;StoreLoad乱序;StoreStore乱序,分别对应于读读乱序,读写乱序,写读乱序,写写乱序。关于这四种乱序行为更为详细的介绍,可参考Preshing的博客:《Memory Reordering Caught in the Act》,《Memory Barriers Are Like Source Control Operations》,或者是《SMP Primer for Android》这篇文章。本文接下来的部分,假设读者已经知道了无论是编译器,还是CPU,都会存在编译乱序与指令执行乱序的现象。

 

编译乱序与指令执行乱序,跟本文讨论的锁的意义有何关系?可以说,不仅有关系,还有很大的关系,关系到锁之所以能够称之为锁,能够用来保护共享资源的关键。

 

一个简单的问题:在存在编译乱序与指令执行乱序的情况下,怎么保证锁所保护的代码片段,不会被提前到加锁之前,或者是放锁之后执行?如果编译器将锁保护下的代码,通过编译优化,放到了加锁之前运行?又如果CPU在执行指令时,将锁保护下的汇编代码,延迟到了放锁之后执行?如下图所示:

如上所示,如果编译器做了它不该做的优化,或者CPU做了其不该做的乱序,那么spinlock保护下的代码片段,同一时刻,一定只有一个线程能够执行的假设被打破了。此时,虽然spinlock仍旧只能有一个线程持有,但是spinlock保护下的代码,被提到了spinlock保护之外执行,spinlock哪怕功能再强大,也不能保护锁之外的代码,提取到spinlock锁之外的代码,能够并发执行。

 

但是上面的测试说明,spinlock保护下的global_count++操作,在多线程下能够正确执行。也就说明,无论是编译器,还是CPU,并没有不合时宜的做上面的这些优化。而分析其原因,刚好引出了锁(Spinlock、Mutex、RWLock等)的第二层意义:Lock AcquireUnlock Release

 

什么是Lock Acquire,Unlock Release又意味着什么?在此之前,需要先看看什么是Acquire和Release。Acquire和Release语义(Semantics)是程序语言和CPU内存模型(Memory Model)中的一个概念。以下,是截取自Preshing博客《Acquire and Release Semantics》一文中,对Acquire与Release Semantics的定义:

 

Acquire semantics is a property which can only apply to operations which read from shared memory, whether they are read-modify-write operations or plain loads. The operation is then considered a read-acquire. Acquire semantics prevent memory reordering of the read-acquire with any read or write operation which follows it in program order. (注:Acquire语义是一个作用于内存读操作上的特性,此内存读操作即被视为read-acquire。Acquire语义禁止read-acquire之后所有的内存读写操作,被提前到read-acquire操作之前进行。

 

Release semantics is a property which can only apply to operations which write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation which precedes it in program order.(注:Release语义作用于内存写操作之上的特性,此内存写操作即被视为write-release。Release语义禁止write-release之前所有的内存读写操作,被推迟到write-release操作之后进行。

 

从Acquire与Release语义的定义可以看出,两个语义对编译器优化、CPU乱序分别做了一个限制条件:

 

  • Acquire语义限制了编译器优化、CPU乱序,不能将含有Acquire语义的操作之后的代码,提到含有Acquire语义的操作代码之前执行;

    acquire sematics

  • Release语义限制了编译器优化、CPU乱序,不能将含有Release语义的操作之前的代码,推迟到含有Release语义的操作代码之后执行;

release sematics

有了明确的Acquire和Release语义的定义,再回过头来看前面提到的锁的第二层含义:Lock Acquire和Unlock Release。加锁操作自带Acquire语义,解锁操作自带Release语义。将加锁、解锁的两个语义结合起来,就构成了以下的完整的锁的含义图:

锁含义

spinlock,只有带有了Acquire和Release语义,才算是一个真正完整可用的锁——Acquire与Release语义间,构成了一个临界区。获取spinlock后的线程,可以大胆的运行全局变量的读写,而不必担心其他并发线程对于此变量的并发访问。

 

好消息是,pthread lib所提供的spinlock、mutex,其加锁操作都自带了acquire语义,解锁操作都自带了release语义。因此,哪怕我们在使用的过程中,不知道有这两个语义的存在,也能够正确的使用这些锁。但是,读者需要实现自己的spinlock、mutex(注:实际情况下,确实有这个必要,数据库系统如Oracle/PostgreSQL/InnoDB,都有自己实现的Spinlock、Mutex等),那么对于锁的了解,到这个层次,是必不可少的。

 

总结

 

本文,作为 #并发编程系列# 的开篇,首先跟大家分析了锁(Spinlock、Mutex、RWLock等)所代表的真正意义。首先,这些锁要么保证同一时刻只能由一个线程持有(如:Spinlock、Mutex),要么保证同一时刻只能有一个写锁(如:RWLock);其次,锁的加锁操作带有Acquire语义,解锁操作带有Release语义。通过这两个条件,保证了加锁/解锁之间,构成了一个完整的临界区,全局资源的更新操作,可以在临界区内完成,而不必担心并发读写冲突。而这正是并发程序设计的基础:构建一个Data-Race-Free的多线程系统。

 

接下来,作为 #并发编程系列# 的后续文章,将会就如何实现自己的Spinlock、Mutex、RWLock?各种锁之间的区别及应用场景?以及各种锁使用过程中的注意事项,逐个展开讨论,敬请期待!

 

注:关于此文中的测试用例,可点击此处下载:global_count

  1. 宋仲凯
    12月 23rd, 201321:15

    豁然开朗

  2. acmerfight
    12月 23rd, 201322:12

    写的真是深入,学习了。当时我也翻译过Python中线程的理解。http://jianshu.io/p/4a13a05e4f1f
    但是跟您这篇文章的深度真是相距甚远,认真学习。

  3. Hongliang Sun
    12月 23rd, 201322:24

    您好,看了你的文章,很受启发。
    然而我有个问题,请问你的实验环境是不是默认为多核系统?
    因为我认为对于spinlock而言,单核处理器与多核处理器的性能会差很多,单核情况下,不拥有spinlock的线程,会不停的自旋,白白浪费CPU时间片,使得CPU利用率降低?

    • hedengcheng
      12月 23rd, 201322:55

      我测试,是在多核环境下做的。spinlock由于不放弃cpu,因此肯定会限制单核下的性能。下次我会写一篇各种spinlock实现与优化的文章。

      • Hongliang Sun
        12月 24th, 201300:15

        谢谢,那真是太好了

      • Bill
        12月 24th, 201323:08

        spinlock锁的出现就是为了解决多核并发编程带来的资源争用,在单核应该是没有使用spinlock锁的必要和意义。

        • hedengcheng
          12月 25th, 201309:39

          首先,单核下,也可以执行多线程程序,也存在资源争用,多线程/资源争用,与单核、多核无关;
          其次,单核下,使用spinlock来保护共享资源无意义,因为等待的线程不释放cpu资源,持有的线程无法释放spinlock。

          • xiao_song
            12月 25th, 201309:50

            所以spinlock适合多核条件下用来保护,执行时间非常短小的代码,
            以轮询代替线程sleep,被唤醒后重新调度的代价。

          • hedengcheng
            12月 25th, 201311:35

            是的。这就是不同类型锁的不同使用场景。

    • aaron
      12月 24th, 201310:55

      看过一些spinlock的实现,都会去判断cpu数目,如果cpu只有一个,那么就会放弃时间片

      • hedengcheng
        12月 24th, 201312:10

        嗯,spinlock的实现,有很多可以深挖的细节。

        • apprentice89
          5月 21st, 201410:52

          之前听中科院侯锐老师讲过spinlock的一个实现,好像使用指令集中的某些特殊的指令,能够提高性能还是降低能耗来着。期待大神写点关于实现的分析。

    • 郜小农
      12月 25th, 201314:10

      linux 单核情况下,spinlock会退化成禁止抢占,除了中断,没有其它任务可以再去得到CPU,也就没有你提到的不停的自旋。

  4. 海鸣
    12月 23rd, 201322:53

    有学习了到了新知识,期待下期精彩内容!

  5. kevin
    12月 23rd, 201323:05

    真心不错哈哈,之前只是知道锁,还不知道CPU和编译器优化也会导致锁的无效,同时知道了Acquire和release让编译器和CPU不乱来。。

  6. June
    12月 24th, 201300:01

    以前完全没有注意到Acquire和Release啊!又学习了!!

  7. bryantism
    12月 24th, 201309:10

    浅显易懂谢谢

  8. 王威
    12月 24th, 201309:41

    这学期正在学习操作系统,哈哈,加深了了解

  9. bryantism
    12月 24th, 201309:53

    请问原子变量是不是也应该有acquire和release语义?

    • hedengcheng
      12月 24th, 201309:57

      原子变量,看不同的实现。有些CPU支持一些原子操作,如cas,那么指令就是不可分割的,因此也就不会出现文中的++分成3条指令执行的问题。如果是c++ 11所支持的原子变量,那么会带有更多的语义,当然也有acquire,release语义可以选择。可以参考这方面的资料。

  10. 外太空木鱼
    12月 24th, 201310:05

    个人觉得 SMP Primer for Android http://t.cn/zYH2j5d 讲得要比 Preshing 的要更简介易懂,而且讲得是why,不是simulation

    • hedengcheng
      12月 24th, 201312:10

      谢谢推荐!这篇文章不错,ARM作为Weak Order的Memory模型,对于顺序方面的问题,会更加注重。

  11. IdleMind
    12月 24th, 201310:12

    好文要赞。
    明白了内存重排序和指令重排序,Acquire和Release。期待后面的文章。

  12. 里白
    12月 24th, 201312:27

    很细致,拜大神

  13. heiyan
    12月 24th, 201313:23

    太赞了

  14. 邓波
    12月 24th, 201321:13

    登博提到的所有知识点自己过去都知道,但素登博这文章给串起来了,迈着轻快地步子吹着小口哨读完。一气呵成。
    通俗易懂有深度!只有像登博理解的如此透彻才能声情并茂的讲出来吧。真棒!
    迫不及待期待下一篇!!!!!

  15. passinger
    12月 25th, 201309:32

    如果在acquire和release之间的代码没执行完的时候应该不能发生线程调度吧,线程的中断应该要在这段锁保护的代码执行完之后才能发生。

    • hedengcheng
      12月 25th, 201309:37

      可以调度,这个没有硬性规定。

      • passinger
        12月 25th, 201310:32

        如果可以调度,会不会由于新的执行线程对共享内存的修改导致被中断线程之前的修改作废,这样在被中断线程重新运行的时候会出错?

  16. magicminglee
    12月 25th, 201310:35

    持续关注中,期待下一篇好文,赞一个

  17. 郜小农
    12月 25th, 201314:13

    期待后续好文,赞

  18. ryan
    12月 25th, 201320:17

    涨之势了,谢谢博主

  19. mutoo
    12月 26th, 201311:48

    请教大神如何评价erlang这种无锁并发编程语言?最近我看了一些erlang的资料,觉得很有意思,但还没有深入学习。

    • hedengcheng
      12月 26th, 201313:01

      对不起,erlang我不懂啊,有时间我也要学习下。

  20. geecoodeer
    12月 26th, 201317:39

    我最近也在看并发编程相关的资料,有以下几个疑问,可否帮忙解答下
    1.内存屏障是否保证CPU将CPU缓存刷写回内存,进而保证多核之间的内存一致性?还是说,内存屏障保证单核寄存器,缓存一致性,然后间接通过MESI等协议来维护各核的一致性?
    2.spinlock 在SMP一般使用 lock CMPXCHG 等类似指令实现,而lock 仅仅适用于锁定单条汇编指令的操作,并且不是范围锁(该汇编指令执行完毕就释放锁)。而mutex这种范围锁是如何实现的?底层有对应的汇编指令吗?

    • hedengcheng
      12月 26th, 201321:11

      说真的,你这个问题,一两句解释不清楚。建议你看看我写的那篇ppt,就是此文中参考的那篇,知识点很多。你的问题都有涉及。

  21. stanjo
    2月 7th, 201410:50

    感谢分享!

  22. 莫铭
    3月 22nd, 201413:19

    好文章,非常感谢,发现了自己理解的多线程多么的狭隘,需要更深入才行

  23. 翅膀
    6月 18th, 201410:44

    够深入, 期待后续文章.

  24. csuhawk
    8月 4th, 201420:02

    这么简单的东西能码这么多字,楼主总结能力不错

  25. bob
    8月 15th, 201417:22

    锁除了有acquire和release语义,应该还要保证可见性,不知道具体是怎么做的。

  26. CC
    12月 12th, 201422:11

    500个线程,我做了下实验,在每个线程都加5000000次的时候,spin lock的时间消耗显然远远大于mutex,spinlock一直在旋转耗用CPU,这种线程个数远远大于核数的情况是不是用spin lock不太好?

  27. bus
    6月 25th, 201510:52

    大神,linux 上c/c++开发 你使用什么工具?介绍介绍,呵呵

  28. Slark
    7月 19th, 201522:14

    感谢,期待后续篇章!

  29. 通通学
    3月 7th, 201610:15

    好东西