并发调试的挑战与磨难 -

2004年11月30日
第2卷，第7期

并发调试的挑战与磨难

你可以逃跑，但你无法躲藏。

KANG SU GATLIN，微软

我们现在稳坐于21世纪，现代程序员面临的最大挑战既不是内存泄漏，也不是类型问题（这两个问题现在都已有效解决），而是并发问题。如何编写日益复杂的程序，将并发作为首要考虑因素？或者更棘手的问题是，如何调试这样一个庞然大物？这些问题甚至让最优秀的程序员也感到恐惧。

此外，计算领域正在发生变化。集群越来越受欢迎，现在即使是夫妻店也开始在本地运行集群。在这个并行性日益增强的世界中，还有一个新的变化，CPU制造商已承诺在很短的时间内将多核处理器推向桌面。（多核处理器是具有多个核心处理单元的芯片。这些核心并行计算，同时通常共享内存。）随着所有这些活动，显然有一股新的硬件浪潮将并行性推向传统上不相关的领域。

那么，今天的并行程序是什么样的呢？它们有许多不同的形式——从用于碰撞模拟的有限元程序到文字处理器。本文是关于调试这些并发/并行程序，以及用于调试的调试器。本文首先深入了解实际问题是什么样的。下一节描述了用于并行调试的一些方法，文章最后展望了未来。请注意，调试器的技术因供应商而异，本文试图阐明一般问题，而不是特定供应商如何实施其解决方案。

并发程序中的常见问题

就像标准顺序程序中广为人知的悬空指针和空指针解引用一样，并发程序中的错误类型也倾向于相对较小但很常见的几类问题。本节重点介绍并发程序的典型问题是什么样的。

在深入探讨之前，我们应该确定我们所指的程序类别。大多数并行程序都是用一种称为SPMD（单程序多数据）的模型编写的。该模型指出，所有进程都运行相同的程序映像，尽管数据不同，并且指令指针不需要以锁步方式执行相同的指令。此外，两个不同的进程可以彼此运行完全不同的函数。多线程程序是使用任务并行模型编写的，其中每个线程执行不同的任务，但全局和静态数据在线程之间共享（本地和线程本地数据是每个线程私有的）。好的，这就是我们关心的程序类别......让我们继续前进。

一般来说，只有在并行程序作为串行应用程序调试完成后，才应将其作为并行应用程序进行调试。您可以通过将进程/线程数设置为 1，有效地将许多并行应用程序转换为串行版本。这种转换对于多进程应用程序更有效，而对于多线程应用程序则不太有效。这样做的原因是调试程序中所有与并发无关的问题。调试顺序程序比调试并行程序容易一个数量级，首先解决所有这些问题非常重要。在应用程序的顺序变体完美运行后，就可以测试并开始将程序作为并行应用程序进行调试。

以下列表并非详尽无遗，但应涵盖您在调试并行程序时可能遇到的 90% 的问题。值得注意的是，进程级并行和线程级并行通常表现出此处列出的不同问题集。例如，不匹配的通信更常发生在进程级并行中；竞争条件和伪共享几乎完全发生在线程级并行中；死锁可能发生在两者中。

不匹配的通信

进程级并行程序通常在各个进程之间来回发送消息，这些进程可以位于不同的物理计算机上。当您使用显式的消息传递 API（例如 MPI，消息传递接口库标准，用于消息传递；请参阅 http://www-unix.mcs.anl.gov/mpi/）时，通信的每一端都有显式的发送和接收。

当存在发送/接收调用，但通信的另一端没有相应的接收/发送时，就会发生不匹配的通信错误。例如，进程 X 可能向进程 Y 发送消息，但如果进程 Y 不尝试接收消息怎么办？或者，如果进程 X 正在等待接收来自进程 Y 的消息，但进程 Y 没有发送消息怎么办？

这种错误的典型结果是进程或线程挂起，这反过来通常会导致下游不匹配的通信，并且还可能导致死锁（在下一节中讨论）。幸运的是，在不匹配通信的现场，有大量信息——包括未应答的调用。因此，调试此类程序通常并不太困难。一种称为消息队列查看（稍后讨论）的技术也有助于简化此类错误的调试过程。

死锁

死锁是计算机科学中最著名的问题之一，餐桌哲学家问题就说明了这一点（有关更多信息，请参阅 http://www.nist.gov/dads/HTML/diningphilos.html）。在多线程程序中，死锁变得更加突出，因为锁成为任务并行编程范例的基本组成部分。由于程序中分散了用于各种资源（通常是并行程序中的内存和 I/O）的锁，因此除非非常小心以确保这些死锁不存在，否则死锁的可能性更大。

例如，考虑以下两个线程的操作序列

线程 1 获取锁 A

线程 2 获取锁 B

线程 1 阻塞，尝试获取锁 B

线程 2 阻塞，尝试获取锁 A

线程 1 和线程 2 最终都阻塞在另一个线程持有的不同锁上。除非采取某种方法来打破这种死锁，否则它们将无限期地冻结——这就是程序中死锁的常见结果：冻结或崩溃。例如，内核模式下的死锁通常会导致错误检查。幸运的是，与不匹配的通信问题一样，在冻结或崩溃后，死锁的根源通常很容易找到。这是因为，为了发生死锁，至少一个线程必须持有锁，并且至少一个线程必须尝试获取锁；在程序执行的任何给定点，或者在检查崩溃转储文件时，这种状态都是显而易见的。当然，在识别出问题后解决问题可能要困难得多，因为有时需要重新设计程序（尽管有时只需释放意外持有时间过长的锁即可）。

竞争条件

当存在共享状态时，就会发生竞争条件——例如，一个共享变量可以被两个或多个不同的线程访问，但没有机制来控制其访问的时间顺序。因此，根据哪个线程首先访问共享状态，应用程序的行为可能会改变。

竞争条件最常见的特征之一是其不确定性。程序可能不会因特定的竞争条件而表现出不良行为，因为访问顺序恰好在 99% 的时间内是“有利的”。然而，偶尔，程序会做一些完全错误的事情，然后您就会遇到崩溃。调试这种情况可能很痛苦，因为 99% 的时间它都按预期工作；只有 1% 的时间您才能发现它工作不正常。更糟糕的是，仅仅向程序添加调试器有时会增加复杂性：这会稍微改变时序，使程序在调试器下始终正确运行，但在不在调试器下运行时会崩溃。是的，它真的可能那么痛苦。

伪共享

在此处列出的错误中，伪共享是独一无二的，因为它不是正确性问题，而是性能问题——这种问题通常难以诊断，并且其影响可能是令人衰弱的。要理解这个问题，您必须了解现代 SMP（对称多处理器计算机）中内存层次结构的基本结构。在大多数 SMP 中，数据缓存对于每个处理器都是私有的，而主内存是共享的。此外，从内存到缓存的数据访问物理粒度称为缓存行，通常是多个字长。问题在于，可能有两个线程，每个线程都在同一个缓存行上工作，但在缓存行上的不同字上工作。缓存失效机制检测到它们正在修改和读取缓存行，但无法检测到它们正在访问缓存行的两个不同部分。结果是缓存行必须不断地写入和从内存中读取。

多范式调试

尽管我们已经关注了传统的并行模型，但至少还有一个模型值得在此处讨论。该模型基于彼此通信的松耦合服务日益普及。如何调试一个应用程序，该应用程序以电子表格作为前端运行，与后端集群和空闲桌面计算机通信（所有这些都与数据库服务器通信），并使用 OpenMP（用于编写多线程应用程序的 API；请参阅 http://www.openmp.org）、MPI 和 Web 服务作为其通信机制的组合？问题不仅包括以上所有问题，还包括跨越这些各种范式边界相关的智力不协调。这是一个没有人甚至开始解决的问题，但这个问题的重要性与日俱增。提示，提示：这是一个很棒的研究课题。

并行调试器和工具的方法

今天有几种并行调试器可用。没有一个是完美的，但它们正在变得更好。此外，虽然它们并不完美，但它们仍然是查找和修复错误的好帮手。本节介绍并行调试器和工具使用的一些方法。对于此处描述的许多解决方案，调试器或工具可以使用几种不同的方法。在本文中，我试图找到一种具有代表性或至少被广泛接受的方法——但列出的内容肯定不是全面的。

让我们首先定义一些在阅读有关调试器时会遇到的术语

暂停。 当进程或线程停止执行时，它将被暂停，并且在适当的提示下，它可以继续执行程序。

单步执行。 在调试应用程序时，程序员可以暂停程序，并且在这个暂停的程序中，程序员可以让指令指针一次移动一条指令。这被称为单步执行。执行此操作的过程称为单步调试。

附加。 调试器附加到进程意味着调试器可以控制进程（例如，暂停或单步执行进程）并检查进程的内存。

断点。 断点是调试器使用的一种机制，用于在源代码中的指定行暂停程序。断点可以是每个程序、每个进程或每个线程的。

标准并行调试

我将此处描述的方法称为标准方法，仅仅是因为它已成为调试并行程序最常用的方法。当大多数人提到并行调试时，他们通常指的是本节中描述的模型。

在标准并行调试模型中，用户在其本地桌面上拥有一个调试器（通常带有图形用户界面前端），他们可以在其中导航调试会话。用户从此调试器调用并行程序（或附加到当前正在运行的并行程序）。这将在多个进程上启动并行程序。然后，调试器附加到可能存在于多台机器上的进程。然后，用户可以在程序中指定断点，就像调试顺序程序一样，但用户也可以指定仅对给定的一组进程和/或线程（分别为进程级和线程级断点）处于活动状态的断点。

此外，一些调试器使用户能够同步进程，以便它们都执行到某一行代码，然后阻塞，直到所有进程都到达此点。如果用户愿意，调试器可以以锁步方式单步执行所有这些进程。

在构建这样的调试器时通常会出现以下类型的问题

可扩展的启动机制。 在本地计算机上使用单个进程启动调试会话所需的时间通常可以忽略不计。启动在 512 个处理器（甚至更困难，10,000 个处理器）上运行的程序在启动时间方面要困难得多。有几种方法可以做到这一点。一种常见的方法是使用基于树的启动机制，其中每个节点告诉 k 个其他节点启动（其中 k 是某个小的整数常数）。

安全调试。 由于正在调试的大多数作业都是远程的，因此必须解决安全问题。特别是，恶意用户可能会尝试将其进程注入到您的调试会话中，伪装成您的进程之一。为了应对这种情况，需要一种身份验证机制来确保每个进程都来自正在进行调试的程序员。

自动附加。 调试应用程序（即使是并行应用程序）也要求用户能够从其进程调用的最早实例开始调试。因此，诸如全局初始化之类的事情应该在调用“main()”（在 C 或 C++ 程序中）之前发生。此外，一些并行程序将生成新的线程和/或进程，并且调试器也应该自动附加到这些新生成的实体。

进程级断点。 当您尝试深入了解并行程序中错误的所在位置时，设置仅对特定进程（或线程）触发的断点变得非常宝贵。此处的部分要求是，为一台计算机设置进程级断点不应不利地影响另一台计算机上进程的运行。

这种标准并行调试的功能在 Etnus 的 TotalView、Streamline Computing 的 DDT（分布式调试工具）以及即将推出的 Microsoft Visual Studio 2005 C/C++ 调试器等产品中可用。

相对调试

另一种方法是相对调试。相对调试背后的基本思想是，即使一个程序在一个处理器上运行，而另一个程序在 1,024 个处理器上并行化，两个相同运行程序的副本中数据结构的状态也应该相同（在指定的时间点）。

例如，给定以下程序片段，假设此循环没有数据依赖性

for(int i = my_process_ID * size; i < (my_process_ID+1) * size; ++i)

k[i] += j[i] – z[i];

在循环的每次迭代中，都会为数组元素 k[i] 赋值。无论这是作为顺序程序还是并行程序运行，此值都应相同。相对调试器同时运行单进程（代码的参考版本）和应用程序的多进程版本，并确保程序的状态相同（或在程序中各个点应该相同时在指定的容差范围内）。如果程序中的值不同，则用户可以中断代码以检查是什么原因导致了这种差异。当您知道并行程序与参考程序不同，但很难跟踪这种差异何时何地开始时，这可能是一个很棒的工具。

相对调试是 Guardsoft 的 Guard 调试器的一项功能。

执行跟踪调试

对于一些较大的并行计算机安装，计算机时间仍然不像台式计算机那样是商品。因此，批处理非交互式作业仍用于访问某些集群。在这些情况下，用户不再具有对应用程序的交互式访问权限；因此，他们无法交互式调试应用程序。解决此问题的一种方法是执行跟踪调试。

并行计算世界中的执行跟踪调试类似于顺序桌面世界中的事后调试，不同之处在于，在顺序桌面世界中，您通常在崩溃转储文件上使用事后调试来找出程序崩溃的原因。使用执行跟踪调试，无论程序是否崩溃，都会生成跟踪文件。

要执行基于执行跟踪的调试会话，您必须使用应用程序的特殊检测构建版本。此检测构建版本将在应用程序执行时将执行跟踪写入日志文件。日志文件允许调试器重放所有发送的消息，并保留它们发送的相对顺序。然后，日志文件成为调试器的输入，用户使用标准并行调试或相对调试来调试重放的过去会话。日志文件的另一个额外优点是，实际的调试过程不会像交互式调试会话通常那样 Disrupt 消息的时序。

可视化

许多人认为可视化仅仅是查看计算结果的一种方式，但事实证明，它也是调试应用程序（尤其是并行应用程序）的强大工具。可视化的基本用途倾向于识别两种类型的错误

• 那些被识别为模式中的异常值。当查看文本文件中的原始数据时，这些模式通常很难看到，但通过可视化，它们变得显而易见。

• 那些从预期模式中产生相当剧烈变化的模式。当查看原始数据时，这些错误很容易看到，但通常很难确定它们何时何地开始。通过可视化，这通常会变得容易得多。

我们将用于调试并行应用程序的可视化分为三种不同的类型

消息队列可视化。在某些消息传递 API（例如 MPI）中，存在消息队列的概念，其中包含有关当前正在处理的消息的信息。通常，有三种类型的队列：发送队列、接收队列和意外消息队列。可视化使用进程中消息队列状态的快照，并构造一个图来表示队列。该图由节点（代表进程）和边（不同颜色，或点线与虚线）组成，这些边表示每条消息的队列类型。

图 1 是消息队列可视化可能是什么样子的一个示例。

通过这种类型的可视化，您可以快速查看沿某些路径的消息队列中是否存在不平衡。

消息时序可视化。在程序执行期间，消息从一个进程发送到另一个进程，并且具有这些消息及其时序的图形视图对于查找错误可能很有用。

大多数并行程序在其消息传递模式方面都具有一定程度的规律性。尽管对于查看代码的人来说，这些模式可能很迟钝，但消息传递模式时序的可视化可以带来一些有趣的见解。例如，看一下图 2 中的可视化。在此图中，我们可以看到进程 6 显然有些奇怪，因为它没有遵循向下一个进程发送消息的模式（进程 8 向进程 1 发送消息，因为进程 8 没有“下一个进程”）。

这只是一个例子。您还可以使用这种类型的可视化来调试瓶颈性能问题（所有消息都发送到或来自少量进程）。

分布式数组可视化。数组是在多个处理器之间分发数据的首选数据结构。在科学程序中，通常有大量的标量值数组，这些数组可以很容易地可视化为 2D 或 3D 网格（当然，高于此维度的维度很难可视化）。然而，这些简单的可视化可以快速揭示异常，这些异常是错误的直接结果。

例如，数组中的值通常具有相对平滑的过渡，因为它们可能表示某个表面上的热量。如果一个区域中的每个值都从 0.0 变为大约 0.2，但在所有内容的中间有一个值 9.8e57——那么，您就有一些东西需要调查。

一些产品执行类似于此处介绍的可视化类型。例如，Etnus 的 TotalView 支持消息队列可视化，英特尔的 Trace Analyzer 支持消息时序可视化，而 Streamline Computing 的 DDT 支持分布式数组可视化。

值比较

分布式数组可视化部分指出，可视化如何以图形格式使模糊的异常变得明显；值比较通过数据的统计分析来实现这一点。

值比较获取一组数据，并根据一组统计标准查找异常值。统计标准可以是相等性、超出两个标准差的值、不符合用户指定函数的值等。例如，如果二维数组中的所有数据都在邻居值的某个增量范围内，除了某个区域中的特定小块数据，那么这块数据可能是您期望首先找到异常的地方。

Streamline Computing 的 DDT 调试器中提供了一组与此类似的功能。

竞争条件检测

竞争条件难以检测和发现，但一些工具和技术可以提供帮助。它们可以分为两大类：静态检测和动态检测。

静态检测竞争条件是一个特别困难的问题。事实上，一般问题被归类为 NP-Hard 问题的复杂度类。话虽如此，有一些静态方法可以找到哪些访问不能涉及竞争条件。请注意，它们可能无法找到所有此类情况，但它们至少可以找到其中的一部分列表。对于那些无法决定是否将它们从所有竞争条件中排除的情况，必须进一步检查——由开发人员手动检查或借助动态检测工具。

动态检测基于使用程序的检测构建版本（或特殊的运行时或二进制重写技术）来查找程序执行期间的竞争检测。程序的这个检测版本能够检测到何时对共享变量的访问没有受到锁的适当保护。在这些情况下，它可以向用户引发错误。通常，动态保护的算法过于严格，但过于严格比错过数据竞争要好。

动态和静态检测可以互补地结合使用。静态检测可以静态推断哪些访问没有竞争条件；然后，动态检测可以进一步缩小可能发生竞争条件的位置。

学术项目 Eraser 是动态竞争条件检测的一种流行的实现。英特尔的 Thread Checker 是一种流行的商业工具，其中也包含竞争条件检测器。

未来的挑战

这里的挑战是巨大的。简而言之，尚不清楚我们是否甚至理解编写复杂并行程序所涉及的所有问题——鉴于此，我们如何才能希望解决调试问题？答案是这将是困难的。编程模型的复杂性与调试的难度密切相关。

例如，阻止内存泄漏的关键技术不是更好的内存泄漏检测工具，而是垃圾回收（以及支持垃圾回收的语言）。我怀疑正确并发程序的圣杯将与实际程序的编写方式的范式转变有关，而不是用于调试程序的工具。

正如您所注意到的，此处列出的各种方法在很大程度上没有解决多范式调试的挑战。这是因为还没有任何方法接近对此问题的令人满意的解决方案。最接近它的是多语言调试，它目前存在于一些高端开发工具中，例如 Visual Studio。如果您正在寻找要开发的产品，那么非常需要一个好的多范式调试器（或将多个调试器联系在一起的基础设施）。

鉴于编写并行程序对于计算机科学和信息技术产业的未来的重要性，我预计在未来几年，伟大的研究和商业产品都将继续解决这个问题。 Q

资源

今天可用的各种产品提供了随附文章中讨论的大部分并行调试功能。

Microsoft Visual Studio 2005 将增加对标准并行调试的支持，包括进程级和线程级断点和单步执行。 http://lab.msdn.microsoft.com/vs2005/

Etnus 的 TotalView 支持标准并行调试以及消息队列可视化。 http://www.etnus.com

英特尔的 Trace Analyzer 支持并行程序的可视化，包括消息时序可视化。 http://www.intel.com/software/products/cluster/tanalyzer/

英特尔的 Thread Checker 具有帮助查找死锁和竞争条件的功能。 http://intel.com/software/products/threading/tcwin/

Streamline Computing 的 DDT（分布式调试工具）支持本文中描述的各种功能，包括值比较和分布式数组可视化。 http://www.streamline-computing.com/softwaredivision_1.shtml

Guardsoft 的 Guard 调试器具有相对调试机制。 http://www.guardsoft.net/products.html

喜欢还是讨厌？告诉我们

[email protected] 或 www.acmqueue.com/forums

KANG SU GATLIN 是微软 Visual C++ 编译器团队 (http://msdn.microsoft.com/visualc) 的项目经理，他专注于代码生成和优化，以及 64 位和高性能计算开发工具。他获得了加州州立理工大学圣路易斯奥比斯波分校的计算机科学学士学位，以及加州大学圣地亚哥分校的计算机科学硕士和博士学位。

最初发表于 Queue 第 2 卷，第 7 期—
在数字图书馆中评论本文

更多相关文章

Adam Morrison - 多核程序中的可扩展同步
为现代多核处理器设计软件提出了一个难题。传统的软件设计（其中线程操作共享数据）具有有限的可扩展性，因为共享数据更新的同步会序列化线程并限制并行性。另一种分布式软件设计（其中线程不共享可变数据）消除了同步并提供了更好的可扩展性。但是，分布式设计使得实现共享数据结构自然提供的功能（例如动态负载平衡和强一致性保证）具有挑战性，并且根本不适合每个程序。然而，通常，共享可变数据结构的性能受到当今使用的同步方法的限制，无论是基于锁的还是无锁的。

Fabien Gaud, Baptiste Lepers, Justin Funston, Mohammad Dashti, Alexandra Fedorova, Vivien Quéma, Renaud Lachaize, Mark Roth - 现代 NUMA 系统上内存管理的挑战
现代服务器级系统通常构建为将多个多核芯片组合在一个系统中。每个芯片都有一个本地 DRAM（动态随机存取存储器）模块；它们一起被称为一个节点。节点通过高速互连连接，系统是完全一致的。这意味着，对程序员透明的是，内核可以向其节点的本地内存以及其他节点的内存发出请求。关键的区别在于远程请求将花费更长的时间，因为它们会受到更长的线路延迟的影响，并且在遍历互连时可能需要跳过多个跃点。

Spencer Rathbun - 使用 Promise 进行并行处理
在当今世界，有很多理由编写并发软件。提高性能和增加吞吐量的愿望导致了许多不同的异步技术。然而，所涉及的技术通常很复杂，并且是许多细微错误的根源，特别是当它们需要共享可变状态时。如果不需要共享状态，那么这些问题可以通过称为 promise 的更好抽象来解决。这些 promise 允许程序员将异步函数调用连接在一起，等待每个函数返回成功或失败，然后再运行链中的下一个适当的函数。

Davidlohr Bueso - 实用同步原语的可扩展性技术
在理想世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅这种扩展不会发生，而且在这些更大的系统上，性能实际上会变得更糟是很常见的。