并发模型与进程演算

并发模型和进程演算对独立进程如何执行、通信和同步提供了形式化描述。

Definition

进程演算是一种形式化代数，用于将并发系统描述为通信进程，它包含并行组合、通信和选择等操作符，以及确定两个进程何时行为相同的等价关系。

Scope

本主题涵盖并发计算的代数模型：霍尔的CSP和米尔纳的CCS，用于通信拓扑结构变化的移动进程的π-演算，以及异步消息传递的Actor模型。它涉及通信和同步原语、行为等价（如双模拟）以及共享内存与消息传递并发之间的对比。

Core questions

• 如何代数地描述并发通信进程？
• 两个并发进程何时在行为上等价？
• 消息传递与共享内存并发相比有何异同？
• 如何建模动态通信结构，例如在π-演算中？

Key theories

通信顺序进程 (CSP)

霍尔的CSP通过在共享通信事件上同步的进程来建模并发，为消息传递语言和进程细化理论奠定了基础。

CCS与双模拟

米尔纳的通信系统演算提供了一种进程代数，具有精确的行为等价概念——双模拟，用于推理进程何时可以互换。

π-演算

米尔纳、帕罗和沃克将进程演算扩展到移动性，允许通信通道本身作为消息传递，从而使连接结构动态演变。

Clinical relevance

进程演算和Actor模型是基于消息传递的并发和分布式语言及框架设计的基础，它们为协议的规范和验证提供了形式化工具。双模拟和细化为正确的并发行为提供了精确的标准。

History

并发理论在1970年代后期随着霍尔的CSP和米尔纳的CCS而成熟，而休伊特的Actor模型（1973年）则提供了一种异步消息传递的替代方案。1992年的π-演算捕捉了进程的移动性。这些演算影响了消息传递语言和并发库，并仍然是协议验证的基础。

Debates

共享内存与消息传递

一个基础的设计问题是并发应该围绕带有同步的共享可变状态组织，还是围绕交换消息的独立进程组织，进程演算和Actor模型倡导后者。

Key figures

• C. A. R. Hoare
• Robin Milner
• Carl Hewitt
• Joachim Parrow
• David Walker

Seminal works

• hoare1978
• milner1989
• milner1992
• hewitt1973

Frequently asked questions

什么是双模拟？

双模拟是进程之间的一种等价关系，当每个进程都可以无限期地匹配另一个进程的可观察步骤时成立，它形式化了两个并发进程表现出相同行为的理念。

π-演算比早期演算增加了什么？

π-演算通过允许通信通道作为消息发送来建模移动性，因此谁可以与谁通信的拓扑结构可以在执行期间改变，从而捕捉动态和可重构系统。