Parallelism != Concurrency

Parallelism,中文一般翻译成“并行”;Concurrency,中文一般翻译成“并发”。这两个词往往被混淆使用,即使在英文资料中,中文翻译使得这种情况变得更糟糕。其实这两个词的含义是完全不同的,这里并不是在咬文嚼字,而是想说明它们本质上确实有不同。为了表达方便,下文一律使用英文中的原词。

Wikipedia 上对 Concurrency 的定义如下:

Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel. Concurrent programs (processes or threads) can be executed on a single processor by interleaving the execution steps of each in a time-slicing way, or can be executed in parallel by assigning each computational process to one of a set of processors that may be close or distributed across a network.
可见,concurrency 并不意味着一定是 parallelism,它是把多个互相作用的计算过程(注:上文第一句中的 processes 不是进程的意思!)组合起来的一种计算形式。为了完成一个大的任务,我们可以把它切割成几个独立的几个步骤,然后把每个步骤交给单独的线程去完成,那么在 UP 上 concurrency 看起来就像是这样:

Parallelism 的定义如下:

Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently (“in parallel”).
也就是多个计算同时执行,在 SMP 上如下图所示:

这里需要注意的是:广义上 parallelism 并不总是指 SMP,广义的 parallelism 也可以发生在指令上,比如支持 SIMD 的 CPU,像 Intel 的 SSE 指令;也可以发生在 CPU 内部的指令 pipeline 上。请结合上下文去理解。

考虑到现在流行的操作系统都是多任务的,那么 UP 也可以达到 SMP 的效果,对于用户空间的程序来说,多任务操作系统即使运行在 UP 上也是和 SMP 上一样的。因此下文中我们将不再区分 UP 和 SMP,并且假设操作系统就是多任务的,即所有多线程的程序都是并行运行的。

这时候,另一个问题随之而来:有 parallelism 的程序一定是 concurrent 的么?未必!根据上面 concurrency 的定义,不同的处理步骤之间需要是互相作用的(interacting),我们完全可以写一个多线程程序,线程之间没有任何互相的作用:比如我们要处理 [1 ~ 40000] 这个数组,我们可以启动4个线程,让它们分别处理 [1 ~ 10000]、[10000 ~ 20000]、[20000 ~ 30000]、[30000 ~ 40000],最后主线程把 4 个结果汇总成一个。这个多线程程序显然可以做到 parallelism,但它没有 concurrency!

有人这么认为,说 concurrency 是程序的属性;而 parallelism 程序执行时机器的属性。现在我们可以知道,这是不严格的。只有当 parallel 的程序的线程之间有了互相作用之后才会有 concurrency!concurrency 比 parallelism 要难得多。

Rob Pike 大牛是这么概括它们的区别的:

Concurrency is a way to structure a program by breaking it into pieces that can be executed independently. Communication is the means to coordinate the independent executions.
所以,concurrency 和 parallelism 的本质区别是,多个线程/进程(或程序的多个部分)之间有没有互相作用和交流。这种交流分两种:一种是共享内存,一种是消息传递。前者我们很熟悉,我们最常用的锁(Lock))或者信号量(Semaphore)就属于共享内存的一种。

另外,需要说明的是,并不是所有的 paraellel 的程序都使用多线程/进程,它们也可以使用 coroutine,使用 events。一言以蔽之,parallelism 是建立在同步(synchronous )代码的基础上,同步代码同时运行;而把一个程序分成几个同步的部分,它们之间允许进行 communication 就有 concurrency 了!

借用 Rob Pike 使用的图来说明一下就是:

Original Program

Parallel Program

Concurrent Program

从图中我们可以一目了然地看出两者之间并没有直接的关系。最后,在《Parallelism is not concurrency》一文中对此有更精辟的概括:

Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Concurrency is all about managing the unmanageable[… ] Parallelism, on the other hand, is all about dependencies among the subcomputations of a deterministic computation.
参考资料:

1. http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference
2. http://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/
3. http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
4. http://stackoverflow.com/questions/1897993/difference-between-concurrent-programming-and-parallel-programming
5. http://concur.rspace.googlecode.com/hg/talk/concur.html#title-slide