（计算机软件与理论专业论文）多线程程序中数据竞争故障的动态检测技术研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 随着支持多线程技术的操作系统与多核处理器技术的普及，多线程技术不再是 一个很遥远的话题。我们在享受着m i c r o s o t ! tw o r d 编写文档与n e t s c a p ef i r e f o x 浏览 网页带来便利的同时，也希望构造自己的多线程应用，但是多线程程序设计相对传 统的程序设计而言还是很困难并且容易出错。在多线程程序设计中，很容易因为没 有使用同步保护机制从而导致产生数据竞争故障，但是该故障很难通过一两次运行 程序而发现，并且纵使发现有数据竞争故障，针对该故障的调试信息也非常难以获 取。因此，研究如何有效的检测多线程程序中数据竞争故障并根据被测程序的实际 情况给予程序设计人员有效的故障信息，是一个非常值得研究的问题。 目前，有很多专家学者在数据竞争故障的检测方面做出了不少工作，其中利用 l o c k s e t 算法来检测数据竞争故障是该领域的主流做法，因而从l o c k s e t 算法派生出 r a c e r 算法、g o o d l o c k 算法等。由于基于l o c k s e t 算法的检测是采用了动态测试方法， 即需要运行待测程序，所以本文引入面向方面编程技术( a o p ，a s p e c to r i e n t e d p r o g r a m m i n g ) ，对待测程序设置切入点来在线监测待测程序的运行状态，通过切入 点能够更为准确的获取待测程序运行时的现场数据，并通过定义多线程程序变量状 态图和变量集合用于对l o c k s e t 算法进行有效的补充，在此基础上提出了基于变量状 态图与锁集的数据竞争故障动态检测算法，并通过该算法对数据竞争故障进行了有 效检测。本文的主要工作如下： ( 1 ) 研究了面向方面编程技术在程序动态测试中的应用 研究了面向方面编程技术的原理、特点与功能，特别是面向方面编程技术中的 切入点设置问题，包括针对待测方法的切入点以及对变量的构造函数切入点的设置 问题，以及在程序动态检测中的应用方式。 ( 2 ) 基于l o c k s e t 算法的数据竞争故障检测方法的研究 针对l o c k s e t 算法所存在的问题，定义了一种用于描述多线程程序中变量状态的 变量状态图和记录程序运行时变量的变量集合，通过变量状态图使原有l o c k s e t 检测 算法降低误报率，通过变量集合使原有l o c k s e t 检测算法支持运行时期的变量分配， 即动态内存交量，在此基础上提出基于变量状态图与锁集的数据竞争故障动态检测 算法。该算法减少了误报情况的发生，使检测更为有效。给出了多线程程序中数据 竞争故障动态检测的系统框架。 硕士学位论文 m a s t e r st h e s i s ( 3 ) 实验验证与结果分析 利用a s p e c t j 完成对待测程序的切入点设置与运行事件获取工作，利用j a v a 和 a s p c c t j 实现了多线程程序中数据竞争故障检测系统原型。以多线程程序访问变量 ( 包括读写操作) 为例，使用本文提出的多线程数据竞争故障检测方法进行了实验， 发现该方法较之l o c k s e t 算法减少了误报的情况，使检测更为有效，并且提供了 l o e k s e t 算法所不能提供的故障现场信息。 关键词：数据竞争；面向方面编程：变量状态图；变量集合；l o c k s e t 算法；动态 检测 项士学位论文 m a s t e r st h e s i s a b s t r a c t w i t ht h e s u p p o r to fm u l t i - t h r e a d e do p e r a t i n gs y s t e ma n dt h ep o p u l a r i t yo f m u l t i - c o r ep r o c e s s o rt e c h n o l o g y , m u l t i - t h r e a d i n gt e c h n o l o g yi sn ol o n g e rt h es u b j e c to fa v e r yd i s t a n t w ee n j o yt h ec o n v e n i e n c et h a tw r i t i n g 、航t 1 1m i c r o s o f tw o r do rb r o w s i n gb y n e t s e a p ef i r e f o x ，b u t a l s ow a n tt ob u i l dt h e i rm u l t i - t h r e a d e d a p p l i c a t i o n s ，b u t m u l t i t h r e a d e dp r o g r a m m i n gi sr e l a t i v e l yt r a d i t i o n a lp r o g r a m m i n gd e s i g nw h i c hi ss t i l l v e r yd i f f i c u l ta n de r r o r - p r o n e i nm u l t i - t h r e a d e dp r o g r a m m i n g ，i ti se a s yt or i s eb e c a u s e t h e r ei sn op r o t e c t i o nm e c h a n i s mi no r d e rt os y n c h r o n i z et h ed a t al e a dt od a t er a c ef a u l t , h o w e v e r ，t h ef a u l ti sd i f f i c u l tt or u nt h r o u g ho n eo rt w ot i m e sa n df o u n d , a n de v e ni ft h e f a u l th a sb e e nf o u n d , t h ed e b u gi n f o r m a t i o nf o rt h ef a u l ti sa l s ov e r yd i f f i c u l tt oo b t a i n t h e r e f o r e ，s t u d y i n g h o wt o e f f e c t i v e l y t e s tm u l t i - t h r e a d e d p r o g r a ma n dg i v e p r o g r a m m e r se f f e c t i v ef a u l ti n f o r m a t i o ni sav e r yw o r t h w h i l er e s e a r c h a tp r e s e n t , t h e r ea r em a n ye x p e r t sa n ds c h o l a r sm a k eal o to fw o r ki nd e t e c t i o no f d a t ar a c ef a u l t , l o c k s e ta l g o r i t h mw h i c hu s et od e t e c td a t ar a c ef a u l ti nt h em a i n s t r e a mo f p r a c t i c e ，w h i c hd e r i v e df i o mt h e l o c k s e ta l g o r i t h ms u c h 嬲r a c e ra l g o r i t h ma n d g o o d l o c ka l g o r i t h m a sar e s u l to fl o c k s e t - b a s e dd e t e c t i o na l g o r i t h mu s ed y n a m i ct e s t i n g m e t h o d s , w h i c hh e e dt or u nt h et e s tp r o g r a m , t h e r e f o r e ，t h i sp a p e ri n t r o d u c e st h e t e c h n i c a la s p e c t - o r i e n t e dp r o g r a m m i n g ( a o p , a s p e c to r i e n t e dp r o g r a m m i n g ) ，t r e a t m e n t o ft e s tp r o g r a mt os e tu pt h ep o i n t c u tf o ro n l i n em o n i t o r i n gt h et e s tp r o g r a m ss t a t ea n d t h r o u g ht h ep o i n t c u tt om o r ea c c u r a t eg a i nr t m - t i m ed a t a d e f i n i n gt h ev a r i a b l es t a t e g r a p h i ca n dv a r i a b l es e tf o rt h el o c k s e ta l g o r i t h me f f e c t i v e l ys u p p l e m e n ta n dd e s i g n i n g t h ev a r i a b l es a t eg r a p h i ca n dl o c k s e tb a s e dd y n a m i cd a t ai v ef a u l td e t e c t i o na l g o r i t h m n l em a i nw o r ki sa sf o l l o w s ： ( 1 ) t h er e s e a r c ho nt h ea o pt e c h n o l o g yi nt h ep r o c e s so fd y n a m i ct e s t i n g r e s e a r c ho nt h ea o pt e c h n i q u e ss u c h 笛i t sp r i n c i p l e s ，c h a r a c t e r i s t i c sa n df u n c t i o n s ， e s p e c i a l l yt h et e c h n i c a li n t h es e t t i n gu pp o i n t c u t , i n c l u d i n gs e t t i n gu pp o i n t e u to n m e t h o d so rv a r i a b l e sc o n s t r u c t o r , a sw e l la sd y n a m i ct e s t i n gp r o c e d u r e sa p p l i e di ns u c h al l l a n n e r ( 2 ) t h er e s e a r c ho nl o c k s e tb a s e dd y n a m i cd a t ar a c ef a u l td e t e c t i o na l g o r i t h m d e f i n i t i o no fv a r i a b l es e ta n dv a r i a b l es t a t eg r a p h i c ，t h r o u g ht h ev a r i a b l es e ts ot h a t t h eo r i g i n a ld e t e c t i o na l g o r i t h mt os u p p o r tt h ed e t e c t i o no ft h ev a r i a b l ea s s i g n m e n ta tr u n t i m ew h i c hi sd y n a m i cm e m o r y v a r i a b l e s ，t h r o u g ht h ev a r i a b l es t a t eg r a p h i cs ot h a tt h e o r i g i n a ld e t e c t i o na l g o r i t h mt or e d u c ef a k ea l a r mr a t e , o nt h eb a s i so fv a r i a b l es t a t e g r a p h i ca n dv a r i a b l es e t ，t h i sp a p e rd e s i g n e dt h ev a r i a b l es a t eg r a p h i ca n dl o c k s e tb a s e d 硕士学位论文 l v i a s t e r st h e s i s d y n a i n i cd a t ar a c ef a u l td e t e c t i o na l g o r i t h m t i i i sa l g o r i t h mr e d u c e dt h eo c c u r r e n c eo f f a k ea l a r m ，s ot h a tm o r ee f f e c t i v ed e t e c t i o n g i v e nt h em u l t i - t h r e a d 酣p r o g r a md y n a m i c d a t ar a c ef a u l td e t e c t i o ns y s t e mf r a m e w o r k ( 3 ) e x p e r i m e n t a lv e r i f i c a t i o na n da n a l y s i s u s ea s p e c ot oc o m p l e t et h es e t t i n gu pp o i n t c u to nt e s tp r o g r a ma n dr e c e i v i n gt h e e v e n tb yp o i n t c u t , u s i n go fj a v aa n da s p e e t jt oa c h i e v eam u l t i - t h r e a d e dd a t an 猕f a u l t d e t e c t i o ns y s t e mp r o t o t y p e m u l t i - t h r e a d e d 扯c e s st ov a r i a b l e s ( i n c l u d i n gr e a da n dw r i t e o p e r a t i o n s ) a sa ne x a m p l e , t h em e t h o du s e di nt h i sp a p e rw h i c hi sm u l t i - t h r e a d e dd a t a r a c ed e t e c t i o nm e t h o dt h r o u g he x p e r i m e n t st h a tf o u n dt h em e t h o dc o m p a r e d 、撕吐i o r i g i n a ll o c k s e ta l g o r i t h mt h a tar e d u c t i o no ff a k ea l a r m , m a k i n gd e t e c t i o nm o r ee f f e c t i v e ， a n dp r o v i d e dt h eo r i g i n a ll o c k s e ta l g o r i t h mc a nn o tp r o v i d ei n f o r m a t i o no nt h ef a u l ta t t h es c e n e k e yw o r d s ：d a t ar a c e ；a s p e c t - o r i e n t e dp r o g r a m m i n g ；v a r i a b l es t a t eg r a p h i c ； v a r i a b l es e t ；l o c k s e ta l g o r i t h m ；d y n a m i cd e t e c t i o n 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：魂月鸭日期：2 。彳年 ，记作s i g n a t u r e ，且有s i g n a t u r e p a t h 。 定义4 2多线程程序执行路径表示时序基础上的一组签名，记作p a t h ，则有 p a t h = s i g n a t u r e l ，s i g n a t u r e 2 7 ，s i g n a t u r e n ) ，其中由1 到n 的下标代表着时间的 前进，也就是s i g n a t u r e l 产生早于s i g n a t u r e 2 ，s i g n a t u r e n 为路径p a t h 中最后一个签 名。 通过如图4 2 所示的多线程程序运行示例说明上述概念。 时间点 l 2 3 4 5 6 7 8 t h r e a d 3 o 呦e d l m e t h d l ( ) l o b j e c t 2 m e t l l o d 2 ( 5 ) 。 ， o b j e e t 3 m e t h o d 3 ( “d o ”) ： o b j e c t l m e t i l d l ( ) ； 。：_ o b j e c t 2 m e t h o d 2 ( 7 ) ： 、_ o b j e c t 2 m e t l l o d 2 ( 1 0 ) l l o b j e c t l m e t h d l ( ) ： ， 图4 2 多线程程序运行示例 在垂直方向上，时间点由l 到8 的过程代表了时间的前进，水平方向上t h r e a d l 到t h r e a d 3 代表了多线程程序中不同的线程，例如，在时间点l 处程序执行状态的 具体含义是，纵坐标代表的是整个程序执行的时间点，由于时序具有不可逆且唯一 性，因而在时间点l 仅有一个线程出于运行状态( 图4 2 中为t h r e a d l ) ，在时间点 1 与t h r e a d l 的交点处存在“o b j e e t l m e t h o d l ( ) ：”语句，该语句表示被t h r e a d l 通过 调用o b j e e t l 上的方法m e t h o d l 来访问的对象o b j e c t l ，而方法m e t h o d l 不需要传入 参数，并且仅代表对方法m e t h o d l 的调用，并不表示直到m e t h o d l 方法完成后程序 才继续执行。 硕士学位论文 m a s t e r st h e s i s 根据定义4 1 ，上述线程与对象调用关系，即签名可以描述为 ”，其中t h r e a d l 表示签名中的运行线程，o b j e c t l 表示被线程访问的对 象，m e t h o d l 表示被调用的方法，n u l l 代表空值( 方法是无参形式的) 。因此该示例 中的程序运行过程可以用表4 1 所示的签名集合描述。 表4 1 示例程序签名集合描述 签名名称签名描述 s i g n a t u r e l s i g n a t u r e 2 s i g n a t u r e 3 s i g n a t u r e , , s i g n a t u r e 5 s i g n a t u r e 6 s i g n a t u r e 7 s i g n a t u r e s 由于时序的不可逆性，由签名s i g n a t u r e l 到签名s i g n a t u r e s 是随着时间前进而发 生的，根据定义4 2 上述示例程序中的执行路径可以表示为：p a t h = s i g n a t u r c l ， s i g n a t u r e 2 ，s i g n a t u r e 3 ，s i g n a t u r e 4 ，s i g n a t u r e s ，s i g n a t u r e 6 , s i g n a t u r e 7 ，s i g n a t u r e s ， 其中p a t h 中的签名s i g n a t u r e 顺序遵循时间顺序，s i g n a t u r e l 最先发生而结束于 s i g n a t u r e s 由定义4 1 和定义4 2 可以推知： 性质4 1 签名s i g n a t u r e 具有唯一性，即每个签名s i g n a t u r e 在整个程序的运 行过程中仅出现一次。 证明：( 反证法) 假设在整个程序的运行过程中存在两个相同的s i g n a t u r e ，则表 明程序在运行过程中，在一个特定时刻同时存在两个相同的线程访问两个相同的对 象，而这与线程调度机制( 一个时刻仅有一个线程处于运行状态) 相矛盾，从而可 知签名s i g n a t u r e 具有唯一性，所以性质4 1 得证。 性质4 2多线程程序执行路径p a t h 中所包含的签名s i g n a t u r e 具有有序性。 证明：在任意给定的一条多线程程序执行路径p a t h 中，签名s i g n a t u r e 的发生是 遵循时序的，也就是说是按照时间上事件发生先后顺序来排列的，可以看出路径p a t h 中的签名s i g n a t u r e 具有有序性，且排序的依据为签名s i g n a t u r e 发生时间，所以性 质4 2 得证。 硕士学位论文 m a s t e r st h e s i s 4 3 基于面向方面编程的多线程程序执行路径跟踪算法 4 3 1 算法的基本思想 基于面向方面编程的多线程程序执行路径跟踪算法主要包括两个步骤( 设置切 入点和生成的签名s i g n a t u r e 并加入到路径p a t h ) ，下面分别对两个步骤进行描述： ( 1 ) 设置多线程程序的切入点 利用面向方面编程技术对多线程程序设置切入点，因为切入点的设置直接关系到签 名s i g n a t u r e 以及p a t h 的产生，而二者是否能够完整的包括了定义4 1 与定义4 2 中 所要求的信息直接关系到后续的数据竞争故障检测工作，所以切入点的设置工作是 该算法的先导工作，本文按照如下步骤设置切入点： 获取多线程程序中类的信息，主要是方法信息：通过观察多线程程序中类的 源代码或者阅读源代码对应的a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) 文档来获取 类的方法信息，主要包括了方法的名称和参数类型以及个数( 如果是无参方法，则 为n u l l ) ； 在类中每个方法上设置切入点：利用面向方面编程技术，在类中每个方法上 设置切入点； 设置b e f o r e 通知：针对每个切入点设置b e f o r e 通知，通过第二章的介绍， b e f o r e 通知是在进入方法体后但在方法正文执行前执行的操作，由于签名s i g n a t u r e 仅表示方法调用信息，并不包含方法的正文完成时间，因而在设置的b e f o r e 通知中， 需要获取执行该方法的线程信息、线程访问的对象信息、方法名称信息以及传入该 方法的相关参数信息。 硕士学位论文 m a s t e r st h e s i s 切, k , 点p o i n t c u t 设置b e f o r e 通 知，获取线 程信息，线 程访问对象 信息，方法 名称信息以 及方法参数 信息，并返 回一个签名 s i g n a t u r e 对象 图4 3 切入点设置示例 如图4 3 所示，类x 中的一个切入点设置为 v o i dm e t h o d ( i n ti ) ”( 类x 中所 有的方法均被设置为切入点) ，按照上述步骤：设置b e f o r e 通知，当b e f o r e 通知执 行后，获取了执行该方法的线程信息、。线程访问的对象信息、方法名称信息以及传 入该方法的相关参数信息，该示例中线程信息为线程的名称“t h r e a d a ”，而对象信 息为类的名称x 和对象标识符的组合 x x o b j ”，该组合亦表示变量地址，方法名 称为m e t h o d 而方法参数信息为传入方法的整型变量“5 。 ( 2 ) 生成的签名s i g n a t u r e 并加入到路径p a t h 在步骤( 1 ) 完成的基础上，首先依据b e f o r e 通知获取的信息生成签名s i g n a t u r e ， 然后将签名加入到多线程程序执行路径p a t h 中去。 如图4 3 所示，在b e f o r e 通知完成之后生成的签名s i g n a t u r e 为“ ”，然后将签名s i g n a t u r e 加入路径p a t h 。 4 3 2 算法描述 基于面向方面编程的多线程程序执行路径跟踪算法描述如图4 4 所示。 图4 4 基于面向方面编程的多线程程序执行路径跟踪算法 该算法需要用到两个数据结构，即s i g n a t u r e 和p a t h , 其中p a t h 采用链表的方式 存贮s i g n a t u r e 从而满足高速产生的s i g n a t u r e 快速插入的需求，对s i g n a t u r e 和p a t h 的j a v a 代码描述如图4 5 所示。 图4 5 签名s i g n a t u r e 和路径p a t h 的描述 硕士学位论文 【a s t e r st h e s i s 上述算法主要是对程序设置切入点后在线监视程序的方法调用，如果不考虑 b e f o r e 获取信息、签名s i g n a t u r e 生成以及路径p a t h 初始化的时间，该算法的主要 开销在于将高速产生的签名s i g n a t u r e 加入路径p a t h ，由于p a t h 采用链表的方式存 贮签名s i g n a t u r e ，故算法的时间复杂度为o ( n ) ，其中1 1 为签名s i g n a t u r e 的数量， 也就是程序中方法调用的个数。 4 4 实验验证 首先，给出待关注的程序代码，如图4 6 所示。 图4 6 待关注的程序代码 通过观察发现，v a l u e 类中包含两个方法，即g e t v a l u e 方法和s e t v a l u e 方法，其 中s e t v a l u e 方法需要一个s t r i n g ( 字符串) 类型的参数。 其次，为待关注的方法编写方面( a s p e c t ) ，在第二章中已经介绍过，方面包含 了切入点、通知和引用等面向方面编程中的元素，因而在针对图4 6 中待关注程序 的方面包含了两个方法( g e t v a l u e 和s e t v a l u e ) 的切入点和针对切入点的b e f o r e 通 知。 v a l u e 类的方面a s p e c t v a l u e ( 基于a s p e c t j 实现) 如图4 7 所示，其中a s p e c t 、 p o i n t c u t 、c a l l 和b e f o r e 均为a s p e c o 内置关键字，其相对应的意义在第二章中已经 介绍，这里不再赘述。 图4 7v a l u e 类的方面a s p e c t v a l u e 再次，需要线程类完成对类v a l u e 所初始化的对象进行访问，为了简单起见， 我们采用两个线程同时访问两个对象的方式来进行实验。两个线程类分别为 对t h r e a d 0 进行了相应描述，而t h r e a d l 只是将t h r e a d 0 中语句 v s e t v a l u e ( “ia mt h r e a d 0 ”) ”改为了 v s e t v a l u e ( “ia mt h r e a d l ”) ”。 3 1 最后，相对应的测试代码和结果( 在线生成的路径) 如图4 9 所示。 圈49 测试代码和在线生成的程序执行路径 如图49 所示，线程t h r e m d o 和线程t n r e a d l 总共调用了2 0 次方法，其中每个 线程各1 0 次，即每个线程分别调用5 次g e t v a l u e 方法和s e t v a l u e 方法。在运行结果 中，每一行代表了一个签名s i g n a t u r e 。可以看出，线程调度器在调度线程时是按照 随机顺序，而这2 0 个s i g n a t u r e 完整的反映了程序的执行路径，实验结果表明算法 成功的生成了多线程程序执行路径。 4 5 小结 本章在结合面向方面编程技术的基础上，定义了描述多线程程序调用关系的签 名s i g n a t u r e 和程序执行路径p a t h 两个概念，着重讨论了基于面向方面编程的多线 程程序执行路径跟踪算法，并对算法的时间复杂度进行了分析，最后通过实验验证 了算法的可行性和有效性。由本章描述的算法所在线生成的签名s i g n a t u r e 将被用于 后续的多线程程序的数据竞争故障检测工作中去。 第五章基于变量状态图与锁集的数据竞争故障动态检测方法 5 1 引言 在线获取多线程程序执行路径后，该路径便可以用于检测程序中的数据竞争 故障。传统的l o c k s e t 算法不支持动态变量而且误报较高，原因在于：( 1 ) l o c k s e t 算法的起始条件过于严格，该算法需要在程序未执行时通过静态分析获取所有的变 量信息；( 2 ) 数据竞争故障的判定准则过于简单。针对上述缺点，本章所要解决的 问题有如下3 个： ( 1 ) 针对现行程序( c c + + 、j a v a ) 的动态变量分配，如何有效的检测动态变 量的数据竞争故障； ( 2 ) 针对传统的l o c k s e t 算法误报较高的缺陷，如何通过使用有效的手段减少 l o c k s e t 算法的误报情况； ( 3 ) 在检测出数据竞争故障后，能否提供有效的现场信息，从而方便开发人员 调试。 在第二章中讨论了常用的几种多线程数据竞争故障动态检测技术( h o a r e 的监 视器原则、h a p p e n s b e f o r e 关系和l o c k s e t 算法) ，有了以下认识： ( 1 ) 检测算法是否支持动态变量，监视器原则和l o c k s e t 算法均不支持动态变 量的数据竞争故障检测，但它们( 尤其是l o c k s e t ) 的检测效率很高； ( 2 ) 检测算法的判定准则是否充分，以l o c k s e t 算法为例，该算法对多个线程 对变量的读取也视为对变量的访问( 写入) ，从而造成误报； ( 3 ) 检测算法是否依赖于线程的交错，基于h a p p e n s b e f o r e 关系的检测算法均 需要依赖于线程调度器制造的交错，从而导致需要大量的测试用例。 本章在l o c k s e t 算法的基础上，定义了多线程程序中变量的状态图，并在此基础 上提出了基于变量状态图与锁集的数据竞争故障动态检测算法，该算法利用状态图 中的状态迁移使检测算法的判定准则更为充分，并利用面向方面编程技术对变量的 构造函数设置切入点，从而使检测算法能够对动态分配的变量进行数据竞争故障检 测，最后通过实验验证算法的可行性。 硕士学位论文 m a s t e r st h e s i $ 5 2 基于变量状态图与锁集的数据竞争故障动态检测方法基础 5 2 1 变量状态图 第二章中的l o e k s e t 算法，详细的定义了多线程程序产生数据竞争故障的必备条 件，即当两个( 包含两个以上的线程) 线程对变量进行访问时( 1 ) 至少一个线程 对变量的访问是写入；( 2 ) 没有采用显示机制防止线程对变量的同时访问。由必备 条件可以知道，对于访问( 对变量的方法调用) 分为写入和读取两种类型，并且访 问能够给变量加锁( 在j a v a 中，通过s y n c h r o n i z e d 关键字来同步方法) 。 定义5 1访问( a c c e s s ) 表示变量方法的调用，在多线程程序中方法的调用 包含了两个属性：同步和读写。其中，同步属性表示该方法是否在执行时获取变量 的锁，而读写属性表示该方法是否在执行时改变了变量的值。 根据定义5 1 可知，访问被分为四种类型：同步写访问、同步读访问、非同步 写访问和非同步读访问，相关描述如表5 1 所示。 表5 1 四种类型访问及其描述 访问类型描述 同步写访问该方法调用时获取变量的锁，执行完成后更改了变量的值 同步读访问该方法调用时获取变量的锁，执行完成后变量的值未更改 非同步写访问调用该方法时不获取变量的锁，执行完成后更改了变量的值 非同步读访问调用该方法时不获取变量的锁，执行完成后变量的值未更改 由于变量的创建是在线程中进行，本文将创建一个变量的线程，称之为这个变 量的创建线程，而这个变量一旦创建，除了创建线程以外的其它访问线程均称之为 该变量的访问线程，如图5 1 中的示例描述了访问、创建线程以及访问线程等上述 概念。 3 5 硕士学位论文 i 旺a s t e r st h e s i s v a l u e v - n e w v a l u e ( ) i j v s e t v a l u c ( 。m a i n ”) ： j v s c t v a l u e ( 。t h r e a d l ”) j v a l u e j a v a v a l u e s t r i n gv ： p u b l i cs y n c h r o n i z e dv o i ds e t v a l u e ( s t r i n gs ) v = s ： ) p u b l i cs t r i n gg e t v a l u e ( ) r e t u r nv ： 】 图5 1 多线程程序示例 如图5 1 所示，示例中描述了3 个线程( m a i n 、t h r e a d l 和t h r e a c l 2 ) 对类型为 v a l u e 的变量v 进行访问，其中，m a i n 线程为变量v 的创建线程，而t h r e a d l 和t h r e a d 2 为变量v 的访问线程。对于所有的方法调用，如 v s e t v a l u e ( “m a i l l ) ”，根据定义 5 1 均为访问( a c c e s s ) ，又因为访问存在4 中类型，所以示例中不同的访问类型如 表5 2 所示。 表5 2 示例中各访问及其类型 访问访问类型 m a i n 线程中的 v s e t v a l u e ( m a i n ) ”同步写访问 m a i n 线程中的 v g e t v a l u e ( ) ”非同步读访问 t h r e a d l 线程中的 v g e t v a l u e ( ) ” 非同步读访问 t h r e a d l 线程中的 v s e t v a l u e ( t h r e a d l ) ”同步写访问 t h r e a d 2 线程中的 v g e t v a l u e ( ) ”非同步读访问 在传统的单线程程序中，变量只可能被一个线程所访问，从而不会发生数据竞 争故障。但是在多线程程序中，存在多个线程对一个变量访问的可能，但是在这种 多个线程同时访问一个变量的环境中，也分为如下5 种情况： ( 1 ) 创建线程对变量的读访问：创建线程在创建了变量后，对变量进行读访问 ( 包括同步读访问和非同步读访问) ，在这种情况下，变量的值是被一个线程所访 问的，因而不会出现数据竞争故障； ( 2 ) 创建线程对变量的写访问：创建线程在创建了变量后，对变量进行写访问 ( 包括同步写访问和非同步写访问) ，在这种情况下，变量的值是被一个线程所访 问的，因而不会出现数据竞争故障； ( 3 ) 访问线程对变量的读访问：变量在创建以后，访问线程对变量进行读访问 ( 包括同步读访问和同步写访问) ，在这种情况下，变量的值虽然被多个线程所访 问，但是值没有改变，因而不会出现数据竞争故障； ( 4 ) 访问线程对变量的同步写访问：变量在创建以后，访问线程对变量进行同 步写访问，在这种情况下，变量的锁被该方法获得，根据定义2 2 ，由于锁具有排 他性，从而导致其他访问线程和创建线程均不能访问该变量，当写访问结束后，该 访问线程才释放变量的锁。当变量的所有写访问均为同步写访问时，不会出现数据 竞争故障，反之，即变量的所有写访问不全是同步写访问时，有可能出现数据竞争 故障，原因在于变量的一个同步写访问能够防止其他的同步写访问并发运行( 利用 锁机制) ，但是无法防止非同步写访问并发运行； ( 5 ) 访问线程对变量的非同步写访问：变量在创建以后，访问线程对变量进行 非同步写访问，在这种情况下，变量不能依靠锁来防止被并发访问，从而可能出现 数据竞争故障。 可以看出，在多线程访问变量的情况下，线程和变量之间的关系使得原本在单 线程程序中简单的调用关系变得有些复杂，这也是数据竞争故障难以检测的原因之 一。如上述的5 种情况，在多个线程对变量进行写访问时可能发生数据竞争故障， 因而本文定义了一种多线程程序中变量的状态图，该状态图能够用来描述变量在多 线程程序中的生命周期，这使得变量状态图不仅能够帮助检测数据竞争故障，还能 够在检测出数据竞争故障时给出变量的状态，从而提供给开发人员有用的调试信 息。 定义5 2变量是程序在内存中分配的空间( j a v a 语言通过 n e w 关键字来分 配空间) ，记作v a r i a b l e ，该空间通过类中定义的方法来访问( 包括读写访问) ，并 且在内存中的变量拥有一系列的状态，变量从创建到回收之前的所有状态迁移均记 录在变量的状态列表v a r i a b l e s t a t e l i s t 中，所有变量的访问均记录在访问列表 v a r i a b l e a e c e s s l i s t 中。 定义5 3变量状态表示在多线程程序中，变量从分配内存空间开始所具有的 普遍表示形态，本文将多线程程序中的变量状态定义为以下4 种：创建线程独占状 态、创建线程访问状态、线程间共享读取状态和线程间共享访问状态。 变量状态从变量分配内存空间开始一直到变量处于上述4 种状态为止，包含了 3 7 硕士学位论文 m a s t e r st h e s i s 多线程程序中变量的生命周期( 创建、运行和回收，上述的4 种状态不包括回收， 原因在于变量在回收时不会发生数据竞争故障，并且j a v a 语言不支持显式的内存 析构) ，上述定义中的4 种变量状态及其描述如表5 3 所示。 表5 3 变量的4 种状态及其描述 变量状态名称描述 创建线程独占状态创建线程创建变量后，变量所处的状态。处于该状态 ( c r e a t e a d o w n )的变量只被创建线程所拥有，和单线程程序一样，因 而不会出现数据竞争故障。 创建线程访问状态创建线程访问( 包括同步读写访问和非同步读访问) ( c r e a t e l l ：l r e a d a e c e s s )变量后，变量所处的状态。处于该状态的变量虽然被 访问，但是如同在单线程程序中一样，顺序的访问不 会造成变量的值不一致的情况发生，因而不会出现数 据竞争故障。 线程间共享读取状态访问线程读访问( 包括同步读访问和非同步读访问) ( r e a d b e t w e e n m a d s )变量后，变量所处的状态。处于该状态的变量已经被 多个线程( 创建线程和访问线程) 所访问，但是访问 线程的访问只是读访问，即不会更改变量的值，因而 不会出现数据竞争故障。 线程间共享访问状态访问线程写访问( 包括同步写访问和非同步写访问) ( a e e e s s b e t w e e n t h r e a d s )变量后，变量所处的状态。处于该状态的变量的值已 经被多个线程( 创建线程和访问线程) 所更改，有可 能出现变量的值不一致的情况，因而有可能出现数据 竞争故障。 定义5 4变量状态图表示变量从被分配内存空间开始到被回收之间的运行 状