贝尔实验室与 CSP 线程

介绍

本文阐述并发编程的一段历史，重点介绍 Hoare（霍尔）的 Communicating Sequential Processes(CSP) 语言的一个特殊分支。这种方式的并发编程有趣在为了思维清晰而舍弃高效。把并发编程仅仅看作是提升性能表现的一种手段就未免太狭隘了，比如，并行磁盘 I/O 请求，通过预取结果降低延迟，亦或者利用多核处理器的优势。这些优点都很重要但不在今天讨论的范畴。毕竟它们能够以其他形式实现，例如事件驱动的异步编程。相反地，我们对并发编程感兴趣是因为它提供了很自然的抽象使得程序更简洁。

大多数科班学生都看过 Andrew Birrell 的 An Introduction to Programming with Threads。SRC 线程模型被当前大多数线程库采用。最大的问题在于它们太低级了。与霍尔提供的通讯原语不同，为了被高效地使用，SRC 风格的线程模型必须与其他技术绑定，通常是共享内存。一般来说，程序员倾向于避免构建自己的高级结构，并因为需要大量底层细节而感到沮丧。

此刻，将 Birrell 的教程赶出你的大脑。CSP 是一种截然不同的线程模型，如果能正视它的不同，你可能会发现它更易于理解。

通信顺序线程

1978 年，在多处理器的背景下，诸多方法被提出用于通信与同步。在信号量（semaphores）、临界区（critical regions）和监视器（monitor）这些同步机制中，共享内存是最常见的通信机制。Hoare 用一种语言原语解决了这两个问题：同步通信。在霍尔的 CSP 语言中，进程通过从具名的无缓冲通道发送和接收值来进行通信。因为这些通道是无缓冲的，发送操作会阻塞直到值被传递到接收者，从而提供一种同步机制。

霍尔举了个例子，生成所有小于 1000 的素数。通过进程流水线模拟埃氏素数筛（The sieve of Eratosthenes），执行下面的伪代码：

p = get a number from left neighbor
print p
loop:
    n = get a number from left neighbor
    if (p does not divide n)
        send n to right neighbor

一个生产者进程不停地将数字 2，3，4，…，1000 喂到流水线的最左边：第一个进程筛掉了 2 的倍数，第二个筛掉 3 的倍数，第三个筛掉 5 的倍数，以此类推：

到目前为止，示例的线性管道特性并不能够代表 CSP，但即使局限于线性管道，该模型也十分强大。Unix 操作系统众所周知的管道有力地证明了其威力，事实上管道还早于霍尔的论文。在贝尔实验室 1964 年 10 月 11 日的一份内部备忘录中，Doug McIlroy 正在摆弄一些后来成就了 Unix 管道的想法：“我们应该有一些像花园里的水管那样耦合程序的办法——当有必要用另一种方式处理数据时再接入另一段。这也是一种 IO 的方式。”

霍尔的通信进程比典型的 Unix shell 管道更通用，因为它们可以被随心所欲地连接。实际上霍尔给出的例子是一个 3x3 的进程矩阵，有点像可用于向量乘 3x3 方阵的素数筛。

当然，Unix 管道机制并不要求线性布局，只有 shell 语法要求。McIlroy 说他曾在早期玩过带有通用管道的 shell 语法，但是没有喜欢到想要去实现它。后来的 shell 确实支持有限形式的非线性管道。Rochkind 的 2dsh 支持 dags，Tom Duff 的 rc 支持树。

霍尔的语言新颖且有影响力，但缺乏几个关键点。最主要的缺陷是用于通信的无缓冲通道不是“第一公民”：它们不能被存在变量中，不能作为参数传递给函数，也不能跨通道发送。因此，在编写程序时必须定死通信结构。

Pan 与 Promela

1980 年，霍尔发表论文仅仅两年后，Gerard Holzmann 和 Rob Pike 创建了一个叫做 pan 的协议分析器，它将 CSP 方言作为输入。Pan 的 CSP 方言有串联、选择和循环，但没有变量。即便如此，Holzmann 报告说 1980 年 11 月 20 日，Pan 在贝尔实验室的数据交换控制协议中发现了第一个错误。这种方言很可能是贝尔实验室的第一种 CSP 语言，为 Pike 提供了使用和实现类 CSP 语言的经验。

Holzmann 的协议分析器发展为 Spin 模型检查器及其 Promela 语言，其通道是“第一公民”的特点与 Newsqueak 一样。

Newsqueak

在不同的方向上奔跑，Luca Cardelli 和 Rob Pike 将 CSP 的思想开发进 Squeak 迷你语言，用于生成 UI 代码（此 Squeak 与 Squeak Smalltalk 实现不同）。Pike 后来将 Squeak 扩展为成熟的编程语言，它孕育了 Plan 9 的 Alef、Inferno 的 Limbo 以及 Google 的 Go。与 Squeak 相比 Newsqueak 主要的语义优势在于它将通信通道视为“第一公民”：与 CSP 和 Squeak 不同，通道可被存储在变量中，作为函数参数，还有在通道之间发送。

Alef

Alef 是一种由 Phil Winterbottom 设计的语言，将 Newsqueak 理念应用至成熟的系统变成语言。Alef 有两种被我们称为进程的类型：proc 和 thread。程序被组织成至少一个 proc，它们共享内存的操作系统进程，可以被预先调度。每个 proc 包含至少一个任务，它们是合作调度的协程。每个任务都被分配至一个特定的 proc，不能在 proc 之间迁移。

proc 的主要作用是提供可以独立于进行阻塞 I/O 的上下文。（Plan 9 没有 select 调用，甚至在 Unix 上如果想要并发计算和网络 I/O 你需要多个 proc。）Acme: A User Interface for Programmers 着重讨论了 proc 和 thread。

Limbo

Inferno 操作系统是 Plan 9 的衍生品，用于机顶盒。它的编程语言 Limbo 很大程度上受到 Alef 的影响。它移除了 proc 和任务直接的差别，实际上只有 proc，尽管它们比大多数人称为进程的要轻量。所有的并行是抢占式的。有趣的是，该语言并不支持锁。相反地，通道通信通常就能提供足够的同步，并鼓励程序员为任何数据都安排一个明确的所有者。显式锁是没必要的。

Libthread

回到 Plan 9 的世界，随着 Plan 9 被移植到越来越多的架构上，Alef 编译器难以被维护。Libthread 最初是为了将 Alef 程序移植到 C 语音而创造的，这样 Alef 编译器就可以退役了。Alef 的 proc 和任务在 libthread 中被称为 proc 和线程。

Go

Rob Pike 和 Ken Thompson 去了 Google 将 CSP 置于 Go 语言并发的核心。