Categories
程式開發

并发神器CSP的前世今生


本文转自“雨夜随笔”公众号,欢迎关注。

程序架构的研究在上世纪七八十年代还处于原始阶段,当时的大部分研究都在研究如何编写顺序代码,而现在所熟知的goto语句那时也正在被讨论,还没有正式引入。而面向对象的范式正在悄悄的变成编程的基石。

一切都显得风平浪静,好像一切都在随着预想的慢慢发展。这时Charles Antony Richard Hoare (简称Tony Hoare)发现了一个问题,那就是并发没有得到太多的关注,于是他开始着手解决这个问题。

Tony Hoare

并发神器CSP的前世今生 1

说起Tony Hoare,初听比较陌生。但是他的另一项研究很多程序员不会陌生,那就是排序算法中的快速排序算法(Quick Sort)。而这个闻名于世的算法是他26岁时发明的,当然除了这些,Tony Hoare在程序设计语言的定义、设计、数据结构、算法和操作系统等许多方面都有很多影响深远的成果。并因为“对程序设计语言的定义和设计方面的基础性贡献”在1980年获得图灵奖。

Hoare在发明快速排序后的第二年,接到了新的任务,为公司的新机器设计一个新的高级语言,而当时他正好搞到一份Algol 60报告的复印件,并参加了Dijkstra(学算法的时候大部分人都听过Dijkstra算法,没错,就是这个人发明的)等人剧本的Algol 60培训班。当时Hoare学着学着就想,不如直接把Algol 60在公司的新机器上进行实现。于是Hoare把这个想法提交给公司,在公司同意后,开始设计和实现Algol 60的一个自己版本。Hoare在一开始就制定了明确的目标,即系统要安全可靠,生成的目标码要简洁,工作区数据要紧凑,过程和函数的人口和出口要清晰、严密等,还明确了整个编译过程采用一次扫描等原则。

而这次实现不仅十分顺利,并且大受欢迎,在世界各国开发的Algol 60版本中效率、可靠性和方便性都非常出色。因此得到了国际学术界的重视。国际信息处理联盟于是任命霍尔为2.1工作组(Working Group 2.1)的负责人,这个工作组的任务是维护和发展Algol。霍尔果然不负众望,主持设计了Algol X以继承与发展Algol 60。正是在Algol X的设计中,霍尔发明了CASE语句。

Hoare还有很多重要的研究和成果。而我们今天要说的CSP理论就是其中非常重要的一点。

CSP

并发神器CSP的前世今生 2

Hoare在发现并发操作没有引起过多的关注后,开始着手进行解决。终于在1978年,Hoare在ACM中发表了经典的“Communicating Sequential Processes”论文。在这篇论文中,Hoare认为输入和输出是两个被忽略的编程原语,尤其在并发代码中。于是Hoare在CSP论文中展示了如何应用通信来建模输入和输出,并提供了如何用CSP来解决一些并发问题,比如寻找10000以内的素数。通过这种方式最终达到“在进程间正确的通信”。当然这个思想在当时是非常超前的,事实上,1978年的论文中,CSP只是一个用来展示通信顺序进程的能力的一个简单的编程语言。连Hoare本身都觉得这个想法过于超前而有些不切实际,他直接在论文中悲观的写道:

Thus the concepts and notations introduced in this paper (although described in the next section in the form of a programming language fragment) should not be regarded as suitable for use as a programming language, either for abstract or for concrete programming. They are at best only a partial solution to the problems tackled.

本文介绍的概念和符号应该不被认为适合作为一种编程语言,无论是抽象的还是具体的编程。他们最多只是一种解决问题的方式。

Hoare担心自己所展示的技术对于未来的并发编程的研究并没有任何作用,这种技术或许没有语言能够按照他的想法来实现。但是接下来的6年里,关于CSP的想法被提炼成对并发系统进行数学建模的方法–进程微积分。并提供了代数规则来对系统进行变化来分析它们的并发和效率。而这正式将CSP的想法投入到并发编程的实践中。

Go语言

并发神器CSP的前世今生 3

在CSP提出后,有些语言尝试将Hoare提出的输入和输出作为原语纳入到自己的语言体系中,比如OCCAM并发处理语言。和传统的加锁方式不同,CSP理论中不允许进程对其他进程的变量赋值,进程之间只能通过通信原语来实现数据交换和协作。但是这些语言都没能真正地为这些原语提供支持。大多数流行语言都支持共享和内存访问同步到CSP的消息传递样式。而采用CSP理论的语言也有,但是基本都没有得到广泛的采用。

直到Go语言出现,正式将CSP的原则纳入到核心原则,并提供了通信的原语支持channel。正因为如此,并发被认为是Go语言的优势之一。并让Go语言在分布式系统、云原生系统和系统中间件中迅速占领了市场。而其他语言基于共享内存的并发模型,在大型和复杂系统中变得很难正确使用。

当然Go还有其局限性,因为CSP的理解成本问题,Go同时也支持传统的加锁方式,也支持共享内存的方式。不过Go已经向其他语言证明CSP的可行性和优越处。并且提出了经典的CSP核心概念:

Do not communicate by sharing memory; instead, share memory by communicating.“不要以共享内存的方式来通信,相反,要通过通信来共享内存。”

而由于Go语言的推广和效果,使得CSP的概念变得流行起来,目前很多语言在尝试将CSP纳入到语言体系中并提供对Hoare提出原语的支持。

并发神器CSP的前世今生 4

参考链接

计算机科学名人堂:Charles Antony Richard Hoare:http://wap.sciencenet.cn/blog-1225851-839515.html“Go语言CSP:通信顺序进程简述:https://tsov.net/uupee/17044/“CSP 1978论文:https://spinroot.com/courses/summer/Papers/hoare_1978.pdf?__cf_chl_captcha_tk__=637000f92bddaa467d97d4404b8c86d40e787bda-1590473325-0-AfwfleSjOLTLNc9NlYQOaERH30eugvvD_pZCpJQp1BuLY7h8FMzdU-1g6gibzt0oPufEBr6ny7EMfaDuavQM9RoUnT5c1kqmUsycipyMJOPCp7-be5mLk7qFSZZm0dWcHb2HuOTkKQpAdCMgqSC4mBSfZ8UvZWjJ3v6kFE6MfP3BnQBtubXk88o3Twg3k8pd8W7xECjsYgSeyLB3xxq9y4-cpagfl0piK4i9QA00A2-Vm5usNU_WVevL5u-tepVkPdZpm8WQITYmKVeU_dTsBWv7Gpal-a1qATffyGGhAweQWYoDSpoO6uj8get5D_7cGe6jkzJEXaq04kHOABe9Us9BKs6qNOV7lE-Xdk7q1EKV