并行和并发需要不同的工具

并发（名词）：指竞争或对抗。

– dictionary.com

并行：指两条直线永不相交的状态。

– Wikip​edia

在并行和并发的问题上，我与Joe Armstrong（译注：Erlang语言发明者） 和 Rob Pike（译注：Go语言发明者）这俩人的看法并不一致。下面我以自动售货机和礼物盒为例来说明我的观点。（配有我用微软画笔精心制作的插图说明哦）

首先从概念上来说并行和并发都是非常流行的东东，很多编程语言和工具都会重点突出自己在这两个方面上的优异表现。

但我却认为并行和并发需要的是不同的工具，每个工具只会在某一个方面非常好，例如：

• Erlang, Rust, Go和STM Haskell擅长并发处理
• Flow, Cilk, checkedthreads 和 parallel Haskell侧重并行处理

也有像Haskell这样的语言，对并行和并发的处理都很擅长处理。但是在Haskell内部这是属于两套不同的工具集，而且Haskell的官方wiki也解释了两者的使用原则，尽量避免在并行中使用并发处理：

Haskell早就意识到一个工具不可能同时解决两个问题。专门针对并行环境设计的新兴编程语言Parsail，也面临同样的问题，虽然它也同时拥有针对并行和并发的工具集，但也建议避免在并行程序里使用并发特性，尤其在编写并发程序时要小心。

持完全相反观点的也有很多人，他们则认为能有效支持并发的工具或语言也会很好的支持并行的模式。Rob pike就说 Go语言具有很好的并发特性。这使得它适合进行并行编程。

利用好并发特性可以简化并行程序结构（提高可伸缩性等）。

同样，Joe Armstrong也说Erlang适合并行编程的原因是因为它具有并发特性，他还说现在还想用非并发的思想去解决并行的问题是 错误的思路。这与Rob pike的观点如出一辙。

到底是什么原因导致的这种分歧，为什么Haskell和Parsail的用户认为并发和并行是两种独立的模式，而go和Erlang的用户则认为并发和并行可以相辅相成呢？ 我觉得是因为大家所要解决的问题不同，才导致了思路的不同，所以在看待并行和并发时所得出的结论就会不同。Joe Armstrong曾经画过一张图来解释这种区别。我也会画一些图来解释这件事情，首先来看下图，这张图和Joe Armstrong画的内容基本一样。

在实际情况下，的确会有单一队列的并发情况，但我还是按照Joe Armstrong的原始的图画了两个队列。从图中我们至少能得出以下结论？

• “并行”意味着能更快速的分发Coke
• “并行”从局部来看，本质上还是并发的问题
• 谁在队列的前面，谁将会先得到Coke
• 我们并不关心谁先谁后拿到Coke，他们最终都会拿到。
• 当然，在这种有先后顺序的队列中，如果Coke在中间就被拿完了，后面的人就会拿不到了----这也是现实世界中可能会发生的情况。

给一群孩子分发礼物会怎么样呢？可乐罐和礼物之间有区别么？

事实上是有区别。自动售货机是一个事件处理系统：人们不定时的到来，并且从机器中取不定数量的罐。而礼物箱是一个计算系统：你知道孩子们的情况，你知道你买了什么礼物，并且你能决定谁能得到什么礼物以及如何得到。

在礼品盒的场景中，“并发与并行”看起来很不同：

那么从上面的例子中，我们可以看出并行和并发的如下区别：

• 并发的某些行为特征和自动售货机是一样的，先到先得
• 并行则相反：在最开始的时候，每个人能拿到什么就是固定的了
• 在处理并发的时候，我们需要靠队列来避免两个孩子抢一个礼物----就像系统中的多个任务竞争访问共享的数据一样
• 在并行的模式下，就不需要队列了，不管谁先谁后，最终都会拿到自己正确的礼物

在图7一大堆礼物的情况下，这个时候队列里并发含义是指一种竞争，对抗的状态：谁先到，谁就能拿到最好的乐高玩具。在俄语中，“concurrent（并发）”（读音：kon-koo-rent）和“competitor（竞争对手）”是同义词。

在图8里，每个礼物盒都写上了名字，每个名字和每个小朋友是一一对应的，他们是并行的，没有交叉，互相之间也没有冲突。（但为什么我在图中画上了箭头，使 这些线相交了呢？一会我会解释这个问题。我们可以先这么想：每个孩子（类似系统中的进程）在搜索目标礼物（数据）的时候，会有相交，但这并不会造成冲突， 也不会影响到谁最终拿到什么礼物）

运算和事件处理

电话客服、WEB服务、银行柜台等应用场景和自动售货机的应用是类似的，并发是他们面临的问题，必须解决不可预知的请求带来的不可避免的冲突，并行设计可以在一定程度上提高此类应用的处理速度，但其归根究底还是并发的问题。

而一些运算型的系统则类似写上名字的礼物，像图形处理，计算机视觉，科学计算等，在这样的系统中，并发不会成为问题，每个的输入和输出都是预先设计的，不会有意外的事件发生，并行的设计方法可以有效的解决此类问题，但也容易带来隐含的bug。

接下来将讨论运算系统和事件处理系统的差别所在，我们先从决定论的因果关系分析来入手，看看这里会有哪些微妙的差异。

确定性：可用和不可用的两种情况

在运算性系统中，结果是确定的，这可以使编程人员轻松很多----我们可以反复的去测试优化、甚至重构整个系统，然后通过结果就能知道我们做的对不对。

而且这种情况下，大家对确定性的要求往往不是那么严格----你并不在意最后找到哪100张图片，只要上面都有小猫就行，你也不在意最终会得到多么精确的PI值，只要知道它是在3和4之间就可以了。

但是在事件处理系统的模型下，什么都是不确定的，事件的不同顺序会产生不同的结果，如果我先到了，我会拿到最后的Coke罐，如果是银行的共享账户，我比你晚了一秒种，钱就会打给你。

当然，在实际的并发系统的开发测试过程中，你可以串行的运行程序，一次只处理一个事件。但一旦用真实的行为去并发的访问系统，你会发现结果和串行的时候是不一样的。

在测试环境中，你根据日志来重现银行共享账户的取钱行为，你运行两次就可能得到两个不同的结果。可能出现的结果的数量取决于系统中冲突的数量。

唉～～，还有比这更让人头疼的事吗？

如何判断并行安全：确定性和正确性

当程序以不同的顺序处理事件的时候，你怎么确定其中没有bug？

在运算系统中，只要你每次运行程序都能得到相同的结果，即使是错误的结果，你也可以基本断定程序是并行安全的。

就像运行一个搜索小猫的程序，但你每次都是搜出了小狗，那说明你的程序是有问题的，但是没有并行的安全问题。

但是在事件处理系统中，情况就复杂了一些，你唯一能确定系统是并行安全的依据，是每次系统都能得到正确的结果。

就像模拟两个人操作银行账户，现实情况下不可能每次的结果都是一样的，那如何判断这个程序没有bug呢？我们只能

从侧面来看，例如会不会导致账户的负余额，会不会连续两次取空一个账户，会不会凭空增加账户金额，等等。

如果上述这些“错误的事情”都没有发生，你就可以认为你的银行系统是安全没有问题的。对电话服务来说，也是这样，你需要先定义出一系列“正确的结果”，然后用这些“正确的结果”验证你的电话服务的是否正常。

很不幸，如果你不了解系统中和时序无关的地方，那么没有人能告诉你一个通用的办法来找到系统中和时序有关的BUG。

，这也是个头疼的问题。

并行性错误：容易定位，很难定义

对于写上名字的礼物来说，不会出现并行的冲突问题--即使礼物上的名字中文写的，即使你不认识中文，这都没关系。看下图的过程和解决办法：

（图注：一个橙色的孩子看到一个礼物，心里想这肯定是我的，就拿了起来。另一个绿色的孩子说，这不可能是你的，我们找个认识中文的姐姐来看看上面的名字是谁。）

所以对并行系统来说，你不认识这些“标记”没关系，只要知道有标记就行了。当两个孩子发生并发冲突的时候，很容易找到一个认识标签的人来判断这个礼物到底是谁的。

这就好像一个自动化的测试工具，不需要知道什么进程必须访问什么数据，只要知道一个进程不能访问被别的进程修改的数据就行了。如果发生了这种冲突访问，那就当做BUG报告给程序员，让开发人员来消除这种访问冲突。

这样的工具现在已经有很多了，Click有，Checkedthreads也带有一个基于Valgrind的工具。

注：1、Click : Intel的C++编译器技术 http://click.intel.com

    2、checkedthreads：一个C++并行框架，https://github.com/yosefk/checkedthreads

    3、Valgrind :一套支持动态分析的工具 http://valgrind.org

但对Haskell来说，你不用这么干，首先你没有“确定的结果”可做对照，而且Haskell在运行时会有一个内置的冲突检测机制来避免一些问题。但用这种动态检测来代替静态分析并不一定能确保没有任何的问题，可能BUG就隐含在刚刚执行的代码中。

这个观点就是，在运算型系统中，你不需要准确的标记出BUG所在，或找到直接的原因，只需确定有BUG就行。就像在孩子和礼物的游戏中，你只需要把指出孩子们在抢哪个礼物就行了。

在事件处理的并行系统中，必须有一个知识丰富的姐姐来掌控全局，解决小盆友的冲突。

这里面还是有问题的，对于成年人来说，大家都可以做到“不动别人的东西”，但对于顽皮的孩子就不一定了。

图注：

1、两个孩子排队

2、前面是礼物盒里是个Iphone手机

3、排到的这个孩子突然尿急，先去撒尿

4、等他回来的时候发现排在他后面的孩子正要拿iphone，于是发生冲突

5、这时姐姐出现了，说:小盆友要遵守秩序，重新排队

6、后面的小盆友哭了：我差点就拿到了iphone。前面的小盆友冷冷的看着他想：如果iphone被他拿走了会怎么样呢？

就像上图所示，礼物没有按顺序发放--这是明显的BUG，会出现冲突，结果导致重新排队。

考虑这样的情况，某人把礼物盒打开了，但临时有事离开了，等他回来的时候这个礼物有可能已经被别人拿走了，这在事件处理系统中可能会是个问题，也有可能没问题，毕竟大家也都是在排队。因此在事件处理系统中，唯一的规则就是不要指定规则，不要给每个孩子预先指定礼物。

下面例子代码就会有这样的问题。这是一段银行的转账程序，并发系统的测试工具能发现其中隐含的BUG。

src.balance -= amount 


dst.balance += amount 

在上面的代码中，我们没有任何同步操作。src.balance可能同时被两个进程 同时修改，可能导致其中的一次修改无效，这就是个严重的问题了。

有一些工具可以检测到系统中类似的数据共享访问的竟态问题，像Helgrind可以通过对内存的监控，发现这样的同步问题，Cilk和checkedthreads也都可以。

我们来看下面的改进程序，这个版本看起来避免了上面的问题，但实际上依然有隐藏的BUG。

atomic { src.balance -= amount } atomic { dst.balance += amount }

上面代码中的“atomic”表示原子操作，保证线程对数据的修改必须在一个队列中依次进行。如果一切都按想象，那没问题，大家会依次访问数据。但测试工具依然会认为上面的代码是有问题的。我们了看看问题到底在哪里。

一个进程从src.balance里拨出了一笔钱之后,没有立即将这笔钱转入dest,就因为某种原因先进入了挂起状态，那么这笔钱就“失踪了”。这就是问题所在？你了解这样的银行业务吗？我不了解，Helgrind估计也是。

下面是一个有更明显错误的代码：

if src.balance - amount > 0: atomic { src.balance -= amount } atomic { dst.balance += amount }

在上面的程序中，一个进程会先检查原始账户src.balance里有没有足够的额度去转账，检查完毕，临时有事又先挂起了，这时另外一个进程到达了，也 执行了同样了检测，发现没有问题，然后就把钱转走了。这时第一个进程恢复了，进入一个转账的队列，等待转账。问题就在这里出现了----等轮到他的时候， 有可能第二个进程刚才已经把账户的钱转空了。

这就像你回来的时候发现自己的iphone手机居然在别的小盆友手里。这是访问的竟态，不是单纯数据的竟态问题了。尽管每个人都在文明的排队，这种状况还是发生了。

那什么竟态呢？这和具体的应用有关，我能确认最后一段代码有问题，但我不能肯定前面的那段就有问题，这都取决于银行的业务模型。如果我们不了解程序要做什么，我们就无法准确定义这个应用中的“竟态”，我们也不

当然，你也可以避开竟态访问，只要把整个转账的过程放在一个原子操作里即可，但这样一来所有的并发问题都得自行处理了。

其实竟态访问带来的一些问题，譬如空指针异常等，是可以重现的，这样就可以很方便的通过一些自动测试工具来解决。

但不幸的是，这种方法在事件响应型的系统是不可行的。

这又是让人头疼的地方!

两种队列：在过程的局部或者过程的两端实现

对于写了名字的礼物，你或许认为这种情况不需要队列，每个人都可以直接找到自己的礼物。

但想象一下，如果数千个孩子同时去找礼物会怎么样？这时候如果不进行排队，肯定会乱成一团糟。所以这种情况下，我们也需要一个或几个队列，但这里的队列，对孩子最终拿到手的礼物不会有影响，队列的选择只会有效率上不同，不会影响结果。

这就是我在上面的图中把每个孩子和自己的礼物用线连起来的原因，这样可以表示一种逻辑上的并行，虽然他们有交叉，但是不会产生冲突。(我很认真地在想办法用画笔把我心里的想法直观的表达出来)

这个情况也是类似的，当四个不同的进程通过相同的内存总线去访问不相关的数据时，他们必须有一个硬件级别的排队。1000个逻辑上独立的进程通过负载调度器分配到4个处理器上时，他们也需要一个队列。

在一个非冲突的并行系统中，会有大量的队列在运行，但他们只是局部的队列，不会影响到最终的结果，无论出现在哪个队列里，程序的最终的运行结果都是一样的。如下图所示：

与之相反，在并发系统中，队列贯穿系统开始和结束的两端，例如:

• 信号量会对应有一个队列，谁在前面谁就能先锁定这个信号量。
• Erlang的进程会有一个消息队列，谁先发出消息谁就会先影响到结果。
• go中的goroutine会监听一个通道，数据写入的顺序会影响执行的结果
• 在事务内存的模型下，失败的提交都要进入队列
• 在无锁容器内，更新失败的进程也要进入队列

在事件处理系统中，不管是简单的还是复杂的队列，你始终要记住，他们的顺序会影响到最终的执行结果，但想想看，这不就有可能形成了竟态访问吗？

在运算型系统或者并行的、无冲突的系统中，队列执行顺序不会影响结果，而且你想用工具来验证这个系统确实是无冲突的。

Rob Pike曾做个一个演示，来展示go语言在构建负载平衡方面的特性，的确很强大也很容易使用，go语言就是为并发环境设计的，并发就意味着排队，排队就会 带来负载均衡的问题。当然，这并非说别的语言里构建负载均衡就有多难，只是强调在有并发特性的语言里特别容易而已。

但这只是故事的一部分，接下来你想要的是无冲突的静态检验或动态检查，go语言也的确可以做到这一带点。但当你真正在运算型系统下工作时，你就会发现这是 一组和goroutines、通道完全不同的接口和工具，即使他们的底层是也是用goroutines和通道实现的。

重要的抢占式进程

因此，运算型系统所需要的冲突预防和检测，并发工具并没有提供。那有没有并发工具提供，但是运算型系统不需要的特性呢？

有，显式的队列就是一个，它不仅仅是不需要的，而且会成为运算型系统的障碍。因为我们知道，运算型系统中队列会导致竟态访问，而且你没办法定位。

另一个运算型系统不需要的特性就是低成本的抢占式进程。

相反，在事件处理的模型下，因为你希望尽可能快的处理大量不同的事件，这里就会出现很多抢占式进程，你希望在10000个进程在运行的时候，还可以立即应对第10001个进程产生的事件。那这种情况就必须要有非常低成本的抢占式进程了。

通过运算型系统，现在可以用廉价的任务来影射到昂贵的系统线程-但任务没有线程那么强大。你不能通过事件来激活任务。任务仅能在队列中等着，当工作线程空闲时才会用来运行它们。不像goroutines（Go语言中的并行程序称为goroutines）那样，你不能同时运行超过操作系统线程数量的任务-你也不需要。 .

任务可以在相当传统的运行时中很好的完成，也可以通过成熟的廉价进程、goroutines等其他方式来完成，当然对我来说这些技术在更低的运行时中需要做一些更多的工作。

这显示出平台是如何进行并行计算的，它不仅是在单系统的运行，也可以是跨系统的进行。

(公平的来说，在运算型系统中通过抢占来获取一优先级理论上可行的-换句话说，如果能判断哪些些新建任务是关键型的任务，那些不是，那么这是可以提高系统 运算的吞吐量的。然而在我又长又难过的经历中，调度器判定关键路径是什么在理论上的可行性多一点。一个愚蠢的贪婪抢占型调度器有没有什么用处。)

同类工具的不同点

并发事件系统的工具并不都是一样的，并行计算系统情况类似。虽然它们都是同一类工具，但是之间有实质性的区别。

• Erlang 一点儿都不允许进程共享内存。这意味着不存在数据竞争，这并不会特别地打动我，因为数据竞争可以很容易的自动检测到，而且通过不共享内存不能消除竞争条件。但是好的一面是你可以无缝的扩展到多个节点，而不仅仅是同一个芯片上的多个核。
• Rust 不允许共享内存，除非它是不可变的。没有简单的多节点扩展，但是在单节点有更好的性能，不需要数据竞争检测，竞争检测可能会由于不高的测试覆盖率出现漏报。（实际并不太像这样——这里有一个更正，其中也声称他们有计划加入并行工具到Rust中。）
• Go 允许你分享任何东西，我认为它用可容忍的验证负担换取了大部分性能。Go有一个数据竞争检测器，竞争条件在事件系统无论如何还是会发生的。
• STM Haskell 允许你自由的分享不可变数据，如果你显式的要求，可变数据也可以分享。它也提供了事务内存接口，我认为这是一个很酷的东西，有时候很难用其它方法模拟。Haskell也有其它的并发工具——有通道，如果你想要Erlang式的多节点可扩展性，显然Cloud Haskell是个不错的选择。

当然最大的区别是你得分别用Erlang、Rust、Go和Haskell写代码。现在我们看看计算系统：

• Parallel Haskell 将会仅仅并行纯代码。这是以没有副作用为代价的没有并行漏洞的静态保证。
• ParaSail 允许副作用，但是不允许很多别的事情，比如指针，结果它仅仅会并行的计算没有分享可变 数据的内容（例如，如果编译器认为两个数组切片没有重叠，那么就可以并行的处理这两个数组切片）。与Haskell类似，ParaSail也有一些并发支 持——也就是可以被分享和可变的“并发对象”——而且文档强调了在你仅仅需要并行的时候不使用并发的好处。
• Flow 依赖纯功能性核心，这进一步限制让编译器充分理解程序中的数据流，允许它针对Hadoop和CUDA等目的平台。语法上看起来像副作用的东西——平行缩减等——被认为是核心上的一层糖果。至少这是读宣言之后给我的印象，诚然我不完全理解（“如果一个映射是满射和内射，那么它是一个双射，因此它是可逆的”这对我们再明显不过）
• Cilk 是加上了并行循环和方法调用的C语言。它允许你分享可变数据，搬石头砸自己的脚，但是他有工具 可以确定性的找到那些漏洞，如果那些漏洞可以在你的测试输入中发生的话。当你不搬石头砸自己脚的时候，使用不受禁止的共享可变数据就很有用——当并行循环 计算任务局部基于副作用优化的事物，然后循环结束，大家都可以使用这些事物时。像孩子打开他们的乐高积木，每个构建块都来自它们，然后将它们组装在一起 ——没有副作用优势就是一块乐高积木。（Proper Fixation的博客——自2008年以来的过分扩展隐喻）
• checkedthreads 很像Cilk；它不依赖语言扩展，它整个都是免费和开放的——不仅是接口和运行时，漏洞查找工具也是。

checkedthreads是我写的，所以这是广告部分；checkedthreads在主流语言C和C++中是可移植的、自由的、安全的和 可用的，不像很多系统需要新语言或者语言扩展。

人们想要用C++1y或者其它类似的规范标准化Cilk，但是Cilk想要添加关键字，而C++不想添加关键字。Cilk在gcc和LLVM的分支是可用 的，但是它不能在所有平台运行（它扩展了ABI），而且它没有合并回主线。有些新的Cilk特性被申请专利了。并不是全部都是自由可用的，等等。
然而Cilk具有的巨大优势是Intel的支持，然而checkedthreads只有鄙人支持。如果因为读了我的checkedthreads相关的博客而认为Cilk适合你，而且你决定使用它，那么我将会实现自动化调试并行程序的目标来获得更多的关注。

不是所有的并发工具都是一样的，不同的并行工具也是不同的——我甚至没有指出在我的例子中最大的不同；它是毛茸茸的东西。不过他们是两个不同的类别，首先要做的事情就是识别对类别。

总结

我们已经讨论了平行、计算系统和并发、事件处理系统的不同点。不同点包括：

• 确定性：可能vs不可能
• 并行安全的信号：确定性vs正确性
• 并行漏洞：容易定位vs很难定义
• 队列：实现细节vs部分接口
• 抢占：几乎没用vs必不可少

对于事件处理系统，并发是本质，并行是部分解决方案——通常来说是好的解决方案（两个自动售货机比一个好）。对于计算系统，并行是本质，并发是部分解决方案——通常来说是不好的解决方案（一堆礼物通常比贴了标签的礼物糟糕）。

通过总结“并行/并发”和“计算/事件处理”，我希望可以表述的更清晰。我也希望没有给事件处理系统抹太多黑——可能我没提到自动验证策略。然而我不保证我的观点和术语使用正确。

有人对事件处理系统感兴趣，从这个角度看它是有价值的——“并发是一次处理几件事情，并行是一次做几件事情”。从这个角度，并行是实现细节，并发是程序的结构。

我相信我的观点也有价值——也就是说，“并行处理不可避免的时间相关的冲突，并行避免不必要的冲突。”——“自动售货机vs贴了标签的礼物”。两者看起来就是这样——并行的箭头是解开的，因为逻辑上就是这样：

最重要的部分是计算代码相对于事件处理代码可以通过使用自动调试工具和静态保证相当容易的做到几乎没有漏洞。

使用自己的工具处理并行不是什么新鲜事儿。Rob Pike在Sawzall上的工作早于在并发语言Go上的工作，Sawzall是一个专门的并行语言，它的代码可以做到总是没有并行漏洞。

然后现在并发工具的名声比并行工具的大——它们可以处理并行，虽然相对比较差。噪音和糟糕经常让我们看不到更好的东西。很遗憾，更好的支持并行将不会做为“抱怨并发”的副作用——或者这种支持在某些已经存在的地方萎缩。

我将会用“为计算代码使用‘裸’并发工具就是在解决错误的问题”来回应Armstrong的“并行化串行代码是在解决错误的问题”。一个简单的事实是用正确的工具并行化的C语言比Erlang更快、跟安全。

所有这就去“为你的工作使用正确的工具”，不要让任何人拿走你的 Apple iPhone ®。