（计算机软件与理论专业论文）并发程序调试的追踪重演机制研究.pdf

尔南大学颂 十 仳论 文 摘要 随着实际应用对并发软件需求的不断增加，并发程序的分析、理解、诵试、测试和维护已经 引起人们的广泛关注。为。发程序出多个异步推进的并行成分组成，f h 十进程渊度顺序以及通信机 制小身的特性，使得程序在相同输入的不同执行中呈现不同的结果。这种并发程序执行的小确定 性直接导致r 程序钳误的，f ；可再现性，即后续的执行无法再现前次执行的错误。十是，以反复执 行程序、幕复再现敝障为核心的传统循环调试方法变得不 l j _ 可用。 再现程序的执行行为是并发程序阔试的重耍问题。囚此我们将传统的循珂、调试方法加以扩 充引入追踪和重演的机制霞欣f 2 序胸某次执行，消除错洪的不可再现性。我们分析了进程m 消 息传递的依赖关系，并阐述了消除并发程序执行不确定性的优化的追踪算法。同时，对于人掣的 并发程序，在调试过程中，如果每次重演都从稃序的最丌始执行，势必会造成资源的大量浪费， 并且不能够满足程序员对调试响应速度的要求。针对这一问题，我们采用渐增式追踪嚣演方法， 引入容错系统中的检查点技术，在并发程序的追踪执行过程j 1 周期性地插入独立式检查点。记录 下各个进程的执行状态，并将进程分割成若干相互独立的检查点问隔。从而在重演的阶段，程序 员丌j 以任意地从自己感兴趣的检盘点开始反复重现程序的某段执行，直到发现错误的问题所存。 存埋论研究的基础上，我们研究和开发了并发程序分析和调试的辅助工具包括并发程序的 追踪重演模块和进程执行轨迹的可视化引擎适用于c 语占编写的进程问以消息传递为丰要通信 机制的并发程序。f ：发程序的追踪重演工具能够追踪程序的原始执行，竹通过设立检查点已录各 进程的执行状态，存重演的阶段可以有选择地蕈现程序的某执行片断：可视化引擎将并发进程的 执行轨迹、榆查点侮置以及进程间的通信关系以简洁的图形方z 碌示给用户。 关键宇并发程序逊程消息传递通信追踪重演检查点消息记录 东南人学坝 l 学位论文 a b s t r a c t n o w a d a y s ，w i t ht h ei n c r e a s i n gr e q u i r e m e n to fc o n c u r r e n ts o f t w a r e ，t h ea n a l y s i s u n d e r s t a n d i n g d e b u g g i n g ，t e s t i n ga n dm a i n t e n a n c eo fc o n c u r r e n tp r o g r a m sh a sb e e nd r a w nm u c ha t t e n t i o nb yp e o p l e t h ec o n c u r r e n tp r o g r a m sc o n s i s to fv a r i o u ss y n c h r o n o u sc o m p o n e n t sb e c a u s eo fp r o c e s ss c h e d u l e o r d e ra n dc o m m u n i c a t i o n ，d i f f e r e n tm n so nt h eg i v e ni n p u tm a yp r o d u c ed i f f e r e n tr e s u l t st h ee x e c u t i o n o fc o n c u r r e n tp r o g r a m si sn o n - d e t e r m i n i s t i c ，w h i c hl e a d st ot h ef a c tt h a tt h ef o l l o w i n ge x e c u t i o n sc a n n o t r e p l a yt h eb u g sp r o d u c e db yp r o c e e d i n ge x e c u t i o nt h u s ，t h et r a d i t i o n a lc y c l i cd e b u g g i n gt e c h n i q u e b a s e do nr e p e a t e dr c e x e c u t i o nt or e p r n d u c eb u g sd o e sn o tw o r ke f f e c t i v e l yf o rc o n c u r r e n t p r o g r a n t s g u a r a n t e e i n gr e p r o d u c i b i l i t yi sam a j o ri s s u ei nt h ec o n c u r r e n tp r o g r a m sd e b u g g i n g s ow ei n t e g r a t e t r a c ea n dr e p l a ym e c h a n i s mi n t ot r a d i t i o n a l d e b u g g i n gt e c h n i q u e ，i n o r d e rt oe l i m i n a t et h e n o n d e t e r m i n a t i o na n dr e p l a yt h ep r o c e e d i n ge x e c u t i o nw ea n a l y z et h ed e p e n d e n tr e l a t i o n sa m o n gt h e c o m m u n i c a t i o no fp r o c e s s e sv i am e s s a g ep a s s i n g ，a n dp r e s e n ta no p t i o n a lt r a c ea n dr e p l a ym e c h a n i s m t od e t e r m i n et h eb e h a v i o ro fc o n c u r r e n tp r o g l a m s a tt h es a m et i m e ，t h ec o n c u r r e n tp r o g r a mi so f t e n l o n g r u n n i n g ，s oi ti sn o tp o s s i b l et or e p l a yt h ew h o l ep r o g r a mf r o mt h eb e g i n n i n go v e ra n do v e r f o r t h i s ，w ep r e s e n ta ni n c r e m e n t a lt r a c ea n dr e p l a ym e c h a n i s ma n di n t r o d u c ei n d e p e n d e n tc h e c k p o i n t i n g s t r a t e g y f r o mf a u l tt o l e r a n t s y s t e m s ，w h i c h c a ns a v et h ei n t e r m e d i a t es t a l e so fe a c hp r o c e s s i n d e p e n d e n t l y , a n dd i v i d ee a c hp r o c e s si n t os e v e r a lc h e c k p o i n t e di n t e r v a l sw i t hi t ，w ec a nr e p l a y p r o g r a m sf r o ma n yi n t e r e s tc h e c k p o i n ti n s t e a do f t h eb e g i n n i n gu n t i lf i n d i n gt h eb u g s b a s e do nt h et h e o r yr e s e a r c h ，w eh a v er e s e a r c h e da n dd e v e l o p e da na n a l y s i sa n dd e b u g g i n g a s s i s t a n tt o o lf 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 f c o n c u r r e n lp r o g r a m s t r a c ea n dr e p l a yt o o la n d v i s u a lm o d u l eo fp r o c e s s l se x e c u t i o nt r a c e ，t h i st o o li sa p p r o a c ht ot h ec o n c u r r e n tp r o g r a m st h a ta r e w r i t t e ni nca n dt h e i rp r o c e s sc o m m u n i c a t i o nv i am e s s a g ep a s s i n g t h et r a c ca n dr e p l a ym o d u l ec a n t r a c et h eo r i g i n a le x e c u t i o no fp r o g r a m s ，a n dt h ec h e c k p o i n t i n g sc a ns a v ee a c hp r o c e s s si n t e r m e d i a t e s t a t e s s oi nt h er e p l a yp h a s e ，w ec a ns e l e c ta n yi n t e r e s tc h e c k p o i n t e di n t e r v a lt or e e x e c u t et h ev i s u a l m o d u l ec a ng i v eat e r s eg r a p ho f p r o g r a me x e c u t i o n ，c h e c k l m i m i n gl o c a t i o na n dp r o c e s sc o m m u n i c a t i o n f o ru s e r k e y w o r d s ： c o n c u r r e n t p r o g r a m ，p r o c e s s ，m e s s a g ep a s s i n g ，c o m m u n i c a t i o n ，t r a c ea n dr e p l a y c h e e k p o i n t i n g ，m e s s a g el o g g i n g 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：当塞日期：塑坐i ：! 垡 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院 签名：址导师签名：期：艘：! ：! 妒 与i f 钙大 学 l ! !上学位沦 史 第一章绪论 肌今，随着用户对软件系统性能要求的提高，并发技术得到，广泛的应h j 。但并发技术的j 泛使用在提高系统性能的同时，【h 给程序员带来了开发和维护的困难：”芨程序执行的不确定性、 错误的小可再现性，使得传统的顺序程序调试方法不再可用。 1 1 选题依据 学期的顺序程序都是一条指令按一条指令地顺序执行。然蛳红客观世界的问题审问q ，存舟 着逻辑上同时发生的活动。为了描述和处础同时发牛的活动，必须使h j 并发机制。 并发程序的设计比顺序程序凼难得多，程序员需要处理好备个进程之间的同步和通信笑糸。 这些问题处王甲得不恰当，会带米i 发程序所特有的一些错误( 如死锁) 。即便是各个逃程之削的 同步和通信关系都是正确的，排除出现在中个进程巾的逻辑错误也是很幽难的。同时，并发程序 的执行取决于程序中各个独立事件发生的先后顺序是动态的、f ；确定的。这种不确定性使得程 序中的错误不能够按照 p 序员安排的环境出现给程序的动态调试带来很大闲难。对于这类问题， 传统的顺序程霄佩试技术显得有些无能为力。 在调试和测试程序时，程序员通常采用循环调试”。2 1 的方法，即以相同的输入反复执行程序， 借助断点和观测点观察程序的运行状态，从而找出 、口j 题的所在。使用循环测试方法的前提是：别 十同样的输入，程序的运行结果( 输出结果和执行路径) 都牛目同，即程序的运行是确定的。并发 程序的执行由于进程的并发性、进程州的通信与同步等原因具有不确定性，即在相同的输入下， 程序每次正常执行的结果部可能4 i 同。这种不确定眭直接导致了铝误的小可再现性”j ：如果程序 的某次调试运7 7 1 t _ 现了一个错误，在程序的后续多次运行中，这个错误t 、j 能币再出现，如果这个 错误出现的几率很小那么程序员r q 能始终无法发现这个错误或查出导致这个错误的原圆。 并发程序的闻试和测试所要解决的重要f _ 题就是要将j 发程穿的4 i 确定性凼素去掉，使其具 有呵再现性 4 f 。为r 消除这些不确定性因素，将并发程序的执行确定化，比较常用的方法是在并 发的环境下引入追踪和重演的机制具体分为两个阶段：第一个阶段追踪程序的原始执行记录 下必要的执行信息；第个阶段在保汪输入信息相同的条件下，根据追踪阶段所记采下来的信息， 控制程序按照原有的状态执行。通过这种方式能够重现并发程序的某次执行，进i 竹传统的循环调 试方法能够得以应用。 为了支持大犁并发程序的快速重演需求，我们将检查点技术和追踪、重演机制融合起来，形 成渐增式追踪i 重演方法；在追踪阶段，记录相关执行信息的同时周期性地插入独立式检查点，保 存各进程的执行状态；从而盎重演阶段，可以选择感兴趣的检查点问隔反复执行，而小必要每次 都从头开始执行整个稃序。 基于以【：所提出的并发 口序执行的追踪和重演的必要性我们牲以消息传递为主要通信方j 的并发模型上提出渐增式追踪蓖演的算法。同刚我们还开发了并发程序追踪，重演t 具，用于追 踪和重演在u n i x 的s y s t e m v 下编写的以消息队列为进程问通信机制的并发程序的执行实现并 发样序执行的确定化。 1 2 拟开展的研究内容 根船国内外住源代码级测试、酾试工具方面的研究，矸发现状，以及最新发展动态我们拟 在建立抽象并发程序模型，利用程序分析技术确定同步事件问的依赖关系：采用o n t h e f l y 算法 检洲竞态消息；引入检查点机制形成渐增式追踪重演算法等方面展开深入研究。具体丽言，本文 的工作将集 ；存以下几个方面： ( 1 ) 建立抽象外发扭序模型。计算机程序可以抽琢为程序流i , q ( p f g ) ，它将濒程序刚图的 形式表示h j 来，莉：程序流l 引上n j 以方便地( 符往足直观的) 分口i 语句闸的前趋后继关系、必经廿 东南大学顺：学位论文 点以及执行路径等问题。我们通过程序流图建立抽象并发程序模型，分析语句问的控制、数据依 赖，提取进程之间的通信关系，并逊一步确定消息传递事件之间的执行顺序和依赖。 ( 2 ) 分析不确定性产生的原因。在基于消息传递的并发程序巾，由于进程凋度和消息延时 等原因，对十同一输入的4 i 同执行可能产生不同的结果，即所谓的执行不确定性。通过分析消息 传递的通信机制归纳出消息接收操作的三种类型，明确消息接收操作之问的竞争是引发不确定 性的根源。从而仪针对有町能引起不确定性的第一种消息接收操作进行分析和讨论。 ( 3 ) 竞态消息o i l t h e f l y 检测算法。为厂提高算法的执行效率，尽力减少探针，效应，我们采 用种优化的追踪算法：在程序的原始执行过程中，在线检测1 1 i 引起不确定性的竞态消息，调j 书 追踪子程序，仪记囊每对竞态消息巾的一个消息的发送顺序f 衙币赴内容) ，将追踪阶段的肘卒 消耗减小到晟少。 ( 4 ) 渐增式追踪重演算法。为厂支持大型并发程序的调试，在基本的追踪和霞演机制巾融 入检查点技术，形成渐增式追踪重演g l 制。具体的，在追踪阶段周期性地插入独、上式检盘点记 录下各个进程的执行状态，茹将进程分割成若干相可独立的间隔；市演的阶段便i j - 以从某个进程 的任何个感兴趣的检查点开盘台循环执行，直至查找到锚误的所在。 1 3 论文结构 本史薛主要章节内容安排女下： 第章作为整个论文的绪论，阐述此项研究的必要性以及可行陛，描述论文的研究内容，并 简要地介绍论文结构。 筇二章介缁并发程序和程序分析的相关概念。包括进程间的笤种通信机制引起井发程序执 行的不确定性的原冈：以及控制流分析，构造程序流图。 第二章建立基于消息传递通信机制的简单并发程序模型，在给定模型的基础r 咩细阐述了 o n t h e f l y 竞态消息检测算法，消除并发程序的小确定性。 第四誊针对大型并发程序的调试提出种渐增式追踪耍演方法，引入检查点和消息皑录投 术，建立分段确定性模型，消除多米勒效应，提高重演阶段的执行效率。 第五章具体讨论关于系统实现的一些细节，包括系统基本框骞、数据结构和算法等问题， 第六章是对整个论文研究和实践工作的总结，综述我们存并发程序分析与调试辅助投术研究 方而获得的成果，并且指出我们现有工作的局限性和有待提高和改进的方面。 2 垒i !盔 堂 翌 主兰 丝堕兰 第二章并发程序的相关概念 随着用户对软件性能要求的臼益提高，越来越多的系统采用并发技术。并发程序具有j i ：发执 行的特性，能够充分利用系统资源，提高系统处理能力。然而系统资源何限，程序的并发执行必 然会导致资源的共亨和竞争，从而改变程序的执行轨迹平u 逃度，引起不确定性，。给系统的调试利 维护带来困难。进程是并发执行的单元，进程之间通过通信相_ 耳怫作完成同步与互斥。奉蕈首先 介绍进程的相关知识以及进程问的常用通信机制；然后讨论了j ：发程咩执行不确定性广生的蟓 囚：最后对程序分析技术的基本碑论加以阐述。 2 1 进程 程序的并发执行充分地利用了系统资源，提高了系统的处婵能力，然而也必然导数资源共享 和竞争，进而影响程序执行结果的封闭性和可再现性。为了拧制和功、调程序执行过程中的软、硬 件资源的共享和竞争，引入了迸程的概念1 5 l 。并发程序一般包括多个进程( 住有的操作系统巾也 可称为任务) ，一个进程是一个程序在一个数据集台上运行的过程，它是系统进行资源分配和调 度的一个独立单位。 进程是一个抽象实体，通过进程的创建原语和撤销原浯完成进程从无到有，从存在剑消亡的 变化。吾个操作系统般都提供了创建进程的系统调削( 如p s o s 提供了tc r e a t e ，u n i x 提供了 f o r k 等) 。进程的创建方式主要有两种：一种是由系统程序模块统一创建；另一种是存层次鲇构的 系统中山父进程创建。在创建进程时，操作系统赋干进程一个唯一的标识符以及p c b 。进程标识 符( 下文称为进程i d 3 是系统内部崩于标识进程的一个整数。p c b 中i 己载j ，该进程的属性，如进 程标识符、现行状态、现场保留区、优先级等。 在层次结构的系统中，一个进程可以创建若干个进程，新创建的进程又可以继续创建进柠。 创建者称为父进程，被创建者称为予进程。父进程可以和了进程并发执行。进程有= 二种基本状态： 就绪状态、执行状态、隔塞状态。当进程获得除c p u 之外的所有需要的资源时，它处于就绪状态： 当进程获得c p u ，其程序正在执行时，它处于执行状忐：当j f 在执行的进程由十某事件m 无法执 行时，便释放c p u 的占有权处于阻塞状态。进程的这三种基本状态可以互相转换： 2 2 进程间的通信 一般来说，进程问的通信根据通信的内容可以划分为两种，即控制信息的传送与人批量数据 的传送。通常，我们把控制信息的交换称为低级通信，而把进程间大批量数据的交换称为高级通 信。低级通信一般只传送一个或几个j 亍：节的信息，以达到控制进程执行速度的作用，常用的机制 何加锁、信号鼙和p 、v 原语等。高级通信方式需要传送人量的数据，蚓的是为了交换信息。夺 节接r 来将介绍几种常用的进程问通信 p c i ? l o 2 。2 1 管道 所谓符道足指进程间i i 千j 文件连接起来的一条通信信道，主要用米进行进程问大基信息的传 送。两个进程问用管道文件进行连接，发送进程以宁符流彤将信息送入管道，接收进程从管道 中接收信息，从而实现通信。管道分为两类：无名管道和有名管道。无名管道是一个连接两个进 程的开放式文件，从管道的一端写入的信息可以从另一端读出。但它的缺点是只能片j 于父子进程 问通信为了使j p | 司簇进程间也能相互通信，需要使崩有名管道。有名管道的一1 作方式基奉类似， 柏无名箭道相比是一种永久性机构，一旦建立就丌j 以用其文件名像操作普通文件一样的随意。 管道实质上灶一个文件，因此管道通信基本r 可以借用文件系统腺有的机制实现，但发送进 程和接收进程之间的相互f j j - 调是文件系统机制无法解决的为了协调双办的通信，管道通信机制 必须提供以f 的协凋能力：( 1 ) 互斥：j 一个进程正在对管道进行 女写操作时，另一进j 1 ，必须曾 东南人学倾 卜 学何论文 待：( 2 ) 同步：当发送进程将数据写入管道后就进入等待，直到接收进程从管道中取走数据后孵 把它唤醒；当接收进程从窄管道读取数据时进入等待，直到发送进程向管道中写入数据再把它唤 醒；( 3 ) 对方是舌存在：只有已经确定对方存在时，方能进行通信。利用管道进i r 通信的优点是 交换的信息量大且信息保存的时间长，缺点是i o 操作的次数较多，同步和控制机构也比较复杂。 2 2 2 消息队列 消息是一个进程传输到另一个进程的信息，它为每个进程提供了使该进车丌的动作与其它进程 同步的机制。消息队列是存放消息的一段缓冲区，可以用米存放移条消息，保证：等待接收的消息 1 二会五失。消息队列叶 是以数据块为基本交换单位除了能像管道一样提供一种先进先m 的队列 操作外，还具有以下特点：( 1 ) 一个消，l , t l 孰列中可以存在多个予队列，每类消息排成一个f 队， 进程可以有选择地读出所需的消息：( 2 ) 当所期望的消息还未写入队列时，接收进程口j 以决定是 否挂起等待消息的到来：( 3 ) 消息队列能够支持进程问的坝向通信，并且个消息队列可以被多 个进程所共享。 从功能方面看，消息队列可以看作是一个消息链表。发送消息的任务使用s e n d 命令把一条消 息放入消息队列，等待消息的进程使用r e c e i v e 命令从消息队列接收消启( 不同操作系统提供的 s e n d 与r e c e i v e 系统调用不周，如：p s o s 提供qs e n d 与qr e c e i v e 函数，u n i x 的s y s t e mv 版本提 供了m s g s n d 与m s g r c v 函数) 。 消息队列和进程一样是一个抽象实体，在使用前必须先被创建。各个操作系统基本上都提供 了创建消息队列的系统调用( 如：p s o s 提供qc r e a t e 系统阚用，u n i x 的s y s t e m v 版本提供了 m s g g e t 系统调用) 。在消息队列被创建时，操作系统为消息队列分配了一个i d 值以及浚消息队列 的q c b 。q c b 中包括了消息队列名称、消息队列i d 、等待进程接收消息的策略、消息队列的k 度以及消息的最大最小长度等信窟。 2 2 3 共享内存 发送进程把需要交换的信息发送到某一约定的存储区域，接收进程从陔区域读取信息，从而 实现多个进程间的通信，这种进程问通信方式称为共享内存。这里的存储区域是指虚拟地址卒阿， 通信进程看到的是虚空间而不是主存。进程的虚拟地址可以映射到仟意一处物理地址，如果两个 进程的虚拟地址映射到同一物理地址，这两个进程便可以利用这一虚拟地址进行垃信。共享内存 允许一个或多个进程通过同时出现存它们虚拟地址空问中的内存来实现通信。一个共享内存建立 后可以附接到同一个进程的多个虚地址空闼上，而同一进程也可附接多个共享存储区。 当共享内存区映射到共享进程的地址空间后，进程间的数据传递便不再涉及内核。此时，对 于共享的数据域的 方蒯便可以通过访j 廿j 键的权跟检验米实现，而无需执行进入内核的系统调 用。共享内存通信机制的优点在十为通信进程提供直接通f 青的手段使得通信进程通过写( 发送 消息) 、凄( 接收消息) 对方的虚空间完成相互通信，效率根高。 2 2 4 远端过程调用 过桎调用也可以看佧一种通信方式。过程调_ 埒j 可以分为当地过程调用和远端过程调用。所谓 远端过程调用是指被调用过程( 雨数) 和调用过程( 函数) 处于不同的进程中。远端过程调用是 客户端朋r 务器体系结构的技术基础。我们一般将调用者视为客户端进程，被调用者视为服务器进 程。客户端进程和服务器进程可以在同一= e 机上，也可以处于不同丰机r 。 远端过程调片j 的实现简沽而方便是远程进程问通信的一种高效形式。具体的过程和本地调 用丰月类似：两用一个远程过程时，调用研、境被挂起：将参数由网络传递给执干亍过程的环境执行 所需的过程；过程完成后将结果传回给调用环境。 2 3 5 邮件槽 邮件 凸提供进程问单向通信能力，建立邮件槽的进程称为邮件槽服务器，与之通信的其它进 程称为咐件槽客，。| j f j r f ：惜客户进程叮以五匝过邮件憎的名字给建立邮p f ：借的进程发送消息，被发 4 送的消息保存在邮件槽巾直到被相廊的进程读取为止。一个进程既r u 咀足邮件槽服务器也可以 是邮件糟客户，因此，通过邮件槽安际上也同样能够实现进程问的双向通信。 存州络环境中，通过不可靠数据搬传递，邮件槽可以给指定网络区域中所有的计算机卜同样 名孚的邮件槽发送消息。和命名管道( 通过可靠数据报传送) 相比，存删络发生错误之叫无法保 证消息的正确接收，但其优点在r 捌有简化的编程接口和指定网络区域内所有前点的广播通信能 b ， 2 3 并发程序执行的不确定性 在并发程序的执行中存在两种不确定性：外部刁i 确定性和内部f i 确定性h 。外部不确定性是 指程序列于相同输入的小同执行具有不同的结果。这种不确定性有时是希单存在的，州以提高程 序的执行效率或者为使用者提供同一问题的不同解决方案：何的是小希望俘住的在后一种情况 下，不确定性应被当作程序中的错误必须尽力消除。内部不确定性是指程序对于干订同的输入的1 i 同执行其有相同的结果，但是程序内部的执行路径不同。 不确定性的引入从根本上况是由于并发程序的多个进程并发执行的结果( 少数是由十一些系 统函数的调用引起) 在很大程度上与进程之问的递信和同步官接相关。以下就以进程间以消息队 列机制和抟享内存机制进行通信所引起的不确定性分别进行讨论。 2 3 1 消息队列 总结多个操作系统所提供的消息接收操作，可以得出消息接收操作主要可以接收三娄消：臣 ”j ：一类是接收任蚵进程发送的消息，二类是接收具有特定标志的消息，三类足接收特定进程发 送的消息。操作系统提供的消息接收操作报话参数来区分接收什么样的消息。例如：往u n i x 的 s y s t e m v 版本中的消息缓冲数据结构m s g b u f 中定义了r e t y p e ，它是消息的特定标志，存消息接收 雨数m s g r c v 函数中的消息类型参数如果为0 则表示n j 以接收任何进程发来的任何消息，如果为正 数n 则襄示只能接收r e t y p e 为n 的消息。 具体地分析这j 类接收操作：第_ 类接收操作非是特定的消息不予接收，因此每一次运行所 接收的消息均相同，从而不会产生不确定性：第三类接收操作接收特定进程发米的消息，可同一 进程消息的发送顺序是由进程的逻辑结构决定，在相同输入下不会改变，从而淳娄接收操作也不 会产生不确定性；第一类接收操作可以接收任何进程来的任何消息，不判断消息的来源，先来者 先予以接收，因此是造成不确定性产生的内部原因。 生于消息队列机制进行进程问通信的并发程序，其不确定性的产生除了上述的内部原因外， 还有其外部原幽：程序的每次执行，操作系统对于各个进程的调度顺序以及消息传递时的延迟都 0 i 辟相同从m 导致消息到达消息队列的顺序不同】”l 。以下足一个以消息传递进行通信的例 子。包括二个进程，进程p 1 向p 2 发送消息，进程p 3 向p 2 发送消息进程p 2 接收两个消息。 进程p 2 中的两个消息接收操作b 和dn j 以接收任何进程来的任何消息，因此山于消息五正时 和进程调度等原因，第一个接收操作b 既可以接收进程p l 发送的消息m 、，也可以接收进程p 3 发送的消息m 2 。图2 1 ( a ) f l 剧2 ，1 ( b ) 分别表示了该并发程序的两次彳i 司执行情况。 p 【 向p 2 发送m p 2 接收任何进程发送束的任何消息 接收任何进程发送来的任何消息 p 3 向p 2 发送m 2 东f 杓人学坝 学位沦史 p 1 p 2p 3 p 1 p 2 p 3 ( “ 圈2 1f f l j 息传递j i 倒 ( b ) 2 3 2 共享内存 对于通过共享内存进行通信的并发程序，从单个进程的角度，每个对共享内存区的读操作都 应被看作是输入操作，因为该进程从共享区读取的内容可能是由另一个进程写 的。如果这个并 发程序在单处理器上执行，我们可以认为是进程的调度造成群序执行的不确定因为在这种情况 下，如果程序的两次执行中进程的调度情况完全一样，那么进程的执行路径必定相同。两当程序 在多处理器环境下执行时，不确定性主要是由竞争条件引起的。所谓竞争条件是指刘同一个共亨 地址的两个非同步的访问，至少其中个访问修改了该共亨地址。竞争条件可以分为同步竞争和 数据竞争两类。其中，同步竞争是用来让程序执行具有不确定性，是程序员故意使用的，不是程 序的错误；l 面对于数据竞争，通常是由程序不止确的同步引起的，应废被当作错谋对待。如果程 序巾对一个共事变量的两个操作( 其中至少有一个是写操作) ，没有被同步语句隔开，就存舟数 据竞争情况。 2 4 程序分析技术 本 y 介绍一些程序分析的基本概念。计算机程序可以抽象为程序流图( p f g ) ，它将源稃序j h 图的形式表示山来，在程序流图上n j 以方便地( 往往是直观的) 分析语句问的前趋后继关系、必 经节点以及执 i 路径等问题。有了这些概念戟可以进一步分丰斤语句c h j 的拧带0 流、数据流，以及各 个通信进程间同步事件的执行序列和相互依赖关系。 2 4 1 程序流图 程序流圈是一种通用的顺序程序表示方法，它反应了程j 手中语句、模块之问的执行顺序和相 互调用关系“”f 。通常我们所说的程序流图是予程序控制流幽，描述拧翩流在各个语句问的流动 关系。 定义2 4 i 程序p 的控制流剧( c f g ) 是有向舟，可崩四兀组 表示，其 ，s 是1 7 点集，子程序中的每个浯句部对应图r r l 的个节点；边集e = i r sj ，s 2 s 且s 执行后， i ，能立即执行s 2 ；s 。和s 。分别为了程序的入口和出口筘点。 有时一个了程序可能有多餐退出语句，为了保征程序流图中终点的唯一性，我们百 砷：幽中加 入一个虚结点s 。，并将所有退卅语句对应的节点都指向它。 定义2 4 2 c f g 中，若 e e ，则称8 l 是s 2 的直接前驱，s 2 是s i 的真接后继，记为p r e ( s j s 2 ) ；语句s 的所有直接前驱组成的集台称为s 的真接f i ( r 驱集，记为p r e d ( s ) ：s 的所有育接后继组 成的集合称为s 的直接后继集记为s u c c ( s ) 。 定义2 4 3 设p a t h = 为一语句，列，若p r e ( s “) 睁1 ，2 ，n 1 ) ，m 0 称p a t h 为 可执行路释。 定义2 4 4c f g 中，若从s i 到s 2 之刈存在。个可执行路径，称s 1 是s 2 的前驱，记为p r e + ( s l ，8 2 ) 。 定义2 4 5 若从s 2 剑程序口节点的每个路径# f f 经过s 。，则称s 【为s 2 一个后向必辫 y ，i ， 6 东由人学碗+学位沦 文 记为p r e d ( s l ，s 2 ) 。s 的所有向后必经结点组成的集合记为f d ( s ) 。 定义2 4 5 敬s l 与s 2 是程序p 的巧条语句，若s 2 的执行与奇墩决_ 丁s ，的执行绍粜，则称s 二 拧制流依赖于s l 。如果s 2 控制流依赖于s 1 且不存在语句s 3 ，使得s 3 位十s l 到s 2 的路径上且5 2 控 制依赖于s 3 ，那么称s 2 控制流直接依赖于s 】。 算法2 4 1c f g 构造算法 ( 1 ) 构造根节点s 删，( 丌始节点) 及表示语句和拧制条件的节点。将其它甘点( 复台语句h 包古最外辰的 控制节点) 作为s 呻。的子节点，用s o n 边连接。 ( 2 ) 对分支语句的每个分支( 包括醯宙分支) 添加一个作为 节点的靠 ，点，分支q 的话f u 钉点( 皿u 皋 札的话) 作为此虚节点的了节点用s o n 边连接。 ( 3 ) 列循环语句添加胡个作为子节点的啦弋t 点，其一 一个表小循环体，循环体r f - 的话f , j 节j ：j ( 如泉的 话) 作为此虚节点的子书点，用s o n 边连接；另一个表示循环结柬。 ( 4 ) 在虚节点的子节点c f - ，若sj 执行完后i j 能市即执行s 2 则用n e x t 边 连接节点s l 承is ? 。 f 5 ) 重复( 2 ) 一f 4 ) 直至h 所骨的i b f , 3 部分析完毕。 【6 ) 构造虚带电s 。( 结束节点) ，所有代表r e t u r l t 语句的节点。i 之相连。 图2 2 是一个c f g 示倒。图中2 和3 是4 的真接前驱，4 是! 的向后必经体点 顺序、分支、循研= 是c 语言巾三种最摹率的控制结构，顺序结构的c f g 中的所有顶点串成 条线，比较简单，本文不，介绍，下面分别讨论分支和循环结构的c f g ：在c 中i r 语句的语法 如蚓23 f a ) 所示其c f g 如图2 3 ( b ) 所示： s w i t c h 语句的一般形式如图2 4 ( a ) 所示，其c f g 如图 24 ( b ) 所示：c 中循环语句有：w h i l e 、d ow h i l e 、f o r 二种形式。其中w h i l e 语句的形和c f g 如 25 t a ) u 网25 ( b ) 所示d ow h i l e 和f o r 语句的c f g 与w h i l e 语句的c f g 大致相l 司。 p r o c e d u r em a x ( x ，y ：i ni n t e g e r ；z ：o u li n t e g e r ) i s t e n x p ：i n t e g e r ； b e g i n i f x y t h e n 一1 t e m p ：2x 一2 e l s e t e m p ：= y ： 一3 e n d i z 。2 t e m p ； 一4 e n f lm a x ； ( a ) 程序示例 i f ( c o n d i t i o n ) s i ：s ，为i 吾句序列 s 2 ：s 2 为语句序列 ( a ) 1 f 语句语法 图2 2 c f g 示铆 图2 3 i f i s - 纠 东南大学硕1 _学位论史 s w i t c hre x p r e s s i o n 、 c a s es e l e c t o r i ： 斯：s l 为语句序列 c a s es e l e c t o r 2 ： s 2 ；j j s 2 为语句序列 c a s es e l e c t o r 。 s n ：s 。为涪句序列 a ) s w i t c h 浯白j 语法 w h i l efc o n d t i o n ) o 主巫) 图2 5 w h i l e 语台j 2 4 2 并发程序控制流图 为了分析并发程序的执行，提取进程之f 、日j 的同步与通信，占先需要将并发程序的源代码转换 为一种内部表示，然后在这个内部表示上进行分析。好的表示会给以后的分析带来很大帮助。h ；，人们已经开发出多种并发程序表示方法，并且在不同领域得到了应用。目前，这些方法的最 大差异表现在对同步的描述上，其中摔制流h ( c f g ) 和p e t r i 网是两种比较典型的方法o ：。为了 解决如何表示并发和同步的问题，必须研制出适当的并发程序表示方法。当然，与并发和同步无 关的语句可用c f g 直接表示出来。 c f gj l - - 比较通用的顺序程序袭示方法，由于并发程序执行的不确定性，一般的c f g 很) f ；直 接应用到并发程序中玄这是因为：第一，按照c f g 的定义，若一个语句s 。执行后可能立即执 行s 2 ，则边 将被包含在c f g 叶1 ，这会导致c f g 的边太多( 指数级) ：第二，判定一个浯句 s ；执行后是甭能够执行s 2 也非常困难。 p e l r i 网是一种非常有效的并发程序表示方法，在死锁检测、可并行性及冲突分析等方面得到 r 较广泛的应用。当用p e t r i 刚表示程序时，每个语句一般别应一个库所和一个变迂，顺序程序的 p e t r i 叫表示与c f g 摹本一致。虽然p e t r i 网是一种分析并发和同步的较好的方法，但它的表示太 复杂。并且基于p e t r i 网的各种分析方法效率都比较低( 大部分是指数级) ，因此p e t r i 删很少直接 用于程序表示。 由于我们分析的重点是在并发程序的执行和进程间的通信行为，所以采用一利，简单方便的方 法构造并发程序控制流图( c c f g ) i l ”：在普通c f g 的基础上，增加同步事什节点和并发边描 述进程间的同步与通信，对于程序中与同步和通信无关的部分则d i 使用各个进程原有的c f g 。 罔2 6 描述r 包含二个进程的并发程序的c c f g ( 为了简洁省略了与并发和通信无关的其它 内容) 。其中，节点表示符进程中的同步事件( 对十基于消息传递机制的并发程序，同步事件定 义为潲息的发送年接收琊件) ：啡个虚线方榧表示一个独立的进程。 东南大学硕l学伯沦文 圈2 6 r c f g 儿圳 9 + 通f 7 边 争 舟川流 朱南人学硕 第三章不确定性的消除 在调试和测试顺序程序时，程序员一般采取循环调试的，疗法，即以相同的输入反复执行籽序， 借助断点和监测点观察程序的运行，从而定位错谋。第二章中已经介绍了州发程序执行具有不确 定性，这种不确定性导致了错误的不可再现性，使得传统的循环调试方法对于并菽鞋序的蛹试失 敛。为了解决这个 、j 题，通常的方法是在循环调试中辅以柴种机制币肌并发程序的某玖执行情况 这种方法称为追踪和重演机制。本章将介绍一种优化的追踪和重演的算法，以消除程序的不确定 性我们的模型针对进程问以消息传递机制进行通信的并发程序。 追踪和重演的机制是觯决调试阶段井发稃序不确定性的仃效地手段，它分为两个阶段：追踪 阶段，在程序的原始执仟中记录必要的执行信息；重演阶段，按照追踪刚已录的信息强制程序的 后续执行重现程序的原始执行情况。 在实际应用中，该算法的关键在于确定追踪阶段必须记录哪此信息、。一方而，为了保证重演 的执彳亍真实地再现原始程序，需要记录下充分的信息；兄一方面，为，避免探针效应p r o b e e f f e c t ) ， 要尽町能地压缩时空开销。如粜追踪记录的信息过多，除了时间花费大以外，还会对h 标秆序 的执行和调度产生难以消除的十扰。除了我们所关心的坛有的并发程序本身会产牛不确定性，通 过插装的追踪程序也会对目标程序的执行产生影响，这种情况称为探针效应。探针效应是不能够 完全避免的但算法时间消耗越人，探针效应越明显。对十宅间而再，为了适应较长的大掣的并 发程序，必须精简追踪文件，因为记录的信息和要执行的并发程序共用内外存空问，随着目标程 序的运行，记录的信扈、越来越多，会在很人程度上影响并，垃程序本身的执行，增加系统的运行负 担。所以我们的算法庄时间和空间r 都必须力求最优，奉章r 一消除不确定性的算法的口标就是 在保证重演和原始执行致的前提下，尽可能地减少追踪的信息以控制n t 空消耗。e l e u 和a s c h i p e r 给出了，重演执行的一致性( e q u i v a l e n te x e e u ，i o n ，的定义”： 个进程的执行是一致的当且仅当这个进程在两次执行中从其它进程所获得的信息部丰玎同。 迸衙，对于一个程序j m 言，只要它所包含的每个进程的执行部保持一