MultiRace-Efficient on-the-fly data race detection

濮阳靖
2023-12-01

     最近在研究数据竞争检测方法,之前的工作是参考了Eraser这个工具1997年提出的基于Lockset方法的动态数据检测,

在Interl的Pin框架的基础上对方法进行了复现(论文中有关动态注解没有完成,这部分以后再整合)。在后续的论文研读中

发现大多数的方法都是基于Happens-Before和Lockset方法结合的思路,于是就看了下面这篇非常具有代表性的两种方法综

合的论文。

Reference:

Pozniansky E, Schuster A. Efficient on-the-fly data race detection in multithreaded C++ programs[M]. ACM, 2003.

      这篇论文也是中所说的方法也是on-the-fly方法(个人理解就是程序执行过程中监测,与之相对应的就是程序执行完成后
利用log文件中信息进行检测),结合了HB方法和Lockset方法进行的动态数据竞争检测,并且加上了必要的改进。下面就来
说一下这两种方法在本文中的利用。

Happens-Before方法-Djit+
本文中HB方法使用的是基于Vector-Clock,改进之后的算法起名为Djit+。使用Vector-Clock,可以保留每个线程的时间戳,对于
一个正在执行的线程来说,它的Vector-Clock就是它当前所知道的其他线程的最先进展(自己当然知道自己的最新进展)。因此,
对于每个访问操作,都可以知道当前访问操作是不是目前位置最新的访问操作。而数据竞争产生,必然会存在至少两个访问操作
的并行执行,其中至少有一个是写访问并且是不同线程的。因此通过HB关系就能够判断两个操作是否是并行执行,因此检测共享
变量的读和写操作就能够检测出执行过程中产生的数据竞争。
这样效率太低了,对于一些稍微大一点的程序而言,共享变量很多,读/写频繁,如果检测每一次读/写,时间和空间上性能将大大
降低,可不可以减少检测的数量呢?答案肯定是有的,论文中提出了一个time-frame的概念,就是一个时间戳,两个同步操作之间
的SV(共享变量)访问操作会被标记为同一个time-frame,这样的话,同一个time-frame的SV访问只需要对第一次读/写操作进行检测
后续的读写操作不会改变time-frame的值,因此也不会有额外的信息产生。另一方面,考虑如果a和b没有发生数据竞争(假设)a
在b之后发生,那么a和b‘(b之前的操作)肯定不会发生数据竞争,因此,我们只需要记录对SV访问的最近的一次读操作和写操作
的time-frame就能够 满足我们检测 数据竞争。

根据上述这些性质,Djit检测的方法如下:

初始化
        对于每个线程t,给定一个VC,其中VC[t]就初始为1
        对每个共享变量v,初始化两个VC,一个是写VC,另一个是读VC,分别表示最近对该SV进行写操作线程的time-frame以及最近
对该SV进行读操作线程的time-frame
        对于同步对象(锁),同样初始化一个VC(VC[i]全为0)

遇到同步对象Release操作
        表明线程t进入了一个新的time-frame(同步操作有明确的先后顺序),VC[t] += 1,同时,同步对象VC中的每个clock需要被更新
为与当前线程VC比较中较大的那个值(同步对象稍后会被其他线程获取)


遇到同步对象Acquire操作
        当前线程的VC的每个clock更新为与同步对象的VC比较中 较大的那个值(当前线程通过其他线程 得到它所知道的所有线程的最
新进展)


遇到共享变量的读/写操作
       
当前线程t会更新SV的改线程对应的历史访问time-frame值,读操作更新读VC[t],写操作更新写VC[t]
        对于SV的读操作,将写VC和当前线程的VC进行比较,看共享变量写VC[u]>=当前线程VC[u](是否有其他线程知道最新的写访问
而非t本身)
        对于SV的写操作,同理需要比较 写VC[u]>=当前线程VC[u],以及读VC[u]>=当前线程VC[u](是否有其他线程知道最新的读访问
和写访问)

        上述比较成立就会报告数据竞争,也就是说当前线程所知道的访问操作并不是最新的,有其他线程的访问操作超过了当前线程的最新进展,那么肯定就是这两个线程访问操作没有同步。


后续将分析改进的Lockset方法!

   

 类似资料: