并发性

在计算机科学中，并发是程序、算法或问题的不同部分或单元在不影响结果的情况下乱序或部分顺序执行的能力。 这允许并行执行并发单元，这可以显着提高多处理器和多核系统中的整体执行速度。 用更专业的术语来说，并发是指将程序、算法或问题分解为与顺序无关或部分排序的组件或计算单元的能力。

根据 Rob Pike 的说法，并发是独立执行计算的组合，并发不是并行：并发是一次处理很多事情，而并行是一次做很多事情。 并发是关于结构的，并行是关于执行的，并发提供了一种构建解决方案的方法，以解决可能（但不一定）可并行化的问题。

已经为通用并发计算开发了许多数学模型，包括 Petri 网、过程演算、并行随机访问机模型、参与者模型和 Reo 协调语言。

正如 Leslie Lamport（2015 年）指出的那样，虽然并发程序执行已被考虑多年，但并发的计算机科学始于 Edsger Dijkstra 1965 年的开创性论文，该论文介绍了互斥问题。 ... 在随后的几十年里，人们对并发的兴趣有了巨大的增长——尤其是在分布式系统中。 回顾该领域的起源，突出的是 Edsger Dijkstra 发挥的基础作用。

由于并发系统中的计算在执行时可以相互交互，因此系统中可能的执行路径数量可能非常多，结果可能是不确定的。 同时使用共享资源可能是导致死锁和资源匮乏等问题的不确定性来源。

并发系统的设计通常需要找到可靠的技术来协调它们的执行、数据交换、内存分配和执行调度，以最小化响应时间和最大化吞吐量。

并发理论一直是理论计算机科学的一个活跃研究领域。 xxx个提议是 Carl Adam Petri 在 1960 年代早期关于 Petri 网的开创性工作。 从那以后的几年里，已经开发出各种各样的形式主义来对并发进行建模和推理。

已经开发了许多用于建模和理解并发系统的形式，包括：

• 并行随机存取机
• 演员模型
• 计算桥接模型，例如批量同步并行 (BSP) 模型
• Petri 网
• 处理计算
  • 通信系统微积分 (CCS)
  • 通信顺序流程 (CSP) 模型
  • π-演算
• 元组空间，例如 Linda
• 简单并发面向对象编程 (SCOOP)
• Reo 协调语言
• 追踪幺半群

其中一些并发模型主要用于支持推理和规范，而其他模型则可以在整个开发周期中使用，包括并发系统的设计、实现、证明、测试和模拟。 其中一些基于消息传递，而另一些则具有不同的并发机制。

不同并发模型的激增促使一些研究人员开发统一这些不同理论模型的方法。 例如，Lee 和 Sangiovanni-Vincentelli 已经证明所谓的标记信号模型可以用来提供一个通用框架来定义各种不同的并发模型的指称语义，而 Nielsen、Sassone 和 Winskel 已经证明 范畴论可以用来提供对不同模型的类似统一理解。

参与者模型中的并发表示定理提供了一种相当通用的方式来表示并发系统，这些系统在不接收来自外部的通信的意义上是封闭的。 （其他并发系统，例如，进程计算可以使用两阶段提交协议在参与者模型中建模。）封闭系统 S 表示的数学表示是使用行为近似从称为 ⊥S 的初始行为构造越来越好的近似 函数 progressionS 为 S 构造一个外延（意义）如下：

表示S ≡ ⊔i∈ω 级数Si(⊥S)

这样，就可以根据其所有可能的行为对 S 进行数学表征。

可以使用各种类型的时序逻辑来帮助推理并发系统。 其中一些逻辑，例如线性时间逻辑和计算树逻辑，允许断言。