并行处理并行人工智能 DBA 设计 / 图形架构师 .NET 3.5 C# 2.0 初学者 C# 3.0 开发 .NET C#

并发编程 -入门

Marc Clifton

4.74/5 (42投票s)

2008年1月3日

CPOL

21分钟阅读

142282

Microsoft Parallel FX 计划概述，包括任务并行库和 PLINQ。

引言

我一直对并行计算很感兴趣，从十几岁时用一种名为 SAIL¹² 的语言（哈，看吧，那是比尔·盖茨最喜欢的语言）开发机器人应用程序开始。我甚至在 Commodore PET Basic 中用 6502 汇编实现了一个扩展，支持并发子程序执行。在 20 世纪 80 年代，我就清楚地意识到并发编程是开发人员必须尽快掌握的东西。显然，“尽快”意味着 25 年之后，因为主流（坦率地说，就是微软）世界终于意识到并发编程不仅是软件开发的下一个合乎逻辑的步骤，而且是下一个**必要**的步骤。

本文本质上是我对 Parallel LINQ (PLINQ) 和 Microsoft 任务并行库 (TPL) 当前情况的研究的正式日志。显然，存在一种利用 C# 3.0 和 .NET 3.5 中 LINQ 和 lambda 表达式功能的推动，以便在并发编程中站稳脚跟。虽然有大量关于跨多种语言的并行计算的信息，但我的兴趣（我怀疑也是这个社区的兴趣）是看看微软在 C# 和 .NET（显然也包括 VB.NET）方面做了什么，因为这会比其他工作（过去或现在）更直接地影响我们。所以是的，本文有所偏向，主要关注微软技术。

我将我的笔记整理成一篇希望可读的文章。文章末尾有大量的参考文献供您深入研究，我大量引用了他人的话，因为他们才是专家，而不是我。我发现并发编程的微软“方式”不仅涉及到 TPL，还需要深入研究 LINQ、lambda 表达式和函数式编程的基础。这很有启发性，因为它让我对并发编程中涉及的不同技术、它们如何相互作用以及它们的优缺点有了更完整的认识。

免责声明：对这些技术的任何理解错误完全是我自己的，如果我发表了错误的陈述和结论，请纠正我。

什么是并发编程？

答案显而易见：并行执行多个任务（或工作单元）。虽然在单核计算机上不会发生真正的并行性（而是 CPU 在任务之间切换），但在多 CPU（每个 CPU 中有多个核）的系统上，可以实现真正的并行性。并行计算也不局限于利用一台物理机器上的核。分布式计算是一种并行计算形式，其中工作单元分布在多台机器上。然而，分布式计算对任务管理（即任务分配）增加了额外的要求，本文不讨论这一点。

并发编程的本质涉及两件事：任务管理和通信。任务管理器负责将工作单元分配给可用线程，而通信涉及为任务设置初始参数并获取任务工作的结果。正是这最后一点，任务通信，是最困难的。正是在这里，由于不正确的锁定机制，开发人员可能会扼杀任何性能提升，甚至更糟的是，当多个任务试图同时更改相同的内存位置时，以及当任务死锁、每个任务都等待另一个任务完成工作时，会产生微妙的错误。

任务通信问题更广泛地归类为状态和内存共享问题。解决共享状态和内存所涉及的同步问题的典型解决方案是使用锁、监视器、信号量和其他技术来阻止线程在单个线程进行更改时改变状态。同步难以测试，这也是错误和性能问题产生的地方。在 Erlang（一种函数式语言）中，同步甚至不是问题。这是通过将变量视为不可变来实现的，并通过线程之间的消息传递，其中消息是发送线程变量的副本。

另一种技术是事务内存。锁定是一种悲观的方法——锁假定内存会被其他人写入，而其他人也会锁定内存。事务内存是乐观的：“……一个线程完成对共享内存的修改，而不考虑其他线程可能在做什么，记录它正在执行的每一次读写操作。它不将确保其操作不会对正在进行的其他操作产生不利影响的责任放在写入者身上，而是放在读取者身上，读取者在完成整个事务后，验证其他线程是否没有同时更改它之前访问过的内存。”¹⁰

因此，从根本上讲，并发编程涉及任务管理和某种形式的状态管理，无论是同步技术、带序列化的消息传递还是事务内存。可能还有我不知道的其他状态管理技术。然而，如您所见，任务管理就是任务管理。状态管理，啊，症结所在！

微软在做什么？

微软参与了并发编程，并成立了并行计算开发中心。这个开发中心有四个顶级方面

F#
TPL
PFX
PLINQ

F#

首先，F# 与并发编程没有直接关系。“F# 是一种用于 .NET 框架的类型化函数式编程语言”¹。然而，F# 包含了异步工作流的概念，主要用于“编写执行异步 I/O 且不希望阻塞线程的并发和响应式程序。”² TPL 最终将被整合到 F# 中，“作为 F# 异步工作流的关键底层技术。”⁴ 此外，正如我后面讨论的，函数式语言由于其性质，非常适合并发编程，因此 F# 团队对并行计算感兴趣是很自然的。

任务并行库 (TPL)

“任务并行库 (TPL) 旨在使编写能够自动使用多个处理器的托管代码变得更加容易。使用该库，您可以方便地在现有顺序代码中表达潜在的并行性，其中暴露的并行任务将在所有可用处理器上并发运行。”³

做什么，而不是怎么做

我听说过，你可以告诉一个人做什么，或者告诉一个人怎么做，但你最好不要告诉一个人做什么**和**怎么做。TPL 通过 PLINQ 和 TPL API，消除了你的命令式代码中关于并行执行工作的“怎么做”部分。你将要做的事情表达为一个工作单元，TPL 会找出最佳的执行方式。PLINQ 利用 TPL，将查询迭代指定为 TPL 分配给线程（通常是处理器核心）的工作单元。

并行任务基础

让我们以 CPian livibetter 的平滑绘制曼德尔布罗特集¹³为例，并将其并行化，演示 Parallel.For 循环。Parallel.For 循环是 Parallel 类中最简单的“结构化”方法。但是，如果你下载 livibetter 的代码来完成这个练习，请确保你

将解决方案转换为 Visual Studio 2008 解决方案
将“Ms”项目的目标框架更改为 .NET Framework 3.5
添加对 System.Threading 的引用

当然，你还需要下载并安装 TPL CTP。

首先，我们必须通过消除副作用使代码线程安全。主要的计算循环如下所示，我已在副作用代码旁边添加了注释

Sci.Math.ComplexNumber z = P2;
progress.Maximum = p.Width;

for (int x = 0; x < p.Width; x++)
{
  // z needs to be localized.
  z.Im = P1.Im;
  // Side-effect: z is global variable.
  z.Re += xStep;
  for (int y = 0; y < p.Height; y++)
  {
    // Side-effect: z is global variable.
    z.Im -= yStep;
    Sci.Math.ComplexNumber C = z;
    int iteration = 0;
    while (z.Modulus < escapeRadius && iteration < maxIteration)
    {
      z = z * z + C;
      iteration++;
    }
...etc

如果我们并行化外层循环，很明显每个工作单元都需要自己的 z 实例；否则，每个工作单元将操作同一个实例，这将对每个单元正在进行的工作产生严重后果。其次，z.Re 通过 xStep 递增的操作不能再进行。循环将针对 x 并行化，因此 z.Re 必须针对每个 x 进行计算，而不是简单地递增。并行化后的版本如下所示（使用 lambda 表达式作为委托）

// Commented out, because it must localized.
// Sci.Math.ComplexNumber z = P2;
progress.Maximum = p.Width;

//for (int x = 0; x < p.Width; x++)
Parallel.For(0, p.Width, x =>
{
  Sci.Math.ComplexNumber z = P2;
  z.Im = P1.Im;
  // z.Re += xStep;
  // Because the for runs in parallel against x, we
  // have to calculate the step for this x.
  z.Re = P2.Re + (x * xStep);

  for (int y = 0; y < p.Height; y++)
etc...

该程序现在将利用可用的核心来生成 Mandelbrot 分形。它运行速度明显更快，并且您可以清楚地看到 CPU 利用率达到 100%。

一个有趣的问题是，为什么要并行化外循环而不是内循环？一个答案是，这样会增加 TPL 任务管理器的开销。任务管理器目前将工作（p.Width 个工作单元）分配给每个核心，每个核心完成整个 p.Width 次迭代（工作单元）。如果你并行化内循环，那么每个工作单元会小得多——确定 z 逃逸前迭代次数的 while 循环——并且获取下一个工作单元的开销会更高（现在是 p.Width * p.Height 次，而不是仅仅 p.Width 次），更不用说 Parallel.For 会将工作单元排队 p.Width 次，而不是像并行化外循环那样只排队一次。

其他并行任务概念

如果您阅读了《优化多核机器的托管代码》³，您会注意到它还讨论了一个 Aggregate 方法。这个方法要么已被移除，要么未包含在 CTP 中。目前，Parallel 类支持的另一个概念是 Parallel.Do 方法。这个方法将 Action 实例数组作为参数，任务管理器将异步执行每个 Action。类似地，Parallel.ForEach 方法对可枚举数据源执行单个操作，并可能并行处理数据源中每个项上的操作。

另一个概念叫做“未来”（future）。“未来，一个计算结果的任务，不是用一个普通的操作构建的，而是用一个返回结果的操作构建的。这个结果是一个类型为 Func<T> 的委托，其中 T 是未来值的类型。未来的结果通过 Value 属性检索。Value 属性在内部调用 Wait，以确保任务已完成并且结果值已计算。”³

任务管理器

Daan Leijen 和 Judd Hall 已经很好地阐述了这一点：“所有任务都属于一个任务管理器，顾名思义，任务管理器管理任务并监督工作线程执行任务。虽然始终有一个默认的任务管理器可用，但应用程序也可以显式创建一个任务管理器。”³

异常处理

关于异常处理，生成异常的任务会传播到调用任务并行处理的代码。引用如下：“... Parallel.For 和 Parallel.Do 函数会累积所有抛出的异常，并在所有任务完成后重新抛出。这确保了异常永远不会丢失，并正确地传播给依赖项。”³

并行扩展程序集（又称并行 FX 库，又称 .NET 框架并行扩展，又称 PFX）

PFX 到底是什么？这有点难以描述。TPL 被称为“使用并行 FX 库”³。我不太清楚这意味着什么，也许微软自己也有点首字母缩写词阅读障碍。所以，我在这里提到它的唯一原因似乎是它是 PLINQ 和 TPL 的伞形程序集/库/扩展。

并行语言集成查询 (PLINQ)

PLINQ 是 LINQ，其中查询并行运行。通过在数据源中添加“AsParallel()”，可以非常容易地将查询从顺序执行转换为并行执行。例如¹⁴

IEnumerable<T> data = ...;
var q = from x in data.AsParallel() where p(x) orderby k(x) select f(x);

“LINQ 的‘一次性集合’编程模型强调指定需要做什么，而不是如何做。如果没有 LINQ，‘如何做’部分通常会通过循环和中间数据结构来表达，但由于编码了太多具体信息，编译器和运行时无法轻易地并行化。另一方面，LINQ 的声明性本质为像 PLINQ 这样聪明的实现提供了灵活性，可以使用并行化来获得相同的结果。”¹⁴

状态和内存共享

TPL、PFX 和 PLINQ 的努力都集中在并行任务处理上，而完全忽略了状态和内存共享问题，这是否让您感到惊讶？这确实让我感到惊讶。在我看来，这是本末倒置。到目前为止，TPL 仅在循环并行性的上下文中解决并行计算问题，其中任务本质上是自主任务。要真正利用并行处理来完成真实世界的任务（其中任务**需要相互通信**），解决并发环境中的状态和内存共享问题至关重要。一种方法（以 Erlang 为例）是完全消除共享状态（任务获取对象的副本，因此它们不必设置锁或处理竞争条件）并消除共享内存（对象副本在任务之间传递而不是引用，再次消除了对锁的需求）。相反，消息用于任务之间的通信，接下来将讨论。

消息传递和消息序列化

在 Slava Akhmechet 关于 Erlang 风格并发的博客¹⁵中，他带领读者重新设计 Java，使其具有传递并发性，以消除状态和内存共享问题，从而消除同步问题。他通过消除同步关键字，并在特定于该线程的堆上实例化对象来实现这一点，因此无法访问另一个线程上的对象。当然，线程确实需要相互通信，这通过发送消息来完成。每个线程都有自己的消息队列，并阻塞直到有消息要处理。然而，由于线程 1 发送的消息将放置在线程 2 的队列中，线程 2 现在拥有线程 1 堆的引用，这违反了目标。所以，消息被序列化了。Slava Ahkmechet 接下来指出了一个非常有趣的事情——因为消息是序列化的，并且发送/接收消息实现了一个接口，我们现在不仅可以在核心之间分发工作，还可以在**机器之间**分发工作。然而，这又带来了一个新问题——确定接收方是否实际收到了消息。

缺点

这种方法的一个显著缺点是，在任务之间传递对象时，序列化会带来性能损失。由于目标任务接收一个副本，它必须由发送方序列化，并由接收方反序列化。如果任务之间使用非平凡（基本是非值类型）对象进行大量通信，我能想象到严重的性能问题。

软件事务内存

另一种似乎备受关注的方法是 STM。“在计算机科学中，软件事务内存（STM）是一种并发控制机制，类似于数据库事务，用于控制并发计算中对共享内存的访问。它作为基于锁的同步的替代方案，通常以无锁方式实现。”¹⁰在 Channel 9 视频⁵中，采访者询问“事务性任务管理”，这指的是软件事务内存。正如 Anders Hejlsberg 指出的，这是一个微软研究项目。请参阅“进一步阅读”中的链接。

考虑因素

任务管理

并非所有任务都占用 CPU 100% 的周期；因此，如果能以一种允许开发人员控制特定类别任务的线程池大小的方式来组织任务，那将很有用。或者，相反，底层任务管理器应该能够分配额外的线程，意识到处理器未充分利用。有了 TPL，应用程序可以创建自己的任务管理器。正如所述：“……您可能希望使用多个任务管理器，每个管理器具有不同的并发级别或处理不同的任务集。”³

调试

不难想象调试具有众多并发任务的应用程序的复杂性。如前所述：“任务管理器接口的另一个重要用途是使用单个工作线程顺序运行所有代码。”³ 虽然这显然不能解决并发相关错误，但它确实提供了一种在顺序执行模式下调试应用程序的机制。

此外，在支持消息传递的并发模型中，通过能够审计消息来方便调试。

无副作用

Anders Hejlsberg 就 PLINQ 发表了以下有趣的声明：“……我们可以更聪明地运行这些查询。我们也许可以做出一些简单的假设，即您在此处调用的任何函数都是纯粹的、无副作用的……”⁵这里的关键词是“无副作用”。这是并发编程的关键：任务必须是无副作用的。实现这一点的机制之一当然是 Erlang 和其他语言使用的无状态、无共享内存范式。然而，我很难说做出这些假设是“简单”的。

重申一下，正如 Joe Duffy 所说：“如果你能用 PLINQ 以一种大部分是函数式的方式，无副作用地表达你的程序……”⁵ 有很多讨论说 TPL 使编写并发应用程序变得容易；然而，真正的难点，即让你的任务无副作用，显然在很大程度上被忽略了。

忏悔时间：“这个库并没有改变你同步访问数据或处理数据的方式……但是当涉及到访问共享资源或共享数据时，你仍然需要锁、监视器或其他机制。”（Anders Hejlsberg）⁵ 并行任务管理是并发编程方程中简单的一面，正如 Anders Hejlsberg 所说，“尽管关于如何管理共享内存和状态的争论仍在激烈进行”，TPL 简化了任务管理。不幸的是，在 TPL 的实际用例中，当共享内存和状态**是**一个考虑因素时，开发人员却被留下了难题。

并发编程需要函数式语言吗？

当被问及 LINQ 可以利用并行性的原因之一时，Anders Hejlsberg 回答道：“这是因为它以更声明式或函数式的风格编写程序和查询，而不是更传统的、命令式语句式的做法。”⁵ 那么，更声明式的编程风格如何促进并行性呢？这句关于“声明式并发允许运行时优化”的话有助于解释其原理

用锁串行访问数据涉及用正确性换取并行性和可伸缩性。巧妙的锁定方案可以用来同时获得两者的好处，但这需要复杂的代码和工程。如果你正在制作一个高度可重用、科学质量的库，那么这种工作量可能是家常便饭。但是，如果你正在编写一个应用程序，那么成本就太高了。

锁采用数据库领域称为悲观并发的技术，而事务内存则倾向于乐观并发。前者禁止事务执行期间对数据结构的并发访问，而后者在提交时检测（有时甚至容忍）有问题的冲突。例如，如果两个并发任务处理相同的数据结构且不冲突，则不需要串行化；然而，一个幼稚的基于锁的算法可能会强制执行它。允许事务管理器使用运行时启发式方法选择合适的执行策略可以产生高度可伸缩的代码。

此外，内存事务可以消除难以调试的“海森堡错误”，例如死锁，这通常会导致程序挂起且难以重现，以及优先级反转和锁队列，两者都可能导致公平性和可伸缩性问题。因为事务管理器控制着锁定细节，它可以确保公平且无死锁的提交协议。”¹¹

然而，当试图理解为什么函数式语言非常适合并发编程时，我发现的主要原因是状态是不可变的。这在 Chris Sells 的《函数式语言摘要》⁶中变得更加清晰，引述如下

所有“变量”都是不可变的，通常称为“符号”
程序状态保存在函数中（特别是传递给函数栈上的参数），而不是变量中

第二点，状态在栈上管理而不是在变量中管理，是函数式编程非常适合并行计算的关键。再次引用 Chris Sells 的话

函数不会产生副作用（“变量”是不可变的）...
由于状态是不可变的，因此无需多线程锁
这使得函数式程序可以自动并行化

啊哈！所以，这是一个更明确的答案，说明了函数式语言在并发编程方面的优势。而且，由于 LINQ 在其查询表达式中将 lambda 演算作为底层机制使用，并且“Lambda 演算为描述函数及其求值提供了理论框架”⁷，因此我们将 LINQ 与其在并发编程中的应用联系起来。

那么，并发编程需要函数式语言吗？不，当然不需要。但是，函数式语言固有的不可变状态极大地促进了并发编程。换句话说，开发人员不必担心锁、信号量等，而这些在状态共享的并发编程中是必需的。

但 LINQ 真的函数式吗？

不是。“LINQ 查询语言使用‘lambda 表达式’，这个概念源于 LISP 等函数式编程语言——lambda 表达式定义了一个未命名函数（lambda 表达式也将是下一个 C++ 标准的特性）。在 LINQ 中，lambda 作为参数传递给其运算符（例如 Where、OrderBy 和 Select）——您也可以类似地使用命名方法或匿名方法——它们是代码片段，很像委托，充当过滤器。”⁹ 需要注意的是，C# 的 lambda 表达式（以及因此 LINQ）并未实现真正的函数式编程；任何 lambda 表达式都可以访问其函数外部的可变变量，并且程序状态仍然保留在函数本身之外。因此，程序员在编写带有 lambda 语法的代码时，仍然必须小心确保线程安全，这也意味着编写线程安全的 LINQ 语句。例如⁸

int i = 0;
var q = from n in numbers select ++i;

不是线程安全的。正如 PFX 博客指出的，“MSDN 上有一组 101 个 LINQ 示例可用，网址为http://msdn2.microsoft.com/aa336746.aspx。不幸的是，其中许多示例依赖于在转换为 PLINQ 等并行模型时不一定成立的实现细节和行为。事实上，其中一些对于 PLINQ 来说是危险的。”⁸

工作窃取

线程可以窃取分配给其他线程的工作。当工作单元导致线程使用不平衡时，这有助于在空闲核心/线程之间分配工作单元。TPL 的目的是支持此功能。

结论

.NET 的 Parallel 类确实从工作单元管理的角度简化了多线程应用程序的开发。状态和共享内存问题仍然需要程序员来解决。为 LINQ 添加并发编程能力是 LINQ 的自然扩展，并且应该在各种场景中证明其价值。最终，PFX（如果我使用这个术语正确的话）应该有助于利用多核系统。我将很感兴趣地看到微软正在构建的架构是否可以进一步扩展到真正的分布式计算。我还会很感兴趣地看到什么样的状态和共享内存解决方案可以与 PLINQ 和 TPL 协同工作。显然，我们正处于另一系列技术进步的边缘，这次是在并发编程领域。

个人观察

在观看 Anders Hejlsberg 的视频时，我不禁感到失望，因为他没有提及 Erlang。事实上，似乎他在回避关于可变性和状态管理的所有问题。诚然，Anders Hejlsberg 在指出 TPL 并未改变你处理同步的方式时，确实有一个“我们必须对此诚实”的声明。对我来说，很明显他和 Joe Duffy 不想触碰这个大象，因为世界其他地方“正在激烈争论”如何处理同步问题。这很公平，TPL 确实使向定义良好的工作单元添加并行性变得更容易。尽管如此，我仍然感到失望，因为问题的真正核心，即同步，已经被推到了一边。我倾向于得出结论，由于 .NET 的 lambda 表达式并非真正的函数式编程，因此 .NET 语言永远无法像 Erlang 等语言那样真正消除开发人员在处理同步问题上的工作（以及因此产生的错误），从而成功解决同步问题。