识别并发问题的工具和方法.doc

识别并发问题的工具和方法本文来自MSDN杂志为了满足用户对计算能力日益增长的需求，硬件行业正在逐步向多核处理器系统发展。与通过具有较大时钟速度的较快处理器提高应用程序性能不同，要改进多核系统的性能，只能通过编写高效的并行程序才能实现。并行处理形式在软件行业问世已久。但是，若要创建利用并行硬件功能的主流软件应用程序，需要对面向顺序应用程序的实践进行重大更改。测试并行应用程序相当复杂。例如，由于并行应用程序显示的行为难以确定，很难检测到并发错误。即使检测到了这些错误，也很难统一重现它们。而且，修复某一缺陷后，很难确保已真正修正了缺陷，而不仅是在表面上掩藏起了问题而已。此外，并行化还可能会引发新的性能瓶颈，而这些也必须加以识别。在本文中，我们将介绍并行程序的测试技术，并提供六种可用于查找潜在严重缺陷的工具。首先，我们将介绍下面几类并发错误：争用条件、不正确的互斥和内存重新排序。争用条件、死锁等内容当多线程程序中有两个或多个执行线程尝试访问同一共享数据，并且其中至少有一个访问为写入时，就会发生争用现象。有害的争用条件会带来不可预测性，且通常难以检测到。争用条件的影响可能在很长一段时间后才会显现，或只有在完全不同的程序部分中才能察觉到。而且，它们也相当难以重现。使用同步技术合理对线程之间的操作进行排序，可以避免出现争用。识别测试数据和报告指标对于并行应用程序，测试数据通过识别方案的可伸缩性方式进行定义。事实上，应用程序展示的可伸缩性取决于所使用算法的可并行性。特定算法可以针对特定的问题域(例如，在非统一分发中搜索)产生超线性加速效果。其他算法由于可并行性有限，可能不会勉强产生并行加速效果，导致总运行时速度的增加与CPU数量不成比例。此外，还有些算法(如排序)不会在整个数据集大小范围内进行线性缩放。因此，您必须了解应用程序的性能针对下列类别如何缩放：线程数或CPU核数通常，用户希望并行应用程序可以随CPU或线程数的增加进行线性缩放。数据集大小通常，用户希望并行应用程序的性能不会随输入数据集的大小增加而降低。执行工作负荷在执行过程中，线程操作的工作负荷并不是一成不变的。工作负荷可能增加或降低、随机变化或呈正态分布。在执行过程中，工作负荷的变化可能会影响应用程序的性能特征。在执行过程中，工作负荷的变化类型包括：恒定工作负荷、增加工作负荷、降低工作负荷、随机工作负荷和正态分布的工作负荷。报告时最常使用执行时间指标。其他报告指标包括与顺序应用程序相比的加速效果，以及针对可伸缩性类别的加速效果。定义报告指标及其测量方式非常重要。可从下列一些有价值的问题开始着手：必须报告哪些值?如何对它们进行报告?用于测量的工具是否会影响性能?此外，如果可以，请分段进行测量，以便了解系统各子部件的性能。有时，争用可能是刻意安排的，可安全进行。例如，假设有一个名为done的全局标志，对于此标志，只有一个写入器，但有多个读取器。写入器线程设置此标志是为了告知所有线程安全终止。所有读取器线程可能使用while(！done)循环运行，重复读取此标志。一旦某个线程发现设置了done标志，便会退出其while循环。在大多数情况下，这属于良性争用。对于检测争用条件可用的工具，稍后我们将在本文中进行讨论。但是，此类工具可能会对实际上属于良性的争用情况发出警告，这样的错误报告称为误报。当两个或多个线程互相等待，形成一个循环并阻止所有线程继续进行时，就会发生死锁。在尝试避免争用条件时，编程人员可能会引发死锁。例如，对同步基元的不正确使用(如按错误顺序获取锁定)可能会导致两个或多个线程互相等待。在不使用锁定构造的情况下，也可能会发生死锁；任意类型的循环等待都可能会导致死锁。请查看以下示例了解可能会出现死锁的情况。线程1执行下列语句：Acquire Lock A；Acquire Lock B；Release Lock B；Release Lock A；Thread 2proceeds like so：Acquire Lock B；Acquire Lock A；/if thread 1has already acquired lock/A and waiting to acquire lock B,then/this is adeadlockRelease Lock A；Release Lock B；在多线程应用程序中，耗尽(Starvation)会无限延迟或永久锁定一个或多个可运行的线程。即使未计划要运行的线程没有被锁定或等待其他线程，也将被认为处于耗尽状态。耗尽通常是由计划规则和策略造成的。例如，如果同时安排一个高优先级、无锁定、持续执行的线程与一个低优先级的线程，那么在单核CPU上，优先级较低的线程将永远没有机会运行。为了帮助避免出现这种情况，Windows®；计划程序时常进行干预，通过提升耗尽线程的优先级降低出现耗尽的情况。如果安排了线程，但由于它们不断响应彼此的状态变化而没有继续向前进行，就会发生活锁。描述此情况最好的例子是：假设两个人在一个狭窄的走廊上相遇，他们都向旁边跨步为对方让路，但每次都正好阻止对方的去路。这样向旁边让路会阻止向前继续进行，从而导致活锁。CPU利用率较高，但却没有完成实际工作，这是典型的活锁警告标志。活锁非常难以检测和诊断。内存排序相关的问题当编译器优化代码时，它可能会决定对代码段重新排序以改进性能。但是，这可能会使监控全局状态变化的线程发生意外行为。例如，假设您有两个执行线程：线程1和线程2。再假设有两个全局变量x和y，二者均已初始化为0。线程1运行以下行：x=10；y=5；线程2执行下列语句：if(y=5)Assert(x！=10)；在此，优化编译器可能会发现，在任何情况下，最终为y重新分配的都是5。它可以对代码重新排序，以便先为x分配10，再为y分配5；从执行这两种分配的单线程角度而言，排序不起任何作用。因此，线程2的声明可能会被放弃，因为x可能不等于10。必要时，可以使用可变变量和编译器内部函数来避免对编译器内存重新排序。还有一点值得注意，通用的优化标志处于打开状态时，线程2可能永远看不到变量y或x的更新。因此，在此用户只能使用可变变量。除编译器重新排序外，还有很多方面都相当复杂。内存访问优化(如缓存)和通过推测执行实现的高级获取功能都可能会使一个CPU上某个线程执行的内存操作被视为由其他CPU上的其他线程以另一种顺序执行。只有在具有多个CPU或多个CPU核的系统中，才会发生这种内存重新排序认知。为了清楚说明此问题，假设有两个执行线程：线程1和线程2。再假设m和n是全局变量，两者均已初始化为0，并且a、b、c和d都是局部变量。线程1(位于处理器1上)执行以下指令：m=5；/A1int a=m；/A2int b=n；/A3线程2(位于处理器2上)执行以下指令：n=5；/A4int c=n；/A5int d=m；/A6逻辑上(在按顺序保持一致的内存环境中)，执行所有这些指令后永远不会发生b=d=0。但是，硬件内存重新排序可能会导致对共享内存(A1和A4)的写入变为存储缓冲区转发，从而导致不同的处理器观察到不同方式的写入。测试策略测试并发应用程序需要测试正确性、可靠性、性能和可伸缩性。通过静态分析、动态分析和模型检查等方法可确定应用程序的正确性。通过研究并行性引发的开销以及压力测试可对性能和可靠性进行测试。通过分析应用程序对不同规模的系统的执行效果可测试可伸缩性。静态分析方法可分析代码，无需实际执行程序。通常，通过查看编译的应用程序的元数据或添加了注释的源代码来执行静态分析。通常，这种分析包括一些正式检查，以确保编程人员的意图和假设可阻止不正确的行为。Prefix和Prefast是适用于本机应用程序的两种最常用的静态分析工具，而FxCop非常适用于托管代码。静态分析有利有弊。其中，优点包括可进行全面而详尽的分析、正式分析有利于增强对产品设计的信心，并且精确的错误报告可使查找并修正错误变得更加容易。但是，要处理并发错误，静态分析需要使用大量注释来指定意图。而且，这些注释自身必须正确。此外，使用静态分析的工具容易生成许多误报，并且需要付出很大精力才能将误报降至最低。在动态分析中，可通过查看执行记录来检测错误。动态分析分为两种类型：联机和脱机。使用联机动态分析的工具在程序执行时对其进行分析；使用脱机动态分析的工具先记录跟踪，稍后才对其进行分析来检测错误。动态分析非常方便，它在编程阶段需要开发人员投入的额外精力很少，甚至无需投入额外精力，生成的误报也很少，可以更轻松地解决比较明显的问题。由于只能在执行路径中发现错误，所以使用比较频繁的路径会产生第一批错误。这样，可以降低改进可靠性的开销。动态分析也有弊端。您只能在执行路径中检测错误，并且需要依赖测试用例来覆盖更广的代码。实际上，某些工具只有在运行中发生争用时才能捕获该争用。因此，即使工具不报告任何错误，仍无法确定是否真的不存在任何错误。另一个弊端是，大多数动态分析工具依赖某种可能会修改运行时行为的手段。由于比较复杂，这些工具的性能可能非常不理想。最后一种方法是模型检查，即用于验证有限状态并发系统正确性的方法。它允许进行正式演绎推理。模型检查器可尝试模拟争用和死锁条件。借助模型检查，即可正式证明不存在争用和死锁。此方法可增强对设计和体系结构的信心、覆盖更广的范围，并且降低对外部驱动程序的需要。与其他测试方法相同，模型检查也存在一些弊端。在大多数情况下，很难自动从代码中提取出模型(在极个别情况下是可以的)。手动执行模型提取也相当繁琐。由于状态空间激增，需要验证的内容也随之增加。在这种情况下，状态的潜在数量可能因过于庞大而无法进行分析。在某种程度上，可通过应用使用复杂试探法的规约技术控制状态空间激增。这种试探法也存在缺陷，如无法检测长时间运行的应用程序中的错误。最后，模型检查还需要严格的设计和实现计划。模型检查可证明此设计没有错误，但是实现仍可能是不正确的。实际上，模型检查仅适用于产品关键的一小部分。还有一些其他混合技术，包括将动态分析与模型检查结合起来。例如CHESS，稍后将为您介绍。争用检测算法静态和动态分析工具都可使用锁集算法，以便在两个或多个线程访问共享内存但没有使用通用锁的情况下报告潜在的争用。从根本上说，此算法假设对于每个共享内存变量v，每个线程在访问变量时都会获得一个非空锁C(v)集。最初，C(v)是所有锁的列表。每个线程同时还会保留两个锁集：locks(t)表示所有持有的锁，writeLocks(t)表示所有持有的写入锁。此算法的计算过程如下：对于每个共享内存变量v，保留一个C(v)锁集。最初，C(v)是所有锁的列表。每个线程同时还会保留两个锁集：locks(t)表示所有持有的锁，writeLocks(t)表示所有持有的写入锁。每当线程t读取v时：C(v)集=C(v)locks(t)。如果C(v)=NULL集，则会生成一个错误。每当线程t写入v时：C(v)集=C(v)writeLocks(t)。如果C(v)=NULL集，则会生成一个错误。事实上，当应用程序运行时，每个变量的C(v)开始收缩。当C(v)为null时(例如，如果线程访问共享内存时其锁集交集为NULL)，将会生成一个错误。遗憾的是，锁集算法报告的所有争用并非都是真正的争用。人们通过应用灵活的编程技巧或使用信号等其他同步基元，可以在不使用锁的情况下编写出不会出现争用的代码，这使得查找真正的错误相当困难。注释和某些禁止可以帮助缓解此问题。另一种用于检测争用的算法是happens-before(之前发生)，它基于分布式系统中事件的部分排序。以下是对此算法的概述，此算法要计算部分排序以确定事件发生的先后顺序(在此上下文中，事件指所有指令，包括读/写和锁定)：在任何单个线程中，事件都按其出现顺序排序。在多个线程中，事件按同步基元的属性排序。例如，如果lock(a)由两个线程获得，则会先解除对一个线程的锁定，然后再对另一个线程进行锁定。如果两个或多个线程访问一个共享变量，但这些访问没有按happens-before关系明确排序，则说明已发生争用。图A中介绍了此算法。线程1的解除锁定发生在线程2的锁定之前。因此，永远不会出现同时访问共享变量的情况，也就不会发生争用。此算法的一大弊端是，监控这种关系的开销非常大。更大的问题是此算法检测争用的功能完全取决于计划顺序。部分排序仅适用于计划的特定实例，并且在不同时间执行同一测试可能会漏掉一些错误。图B不会报告任何争用，但按图C中的执行顺序则会报告争用。据说，许多争用在产品发布多年后才会发生。因此，这种检测方法并不能让人完全放心。从一方面来看，happens-before很少出现误报。大部分错误都是真实的。但是，happens-before会漏掉许多错误(漏报)，并且难以有效实现。同样，锁集算法非常有效，可以检测到更多错误。但是，它容易生成过多的误报。人们一直在尝试如何将这两种算法结合起来以克服两者的弊端。备注：这些争用检测算法已经演变发展了多年，可通过搜索ACM/IEEE门户找到这些算法的相关信息。图A Happens-Before算法(单击图像可查看大图)图B将不会报告争用(单击图像可查看大图)图C将检测到争用(单击图像可查看大图)并发测试工具市场上存在大量并发测试工具，可帮助您处理潜在的死锁、活锁、挂起以及运行并行事务时遇到的其他任何问题。下面介绍的每种工具都适用于特定的领域。CHESS由Microsoft Research创建，它是模型检查和动态分析的巧妙组合(请参阅/fwlink/?LinkId=116523)。它通过系统地探究线程计划和交错来检测并发错误。它能够发现争用条件、死锁、挂起、活锁和数据损坏问题。为便于调试，它还提供了完全可重复的执行功能。与大多数模型检查相同，系统探究可以全面涉及整个系统。作为动态分析工具，CHESS可在专用计划程序上重复运行常规单元测试。每次重复时，它将选择不同的计划顺序。作为模型检查器，它可控制能够创建特定线程交错的专用计划程序。为控制状态空间激增，CHESS应用部分排序规约技术和新的迭代上下文界限。在迭代上下文界限中，CHESS不会在深度上限制状态空间激增，而是限制给定执行中线程切换的次数。在线程切换期间，线程本身可以运行任意数目的步骤，从而使执行深度不受任何限制(相对于传统模型检查，这是一大优势)。根据以往经验，只需少数系统线程切换就可以检测出大部分并发错误。CHESS可以检测死锁和争用(使用/fwlink/?LinkId=116877中介绍的Goldilocks锁集算法)，但还有赖于编程人员来判断其他状态。它旨在终止所有程序，并有效保护所有线程继续进行。因此，如果程序进入连续循环状态，CHESS将报告活锁。从测试角度考虑，您可以首先将迭代上下文界限设为2，开始运行CHESS。如果检测不到错误，可将此界限增加到3，依次类推。根据以往经验，使用界限2和3应可检测到大部分错误。因此，这种方法可以非常快速且有效地检测到错误。从工具方面考虑，CHESS不使用Win32®；API同步调用进行控制，并且故意引入了不确定性。此外，它要求开发人员代码中包括大量声明来确保状态的一致性(良好的代码都应满足此要求)。但是，与大多数动态分析工具相同，它需要良好的测试套件才能涉及更广的范围。对于只能依靠压力来更好地进行交错测试的开发人员和测试人员来说，CHESS是一种很好的选择。它采取常规单元测试，巧妙地模拟有趣的交错。Intel线程检查器这是一种动态分析工具，用于查找死锁(包括潜在死锁)、延迟、数据争用以及对本机Windows同步API的不正确使用(请参阅/fwlink/?LinkId=115727)。线程检查器需要实施源代码或编译的二进制文件，才能使每个内存引用和每个标准Win32同步基元可见。运行时，实施的二进制文件可为分析程序提供充足的信息以构建执行部分排序。然后，该工具对部分排序执行happens-before分析。有关happens-before分析的详细信息，请参阅争用检测算法侧栏。为了获得更好的性能和可伸缩性，此工具仅会记录对共享变量的最近访问，而不会记录所有访问。这有助于提高该工具分析长期运行的应用程序的效率。但是，该工具也存在弊端，它可能会漏掉一些错误。这是一种折衷，或许找出长期运行的应用程序中的大部分错误比发现短期运行的应用程序中的所有错误更加重要。该工具唯一最大弊端是，它无法通过联锁操作(如在自定义转锁中使用的操作)解决同步问题。但是，对于仅使用标准同步基元的应用程序，该工具可能是用于并发测试本机应用程序的最受支持的测试工具之一。RacerX此流敏感静态分析工具用于检测争用和死锁。它克服了需要繁琐地为所有源代码添加注释这一难题。实际上，唯一的注释要求是，用户提供一个指定用于获得和释放锁的API的表。还可以指定锁定基元的属性，如旋转、锁定和重入。通常，此表非常小，最多包括30个条目。这样，可大大减轻大型系统源代码注释的负担。在第一阶段，RacerX基于每个源代码文件迭代，并构建控制流图(CFG)。CFG提供了有关函数调用、共享内存、指针使用以及其他数据的信息。当RacerX构建CFG时，它还可以返回参考同步基元表，并标出对这些API的调用。构建好完整的CFG后，即可进入分析阶段，该阶段包括运行争用检查程序和死锁检查程序。遍历CFG可能需要花费很长时间，但是可以利用适当的规约和缓存方法将遍历时间降至最低。遍历上下文流时，可使用锁集算法捕获潜在的争用(有关此算法的详细信息，请参阅争用检测算法侧栏)。对于死锁分析，每次执行锁定时，它都会计算锁定周期。在最后一个阶段，将对报告的所有错误进行后期处理，以按照错误的重要性和危害程度排列它们的优先级。就像对静态分析的预期一样，作者满怀信心地倾注了大量精力来尝试降低误报和现有错误。最后，此工具的效果非常显著，从测试工程角度而言，它看起来切实可行。Chord它是一种对流不敏感但对上下文敏感的静态分析工具，适用于Java。由于对流不敏感，它比其他静态工具的可伸缩性更强，但精确性较差。此外，它还考虑到了Java中可用的特定同步基元。使用的算法非常复杂，需要引入多个概念。(有关Chord的详细信息，请参阅/fwlink/?LinkId=116526。)KISS由Microsoft Research研发，此模型检查器工具适用于并发C程序。由于并发系统中的状态空间快速激增，KISS将并发C程序转换为可模拟交错执行的顺序程序，然后使用顺序模型检查器执行分析。使用将并发程序转换为顺序程序的语句执行此应用程序，同时由KISS负责控制非确定性。非确定性上下文切换根据上述CHESS中介绍的类似原则进行限制。编程人员可引入声明来验证并发假设。该工具不会产生误报。它是一个研究原型，Windows驱动程序团队已用过该工具，它主要使用C代码(请参阅/fwlink/?LinkId=115723)。Zing该工具是一个纯模型检查器，用于对并发程序进行设计验证。Zing使用自己的自定义语言来描述复杂的状态和转换，并且完全能够建立并发状态计算机的模型。与其他模型检查器相似，Zing提供了验证设计的综合方法；此外，您可以验证假设，并明确证明是否存在特定条件，从而增强对设计质量的信心。它还通过创新的规约技术解决了并发状态空间激增问题。Zing使用的模型(用于检查程序正确性)必须手动或通过转换器创建。虽然可以编写一些特定域转换器，但目前我们尚需探索适用于本机或CLR应用程序的任何完整且成功的转换器。如果没有转换器，我们确信Zing无法用于大型软件项目，只可用于验证项目的关键子部件的正确性(请参阅/fwlink/?LinkId=115725。)性能测试性能测试是并发测试过程中不可或缺的一部分。毕竟，开发并行应用程序的一个主要目的就是提供优于顺序应用程序的高级性能。正如Amdahl定律和Gustafson定律中的基本原理，并行应用程序实现的性能深受下列方面的影响：其算法的可并行性方面、程序中顺序部件数量、并行化开销和数据/工作负荷特征。通过执行性能测试，项目负责人可以了解和分析并行应用程序的性能特征。对并行应用程序执行性能测试的常用方法与顺序应用程序的性能测试方法相同。下一部分将介绍如何针对并发应用程序调整某些关键的性能测试步骤。要了解最有帮助的测量因素，请参阅识别测试数据和报告指标侧栏。执行性能测试最重要的步骤是定义测试目标。对于并行应用程序来说，有效的测试目标包括：了解所用算法的可并行性/可伸缩性、了解各种设计备选方案的性能特征、调查同步和通信开销以及验证是否符合性能要求。值得注意的是，性能测试的目标和范围也可能因测试执行人员的不同而有所差异。例如，部署并行应用程序的客户执行性能测试可能是为了确保满足业务需求，而开发团队可能对执行详尽的性能测试以发现性能瓶颈并改进程序的可并行性更有兴趣。此外，测试目标在整个软件开发周期中可能会有所不同。在设计和实现阶段，测试目标可能是了解和改进应用程序的性能特征；而在测试和发布阶段(稳定阶段)，测试目标可能是确保各版本的性能不出现回退。在性能测试过程中，另一个重要步骤是定义测试方案并为这些方案设定目标。如果开发团队对了解并行应用程序的性能特征感兴趣，则可定义三种测试方案：客户方案测试、关键性能指标(KPI)测试和微基准(MBM)测试。各种性能测试之间的关系可视为与系统测试、集成测试和单元测试之间的关系相同。也就是说，客户方案测试会引发一组KPI测试，而KPI测试会引发一组MBM测试。通过了解各种测试类型之间的关系，开发人员可以了解并行应用程序各子部件之间的性能关系。了解此关系后，还可以更好地排列性能错误的优先顺序；更重要的是，开发团队可以针对客户性能投诉做出响应，提供面向结果的建议。为任何重要的应用程序设定性能目标都是一项艰巨的任务，更不用说为并行应用程序设定性能目标了。设定目标的一种方法是基于下列呈三角关系的指标来派生目标：应用程序每个组件和子组件的预期算法或理论性能指标、相对分析(比较对象包括类似的竞争方应用程序)和现有的实现/应用程序(如果存在)剖析。与测试目标一样，每个测试方案都应定义一组验收条件(一组用于验证测试结果的值)。对于并行测试方案，可使用下列变量作为验收条件。测试结果中的偏差它指示应用程序的不稳定性。通过计算结果的标准偏差，可以了解测试结果中的偏差。CPU使用率如果CPU使用率较低，则可能表示出现死锁和同步开销等并发错误。相反，高CPU使用率也不一定表示成功，因为活锁同样会导致高CPU使用率。垃圾回收对于托管应用程序，过多的内存管理操作可能会阻碍实际的操作执行，可能表示设计或实现存在错误。线程执行总时间如果程序按顺序执行，通过此变量可估算出总执行时间。将线程执行总时间与按顺序实现的同一算法程序的已用时间进行比较，可以了解并行化开销(还可用于注释测试是否有效)。内存使用总量测量内存使用总量有助于了解应用程序的内存配置文件。对于托管应用程序，垃圾回收器对于改变应用程序的内存使用总量具有重要作用，因此在评估内存使用率时应对此加以考虑。在开始进行性能测试之前，您可以执行下列三个重要步骤来确保获得更相关的结果。首先，使测试环境中的偏差降至最小(应用程序和测试环境都可能引入偏差)。在测试环境中，可通过停止不必要的服务和应用程序并减少网络干扰降低偏差；对于应用程序导致的偏差，可通过执行预备迭代和收集多次测试迭代中的测量值来降低偏差。其次，对于托管应用程序来说，垃圾回收器执行不当可能会导致性能结果无效。因此，您应该在收集测量值和/或将GCLatencyMode更改为LowLatency(这种情况仅存在于Microsoft®；.NET Framework 3.5中)之前或之后强制调用垃圾回收(GC)，以此来降低性能测试过程中调用垃圾收集器的可能性。第三，在收集测量值之前始终要执行准备工作。在收集测量值之前执行一次测试来做好准备工作，可以降低原始成本，如变量初始化、JITing成本(在托管应用程序中)和初始缓存缺失延迟。请注意，根据性能方案，测量冷启动性能可能也很重要。(有关提高应用程序启动性能的详细信息，请参阅/magazine/cc 337892.aspx。)有关并发测试的其他参考资料使用同步/fwlink/?LinkId=115730 Bugslayer：等待链遍历m