阿男的小窝

View the Project on GitHub

关于并发编程的一些思考(一)

(这个系列的文章也是旧文,慢慢整理到博客当中。)

梳理学习的脉络,给大家讲讲atomicitylockconsistency三个概念和它们背后的世界。

我们已经在一个并行计算的世界里面了:我们的CPU是多核的,我们的操作系统是多任务操作系统,我们生活在网络时代,网络群集部署是并发的自然应用。所有和并发相关的领域,重要性都会越来越加强,所以把并发这块学好也是很重要的。

并发编程涉及到三个大的问题:

实际上并发编程是非常有趣的,因为它贴近我们日常生活中的很多场景,在学习过程中,我们就可以感受到。

为了实现协同工作,我们要用到很多技术。比如,如果多个worker要同时访问一个资源,那么必然要有先后顺序。如何协调这种顺序呢?这里面就引申出很多的标准化的概念,用于描述各种可能的场景,比如Quiescent ConsistencySequential ConsistencyLinearizability

此外,一个worker在使用一个资源的时候,如何保证其它worker不动这个资源?也就是说,如何保护这个资源?这就涉及到了Lock(锁)的概念。但是锁本身该如何实现?这里面要有很多比较艰难的学习过程。

还有更复杂的情况,可能一个worker要做3件事情,要保证这三件事情要么同时成功,只要有一件事情失败,那么整个3件事情要全部算做失败,回到初始状态。这里面就有了Transaction(事务)的概念。

这些加在一起,就是并发编程的研究领域了,里面涉及到的理论模型,算法,实际应用。后续的文章会讲这些内容。

大家觉得并发编程学习起来很难,其实这块主要是知识体系比较庞大,设计比较多,理论学习比较漫长,找到一个学习的脉络,学习起来就不难。

首先我们要明白并发编程要解决什么问题。所谓「并发」,本质上就是指,同时有多个worker在工作,这些workers可能在做同一个task,也可能在做不同的task。此外,如果是多个tasks,那么这些tasks,可能相互之间有关联,也可能没有关联。

那么我们把上面所说的场景详细划分一下。首先是最简单的,一个worker,一个task,这种就谈不上「并发」了,就是一个线性的一个人的独立工作。这个就没什么可讲的。

接下来是多个workers,做多个tasks,但是多个tasks之间毫无关联,这个也没什么可讲的,就相当于各个worker做各自手里毫不相关的task,一个个都是孤岛,那么也和之前一个worker,一个task本质上是一样的。就算是每个worker手里有多个tasks,如果worker手里的task互相不相关,那也是一样的情况。

最后一种情况是我们要考虑的,其实是两种情况,就是多个workers对应一个task,或者对应多个tasks,但是多个tasks之间有关联性。

这两种情况涉及到两个问题:第一个问题,多个workers之间如何协调执行顺序?如果执行顺序错误,很可能任务失败,这里面涉及到任务本身的逻辑。

第二个问题是,多个workers之间如何不冲突地使用资源?因为多个workers可能在执行一个任务,这个任务里面涉及的到的资源是共享的,而这些资源可能不能同时交给多个workers去使用,否则可能会产生逻辑错误。还有就是如果多个tasks之间有关联性,那么它们的资源也可能有关联性,可能在使用方面也是有顺序性和独占性。

因为,并发编程所有的理论,实现,设计模型,就是要解决这两个问题:「协调并发执行循序」,「协调资源的使用」。

为了解决「协调并发执行循序」,「协调资源的使用」这两个问题,人类做了大量的研究,产生了很多的研究结果,制造了很多解决实际问题的工具。而我们要学习的就是这些东西了。

为了协调并发执行顺序和协调资源的使用,我们需要协调的手段。比如,如何让Worker A等待Worker B完成了特定任务后,再继续执行任务?

还比如,如果Worker AWorker B都要使用Resource X,但是不能同时对Resource X做操作,怎样才能让它们不同时操作Resource X

这种情况下,我们往往使用「锁」来实现「互斥」,「独占」,来完成「协调执行顺序」和只允许一个worker访问某个resource的工作。

于是,「锁」,也就是lock的实现,如何可靠地获得锁,如何可靠地释放锁,就是一个研究领域。

什么叫「可靠地获得锁」?我们可以自己想想。应该可以大概想到一些内容,比如:不能让两个worker同时获得同一个lock,那么这个lock也就没有意义了。所以在lock的实现方面,我们不能让这种事情发生。

为了避免这种事情发生,最终我在硬件上有保障,保证lock的可靠性,也就是说,硬件必须要提供atomicity,原子性。体现在观测结果上,所有worker都需要观测到一个object的「状态改变」的「一致性」。不能说A观测到一个状态的改变,B没观测到,如果是这样的话,锁的实现是无从谈起的。

大家是不是觉得概念上很抽象?但是在软件的实现上,我们经常会和上面所说的atomicity打交道的。

最常见的就是Java里面的volatile这个关键字。如果我们一个「变量」不使用volatile这个关键字,那么Java的「虚拟机」可能就不会「同步」这个「变量」。如果你的程序是multi-threaded,也就是「多线程」的,每一个thread里面观测到的这个「变量」的值可能是不一样的。

为什么?因为层次的丰富性。什么意思?我们的程序面对一个多层的世界:虚拟机,操作系统,CPU。

现代的虚拟机或是操作系统使用的是复杂的虚拟内存实现,为的是效率最大化。对于多线程,使用的是allocation on demanding的策略。也就是说,能共享的数据,就尽量共享,需要分割的数据,再独立划分空间。

然后是CPU,现代的CPU都提供缓存,提高运行速度,多核CPU下,每颗CPU有自己独立的缓存。你看到的数据是CPU缓存数据,而不是内存里面的实际数据。

于是什么时候CPU更新缓存就成了问题。单线程的程序没有这个焦虑,但是多线程的程序里面,就算是一个Thread更新了一个「共享变量」的数据,另一个Thread也不一定能看得到这个改变。

为什么?这里面有好多层要考虑的因素:首先,CPU的缓存也是提供给操作系统指令接口,由操作系统负责更新策略的。

其次,虚拟机在实现的时候,要提供给代码编写者接口控制CPU的缓存更新。比如Java的volatile关键字。一切为了性能。

但是对于新手,就不知道这些,可能觉得,我在一个thread里面更新了一个共享数据的值,那么在另一个thread里面就可以观测到,其实根本不是。

如果你不使用volatile关键字,另一个thread读到的可能还是另一个CPU里面的「缓存」数据,而不是「内存」里面更新后的数据。下图展示了CPU缓存,Thread观测到的数据,以及内存的关系1

所以,lock的实现,要基于所有这些层次丰富的世界进行考量,要考虑到所有的观测不一致的可能性。所以说,软件的「锁」的实现,是基于「硬件」,「操作系统」,「虚拟机」一个综合考虑,最终落到一个实处:CPU是一个晶振芯片,时间的原子性。

我们之前说,volatile关键字保证CPU每一个核都会更新自己的cache,保证多个thread下,某一个thread更新了一个变量,这个内存里面的数据改变,可以更新到每一个CPU的cache里面去。

那么我们可以再想,如果CPU的某一个core的cache正在更新的时候,这个core上面的thread正在读取这个变量怎么办?岂不是成了薛定谔的猫?

所以在硬件设计上面,就不能允许这种情况的存在:CPU的指令是一条一条执行的,而cache的更新则保证会在前一条数据修改指令结束后,下一条读取指令到来前,cache更新完毕,而不管是哪个core写,哪个core读。

如果没有CPU的原子性作为保障,一切秩序都无从谈起。

而为什么我们使用volatile关键字,就可以保证一个变量会更新到CPU所有core的cache里面去了呢?

为什么并发编程难?层次的丰富性。

好,我们来看CPU的cache的实现2

如上所示,CPU里面有Cache Line的概念,也就是说,如果是在一条cache line的的数据被修改,那么一条线上各个CPU的cache都要被更新。就像上面看到的那样,就算这条线上的某一个数据被更新,那这条线上所有的cached data都要从内存重新加载。Intel的这个设计,叫做MESI (Modified/Exclusive/Shared/Invalid) protocol

而现代的编译器或是虚拟机,会去做一些优化工作,维护一个thread local变量,不让shared data放在一个cache line上面去,这样一个变量被一个thread更新的时候,并不会造成所有的cache line更新。为什么要这么做?当然是为了速度和效率。而volatile关键字当然就是保证这种编译器或是虚拟机内部不会做这种优化,保证这个变量一定会更新到cache line。

所以原子性的保证,来自于这么多层面,这是我们要了解的。

我们了解了Atomicity的概念,直到了这个是一切的保证。为什么这么说?比如我们让CPU执行两个指令:

x = 3
x = -4

那么x在某一个状态的时候,要么为3,要么为-4,不可以是-35这种毫不相干的状态。因此我们说如果一个operationatomic的,硬件要保证这个operationatomicity,否则计算的可靠性就无从谈起了。

从我们硬件使用者的角度来看,这是最起码的东西,但是从硬件实现者的角度来看,变量的赋值至少要经过:寄存器,CPU的二级缓存,DMA通道,内存单元。对于赋值还好,对于运算要考虑的更多。比如Intel在操作SSE寄存器的时候提供Memory Fencing的能力来保证原子性,目前不必理解细节,但是我们要知道硬件在设计的时候,提供Atomicity并不像使用者看到的那么简单。

Atomicity说的差不多了,关于锁的具体实现和具体分类我们后续再讲。接下来我们要想想协调workers的执行顺序的问题了。

首先得定义什么是执行顺序。

在现实生活中,我们对很多工作的顺序要求其实是不一致的:有的工作有严格的步骤,必须按照1,2,3这样的顺序完成。如果1没完成,不可以开始2,如果2没完成,不可以开始3。这种我们叫做blocking sequential work,首先,它是blocking的,1会把2给block住,2会把3给block住。

还有的工作,并不在意顺序,可以123,也可以231,怎样都行,只要123之间不会互相会影响就可以的。比如上面举的例子:

x = 3
x = -4

假如两个worker,一个让x=3,另一个让x=-4,如果我们允许结果是3或者-4,只要不是-3就行,这种也是非常简单的。

真正难的是更细微的同步协调层面。比如之前举例子用到的Java的volatile关键字这里。如果worker1把一个共享的变量x赋值3,此时worker2却看不到这个更新的变量,原因是worker1和worker2在CPU的不同core上面,而worker2的core cache和worker1的core cache没有同步,这种情况是允许的吗?

如果你的使用场景允许,就可以不使用volatile关键字标记变量,如果你的使用场景不允许这种不同的情况发生,就要使用volatile关键字,防止compiler进行的优化造成CPU的cache line不更新。

不允许的场景,我们叫做linearizable consistency。但是volatile关键字保证的是atomicity,一个变量的写入,保证所有的观测者都看到这个更新,但是不保证各个观测者之间的工作顺序,所以我们说linearizable consistencynonblocking的。

我们再想另一个场景,在编译器里面,有时候,我们的目标代码会被优化,比如gcc编译器会提供好几个优化的级别。

高级别的优化,甚至会打乱源代码的执行顺序,编译器在认为破坏代码顺序不回影响运算结果的话,会做这种优化。为什么要打乱代码的执行顺序?因为CPU有pipeline的设计3

如上图所示,CPU内部有Instruction Fetch单元,Instruction Decode单元,Execution单元,Memory Access单元。因此,每一个CPU周期,不同的单元可以并行执行各自的任务。因此如果我们合理安排汇编代码,比如一条取内存的代码,跟着一条执行运算的指令,CPU就可以并行执行两条指令:

因此compiler可能会把源代码中的代码顺序重新安排得更合理,让CPU执行效率更高。

你的代码能够允许这种优化吗?如果不允许,那么你的代码很可能要求sequential consistency这个级别的同步,如果允许,那么你的代码可能要求quiescent consistency就可以。

到这里,给大家讲了atomicitylockconsistency三个概念和它们背后的世界。来看一下关于并发这个领域里面很重要的概念transaction,也就是常说的「事务」。所谓「事务」,就是假设有工作x,y,z,要把它们看成一个整体,要么一起成功,要么一起失败。

如果成功,这个事务就算完成了,如果失败,那么所有的工作都要返回到初始状态,这个返回的动作,叫做rollback,中文就是「回滚」。

所以说事务是一个并发领域的综合应用,我们要考虑很多问题:首先,怎样把不同的任务可以做成一个整体?

然后,如果执行到工作y的时候失败了,那么怎样让工作回滚到xyz都没发生的初始状态?

还要考虑的是,当worker a在进行xyz这个事务的时候,我们要保证这个事务所用到的资源不受打扰,要如何整合资源并实现排他性?所有这些都是事务要考虑的范畴。

如果我们把网络加进来,问题会变得更为复杂,如果我们的工作x在机器a,工作y在机器b,工作z在机器c,之间是通过网络通讯完成的,那么我们怎么保证事务的可靠性?怎么保证在中间环节出错后,可以可靠的rollback?

所以「事务」这个领域的问题,不单纯是一个理论问题,而是一个和具体的世界打交道的问题。因此,所有有关「事务」的研究,不光是研究「事务成功」如何,或是「事务失败」如何rollback,而是要考虑,「事务失败」后还不能rollback,这些灾难的情况都有哪些可能,如何处理,这才是完成的拼图。

所以「事务」这个领域的话题太大了,模型也特别多,基于网络的事务协议更是复杂。个人觉得没必要学得面面俱到,但是会慢慢给大家分享一些这个领域最有价值的东西给大家。

  1. http://tutorials.jenkov.com/java-concurrency/volatile.html 

  2. https://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads 

  3. https://en.wikibooks.org/wiki/Microprocessor_Design/Pipelined_Processors