虚拟时间及其在数据竞争检测中的应用

禹 振，苏小红，王甜甜，马培军

(哈尔滨工业大学 计算机科学与技术学院，150001哈尔滨)

虚拟时间能精确刻画并发事件的发生顺序，为并发计算的性质分析［1］、缺陷检测［2］和故障恢复与调试［3］奠定基础，因此无论在非共享内存的分布式系统还是共享内存的多核/多处理器并发系统中都得到了广泛应用.

虚拟时间起源于分布式系统.与内存分离的分布式系统不同，共享内存的多线程并发系统容易遭遇数据竞争［4-5］，即对某一共享内存单元，存在来自不同线程的2个无序访问，且有1个为写访问.检测数据竞争的关键在于检测对共享内存单元的2个访问是否是无序的.虚拟时间可以为内存访问事件分配时钟，从而2个访问之间的顺序关系能通过比较时钟获得.

现已有针对不同应用场景的多种时钟机制.本文略去各种时钟机制的应用背景，将它们统称为虚拟时间;建立抽象的分布式执行模型，统一描述虚拟时间的3种基本实现形式及相关优化与改进技术;讨论将虚拟时间应用到共享内存并发系统的数据竞争检测中需要解决的关键问题，并以4个应用实例为例展示基于虚拟时间的数据竞争检测系统的时钟分配和竞争检测机制.

1 问题描述

图1所示的分布式系统由3台异构计算机组成，每个计算机上运行一个进程，进程之间消息的下标表示消息发生的顺序.在分布式系统中，由于时钟震荡频率不同，不同处理器在同一时间的机器时间可能不同，而在不同时间的机器时间又可能相同，这就导致难以为不同处理器或者进程中发生的事件确定相对顺序.例如，假设图1中进程p1、p2和p3各自所在机器的震荡频率分别为6、8和10，则基于局部时钟的通信图如图2所示．其中当p3给p2发送消息msg3时，由于p2的时钟走的比p3的慢，所以接收到msg3时，本机的时钟56比msg3附带的发送时钟60小．这是不合理的，因为事件的接收时间应迟于其发送时间．

图1 分布式系统示例

图2 局部时钟的通信图

为解决这一问题，研究者们提出虚拟时间［6-11］，又称逻辑时间，作为分布式系统的全局时间，使得系统中的事件可以通过比较其发生时被赋予的时钟来确定事件的先后顺序.

2 模型与概念

一个分布式计算，即分布式程序，由n个异步执行的进程p1，p2，…，pi，…，pn构成．每个进程执行3类操作:发送消息、接收消息和本地计算．进程之间由通信网络互连、不共享内存、只通过传递消息进行通信．

定义1(分布式执行的抽象模型) 单个进程pi(1≤i≤n)的执行产生事件序列中的事件具有自然序，即事件按照其发生时的顺序构成全序关系．整个分布式计算的执行对应的事件集合E={e|e∈E(pi)，i=1，2，…，n}，事件之间的顺序关系由happens-before［10］描述．

对于任意的事件e∈E，Dsp(e)表示事件e的进程号，Usp(e，Dsp(e))表示事件e在事件序列E(pDsp(e))中的序号．假如事件是消息发送操作，则其发送的消息表示为msg对于任意消息表示进程pi发送的操作，表示进程pj接收进程pi发送的的操作．本文定义happens-before关系来为E中事件排序.

定义2(happens-before关系)对于事件ε，ω∈E，ε和ω具有happens-before(简称hb)关系，记为ε→ω，当且仅当:1)Dsp(ε)=Dsp(ω)=i，且Usp(ε，i)＜Usp(ω，i);2)Dsp(ε)=i，Dsp(ω)=j，i≠j，且存在消息msg，使得ε=Snd(msg，i)和ω=Rcv(msg，j);3)存在φ∈E，使得ε→φ且φ→ω．

hb关系是反自反的、反对称的和可传递的．如果两个事件不具有hb关系，则称之为并发事件.按照hb关系对E中事件进行排序，则得到全体事件的一个偏序图．

定义3(抽象虚拟时间系统)一个虚拟时间系统的构成为:事件集合E、虚拟时间T和映射函数C．其中C是从E到T的映射T=C(E)，表示为集合E中的每个事件e分配一个虚拟时钟C(e)，所有事件的虚拟时钟构成虚拟时间T．

定义4(弱连贯和强连贯［12］)对于一个虚拟时间系统和E中具有hb关系的两个事件ε和ω，如果ε→ω⇒C(ε)＜C(ω)，则称该虚拟时间系统为弱连贯的;如果ε→ω⇔C(ε)＜C(ω)，则称之为强连贯的．

在虚拟时间系统的3种基本实现形式中，标量时间系统是弱连贯的，而向量时间系统和矩阵时间系统都是强连贯的.

3 虚拟时间系统

3.1 标量时间系统

标量时间系统由文献［6］提出.在标量时间系统中，初始时刻各个进程ps(1≤s≤n)的标量时钟为0，进程ps的当前时钟记为Cs，消息msg的时钟为Cmsg，Cmsg为消息发送进程在发送msg时的时钟．若表示进程ps正要执行的事件，则事件的时钟根据如下规则更新:

1)如果该事件不是消息接收事件，则Cs=Cs+d(d通常取1)，然后

2)如果该事件是消息msg接收事件，则Cs=

图3是基于标量时间系统的通信图.其中，p2根据接收到的消息msg3所携带的时钟60，将自己的时钟从56改为61;类似地，p1在接收到消息msg4时，将自己的时钟改为70．标量时间不能保证如果两个事件的标量时钟存在大小关系，则两个事件具有hb关系．例如图3中，假设p1在标量时钟18时发生事件a，p2在标量时钟24时发生事件b，则虽然C(a)＜C(b)，但并不存在a→b．因此标量时间系统是弱连贯的．

图3 标量时间系统的通信图

3.2 向量时间系统

向量时间系统由文献［7-8］提出．假设分布式计算中共有n个进程参与，则初始时刻各个进程pv(1≤v≤n)的向量时钟为［0，0，…，0］(共n个0)．进程pv的当前时钟记为Cv，它是一个n维向量，其第v维分量Cv［v］表示进程pv的执行进展，其第k维分量Cv［k］表示进程pv对进程pk的最新知识，即pv是否了解pk发生了多少事件，pv是否了解pk的执行进展．消息msg携带消息发送进程发送消息时的时钟Cmsg表示进程pv正要执行的事件．事件的时钟根据如下规则更新:

1)如果该事件不是消息接收事件，则仅更新Cv的第v维分量:Cv［v］=Cv［v］+d(d通常取1)，然后

2)如果该事件是消息msg的接收事件，则对于1≤k≤n，Cv［k］=max(Cv［k］，Cmsg［k］);并且Cv［v］=Cv［v］+d(d通常取1)，然后

图4中，初始时刻3个进程p1，p2和p3的向量时钟都为［000］．当各自的第1个事件发生后，3个进程的时钟分别变为［100］，［010］和［001］．当进程p1的第2个事件发生时，根据向量时钟更新规则1)，该事件被分配时钟［200］;由于该事件是消息发送事件，故发送的消息msg上携带时钟［200］．当进程p2接收到消息msg时，根据向量时钟更新规则2)，p2的消息接收事件被分配时钟［220］．

向量时间系统是强连贯的，任意2个事件a和b，如果C(a)≤C(b)，则a→b;反之，如果a→b，则一定有C(a)≤C(b)．在向量时间系统中，仅根据事件的向量时钟就可以判断两个事件是否具有hb关系．例如图4中的事件a和b，它们的向量时钟分别是［340］和［232］，因为既不存在C(a)≤C(b)，又不存在C(b)≤C(a)，故它们是并发事件．

图4 向量时间系统的通信图

3.3 矩阵时间系统

矩阵时间系统由文献［9-11］提出.假设分布式计算中共有n个进程参与，则初始时刻各个进程pm(1≤m≤n)的矩阵时钟为n×n的0矩阵．进程pm的当前时钟Cm为一个n×n矩阵，其中:元素Cm［m，m］表示进程pm的执行进展，Cm［m，k］(1≤k，m≤n)表示进程pm对进程pk执行进展的最新知识，Cm［k，l］(1≤k，l，m≤n)表示进程pm最近所知道的对进程pk对进程pl执行进展的最新知识的知识．消息msg携带消息发送进程发送消息时的时钟Cmsg，表示进程pm正要执行的事件，其时钟根据如下规则更新:

1)如果该事件不是消息接收事件，则仅更新Cm的第m行第m列元素:Cm［m，m］=Cm［m，m］+d(d通常取1)，然后C()=Cm;

2)如果该事件是消息msg的接收事件，且该消息来自进程pj(1≤j≤n，j≠k)，则1≤k≤n，Cm［m，k］=max(Cm［m，k］，Cmsg［j，k］);1≤k，l≤n，Cm［k，l］=max(Cm［k，l］，Cmsg［k，l］);Cm［m，m］=Cm［m，m］+d(d通常取1)，然后C()=Cm．

图5中，初始时刻3个进程p1，p2和p3的矩阵时钟都为当各自的第1个事件发生后，3个进程的时钟分别变为，当进程p1的第2个事件发生时，根据矩阵时钟更新规则1)，该事件被分配时钟;由于该事件是消息发送事件，故发送的消息msg上携带时钟当进程p2接收到消息msg时，根据矩阵时钟更新规则2)，p2的消息接收事件被分配为时钟

图5 矩阵时间系统的通信图

矩阵时间系统是强连贯的，任意事件a和b，如果a→b当且仅当C(a)≤C(b)．例如图5中的事件a和b，它们的矩阵时钟分别是和，既不存在C(a)≤C(b)，又不存在C(b)≤C(a)，因此它们是并发事件．

4 虚拟时间的改进与优化技术

4.1 丢弃过时时钟

当某个事件发生时，并不需要与所有已发生的事件进行时钟比较，而只需要与一些事件进行比较即可，因为另一些事件在该事件发生前或者发生时已经“过时”.

4.1.1 列投影技术［12］

图6使用列投影技术丢弃过时时钟，矩阵下方的横线表示对矩阵的每一列求取最小值．进程p3的第2个事件e23发生时，被赋予矩阵时钟由于，因此p3知道所有进程p1，p2，p3都知道进程p1已执行了2个事件．此后任何事件e的时钟的第1行第1列肯定≥2，且→e．因此p1的前2个事件a和b在今后的时钟比较时可以忽略．

图6 列投影技术丢弃过时时钟

4.1.2 探询(Snooping)技术［13］

列投影技术对过时信息的计算依赖于事件的矩阵时钟，而后者只能根据进程内执行进展或者进程间消息传递而更新，速度较慢.这就导致列投影技术对系统全局进展的最新知识较滞后.鉴于此，探询技术不再被动等待进程间的消息传递，而是主动探询各个进程的最新进展，从而获得对系统全局进展的实时知识.图7使用探寻技术对图4所示的通信图进行过时时钟丢弃.进程p1的第2个事件的时钟在图4中是［200］，在图7中的snooping时钟是．探寻技术在计算事件b的snooping时钟时，主动去询问进程p2和p3的当前时钟，分别得到［010］和［001］，然后结合p1的当前时钟构成b的snooping时钟.一旦得到事件的snooping时钟，探询技术就采用列投影技术来计算可被丢弃的时钟.在p3的第2个事件发生时，探寻技术丢弃进程p1的前2个事件的时钟，这与列投影技术一样;在p1的第3个事件发生时，探寻技术丢弃p2的前3个事件的时钟，这是列投影技术无法做到的．

图7 探询技术丢弃过时时钟

4.2 减少消息带宽

文献［14］发现如果从上次向进程pj发送消息以来，进程pi的时钟向量的第i1，i2，…，in1个分量变为v1，v2，…，vn1，则下次pi向pj发送消息时，只需发送发生变化的分量＜(i1，v1)，(i2，v2)，…，(in1，vn1)＞．进程pj接收到该压缩格式的向量时钟后，如图8所示更新自己的时钟:对于k=i1，i2，…，in1，Cj［k］=max(Cj［k］，vk)．

图8使用Singhal技术传递消息.其中p3传递第3个消息给p2时，消息上附带的信息是＜(3，4)，(4，1)＞．这是由于上次p3给p2传递消息时，p3的时钟是［0020］，而当前p3时钟是［0041］，向量时钟的第3项从2变为4，第4项从0变为1．p2接收到该消息后，将自己的时钟从［1320］变为［1441］．

图8 使用Singhal技术传递消息

4.3 可折叠时钟

可折叠时钟［15］(accordion clock)只维护对于当前活跃的进程的知识.对于尚未启动或者已经结束的进程，可折叠时钟不维护对于它们的任何信息.可折叠时钟的时钟长度随着分布式计算中进程的启动和结束而伸展与收缩，从而总是维护对于“必要”进程的知识.

可折叠时钟的分量具有形式(s，pid)，其中s表示进程pid的本地时钟．图9使用可折叠时钟为分布式计算中的事件进行排序．其中，初始时刻3个进程的p1，p2和p3的可折叠时钟都为空．当各自的第1个事件发生后，3个进程的时钟分别变为［(1，1)］，［(1，2)］和［(1，3)］．当进程的第2个事件发生时，该事件被分配时钟［(2，1)］;由于该事件是消息发送事件，故发送的消息msg上携带时钟［(2，1)］．当进程p2接收到消息msg时，p2的消息接收事件被分配时钟［(2，1)，(2，2)］．

图9 可折叠时间系统的通信图

5 虚拟时间的数据竞争检测

将虚拟时间应用在数据竞争检测中，面临3个问题:1)哪些事件是消息发送和接收事件;2)哪些事件需要为其分配时钟;3)哪些事件需要进行并发检测.已有研究［16-19］将以下事件作为消息发送/接收事件:fork/线程入口点，线程退出点/join，unlock/lock，signal/wait;为以下事件分配时钟:消息发送/接收事件，内存访问事件;对以下事件进行并发检测:内存访问事件.

本文介绍了基于向量时间的4个数据竞争检测系统，即Dij+系统，FastClock系统，Weaker-than系统和Threadset系统.

5.1 Dij+系统

Dij+系统为每个共享变量x维护2个时钟向量awx和arx，分别代表各个线程对x的最新写访问和读访问.Dij+如下更新共享变量的2个时钟向量:在t的某个时间帧中，a是对x的第1个访问，如果a是读访问，则arx［t］=Ct［t］;如果a是写访问，则awx［t］=Ct［t］．Dij+在t执行完a后，检测数据竞争:是否存在某个线程u，使得如果a是读访问，则awx［u］＞Ct［u］;如果a是写访问，则awx［u］＞Ct［u］或者arx［u］＞Ct［u］．

Dij+能保证若x上存在数据竞争，则至少一个会被检测出来.图10解释了Dij+的时钟更新机制，其中所有事件都是对x的写访问事件.在图10(a)中，来自不同线程的两个事件a和b具有hb关系，则按照hb定义，c1和c2也与b具有hb关系，因此无需保存c1和c2对x的访问信息．在图10(b)中，a和b是并发的，而且c1和c2也可能与b是并发的;这种情况下Dij+可能漏检c1(或c2)和b构成的数据竞争，但能保证检测到a和b这一对数据竞争．

图10 Dij+时钟更新机制的原因

5.2 Fastclock系统

若有n个线程，则Dij+对线程t的每个读写操作，需要耗费O(n)时间来检测它是否与其他线程的读写操作存在数据竞争．假如事先知道某个线程w对共享变量x的访问是到当时为止所有线程对x的最新访问，则当线程t对x进行访问a时，只需进行以下比较来检测数据竞争:awx［w］＞Ct［w］或者arx［w］＞Ct［w］．此比较的时间复杂度是常量级的，即O(1)．因此awx和arx只需存储最新读写共享变量的线程的本地时钟和线程号，称为epoch(形式为c@t)，存储空间也由O(n)降为O(1)．

FastClock时钟更新机制如下:如果多个读访问并发访问x，则arx是epoch形式的向量时钟，以同时记录多个读访问;如果多个读访问顺序访问x，则arx是标量时钟;如果多个读访问并发访问x后，遇到对x的写访问，则arx从向量时钟变为变量时钟;无论多个写访问顺序或者并发访问x，awx都是标量时钟.FastClock竞争检测机制与Dij+类似.

5.3 Weaker-than系统

对于给定的2个事件p和q，以及将来发生的任何事件r，如果IsRace(q，r)蕴含IsRace(p，r)，则说事件p相对于事件q来说受到(锁)的保护更弱(weaker-than)，更易于与其他事件构成数据竞争．其中IsRace(e1，e2)用于判断2个访存事件e1和e2是否构成数据竞争对．对于p和q，Weaker-than只保留更弱者p，而丢弃q，并且将来发生的事件r，都将与p进行hb关系比较，而不与q进行比较．Weaker-than系统与Dij+系统一样，保证如果共享变量上x上存在数据竞争，则它至少会检测到其中一个．

5.4 Threadset系统

与Dij+类似，Threadset为每个共享变量x维护一个并发访问集Sx，其中保存着epoch形式的时钟.与Dij+不同的是，Sx不区分共享变量的读访问与写访问，因此可能将2个读访问报告为数据竞争．Sx使用可折叠时钟表示，其大小随并发访问的数目增大或者缩小．Sx中使用hb关系来检测两个访问是否并发:当线程t读访问或者写访问x时，Threadset将(t，Ct(t))添加到Sx中，然后检查是否存在(u，k)∈Sx，使得k≤Ct(u);如果存在的话，则说明(u，k)代表的访问与本访问具有hb关系，故从Sx中删除(u，k)，Sx中剩余元素都是有可能相互并发的访问．但单独使用Sx，Threadset不能判断是否有数据竞争发生，还需要x的锁集信息Lx．Threadset结合hb算法和锁集算法［20-21］来检测数据竞争．

6 结 论

1)提出虚拟时间和虚拟时钟的概念，给出虚拟时间系统的形式化定义，对虚拟时间和虚拟时钟的概念作出区分.

2)建立抽象的分布式执行模型，在同一框架下统一描述虚拟时间的3种基本实现形式和相关改进优化技术.

3)总结将虚拟时间应用到数据竞争检测时需要解决的关键问题，以4个数据竞争检测器为例说明基于虚拟时间的数据竞争检测系统的时钟分配和竞争检测机制.

4)本模型清晰准确地刻画虚拟时间的不同实现形式，有助于降低基于虚拟时间检测数据竞争的应用难度.

［1］罗军，王宏，李文生.基于向量时钟模型的NoSQL最终一致性的研究［J］.计算机工程与应用，2013，49(23):100-102.

［2］宋庆祯.开放式协同环境下分布式事务提交和恢复机制的研究［D］.广西:广西大学，2005.

［3］刘磊，黄河，唐志敏.支持多核并行程序确定性重放的高效访存冲突记录方法［J］.计算机研究与发展，2011，49(1):64-75.

［4］LU S，PARK S，SEO E，et al.Learning from mistakes:a comprehensive study on real world concurrency bug characteristics［J］.ACM SIGPLAN Notices，2008，43(3):329-339.

［5］霍玮，于洪涛，冯晓兵，等.静态检测中断驱动程序的数据竞争［J］.计算机研究与发展，2011，48(12):2290-2299.

［6］LAMPORT L.Time，clocks，and the ordering of events in a distributed system［J］.Communications of the ACM，1978，21(7):558-565.

［7］MATTERN F.Virtual time and global states of distributed systems［J］.Parallel and Distributed Algorithms，1989，1(23):215-226.

［8］FIDGE C.Logical time in distributed computing systems［J］.Computer，1991，24(8):28-33.

［9］FISCHER M J，MICHAEL A.Sacrificing serializability to attain high availability of data in an unreliable network［C］//Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems.New York:ACM，1982:70-75.

［10］WUU G T J，BERNSTEIN A J.Efficient solutions to the replicated log and dictionary problems［J］.Operating systems review，1986，20(1):57-66.

［11］SARIN S K，LYNCH N A.Discarding obsolete information in a replicated database system［J］.IEEE Transactions on Software Engineering.1987，13(1):39-47.

［12］RAYNAL M，SINGHAL M.Logical time:Capturing causality in distributed systems［J］.Computer，1996，29(2):49-56.

［13］DE BOSSCHERE K，RONSSE M.Clock snooping and its application in on-the-fly data race detection［C］//Proceedings of the 3rd International Symposium on Parallel Architectures，Algorithms，and Networks.Piscataway，NJ:IEEE，1997:324-330.

［14］SINGHAL M，KSHEMKALYANI A.An efficient implementation of vector clocks［J］.Information Processing Letters，1992，43(1):47-52.

［15］CHRISTIAENS M，DE BOSSCHERE K.Accordion clocks:Logical clocks for data race detection［C］//Proceedings of the 7th International European Conference on Parallel Processing.Berlin，Heidelberg:Springer，2001:494-503.

［16］CHOI J D，LEE K，LOGINOV A，et al.Efficient and precise datarace detection for multithreaded object oriented programs［J］.ACM SIGPLAN Notices，2002，37(5):258-269.

［17］FLANAGAN C，FREUND S N.FastTrack:efficient and precise dynamic race detection［J］.ACM Sigplan Notices，2009，44(6):121-133.

［18］POZNIANSKY E，SCHUSTER A.MultiRace:efficient on-the-fly data race detection in multithreaded C++programs［J］.Concurrency and Computation:Practice and Experience，2007，19(3):327-340.

［19］YU Y，RODEHEFFER T，CHEN W.Racetrack:efficient detection of data race conditions via adaptive tracking［J］.ACM SIGOPS Operating Systems Review，2005，39(5):221-234.

［20］ZHOU P，TEODORESCU R，ZHOU Y.HARD:Hardware-assisted lockset-based race detection［C］//Proceedings of the 13th International Symposium on High Performance Computer Architecture.Piscataway，NJ:IEEE，2007:121-132.

［21］XIE Xinwei，XUE Jingling，ZHANG Jie.Acculock:Accurate and efficient detection of data races［J］.Software:Practice and Experience，2013，43(5):543-576.