没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记174(2007)5-22www.elsevier.com/locate/entcs多线程C++服务器应用程序ArndtMuühlenfeld1,2 FranzWotawa3格拉茨理工奥地利格拉茨摘要由于一方面对处理能力的需求不断增加,但另一方面对CPU时钟速度的物理限制,多线程编程在当前应用中变得越来越重要。不幸的是,多线程程序很容易出现编程错误,导致难以发现的缺陷,主要是竞争条件和死锁。对帮助发现这些错误的工具的需求是迫切的,但目前可用的工具要么因为需要注释而难以使用,无法处理超过几十个kbps的错误,要么发出太多错误警告。本文介绍了免费提供的工具Helgrind的实验和使用它调试一个服务器应用程序,包括500 kbps的结果。我们提出了改进的C++程序的运行时分析,导致错误警告的显着减少。关键词:数据竞争,竞争条件,调试,并行程序,同步,多线程编程,面向对象编程,静态-动态协同分析1介绍硬件每年都变得越来越强大最近的发展已经将CPU速度推到了可管理频率的边缘进一步的改进只能通过增加CPU(或一个芯片上的CPU核心)的数量来实现。今天的软件不能从多处理器机器中受益,除非它使用多线程。因此,对“多线程”应用程序的需求此外,多线程是一种强大的范例,可以帮助将程序划分为执行的逻辑线程,从而使交叉操作更容易建模。但是并行执行引入了可能的错误,1在“V oI PL?osung s modd el l f uür k o erg g e n t e Netze”的版本中,已开发了此版本。它得到了奥地利研究促进署(http://www.ffg.at)的支持,项目合同号为809178。2电子邮件:amuehlen@ist.tugraz.at3电子邮件:wotawa@ist.tugraz.at1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2007.04.0046A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5以通过常规调试技术来检测和定位。这是由于并发程序的执行顺序不可预测,因此也是不确定的如果没有适当的同步,可以识别出并发执行特有的两大类错误。数据竞争,其中对共享内存位置的非同步访问会导致数据不一致;死锁,其中两个或多个线程会互相阻塞,主要是因为循环依赖。因此,开发人员需要工具来帮助发现这类错误。针对多线程程序中的故障检测,提出了模型检查、静态分析和运行时分析等解决方案。状态空间爆炸问题的模型检验支持。尽管所有的努力(例如反例引导抽象细化[3]),它仍然不适用于大型程序。静态分析技术试图通过对源代码应用语法分析来定位可能的错误。通过静态分析检测所有可行的数据竞争是众所周知的NP难题[11]。C++领域的另一个问题是缺乏免费可用的正确和可靠的解析器来生成合适的抽象表示。运行时方法的可伸缩性很好,但只考虑执行路径上的错误。因此,检测所有可能的数据竞争是不可能的。一个高效的基于锁集的运行时算法Eraser [14]在开源工具Valgrind中实现,因此适用于所有基于Linux-x86的环境。不幸的是,至少对于C++应用程序来说,错误报告的可能数据竞争的数量太大,使得该工具难以使用,因为每个报告的位置都必须手动检查。一般来说,该算法易于使用,因为它不需要程序员进行特殊这使它成为日常使用的完美工具。然而,一般的程序员不会使用一个生成数百个虚假警告的工具,他必须手动分析,因为这是一个耗时且容易出错的任务。因此,有必要在保持原始无监督可靠行为的同时减少误报的数量。此外,不应需要程序员编写的注释。解决方案是结合静态和运行时分析,通过自动注释程序,并对程序员透明。注释为运行时方法提供了从源代码结构中收集的附加知识虽然这些提示减少了误报的报告,但它们不是必需的。因此,仍然可以分析程序,其中只有部分源代码可用。这项工作提出了从实验中的工具Helgrind的橡皮擦实现应用到现有的网络服务器应用程序的结果。做了两个改进:一个是更好地模拟实际的硬件行为(即,总线锁定)。另一个是为了应付C++特有的实现问题所引入的影响。这大大减少了误报报告的数量,使该工具可用于调试大型C++应用程序。特别是,在我们的实验中,通过我们的改进消除的假阳性的数量是在A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)57范围为警告总数的65%至81%。本文的组织如下:第2节包含了一个概述的运行时方法在多线程程序中的故障检测,并提出了运行时检测在Helgrind实现更详细。在第3节中,我们提出了我们的源代码注释的方法,以使运行时分析更准确,并描述了一般的实验环境。第4节是我们实验的结果。最后,第5节总结了我们的结果的一般性讨论的文件。2故障检测在本节中,我们首先给出并发程序特有的错误的一些定义。然后,运行时的方法来检测这些故障的概述。其次是一个更详细的描述,在免费提供的工具Helgrind,这是作为我们的实验的基础上实现的算法。2.1定义并发程序特有的故障是数据竞争和死锁。死锁定义为一种状态,其中两个或多个线程的集合中的每个线程都试图获取集合中其他线程之一已经持有的锁。因此,线程以循环的方式彼此阻塞当两个或多个并发线程访问未被适当的同步构造保护的共享监视器),并且其中至少一个修改所访问的组件的内容这个定义有点限制性,实际上描述了Eraser算法强制执行的锁定策略。这个定义的弱点在于,即使对共享位置的每一次访问都受到适当同步的保护,程序也可能达到不一致的状态。在下面的示例中,这一点将变得更加清晰:假设,我们有一个包含两个元素的数据结构:让我们说一个任意人的出生日期和年龄。这两个变量相互依赖,因为可以通过计算从出生日期到现在的时间来计算人的当前年龄。此外,还有一个同步对象保护对数据的访问。有两个setter方法,一个设置出生日期,另一个设置年龄。现在,当更新结构时,我们首先写入新的出生日期,然后调用设置新的年龄值。 这两种方法都使用同步来保护它们的字段访问。因此,对共享位置的每一次访问都受到同步保护的规则得到了满足。然而,在相互依赖的两个写访问之间可能达到不一致的状态,因为锁在其间被释放。即使对数据结构的每一次访问都受到锁的保护,也有可能达到数据的不一致状态。在[1]中,这被称为高级别数据竞赛,因为数据竞赛的概念似乎并不强大8A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5在其他作品[4,15]中,这个问题是通过原子性的定义来解决的。和原子性侵犯。虽然锁定策略通常不会导致实际故障,但它本身会对应用程序的性能产生影响。在最坏的情况下,所有数据都受到保护一个(全局)锁,导致不必要的阻塞独立线程。一般来说,所有线程对全局资源的大量使用会降低性能,并大大降低多处理器系统的速度。2.2动态方法大多数动态方法都基于锁集算法Eraser或LamportEraser[14]中实现的算法试图通过维护一个包含每次访问时活动的所有锁的锁集来识别保护共享位置的锁。因此,它能够检测对锁定规则的违反,该规则要求每个共享位置在每次访问时都由相同的锁(或锁集)保护。DJIT算法[6]是为检测DSM系统毫页中的数据竞争而开发的一种方法。它利用向量时间帧和访问日志来检查对共享位置的并发访问之间的happens-before关系。它依赖于一个底层连贯系统的假设,只检测第一个明显的数据竞争。锁集算法的主要优点是能够检测执行路径上存在的所有可能的数据竞争。另一方面,它有时会给出太多的错误检测。DJIT试图只定位明显的数据竞争。 因此,它检测锁集方法报告的共享位置子集上的数据竞争,并错过一些真正的数据竞争。 因此,Multi-Race [13]试图通过将锁集和DJIT的增强版本组合到一个公共框架中来提高数据竞争检测能力。在[12]中,作者将基于锁集的数据竞争检测器与基于向量时钟的Java同步原语的happens-before关系检查相结合。这些原语上的动作被看作是对它们之间的内存访问施加顺序的事件。不幸的是,他们的假设,即非同步存储器写入成为可见的因果顺序是真的,在所有SMP系统,也不是信号和等待操作之间的关系的条件强到足以施加假定的顺序。在线技术的一个主要缺点是,它们会显著减慢应用程序的执行速度。因此,它们的使用需要适应环境以支持较慢的反应。原则上,在线检查器可以在事后工作,从而减少由于在线计算而造成的性能影响。但是它们仍然需要记录执行跟踪。因此,在线技术支持它们对大量数据的需求尽管如此,on-the-checker可以很好地随程序大小扩展。它们并不完整,因为只发现了执行路径上的错误,但已在A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)59工业软件开发。一个实现是免费提供的工具Helgrind。我们使用它作为我们实验的基础,底层算法在下面的部分中描述。2.3运行时分析2.3.1黑尔格林Helgrind是一个Valgrind工具[10,9],用于检测C和C++程序中的数据竞争。它使用Eraser算法[14]和Visual Threads [5]的改进,以减少误报的报告。Valgrind是Linux ELF二进制文件的二进制插装框架,最初用作内存检查器。 从版本2开始,应用程序被划分为一个核心,它从可执行的二进制文件生成中间代码,并使用即时编译来解释代码以提高速度,以及一个皮肤或工具,它在执行之前对中间代码进行检测并解释结果。这使得Valgrind成为一个强大而灵活的工具,用于各种运行时检查。为了在检查器的后续运行中抑制错误报告,可以编写所谓的抑制文件,其中包含误报位置的报告类型和调用堆栈模式或不可修改的代码部分(e.g.、第三方图书馆)。2.3.2基本算法(橡皮擦)Eraser [14]是一种算法,它检查给定程序对共享内存位置的每次访问是否受到适当同步的保护。在这个实现中,它只适用于使用POSIX线程库的程序,因为对该库的调用被拦截,以跟踪内存和线程系统的状态。的 基本 同步 对象 在 POSIX线程 是 一 互斥量exclusion),以及获取(锁定)和释放(解锁)它的方法只有一个线程可以在任何给定时间保持锁。所有其他试图锁定它的线程都会被阻塞,直到互斥体再次被释放。为了避免注释的需要,Eraser算法尝试推断保护共享内存位置的互斥体,如果该位置未受保护,则发出警告。为每个共享内存位置维护一个锁集,该锁集包含在对共享内存位置的所有访问期间持有的锁集的交集。伪代码中的基本算法设locks holded(t)是线程t持有的锁的集合。对于每个v,将C(v)初始化为所有锁的集合%%REVIEWER:For each v−> For each variable v在线程t每次访问v时,设置C(v):=C(v)锁定保持(t);如果C(v)={},则发出警告。这应该找到所有可能的数据竞争,但会导致太多的误报。10A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5Fig. 1. 状态来表示内存位置。 在分配之后,它以状态NEW开始。在初始化期间,它由分配线程独占,直到另一个线程读取或写入位置。然后,达到SHARED状态之一,并初始化锁集以进行一致性检查。然而,竞争条件仅在SHARED-MODIFIED状态下报告。一个主要的缺点是初始化和读共享数据没有得到正确的处理。对于某些共享变量来说,锁是不需要的,因为这些共享变量只被一个线程初始化一次,随后只被其他线程读取因此,在Eraser算法中引入了状态,使其能够处理这些情况(参见。图1)。只要只有一个线程使用内存位置,锁集就不会初始化。当另一个线程访问内存位置时,锁集被初始化为所有活动锁,并且算法报告导致空锁集的下一个写访问。现在,一个分配内存位置的线程拥有它,直到另一个线程访问同一个内存位置。因此,分配线程可以初始化共享变量,然后将其与其他线程共享以仅用于读取,而不会导致竞争检测器的警告存在这样的情况,其中算法现在是不完整的,因为它依赖于实际交织。当另一个线程在共享内存初始化完成之前进行第一次读访问时,就会发生数据竞争。它不会被算法检测到,因为在观察到的交错中,所有写入都发生在第一次(共享)读取访问之前。根据作者的说法,这个缺点是通过减少修改后的算法报告的误报量来克服的。用不同的测试数据进行重复测试(导致不同的交织)可以帮助发现这样的数据竞争,如果它们存在的话。在原始的Eraser al-出租中提出的读写锁的扩展在Helgrind中没有实现。尽管在某些情况下会很有用。当变量进入Shared-Modified状态时,检查如下:设locks holded(t)是线程t在任何模式下持有的锁的集合。设写锁持有(t)是线程t在写模式下持有的锁的集合。对于每个v,将C(v)初始化为所有锁的集合。在线程t每次读取v时,设置C(v):=C(v)锁定保持(t);如果C(v)={},则发出警告。在线程t每次写入v时,setC(v):=C(v)是否保持写锁(t);A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)511线索1:线索二:线索三:图二.线程由线程段组成,这些线程段由线程创建和连接操作分隔。仅限于非重叠线程段的内存访问即使不是由单个线程完成,也仍然是独占的。如果C(v)={},则发出警告。螺纹段另一个导致警告的典型场景如下:一个线程分配内存,通过将其设置为有用的东西来分配内存,并启动第二个线程,该线程应该处理数据。一段时间后,第一个线程等待第二个线程完成,然后再次使用内存因此,内存在线程之间共享,但在任何时候只有一个线程访问它。所有权传递给第二个线程,直到它终止。VisualThreads([5])使用该观察结果,通过引入线程段(参见图2)。一个线程不再是一个处于EXCLUSIVE状态的共享变量的所有者,而是一个拥有它的线程段。然后,每当另一个线程访问内存时,都会检查线程段是否重叠。如果不是,新的线程段将成为新的所有者,而不是变量切换到SHARED状态。对Eraser算法的修改:(i) 当数据d被标记为EXCLUSIVE时,将其与当前线程的线程段id相关联,而不是与线程id相关联。(ii) 如果数据d被标记为对线程段TSi是独占的,并且正在被TSj触及,并且TSi在图中发生在TSj,则不是将数据移动到共享状态之一,而是将d与TSj相关联。国家仍然是排他性的。3改进和实验在Helgrind的早期实验之后,我们发现了两个有助于减少误报数量的改进。3.1改进首先,我们纠正了Helgrind中硬件总线锁的实现它是通过使用一个特殊的互斥锁来实现的,这个互斥锁在每次显式调用预编译器时都被锁定。根据Intel的i386规范,读操作不需要使用预处理器。只需要写。一个正确的工具-加入创建加入创建TS2TS1TS4TS3TS2TS1TS112A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5二进制图三. 调试过程的数据流。 对全部或部分源代码进行分析和检测。生成的二进制文件在VM Valgrind上执行,并带有数据竞争检测。这更像是一个读写锁。这需要在Helgrind中实现读写锁。该工具的修改版本在内部支持rw-locks。作为一个好处,可以轻松添加对相应POSIX API的支持Helgrind能够在不需要源代码的情况下工作。因此,检测过程独立于编程语言。不幸的是,许多分析的警告都是由C++特定代码引起的。当一个对象的析构函数被调用时,它的父类的每一个析构函数都会在实际释放与该对象相关的内存之前被调用。超类的析构函数应该只能看到它的类的属性,因此必须改变环境以反映属性和虚方法指针的变化。这种改变是通过写入对象内存中的一个位置来完成的由于多态对象销毁代码导致的误报数量相当大,并且手工识别它们的工作量太大,因此有必要自动抑制它们。这是通过在程序的源代码中注释每个删除操作来完成的,以便将用于竞争检测的删除内存标记为由运行线程独占。这样,在销毁期间其他线程的访问仍然被检测到。源代码不可用的程序部分将不会从该注释中受益,因此仍然会导致误报。不过,虚报总数有所减少。该方法不需要对整个程序进行分析,并且易于集成到构建过程中。注释可以被插入到生产代码中,因为在正常程序执行下,对Helgrind的用户空间调用是一个空操作,执行时间可以忽略不计。注释是即时完成的,并且很容易从构建过程中删除,因为源代码不会被注释工具或程序员修改下一节将更详细地介绍整个过程。3.2调试过程当使用原始Helgrind算法检查程序时,不需要以特殊的方式编译源代码。为方便起见,需要符号信息。如果没有调试符号,Helgrind就无法打印源代码行信息或调用堆栈上疑似故障位置的函数名。要检查程序的错误,可以使用Helgrind在未修改的情况下运行。程序-注释源代码Sourceinstrumentation编译结果执行(VM)A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)513/原始源代码/voidg( charg){删除p;}/#includevalgrind/helgrind.h>namespace{模板类Type>inlineType删除器(Type删除对象){VALGRIND HG DESCRIPCT(object,sizeof(Type));返回对象;}}voidg( charg){deleteca deletor single(p);}见图4。注释的一个例子。操作符delete的参数通过一个函数传递,该函数向竞争检测器宣布内存被销毁。宏VALGRIND HG DESIGNCT扩展为一系列助记符,在正常执行下不做任何事情,但被Helgrind的解释器识别为特殊的函数调用。解释结果的第二步是必要的。改进Helgrind所需的仪器需要额外的第一步。如后所示,插装可以在构建过程中完成,而无需对源代码进行可见的修改,更重要的是,无需用户交互,从而保持调试技术的易用性在向过程添加自动源代码注释之后,修改后的调试过程由三个部分组成(参见见图3)。仪表所有可用的源代码都可以被检测,以帮助减少运行时分析的错误目前,只有delete操作符被注释为将被析构的对象的内存标记为独占的、已销毁的。有关插装代码的示例,请参见图4,但请注意,它是以实际流程中不存在的状态呈现的,因为为了清楚起见,省略了预处理。运行时分析不需要源代码插装,但是插装的结果更好。执行该程序在虚拟机上使用来自自动化测试套件的测试数据执行。运行时分析是基于工具Helgrind。结果写入日志文件。分析日志文件由用户分析,以验证报告的可能数据竞争是否实际上是数据竞争,如果是,则对程序进行更正。14A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)53.3SIP代理服务器的设置与环境所有实验都是在Linux x86系统上进行的。 被测应用程序是一个用于会话发起协议(SIP)的信令服务器应用程序,用于IP语音(VoIP)电话网络,并利用POSIX线程进行多线程和同步原语。使用的并发模式是“每请求一个线程”,即,为每个请求创建一个新线程。这非常适合VisualThreads的线程段改进,因为所有权是通过线程创建传递给工作线程的。虽然同步已经通过锁完成,但是有必要检查应用程序的数据竞争和死锁,因为它在多线程运行时显示该应用程序是由数百kbps的C++代码构建的,因此仅作为概念验证编写的实验工具不适用。此外,对C++语言构造的使用没有限制,排除了许多依赖于仅使用C++语言的子集(例如,保持解析器简单)。仪表对于插装,使用C++解析器ELSA。 ELSA基于Elkhound,一个GLR-Parser生成器[8]。ELSA构建了一个抽象语法树,用于源代码分析和注释。解析器的输入必须经过预处理,因为解析器不读取外部文件,而且解析器要求所有信息都包含在源文件中。因此,插装和编译过程有三个阶段。首先,使用GNU编译器对源文件进行预处理。然后解析器读取预处理的源文件并生成带注释的源文件。在第三步也是最后一步,编译器从带注释的源文件生成目标代码这可以在构建过程中替换编译器调用的shell脚本中完成,从而使检测对构建工具和程序员透明。由于插装只向VM添加用户空间调用,这些调用在正常执行下除了一个小延迟外没有任何影响,因此它可以在每个构建过程中完成。缺点是由于额外的第二阶段(仪器)而增加了构建时间。试验台带有数据竞争检测的测试需要一个测试环境,最好是一个自动化测试套件,以保证测试运行的可靠可重复性。困难在于测试中程序的不同计时行为,因为在虚拟机上执行会使其减慢20-30倍。因此,在某些情况下,超时必须适应变化的响应时间。此外,Vir-A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)51570060050040030020010000 1 2 3 4 5 6 7 8Testcase图五.调试过程的结果。八个简单的测试用例,使用不同的竞争检查器配置运行。条形图的两个上部表示误报,较小的(顶部)部分表示由于错误解释硬件总线锁而引起的警告,较大的部分表示由于访问对象的析构函数而引起的警告。实际机器本身是单线程的。因此,增加更多的处理器也无济于事。在我们的环境中,用于SIP代理服务器上实验的11个测试用例中有8个没有更改。基本的请求模式由自动化测试套件交付给应用程序。这个测试套件的主要工具是SIPp,一个SIP负载测试工具。对于数据竞争,使用在线检查器(Helgrind)。互斥锁上的死锁是由应用程序在试图获取锁函数内的锁时使用超时来检测的。由于竞争检查器也进行死锁检测,因此不需要应用程序级检测。4结果包含8个测试用例的测试套件在三种不同的配置下运行。在用原始的Helgrind运行它之后,记录了报告的可能的数据竞争的数量。在检查单个警告之后,很明显,大多数警告都是误报,这是由于硬件总线锁语义的错误实现和销毁时对象的自动修改造成的下文对这两种情况作了解释第二次运行是用硬件总线锁(HWLC)的正确实现完成的,其中许多警告消失了。此运行不需要源代码插装。在第三次运行(HWLCD+DR)中,源代码被注释为在调用析构函数之前标记在所有情况下,这进一步减少了报告的可能数据竞争量的一半以上(图6)。尽管如此,报告的数据竞争的数量仍然很大,其中大多数是真正的同步失败,但有些故障形成了源于同一起源的组。 这意味着,在修复后重新编译测试套件通常是一个好主意。麻烦了然后,与已纠正缺陷相关的所有警告将消失,误报(硬件锁)误报(析构函数)正确报告数据争用报告的位置16A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5测试用例原始HWLCHWLC+DRT1483448120T231921560T325219449T4576490149T5631547146T6620604181T7327269115T835727078见图6。调试过程的结果。这些数字是在不同配置下报告的“可能的数据竞争位置”的数量。首先,使用最初在Helgrind中实现的算法。其次,对Helgrind中硬件总线锁的仿真进行了修正。最后一列包含在对删除操作附加应用源代码注释之后的结果。不必再考虑。此外,可能由校正引入的故障产生新的警告。在使用Helgrind和GNU C++标准库时出现的一个问题是错误报告,这是由于标准容器对象中的内存分配策略。内存在内部被重用,对重用内存区域的访问被报告为数据竞争,即使访问通过释放和分配分开,因为Helgrind对它们一无所知幸运的是,GNU标准C++库的分配策略是可以用环境变量配置的,这必须在调用Helgrind之前完成4.1真阳性在我们的实验中,我们在分析的程序中发现了一些真正的bug。由于应用程序有大约500 kbps,因此并不总是容易确定报告的警告是真正的缺陷,错误的警告还是只是良性的竞争。尽管如此,我们还是在程序中发现了很多真正的缺陷--这里列出了一些似乎很常见的错误。最早报告的数据竞争之一是应用程序的死锁检测代码。不幸的是,为了删除竞态条件,这段代码并不容易修改。因此,将其禁用以进行进一步实验。4.1.1终止和终止顺序问题另一个发现的错误是初始化顺序的问题,即,线程在其使用的部分数据结构被初始化之前启动。此错误不是由工具直接发现的,而是由于在使用检测运行程序时的不同时间表而发生的。在“通常”的环境中A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)517mapstring,DomainDatan>ServerModulesManagerImpl::getDomainData(){MutexPtr mut(m pMutex);//Guardreturnm;}图7.第一次会议。由于返回引用,属性不受保护在程序关闭时,另一个数据竞争发生了,因为一个数据结构在使用它的线程终止之前就被破坏了4.1.2同步问题简单的锁定有时会导致未注意到的bug(图7)。 快速浏览源代码可以让程序员放心,一切都很好。但是,即使在类的所有方法中都持有锁,也存在没有适当同步的数据访问。例如,一个方法返回对属性的引用而不是其内容。在测试程序中发现的情况下,属性是一个map,因此它的使用应该受到锁的保护。这个错误需要重写函数和所有使用它的函数,因为返回对内部数据结构的引用会阻止适当的为了改变这一点,函数的签名会改变,对函数的所有调用也会改变。4.1.3系统功能使用不当在多线程环境中,某些系统函数的使用是不安全的。特别是,所有使用静态数据的函数,或者更糟的是,返回指向静态数据的指针的函数都不是线程安全的。在应用程序中使用这些函数中的一些可能导致工具报告的数据竞争glib-c手册页上的注释承认了这一点:localtime()返回指向静态数据的指针,因此不是线程安全的4.2假阳性三种假阳性占主导地位的结果。这里描述的前两种类型已经通过我们的改进解决了,而其他类型仍然存在。4.2.1派生类的析构函数Helgrind在一些类的析构函数中报告了一个锁定策略违规。这些析构函数主要是由编译器生成的默认析构函数,但重要的共同属性是它们都属于派生类。当一个对象的析构函数被调用时,它的父类的每一个析构函数都会在实际释放与该对象相关的内存之前被调用。超类的析构函数应该只能看到它的类的属性。因此,必须改变环境以反映属性和虚方法指针的这种变化。这种改变是通过写入对象内存中的某个位置来完成的。如果内存处于共享18A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)51/! 阿菲莱stringtest.cpp2\brief测试std::string −对象的共享读访问。3米/45#包含字符串6#includepthread.h>78voidfunctional.js(voidfunctional.js)9{10std::string text =std(std:: stringstring)arguments;11return0;12个文件夹1314int main(){1}16std::stringtext(18pthread t thread id;19pthread create(thread id,0,workerThread,text); 2021睡眠(1);22std::string text copy = text;//−reported constriction2324intcount=0;25pthread join(thread id,result);返回0; 28个文件夹见图8。std::string类型的共享对象的示例。字符串通常使用引用计数来实现。因此,当复制字符串对象时,有时需要通过添加新引用来修改源对象。==19670==在0x1D6F9168==19670== at 0x1D548451:std::string::Rep::M grab(std::allocatorchar>const&,std::allocatorchar>const&)(在/usr/lib/gcc−lib/i686−pc−linux−gnu/3.3.2/libstdc++.so.5.0.5中)==19670== by 0x1D548517:std::string::string(std::stringconst)(in/usr/lib/gcc−lib/i686−pc−linux−gnu/3.3.2/libstdc++.so.5.0.5)==19670== by 0x804879F:main(stringtest.cpp:22)==19670==Address0x1D6F9168is8bytesinsideablockofsize21aloc==19670== at 0x1D4A8433:operator new(unsigned)(vg replace malloc.c:133)==19670== by 0x1D545A98:std::default alloc templatetrue,0>::allocate(unsigned)(在/usr/lib/gcc−lib/i686−pc−linux−gnu/3.3.2/libstdc++.so.5.0.5中)==19670== by 0x1D54B3F7:std::string::Rep::S create(unsigned,std::allocatorchar>const)(在/usr/lib/gcc−lib/ i686−pc−linux−gnu/3.3.2/libstdc++.so.5.0.5中)==19670== by 0x1D54C13E:(within/usr/lib/gcc−lib/i686−pc−linux−gnu/3.3.2/libstdc++.so.5.0.5)==19670==前一状态:共享RO,无锁见图9。Helgrind发出的警告示例。 警告的来源在GNU标准C++库中,方法mgrab()添加了一个对字符串对象的引用。状态然而,当线程删除对象时,线程应该是对象的唯一所有者。因此,数据竞争检查器可以将其内存的状态设置为独占。这在以下假设下成立:在调用delete并因此调用其析构函数之后不访问数据。这个假设的实际违反是由普通的内存检查工具检测到的,这些工具能够检测对已释放内存块的访问。因此,它不是多线程程序的特殊情况,在数据竞争检测过程中可以忽略。4.2.2硬件总线锁在这个简单的例子中(图8),Helgrind在第22行的分配中报告了一个可能的数据竞争。报告是由对引用计数器的共享访问引起的该操作由硬件总线锁保护,但在此写入之前的读取访问不使用锁,因此锁集为空。在第一次发生写入之前不初始化锁集的技术在这里没有帮助,因为已经存在对该存储器位置的写入。A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)519图10个。在每请求一线程模式中,对消息数据的访问由线程创建和- 加入行动。该算法通过比较线程段来推断访问仍然是独占的(每个线程段)。工作线程:创建等主题:Create设置数据邮政见图11。在使用线程池的模式中,对消息数据的访问由消息put和get操作分隔。(post-wait)Helgrind使用的算法没有考虑到访问仍然是独占的。线程(WorkerThread)检测算法不考虑操作是原子的。引用计数器的读写操作是原子的,因为它是一个整数值,所有的写操作都受到总线锁定前缀的保护。不可能从简单的观察中得出这一点,因为引用计数器是包含数据的结构的一部分。如果Helgrind支持读写锁,那么硬件总线锁可以被模拟为读写锁,在每次读访问时都保持读取,并在使用锁前缀时锁定这将更准确地模拟总线锁的行为,并删除string类中的虚假警告如前所述,我们成功地实施了这一纠正4.2.3所有权转移应用程序中使用的方法是为每个请求生成一个新线程。当任何时候未完成的请求数量超过并行运行的线程的最大允许数量时,应用程序将失败。高性能服务器应用程序必须处理许多并行请求,通常将所有传入的请求放入队列中,同时有固定数量的线程(即线程池)从队列中获取数据进行处理。这也避免了为每个请求创建和销毁线程的开销。因此,对于被测应用程序,计划利用以某种方式使用线程池的模式。这导致竞争检测算法将报告更多误报的问题。在每请求一个线程的模式中,对传递给工作线程的数据的访问图10)。当使用线程池时,情况发生了变化。线程创建是在数据初始化并传递给工作线程之前完成的,因此需要进行数据争用检测处理数据20A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)5算法在首次写入此数据时报告警告。访问被消息队列上的put和get操作清楚地分开,但是算法没有检测到这一点(参见。图11)。4.3假阴性在Eraser算法中引入状态与延迟锁定设置记录相结合降低了算法的检测能力。它最大的优点之一是能够独立于执行顺序报告数据竞争。假设,一个线程写共享位置而没有获得锁,而另一个线程做同样的事情,但碰巧在访问期间持有锁。如果第一次访问发生在第二次访问之前,则不会报告警告,因为锁集初始化延迟到第二个线程的访问,访问锁被保持。如果不同的调度导致另一个执行顺序,则发现并报告(可能的)数据争用。但这并不能保证在开发环境中发生,并且可能在将软件交付给客户后导致失败。事实上,在实验过程中,在源代码中发现了此类情况,并且测试过程没有报告这表明,它应该将在算法的未来增强中得到解决。4.4总结我们遇到的算法问题(假阳性和假阴性)分为三类:• C++实现特定问题(析构函数)。这是通过源代码分析解决的。• 硬件相关解释(CPU锁定前缀)。在纠正硬件总线锁的实现后,这也得到了修复。• 没有考虑高级同步原语所施加的执行顺序(误报),或者错误地认为它是有保证的(误报)。基于低级结构的高级同步是一个需要进一步改进的领域4.5性能与静态方法不同,动态分析可以很好地扩展大型程序。程序的长度并不是很重要,因为空间和时间复杂性的主要参数是执行轨迹的长度。一般来说,大多数运行时技术可以在线或非在线执行。两者各有优势。即时分析通常对被分析程序的执行速度有显著的负面影响。业务流程分析需要记录信息,这可能会导致大量内存使用。一方面,A. Mühlenfeld,F.理论计算机科学电子笔记174(2007)521当否则必须记录的信息量很大时,技术是优选的。另一方面,当运行时分析会使程序变慢而变得无用时,日志记录和运行时分析是必要的。在我们的例子中,对内存位置的每次访问都必须被记录下来,对于长的执行跟踪,线程分析几乎是不可能的。因此,分析所消耗的时间直接降低了被观察程序的执行速度此外,由于Valgrind在虚拟机上执行二进制文件,即使没有插装程序执行也很慢。使用所提出的算法进行分析的程序的执行比不使用Helgrind运行时慢20-30倍。当将这个数字与其他作品进行比较时,其中所报告的Eraser类算法的减速约为2-3(甚至更少),必须考虑到这些结果是在程序总是在虚拟机上执行的环境中获得的,如Java VM(如[2,12])或Microsoft如果在Valgrind上运行,程序在没有检测的情况下会减慢8-10倍。因此,我们的结果是可比的,以前的作品。5结论目前,存在许多即时竞争检测算法的实现不幸的是,大多数学术概念验证实现并不适用于现实世界的应用程序。至少,需要处理C++的一个以上的子集是一个淘汰标准,因为据我们所知,没有一个解析器可以免费获得,能够为完整的ISO C++语言生成抽象语法树此外,对于工具中的具体实现,附加标准决定它是否有用通常,程序员不愿意花太多时间调整参数或分析工具输出。为了最有用,一个工具不应该要求用户是一个学者。因此,分析过程必须易于设置,并且结果应该包含非常少的错误警告。一个很好的例子是开源的内存检查器Valgrind,由于其易用性和输出的有用性,它被不同环境中的我们使用免费工具Helgrind(它是Val-grind的一部分)进行的实验表明,它是一个很好的研究基础,但会生成太多错误的警告,无法在生产环境中使用我们分析了该工具为大型商业服务器应用程序生成的数百结果包含许多误报,但我们也发现了真正的bug。在此基础上对算法进行了改进,并分析了改进后的结果
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功