并行和并发需要不同的工具
作者:licqi 时间:2013-07-05阅读数:人阅读
并发(名词):指竞争或对抗。
– dictionary.com
并行:指两条直线永不相交的状态。
– Wikipedia
在并行和并发的问题上,我与Joe Armstrong(译注:Erlang语言发明者) 和 Rob Pike(译注:Go语言发明者)这俩人的看法并不一致。下面我以自动售货机和礼物盒为例来说明我的观点。(配有我用微软画笔精心制作的插图说明哦)
首先从概念上来说并行和并发都是非常流行的东东,很多编程语言和工具都会重点突出自己在这两个方面上的优异表现。
但我却认为并行和并发需要的是不同的工具,每个工具只会在某一个方面非常好,例如:
- Erlang, Rust, Go和STM Haskell擅长并发处理
- Flow, Cilk, checkedthreads 和 parallel Haskell侧重并行处理
最佳实践:优先使用并行,然后再考虑并发。Haskell早就意识到一个工具不可能同时解决两个问题。专门针对并行环境设计的新兴编程语言Parsail,也面临同样的问题,虽然它也同时拥有针对并行和并发的工具集,但也建议避免在并行程序里使用并发特性,尤其在编写并发程序时要小心。 持完全相反观点的也有很多人,他们则认为能有效支持并发的工具或语言也会很好的支持并行的模式。Rob pike就说 Go语言具有很好的并发特性。这使得它适合进行并行编程。 利用好并发特性可以简化并行程序结构(提高可伸缩性等)。 同样,Joe Armstrong也说Erlang适合并行编程的原因是因为它具有并发特性,他还说现在还想用非并发的思想去解决并行的问题是 错误的思路。这与Rob pike的观点如出一辙。 到底是什么原因导致的这种分歧,为什么Haskell和Parsail的用户认为并发和并行是两种独立的模式,而go和Erlang的用户则认为并发和并行可以相辅相成呢? 我觉得是因为大家所要解决的问题不同,才导致了思路的不同,所以在看待并行和并发时所得出的结论就会不同。Joe Armstrong曾经画过一张图来解释这种区别。我也会画一些图来解释这件事情,首先来看下图,这张图和Joe Armstrong画的内容基本一样。 在实际情况下,的确会有单一队列的并发情况,但我还是按照Joe Armstrong的原始的图画了两个队列。从图中我们至少能得出以下结论?
- “并行”意味着能更快速的分发Coke
- “并行”从局部来看,本质上还是并发的问题
- 谁在队列的前面,谁将会先得到Coke
- 我们并不关心谁先谁后拿到Coke,他们最终都会拿到。
- 当然,在这种有先后顺序的队列中,如果Coke在中间就被拿完了,后面的人就会拿不到了----这也是现实世界中可能会发生的情况。
- 并发的某些行为特征和自动售货机是一样的,先到先得
- 并行则相反:在最开始的时候,每个人能拿到什么就是固定的了
- 在处理并发的时候,我们需要靠队列来避免两个孩子抢一个礼物----就像系统中的多个任务竞争访问共享的数据一样
- 在并行的模式下,就不需要队列了,不管谁先谁后,最终都会拿到自己正确的礼物
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会监听一个通道,数据写入的顺序会影响执行的结果
- 在事务内存的模型下,失败的提交都要进入队列
- 在无锁容器内,更新失败的进程也要进入队列
- Erlang 一点儿都不允许进程共享内存。这意味着不存在数据竞争,这并不会特别地打动我,因为数据竞争可以很容易的自动检测到,而且通过不共享内存不能消除竞争条件。但是好的一面是你可以无缝的扩展到多个节点,而不仅仅是同一个芯片上的多个核。
- Rust 不允许共享内存,除非它是不可变的。没有简单的多节点扩展,但是在单节点有更好的性能,不需要数据竞争检测,竞争检测可能会由于不高的测试覆盖率出现漏报。(实际并不太像这样——这里有一个更正,其中也声称他们有计划加入并行工具到Rust中。)
- Go 允许你分享任何东西,我认为它用可容忍的验证负担换取了大部分性能。Go有一个数据竞争检测器,竞争条件在事件系统无论如何还是会发生的。
- STM Haskell 允许你自由的分享不可变数据,如果你显式的要求,可变数据也可以分享。它也提供了事务内存接口,我认为这是一个很酷的东西,有时候很难用其它方法模拟。Haskell也有其它的并发工具——有通道,如果你想要Erlang式的多节点可扩展性,显然Cloud Haskell是个不错的选择。
- Parallel Haskell 将会仅仅并行纯代码。这是以没有副作用为代价的没有并行漏洞的静态保证。
- ParaSail 允许副作用,但是不允许很多别的事情,比如指针,结果它仅仅会并行的计算没有分享可变 数据的内容(例如,如果编译器认为两个数组切片没有重叠,那么就可以并行的处理这两个数组切片)。与Haskell类似,ParaSail也有一些并发支 持——也就是可以被分享和可变的“并发对象”——而且文档强调了在你仅仅需要并行的时候不使用并发的好处。
- Flow 依赖纯功能性核心,这进一步限制让编译器充分理解程序中的数据流,允许它针对Hadoop和CUDA等目的平台。语法上看起来像副作用的东西——平行缩减等——被认为是核心上的一层糖果。至少这是读宣言之后给我的印象,诚然我不完全理解(“如果一个映射是满射和内射,那么它是一个双射,因此它是可逆的”这对我们再明显不过)
- Cilk 是加上了并行循环和方法调用的C语言。它允许你分享可变数据,搬石头砸自己的脚,但是他有工具 可以确定性的找到那些漏洞,如果那些漏洞可以在你的测试输入中发生的话。当你不搬石头砸自己脚的时候,使用不受禁止的共享可变数据就很有用——当并行循环 计算任务局部基于副作用优化的事物,然后循环结束,大家都可以使用这些事物时。像孩子打开他们的乐高积木,每个构建块都来自它们,然后将它们组装在一起 ——没有副作用优势就是一块乐高积木。(Proper Fixation的博客——自2008年以来的过分扩展隐喻)
- checkedthreads 很像Cilk;它不依赖语言扩展,它整个都是免费和开放的——不仅是接口和运行时,漏洞查找工具也是。
- 确定性:可能vs不可能
- 并行安全的信号:确定性vs正确性
- 并行漏洞:容易定位vs很难定义
- 队列:实现细节vs部分接口
- 抢占:几乎没用vs必不可少
本站所有文章、数据、图片均来自互联网,一切版权均归源网站或源作者所有。
如果侵犯了你的权益请来信告知我们删除。邮箱:licqi@yunshuaiweb.com