6. 并发编程范式

6.1. 概述

为什么以及何时需要并发？

  • 当它自然地适合问题域时

    • 多个自主行为/模拟

    • 用户界面：定时事件、后台活动

  • 当技术解决方案领域需要它时

    • 更高效地使用可用资源：异步计算

    • 图形用户界面：低级输入事件的排队

    • 多核系统

    • 网络服务/分布式系统

主要注意事项：

  • 物理(并行度)与逻辑并发

  • 加速以及预期的时间

  • 数据并行度与任务并行度

6.2. 活动术语和关注事项

  • 进程：自己的内存

  • 线程：共享内存 and “线程本地”状态

  • 前景与背景

  • CPU绑定与IO绑定

  • 从运行到完成与协调

  • 进度报告

  • 取消

6.3. 线程安全

  • 非决定论

  • 非决定论的程度：见下文小节

  • 竞争条件

  • 线程安全问题的根本原因

6.3.1. 理解非决定论的程度

考虑以下两个并发增量操作的小示例：

/*f1*/ final int local1 = shared;    /*f2*/ final int local2 = shared;
/*s1*/ shared = local1 + 1;          /*s2*/ shared = local2 + 1;

在分析竞争条件时，我们可能会想要列举不同可能的交织。虽然这个示例看起来很合理，但这很快就变得不切实际，因为具有更多步骤的大量线程会出现组合爆炸。(详情请参见CDER章节。)

为了理解这种组合爆炸，让我们计算一下在以下情况下可能的交织 \(k\) 带螺纹的螺纹 \(n\) 每个步骤。我们回想一下二项式系数 \(i\) 选择 \(j\) 定义为

\[\binom{i}{j}=\frac{i！}{j！(i-j)！}\text{for}0\leq j\leq i\]

在我们的案例中，有 \(kn\) 步骤，第一线程从中选择 \(n\) ；有 \(\binom{{kn}}{{n}}\) 这是可能的。这片叶子 \((k-1)n\) 步骤，第二个线程从中选择 \(n\) ，以此类推。最后，这里有 \(n\) 剩下的步骤，这是最后一个线程的唯一选择。选择的总数是每个线程的选择的乘积：

\[\Binom{kn}{n}\Binom{(k-1)n}{n}\dots\Binom{2n}{n}\Binom{n}{n}= \frac{(Kn)！}{n！(kn-n)！}\frac{((k-1)n)！}{n！((K-1)n-n)！}\dots\frac{(2n)！}{n！(2n-n)！}\frac{(N)！}{n！(n-n)！}\]

这里，每个分母中的第二个因子与下一个顶层因子的分子相抵销，最后一个分母中的第二个因子为 \(1\) ，离开

\[\frac{(Kn)！}{{n！}^k}\]

当线程的数量和/或它们的步骤数量增长到超过两个时，交织的数量变得非常大。

\[\begin{split}\BEGIN{矩阵} n/k&k=2&k=3&k=4\\ N=2&6&90&2520\\ N=3&20&1680&369600\\ N=4&70&34650&63063000 \end{矩阵}\end{split}\]

因此，我们不能试图理解，更不用说列举所有可能的交织了。相反，我们需要考虑约束条件，例如，f1总是发生在s1之前，而f2总是发生在s2之前。

然而，一旦我们使每个线程原子化，交织的数量就会急剧减少到 \(k!\) 。

6.4. 处理共享状态

  • 互斥/锁定

  • 禁闭

  • 不变性

  • 案例研究：GUI和单线程规则

6.5. (相互冲突的)设计力

6.6. 特定的并发机制

语言构造、模式、构建块：

6.7. 参考：并发和异步计算