（计算机软件与理论专业论文）基于重放的并发程序调试技术研究.pdf

摘要 随着并发程序日益广泛的使用，并发程序的调试也变得越发的重要。传统的循环调试技术主 要是设置断点，多次执行源程序，逐步定位错误位置。因为顺序程序的执行结果主要取决于程序 的输入，所以这种方法对于顺序程序十分有效，但是对于并发程序，问题要复杂得多。 首先，并发程序的并发性和不确定性，导致了对于一个给定的并发程序，即使在相同的输入 下，也可能产生不同的结果，或者是结果相同，但是执行的路径不同。正确发现和纠正错误的前 提是能够不断地让同样的错误重复出现，然而在并发程序调试时，可能无法得到错误信息，或者 观察到了错误，再次运行时却无法得到上次的错误状态。这就迫切需要有一种机制，使得在调试 时能够确定性地执行程序。其次，并发程序一般都含有多个进程，它们之间存在着复杂的通信和 同步，因此在调试时程序员希望对并发程序的执行流程和进程间的通信有一个整体的把握，然而 人工查阅代码获得进程问的通信关系几乎是不可能的。这将使得程序员难于分析和理解并发程序， 调试时必须在多个进程问频繁地切换和盲目地跟踪，调试效率将大大降低。这就有必要给程序员 提供进程问的通信关系。 基于上述问题，我们研究和开发了并发程序分析和调试工具，其中包括基于重放的并发程序 调试工具和进程间通信关系提取和描述工具。该工具基于用c 语言编写的进程间以消息队列和共 享内存为通信机制的并发程序。基于重放的并发程序调试工具追踪并发程序执行，以便在重放的 基础上调试并发程序；通信关系提取和描述工具用于自动提取源代码中可能的通信关系和本次执 行时实际的通信关系，并将关系以图形的方式显示给用户。 关键字： 并发程序并发调试进程消息队列通信追踪重放 a b s t r a c t w i t ht h ew i d eu s eo fc o n c u r r e n tp r o g r a m s ，i ti sm o r ea n dm o r ei m p o r t a n tf o rd e b u g g i n go ft h e m t h em e t h o do ft r a d i t i o n a lc y c l i cd e b u g g i n gi st os e tb r e a k p o i n t s ，l o o ku pt h es t a t e so fb r e a k p o i n t s ，a n d e x e c u t et h es o u r c em u l t i p l et i m e s b e c a u s et h er e s u l t so fe x e c u t i o na t ed e t e r m i n e db yt h ei n p u t ，t h i s m e t h o di se f f i c i e n tf o rs e q u e n tp r o g r a m s b u ti td o e sn o tw o r kw e l lf o rc o n c u r r e n tp r o g r a m s f i r s t l y ，c o n c u r r e n tp r o g r a m s c o n c u r r e n c ya n dd e t e r m i n i s mr e s u l tt h a te v e nw i t ht h es a m ei n p u ti t w i l lg e td i f f e r e n tr e s u l t so rd i f f e r e n te x e c u t i o np a t h sw h e ne x e c u t i n gt h ep r o g r a m s m a k i n gt h ee r r o r o c c u rr e p e a t e d l yi st h ep r e c o n d i t i o no fd e t e c t i n ga n dc o r r e c t i n gt h ee r r o r s ，b u ti ft r a d i t i o n a l c y c l i c d e b u g g i n gm e t h o di su s e do ni t ，t h ee r r o rs t a t e sm a yn o to c c u rs ow en e e dam e c h a n i s mt of o r c et h e p r o g r a m st oe x e c u t ed e t e r m i n i s t i c l y s e e o n d ly ，p r o g r a m m e r sw a n tt oh a v eag e n e r a li d e aa b o u tt h e i n t e r a c t i o no fc o n c u r r e n tp r o c e s s e s ；b u ti ti s i m p o s s i b l et oe x t r a c tt h ec o m m u n i c a t i o nr e l a t i o n s h i po f c o n c u r r e n tp r o c e s s e sb ym a n u a lr e a d i n gs o u r c ew i t h o u tt h eg e n e r a li d e aa b o u tt h ei n t e r a c t i o n ， p r o g r a m m e r sa n a l y z ea n dc o m p r e h e n dt h ep r o g r a m sd i f f i c u l t l yd u et os w i t c h i n ga m o n gp r o c e s s e sa n d t h e ya r el i k e l yt og e ti n t oam e s s i no r d e rt oi m p r o v et h ed e b u g g i n ge f f i c i e n c y ，w ee x t r a c tt h e c o m m u n i c a t i o na m o n gp r o c e s s e sa n dv i s u a l i z ei tt op r o g r a m m e r s f o rt h er e a s o n ss t a t e da b o v e ，w eh a v er e s e a r c h e da n dd e v e l o p e da n a n a l y s i sa n dd e b u g g i n gt o o l f o rc o n c u r r e n tp r o g r a m s ，w h i c hc o n s i s t so fc o n c u r r e n tp r o g r a m sd e b u g g i n gt o o lb a s e do nr e p l a ya n d c o m m u n i c a t i o nr e l a t i o n s h i pe x t r a c t i o nt 0 0 1 t h i st o o li su s e dt o a n a l y z ea n dd e b u gc o n c u r r e n t p r o g r a m sw h i c ha r e w r i t t e ni nca n du s em e s s a g eq u e u e sa n ds h a r e m e m o r ya sc o m m u n i c a t i o n m e c h a n i s m k e y w o r d s ：c o n c u r r e n tp r o g r a m ，s o f t w a r ed e b u g ，p r o c e s s ，m e s s a g eq u e u e ，i n t e r - p r o c e s sc o m m u n i c a t i o n t r a c ea n dr e p l a y 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：蓐出斌巡日期：碰址乞l 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院 签名：声痢峪蚌导师签名： 东南大学硕士学位论文 第一章引言 1 1 选题依据 并发程序将功能交由多个进程麸同协作完成，因而与顺序程序相比具有高效性，得到了广泛的应用。 但是，并发技术的广泛使用在提高系统性能的同时也给系统的测试与维护带来了困难：首先，并发程序 执行的不确定性使传统的顺序程序的调试方法不再可用；其次，进程间复杂的同步和通信的存在影响了 程序员对于并发程序的分析和调试。因此，有必要建立一种机制来辅助并发程序的调试，使得程序员熟 悉的传统循环调试的思想继续有效。 1 2 基于重放的程序调试的目的和意义 虽然并发技术得到了大量应用，在日常生活及生产中发挥了越来越重要的作用，但是并发执行本 身的并发、不确定等特性却给并发程序的后期调试和维护带来了极大的困难。维护人员难于理解并发程 序所表现的内在逻辑和程序流程难于使用传统的循环调试方法去发现和纠正错误。 在调试和测试顺序程序的时候，程序员一般采取循环调试的方法。使用循环调试的前提是待调试对 象在给定输入后，执行路径必须是确定的：顺序程序的执行正好符合此条件，所以循环调试对于顺序程 序十分有效，但是对于并发程序，问题要复杂得多。并发由于自身特有的性质导致了并发程序执行具有 不确定性，即在相同的输入下，程序每次正常执行的结果可能不同，或者结果相同，但是内部的执行路 径不相同。这种不确定性直接导致了错误的不可再现性：如果程序的某次调试运行出现了一个错误， 在程序的后续多次运行中由于不同的执行路径，这个错误可能不再出现。因此并发程序执行的结果不仅 取决于程序的输入，还取决于该次执行的同步操作序列“。如果这个错误出现的几率很小，那么程序 员可能始终无法发现引起这个错误的原因，导致了多次无谓的跟踪和执行，浪费了大量的人力和资源。 为了能够继续使用循环调试的方法调试并发程序，必须能够使并发程序的执行确定化。我们采用的 方法分为两个阶段”j ：第一个阶段是记录阶段，记录并发程序的原始运行并且记录必要的执行信息； 第二个阶段是重放阶段，在保证输入给程序的信息与追踪阶段相同的前提下，根据记录阶段记录的信息 控制程序的执行，熏现原始的执行状态。在能够重现并发程序的某次执行的条件下，循环调试方法将可 以用于并发程序的调试，从而降低并发程序测试和调试的难度。 基于以上提出的追踪重放并发程序执行的必要性和可行性，我们研制和开发了基于重放的并发程序 调试工具，该工具用于对l i n u x 下编写的以消息队列和共享内存为进程间通信中介的并发程序的调试。 1 3 通信关系提取的目的和意义 调试过程中，测试人员希望对程序的执行有个总体的把握，既可以感知程序执行的控制流和数据 流，否则由于埋头于源代码级的调试，对于多个并发实体之间相互作用，调试人员疲于思维上的切换 易陷入迷茫状态；其次，并发程序中有些缺陷是很难利用源代码级的调试直接从程序在某个点的状态中 发现的，例如资源竞争、时序紊乱、死锁之类的与进程问相互作用有关的问题。 并发程序一般包括多个进程，进程间存在着复杂的同步和通信，它们通过协作共同完成程序的功能， 因此，为了更好地理解并发程序的并发行为和内在的逻辑，有必要对进程问的通信关系进行提取和描述。 自动化通信关系提取工具能够将并发程序的通信关系用图形的方法加以显示，所以测试与维护人员不需要 花大量的时间阅读代码就可以了解系统中各个模块之间的通信关系，从而可以降低调试与维护系统的难 度。现今，许多可视化工具被应用于顺序程序的分析和理解，并且取得了很好的效果。但是，大部分可视 化工具并没有考虑并发程序中并发语句执行的不确定情况，因此，很少可视化工具可以被应用于分析和理 解并发程序。迫切需要一种可视化工具能够应用于并发程序的分析和理解，即能够将并发程序的通信结构 以图形的方式显示给程序员，来减轻程序员的负担。 东南大学硕士学位论文 针对并发程序的分析和理解问题，我们研制和开发了通信关系的自动化提取工具。它应用于以c 语 言编写的进程间以消息队列和共享内存为通信中介的并发程序，主要分为两个部分：第一部分静态分析并 发程序，从而得到一个可能的进程间的通信关系；第二部分则是根据当前的执行情况准确的给出进程间的 通信关系并以图形的方式加以显示。 1 4 研究现状 关于并发程序的调试方法，国内外已有研究者做过一些工作。陈振强通过分析并发程序的行为， 构造程序流图、检测同步错误和数据竞争”。7j 。张斌在分析并发程序依赖关系的基础上，提取出任务间的 通信关系，建立并图形化显示通信关系模型【。以上两者均是通过静态分析程序的方法进行测试和调试， 不会引入探针效应，但是该类方法随着程序规模的增大，算法的复杂度较高，而且无法了解程序的执行 细节。b a i a r d i 设计的d e b u g g e rl 9 1 中，编程人员可以通过行为规范描述，预先提供一个e c s p 程序的期望 行为；在执行中，判断运行时的行为是否符合预先提供的行为规范，若不相同，根据不符的类型，执行 相应的预定义动作分析程序执行结果，因此它的主要目标在于程序的验证。j a s o n 提出的c b u g i 川， 它在源代码中植入调试钩子，然后将源代码和调试器编译，一边执行一边调试，然而由于程序执行的不 确定性，单次执行时错误是随机的，所以这种一步式的调试方法效果不是很好。 1 5 论文结构 本文各主要章节内容安排如下： 第一章做为攘个论文的绪论。介绍相关的背景知识，阐述了选题的依据和必要性，在给出研究内容 和方法后，简要地介绍论文结构； 第二章介绍并发程序的有关问题及程序分析技术： 第三章详细讨论了基于重放的并发程序的调试，绘出了一个基本的框架： 第四章详细论述了静态和动态的通信关系的提取方案： 第五章介绍了整个调试平台的系统实现： 第六章是对整个论文研究和实践工作的总结，指出了我们现有工作的局限性和有待提高及改进的方 面，并简要阐述我们正在进行或将要进行的研究工作。 东南大学硕士学位论文 第二章并发的有关问题及程序分析技术 随着用户对软件的性能要求日益提高，越来越多的系统采用了并发设计，但是并发程序的不确定性 给系统的调试和维护带来了困难。本章首先介绍进程的相关知识、进程闻的同步和通信机制，以及并发 程序执行的不确定性原因，最后阐述了程序分折的基本技术。 2 1 进程的基本概念 程序是一个静态的概念，它是一系列指令的集合：进程区别于程序，它是一个动态的概念，是程序 在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程的实质是程序的一 次执行过程。引入进程之后，可以将所需要完成的功能分配到若干个进程中，由多个进程协作完成，因 此，并发程序较顺序程序具有更高的执行效率。 进程是一个抽象实体，是程序一次执行的内存映像。它一般由进程控制块( p c b ) 、正文段和数据段 构成。一个进程只有一个进程控制块，它是进程存在与否的唯一标志，因为操作系统只能依据控制块才 能感知进程、管理进程和控制进程。正文段是可被共享的重入码，而数据段则是存放进程执行时所访问 的数据。进程有三种基本状态：就绪状态，执行状态和阻塞状态。 操作系统一般都提供了创建进程的系统调用( 如l i n u x 提供了f b r k 、e x e e 等) 。在创建进程时，操作 系统赋予进程一个唯一的标识符以及控制块，它记载了该进程的属性，如进程的标识符、现行状态、现 场保留区、优先级等。进程标识符是系统内部用于标识进程的一个整数，它是进程的描述符。一个进程 可以创建若干个子进程，新创建的进程又可以继续创建进程。 2 2 进程间的同步与通信 并发程序一般都含有多个进程，共同协作完成一个复杂的任务。在执行的过程中，进程既要互斥地 访问临界资源，防止出现死锁或饥饿；又要同其它进程交流控制信息和数据信息，完成共同的任务。下 面将分别加以介绍。 2 2 1 同步 异步环境下的一组并发程序，因直接制约而互相合作、互相等待，按照一定的速度执行的过程叫做 进程问的同步。进程间的同步主要有两种基本方式：互斥( m u m a le x c l u s i o n ) 和条件同步( c o n d i t i o n s y n c h r o n i z a t i o n ) 。 进程是申请系统资源的基本单位。但是由于系统资源数量有限，申请可能会导致资源的竞争。如果 竞争失控，要么资源遭到破坏，要么是各个进程形成死锁。操作系统提供了些互斥工具保证相关进程 互斥的进入临界段，从而互斥的访问临界资源。互斥手段主要有硬件级的t s 操作和著名的p v 操作。当 然，锁文件、同步的消息队列和信号等都可以构成进程间的互斥。 条件同步是指一个进程在执行中，如果不满足某个条件，则它将在此条件上等待，直到其它进程改 变了它的状态后，才继续执行。同步的方式有p v 操作、条件临界区和管程。但是前两种方式将同步代 码分散到各个进程中，每个进程要对同步段代码的正确性负责，倘若出错，则整个同步过程将出现紊乱。 管程即是为解决这个问题而产生的，它将分散在各个进程的同步段代码集中起来管理。在管程中，任一 时刻只允许一个进程是活动的，从而实现了进程互斥；条件变量与队列相关联，凡是阻塞在该条件变量 上的进程都列入它的相关队列中，从而实现了条件同步。 2 2 1 通信 进程间的通信方式主要有消息队列、共享内存、远端过程调用、软中断以及共享文件等。 消息队列消息是一个预定义的数据结构，进程为生成的消息指明了消息类型。消息队列是个多 东南大学硕士学位论文 对多的通信机制，消息队列并不是指定为某个特定进程服务：一个或多个进程可以向同一个消息队列发 送消息或者从该消息队列接收消息。消息队列和进程一样是一个抽象实体，在消息队列被创建时，操作 系统为该消息队列分配一个i d 值以及q c b ( q u e u ec o n t r o lb l o c k ) 。q c b 中包括了消息队列名称、消息队 列i d 、等待进程接收消息的策略、消息队列的长度以及消息的最大最小长度等信息。消息队列可以看作 是一个消息结构链表。发送消息的进程使用s e n d 命令把一条消息放入消息队列，等待消息的进程使用 r e c e i v e 命令从消息队列接收消息。 共享内存访问共享的进程数据空间来实现多个进程间的通信称为共享内存。通常由一个进程来 创建或是分配一个共享内存段，一个共享内存建立后可以链接到同一个进程的多个虚地址空间上，而同 一进程也可链接多个芡享内存。共享内存一经创建，在权限允许下，其他的进程即可获得共享内存段的 访问，并将其映射到自己的数据空间中。共享内存使多个进程可以访问同一块内存空间，进程通过写和 读共享的虚空间完成相互通信，因此它是最快的i p c 形式。当然它往往与其它通信机制，如信号量结合 使用，来达到进程间的同步及互斥。 2 3 并发执行的不确定性 并发程序中的不确定性存在两种情况：其一，程序对于相同的输入的不同执行具有不同的结果； 其二，对于相同的输入，程序的不同执行具有相同的结果，但是内部的执行路径不同。以下我们就消 息队列和共享内存这两种通信方式所引起的不确定性分别进行讨论。 2 3 1 消息队列 一般操作系统的消息接收操作主要可以接收三类消息】：一类是接收任何进程投送的消息，二是接 收具有特定标志的消息，三是接收特定进程发送的消息。例如在l i n u x 系统下，消息接收函数m s g r c v 中 有一个参数表明该操作将要接收的消息的类型如果该参数为0 ，则表示可以接收任何进程发来的任何 消息，如果为正数n 则表示只能接收m s g t y p e 为n 的消息，如果为负数( 如n ) ，则表示接收消息标志小 于n 的消息。 我们分析上面提到的三类接收操作。第二类接收操作不是特定的消息不予接收，因此每一次接收操 作接收的消息均是确定的，不会产生不确定性；第三类操作接收特定进程发来的消息，同一进程消息的 发送顺序是由进程的逻辑结构决定的，在相同输入下不会变，因此该类接收操作也不会产生不确定性； 而第一类操作由于接收操作可以接收任何进程发送的任何消息，先来先予以接收，并不判断消息的来源 和类型，因此它是使用消息队列进行通信的并发程序执行的不确定性产生的内部原因。 如图2 1 所示，r e c v l 是第一种类型的消息接收函数，它。 可以接收任何进程发送过来的消息。图中所示的是程序的一种 执行，m s g l 先于m s 9 2 到达进程二对应的消息队列：但是若 m s 9 2 比m s g l 早到达。则程序的执行中，r e c v l 将是接收消息 m s 9 2 ，而m s g l 由顺延的r e c v 2 接收。因此，第一种类型的消 息接收将引起执行的不确定性。 使用消息队列进行通信的并发程序执行的不确定性的产生 除消息接收操作这一内部原因外，还有其产生的外部原因：程序的每次执行，操作系统的调度策略以及 消息传递时的延迟都不尽相同，从而导致了消息到达消息队列的顺序不同【1 2 - 1 4 1 。 2 3 2 共享内存 在共享内存通信方式中，进程间通过访问共享的进程数据空间来实现通信。对于用共享内存进行通 信的并发程序，每个对共享内存区的读操作都应该被看作是输入操作，因为该进程从共享区读取的内容 可能是由另一个进程写入的。如果这个并发程序在单处理器上执行，我们可以认为是进程的调度造成程 序执行的不确定。而当程序在多处理器环境下执行时，主要的不确定性是由竞争条件( r a c ec o n d i t i o n ) 引起的。所谓竞争条件是指对同一个共享地址的两个非同步的访问，至少其中一个访问修改了该共享地 址1 1 5 ”l 。竞争条件可以分为同步竞争( s y n c h r o n i z a t i o nr a c e ) 和数据竞争( d a t ar a c e ) 两类。其中，同步 4 东南大学硕士学位论文 竞争是用来让程序执行具有不确定性，是程序员使用的种手段， 不是程序的错误，而对于数据竞争通常是由程序不正确的同步 引起的，应该被当作错误对待。如果程序中对一个共享变量韵两j = b ； 个操作( 其中至少有一个是写操作) 没有被同步语句隔开，就存 在数据竞争情况。 如图2 2 所示，进程p 】和p 3 均有对共享内存s 的读操作， 而p 2 则是对s 的写操作。图2 2 是程序的一种执行情况，p l 和 p 3 中的读操作先于p 2 中的写操作执行；但是由于这些操作之间 p 1p 2p 3 图22 没有任何同步语句隔开，p 2 的读操作就有可能先于p l 或是p 2 的写操作执行，从而发生数据竞争。 2 4 程序分析技术 程序流图( p f g ) 是一种通用的顺序程序表示方法，它反应了程序中语句、模块之间的执行顺序和 相互调用关系i ”i 。通常我们说的程序流图是函数流图，它描述控制流在函数的各个语句间的流动关系。 定义2 4 1 函数流图表示为一个四元组 ，其中s 为图的节点集，函数中的每条语句 都对应图中的一个节点：边集e = l s l ，s 2 e s 且语句s l 执行后，s 2 可能成为下一条执行语句 s s ； s 。丌v 称为函数的起点或入口，s 。为函数的终点或出口。 程序分析技术主要有控制依赖分析和数据依赖分析。对于并发程序进程间的通信关系的提取来说， 数据依赖分析相对重要，下面我们仅对数据依赖做一个介绍，它包含了函数内和函数间的数据依赖分析。 2 4 1 函数内分析 定义2 4 2 对于函数f 内两个语句s l 与s 2 在s l 中定义了变量v ，s 2 中使用了v ，如果在从s l 到s 2 存在一条路径，在这条路径上的任何一条语句都不再对v 重新定值，那么称s ：数据依赖于s ，。 首先需要讨论一些必要的概念，如定义集、引用集、依赖集、输入集、输出集2 ”。 定义2 4 3 设s 是程序流图中的任一节点，定义语句s 的 ( 1 ) 定义集d e f ( s ) = v iv 是在语句s 中值被定义或者修改的变量 ： ( 2 ) 引用集r e f ( s ) = v iv 是在语句s 中被引用的变量 ： ( 3 ) 输入集i n ( s ) ，所有能到达语句s 入口处的定义的集台，即 i n ( s ) = ( t ，v ) lv e d e f ( t ) 1 j 不存在语句t ，t 位于从t 到s 的某一路径上，使得w d e f ( t ，) ) ； ( 4 ) 输出集o u t ( s ) 所有能到达语句s 出口处的定义的集合，即 o u t ( s ) = ( s 。，x ) i ( s ，x ) i n ( s ) x # d e f i s ) ) u ( s ，x ) ix d e f ( s ) ) 。 沿着程序执行流程由前至后，集合i n 和o u t 记录了各变量定义位置的变化，这两个集合之间存在 如下关系： i n ( s ) = u s t e i r e d ( s ) o u t ( s ) ( 公式2 1 ) 另外，定义集合g e n ( s ) = “s ，v ) iv d e f ( s ) ) ；k i l l ( s ) = ( t ，v ) i ( t ，v ) m n ( s ) v e d e f ( s ) ； 因此我们可以得到对于任意语句s ，有： o u t ( s ) = i n ( s ) 一k i l l ( s ) w g e n ( s ) ( 公式2 2 ) 公式2 1 和2 2 的联立称为到达一定值的数据流方程，其中，o e n ( s ) 可以由p f g 真接求出，k i l l ( s ) 可 以由p f g 和i n ( s ) 直接求出，所以，数据流方程实际上是关于i n ( s ) 和o u t ( s ) 的f & 性联立方程【l ”。 2 4 2 跨函数分析 函数f u n 通常由多条语句组成的，我们用s m 来代替函数中所有语句。将函数调用语句记为s 。我 们采取先计算d e f ( s f 。) 和r e f ( s f 。) 。再计算d 嘣s 。目i ) 和r e f ( s “i ) 的方法来进行跨函数的分析。在跨函数 分析数据依赖关系时，需要考虑函数内影响函数外的因素，如传地址型参数、全局变量及返回值。在实 际分析时，对于函数中的每条返回语句“r e t u r nr ；”，为了分析方便，使用“f u n = r ”予以代替。 在计算d e f ( s r 。) 时，可以将在f u n 内被使用的非局部变量视为传地址参数处理，有如下公式： 东南大学硕士学位论文 d e n s m 。) = vj ( s ，v ) l n ( s 。f ) v 是以地址方式传递的参数) u h d e n s 。“) 的获得需要在d e f f s f u 。) 的基础之上，对于d e f ( s f l l 。) 中的任意变量v ，如果v 是一个非局部变 量，那么将v 加入到d e f f s 。a ) 中；如果v 是一个形式参数，那么将v 所对应的实在参数加入到d e n s 。n j 中；如果v 是 n ，那么将r 加入到o e f f s 。_ 1 ) 中。 在计算r e f f s m 。) 时，我们仅考虑函数的形式参数和非局部变量，有如下公式成立： r e f f s m 。) 2u s e s r e f g ( s ) u 昂l ，f p 2 ，审。) 其中，s 是函数f u n 的语句集合，r e f g ( s ) 是语句8 所引用的非局部变量的集合f p t ，昂2 ，是函数的形 式参数的集合。 r e d s 。) 的获得需要在r e f i s ) 的基础之上，对于r e f ( s ) 中的任意变量v ，如果v 是一个形式参数， 那么首先获得v 所对应的实在参数，并将该实在参数所引用的所有变量加入到r e d s 。1 1 ) 中；如果v 不是 一个形式参数，那么将v 加入到r e d s 。“) 中。 综合函数内分析与函数间分析，我们可以计算出某函数所有语句的定值集和引用集。 计算函数f 中所有语句的定值集和引用集的过程如下： ( 1 ) 在f c g ( 函数调用图) 中找到一个出度为0 的节点，计算此节点对应函数的每条语句的定值集、 引用集与输入集； ( 2 ) 计算调用该函数的所有调用语句的定值集和引用集： ( 3 ) 在f c g 中删除该节点以及所有指向该节点的边； ( 4 ) 转第( 1 ) 步。 其中，第f 1 ) 步细化为： ( 1 ) 通过词法与语法分析的结果，可以获得当前函数p f g 中节点的定值集和引用集： ( 2 ) 初始化p f g 中每个实在节点的输入集i n 和输出集o u t 分别为。和生成集g e n ，并初始化p f g 中 虚拟节点s e n t r y 的输入集i n 为该p f g 所对应函数的所有形式参数( 在该函数内被使用的非局部 变量被看作是以地址方式传递的形式参数) ，然后根据公式2 1 与2 2 的联立方程以及p f g 中节 点的定值集和引用集进行迭代计算，得到p f g 中每个节点最终的输入集： 6 东南大学硕士学位论文 第三章基于重放的并发调试 在调试和测试顺序程序的时候，程序员一般采取循环调试的方法，即以相同的输入反复执行程序， 借助断点和观测点观察程序的运行状态，从而找出程序的问题所在。但是在第二章中，我们已经介绍了 并发程序执行具有不确定性，这种不确定性导致错误的不可再现性。从而无法使用循环调试的方法调试 并发程序。为了解决这个问题，需要某种机制来确定化地重现并发程序的某次执行情况。我们下面假设 讨论的并发程序的通信是基于消息队列和共享内存机制的。 3 1 调试策略 由于并发程序的不确定性，传统的一边运行一边调试的策略显得力不从心，而且这种一步式的方法 在观察程序行为时还容易引入探针效应，导致超时、错序等问题。 如果在追踪程序的运行时能够判断每个消息接收操作所接收消息的来源及去向信息，并予以记录， 那么在重放时就可以根据记录的信息为每条消息形成特定标识，强制每个消息接收操作接收具有特定标 识的消息，从而避免因为接收任何进程发送的任何消息所带来的内部不确定性。同时，基于共享内存的 通信方式，如果记录了进程对于某个共享对象的访问顺序，我们就可以在再次执行中消除同步和数据 竞争，得到确定性的执行序列。 由于进程的逻辑结构不因程序的不同执行而改变，因此如果对每个进程中的同步事件( 在基于消息 队列机制的通信中，同步事件是指消息发送和接收操作；基于共享内存中，同步事件是指共享对象的读 写操作) 按照逻辑结构中的出现顺序进行编号，对于程序的每次执行，同步事件的序号不变。根据这个 性质，程序中的每个同步事件可以用唯一的进程号以及该同步事件在该进程逻辑结构中的序号标识。 基于以上的考虑，本文提出三步式的调试策略p 4 ”j ：源代码插装、同步事件的监视与记录、执行重 放。在重放阶段可以进行事件检测，程序执行状态的查看和进程间通信的可视化等操作，如图3 1 所示。 第一阶段：源代码的插装。基于事件的并发程序调试需要根据并发语言的特点，定义影响程序执行 不确定性的事件，建立相应事件的信息收集和执行控制机制，形成函数库。在调试过程中，就可根据此 函数库，对源代码中的标准库函数、系统调用进行替换。 第二阶段：同步事件的监视与记录。为了对程序执行进行准确的重放，我们替换标准库函数或系统 调用的入口，使得在执行这些函数或系统调用时，能够监视识别同步事件，并给这些事件打上时间戳， 收集事件信息。在事件记录阶段，记录操作的时空开销都应当尽量小，以避免h e i s e n b e r g 现象，减小探 针效应。 第三阶段：执行的重放。根据记录的事件信息，并发程序将按照被监视时的顺序执行。在此基础上， 我们就可以进行事件检测，程序执行状态查看，并将进程间的通信关系可视化。 l 可执行 。叫o b i l 匮、 卅： 牺7 三i 腰3 1 调试策略示意圈 3 2 源代码插装 在对被测程序进行静态分析并植入探针的过程中，必须考虑相应的插装策略。有两种策略可以考虑 7 东南大学硕士学位论文 一是在关注的函数调用的前后加入探针：二是将关注的函数调用替换为自定义的函数。为了在同步事件 的监视记录过程中方便地收集事件信息，并在重放时对进程的行为进行准确控制，我们采用第二种策略 对源代码进行插装，替换标准库函数或系统调用的入口。 定义3 2 假设待插装函数为r t y p e f u n c ( t y p e la l ，t y p e 28 2 ，t y p e na 。) ，其中，t y p e l ，t y p e 2 ，t y p e n 分 别为形式参数8 l ，a 2 ，a n 的参数类型，r t y p e 为函数的返回类型；则f u n c 对应的封装函数为： r t y p ef u n c ( t y p e ta l ，t y p e 2a 2 ，t y p e na n ，t y p e m + lb l ，t y p a n + 2 b 2 ，t y p e n + mb m ) p r e s t a t e m e nt i f u n c ( 8 1 ，a 2 ，a n ) ， p o s t s t a t e m e n t ； i ； 其中，b l ，b 2 ，b 。为f u n c 完成特定功能所必须引入的额外参数信息，p r e s t a t e m e n t 与 p o s t s t a t e m e n t 为完成特定功能的插装代码，不能同时为空。 根据定义，功能封装函数f u n c ( a l ，a 2 ，b l ，b 2 ，b 。) 同时拥有了原函数和插装代码所具备的功 能，将其代替源代码中出现的f u n c ( a l ，a 2 ，a 。) ，便可完成函数的插装。 3 3 同步事件监视与记录 经过第二章的分析，引起并发程序执行不确定性的主要原因有以下几点：其一，基于消息队列的通 信机制允许某些接收操作接收不同类型的消息( 第二类消息) ；其二，共享内存访问中存在进程间的同步 竞争和数据竞争。为了消除不确定性，实现程序的准确重放，我们采用向量时间戳，标识同步事件。 3 3 1 向量时间戳 逻辑时间戳应满足以下时钟条件”4 。j ：若a _ b ，则c c a ) c ( b ) ，其中“斗”表示( h a p p e n ，b e f o r e ) 关系。公式表明：事件a 和事件b 之问存在因果关系，如果事件a 发生在事件b 之前，那么事件a 的逻 辑时间戳应该小于事件b 的逻辑时间戳。逻辑时间戳在描述进程问事件时序时应满足以下关系： 若a 和b 是进程p 中的两个事件，且a 在b 之前发生则有a _ b ； 若a 是消息的发送事件，b 是消息的接收事件，或者a 先于b 访问共享变量o ，则有a 斗b ： 若e t _ b 且b - c ，则有a 斗c ； 向量时间戳是一种逻辑时间戳，它可以用来精确地表示一个偏序关系”。给程序的每一个同步事件 打上一个向量时间戳，根据这些事件的时间戳向量就能够知道事件之间的时序关系。下面简要地描述一 下如何在以消息传递和共享内存作为通信方式的并发程序中实现向量时问戳。 假设每个进程p i 有一个本地向量时钟v c p t = 【v c 。，1 ，v c p ? ，v c n n ，其中每一个分量都是整数， 分别对应程序中的每一个进程。进程p 中本地向量时钟v c 。的第i 个分量的值v c 。1 表示进程p ，当前正 在执行事件的上一个事件；此外每一个共享对象有一个向量时钟v c 。，它标记了最近存取该共享对象的 同步事件。 当进程p 。对麸享对象o 进行同步操作e 。f 时，按照下面的规则给出该同步操作的标记时间戳： 计算v c ( e 。f ) 一m a x ( v c v c o j ) + a ；，其中m a x 两数求两个时间戳向量的对应分量的最大值：， 是一个有n 个分量的向量，除了第i 个分量的值为l ，其余分量值为0 ； 将v c ( e ，) 的值赋给v c p i 和v c o ，； 当进程p i 发送一个消息m s g 给进程p 时，按照咀下规则给出该发送操作s e n d 的时间戳： 计算v c ( s e n d ) = v c p i + ，i 是一个n 维分量向量，第i 个分量的值为1 ，其余分量值为0 ； 将v c ( s e n d ) 的值赋给v q ，并将v c ( s e n d ) 附加到消息m s g 中发送出去： 当进程p i 从进程p j 接收到一个消息m s g 时，按以下规则给出该接收操作r e c e i v e 操作的时间戳： 计算v c ( r e c e i v e ) = m a x ( v c p i ，v c m q ) + ，其中m a x 函数求两个时间戳向量的对应分量的最大值： v c m 是通过消息m s g 传递过来的发送操作的时间戳；，是一个有n 个分量的向量，除了第i 个分量的 值为1 ，其余分量值为0 ： 8 东南大学硕士学位论文 将v c ( r e c e i v e ) 的值赋给v c p ，； 向量时间戳表示出了同步事件间的一个偏序关系( e ，斗) ，即给定同步操作o p i 和op j ( 它们可以 是共享内存访问操作，或是消息的发送和接收操作) 有： o p ijo p j 营v c ( o p i ) = e v e n t 州) w r i t e r 在进程k 中， 记录无序共享对象访问 e v e n tv c = m a x ( w r i t e 珏e v e n tv c ) e n d i f w r i t e t s = e v e n t v c ；当前时阃戳更新 w r i t e r2e v e n t , , 从r c a d s e t 中移除在e v e n t 事件之前的元素 b r e a k ； c a s er e a d ： i f ( w r i t e r v c u = e v e n t , 比壮】) w r i t e x 在进程k 中：冲突检查 记录无序共享对象访问( ， e v e n t 比= m a x ( w r i t e 珏e v e n tv c ) e n d i f r e a d t s = 妇伸耐甄e v e n t v c )取得r e z d s e t 中所有r e a d 事件的时间戳最大值 从r e a d s e t 中移除在e v e n t 事件之前的元素 将e v e n t 加入到集合r e a d s e t 中 b r e a k e n ds w i t c h e n dw h i l e 根据算法1 ，程序在运行过程中动态地建立各个同步事件的时序关系。进程内的同步事件的向量时 间戳构成一个递增的序列，这个时序是由程序逻辑确定的，不会改变；不同的进程间，消息的发送和接 收事件构成了s e n d - - - 4 r e c e i v e ，内存访问按照访问的先后顺序构成了“一”关系。我们没有必要记录所 i o 东南大学硕士学位论文 有的同步操作，而是关心那些引起竞争的消息发送和接收顺序，以及引起共享内存访问时同步竞争和数 据竞争的操作。通过记录这些重要的执行信息后，我们可以在重放时强制进程中的接收事件接收特定的 消息，访问内存按照原始的顺序进行。 p 1p 2 p 3 s e n d 【1 r s ( 0 1 【 - - + 一 消息传递 共享内存访问顺序 r s ( o ) 读共享内存o w s ( o ) 写共享内存。 图3 4 进程间时序关系示意图 ) 【0 , 0 ，1 】 【l 4 ，2 1 【1 , 4 ，3 】 图3 4 就是用向量时间戳表示的“寸”关系例子。用箭头连接的两个同步事件表示它们之间存在直 接的“一”关系；文字旁的数字表示发生事件的时间戳向量。虚线箭头表示依次访问同一个共享内存的 顺序。如图中p 2 首先写共享变量o ，然后p l ，p 2 ，p 3 和p 2 再分别对o 进行读、读、读和写，记录过 程中我们记录了以下信息：w s ( o ) o ，l ，0 】必须在r s ( o ) 2 ，1 ，o 和r s (