基于Lockset的数据竞争检测方法汇总(四)

     今天讲的这篇文论中提到的Lockset方法同样也是和Happens-Before结合来进行动态数据竞争检测,这篇论文中使用的Happens-Before方法不是上一篇文章中提出的Djit+方法,而是使用Threadset方法,同时这篇论文提出的自适应检测方法能够在Threadset和Lockset自由切换,并且在检测共享对象的粒度上也是自适应的(这里的话不会提如何自适应的,将会在以后的文章中提到)。

Reference:

Yu Y, Rodeheffer T, Chen W. Racetrack: efficient detection of data race conditions via adaptive tracking[C]//ACM SIGOPS Operating Systems Review. ACM, 2005, 39(5): 221-234.

     我们还是主要来关注一下Lockset的状态变迁在这篇文章中是如何进行的。

     在对Lockset进行分析之前,我们有必要需要知道文中使用的Happens-Before方法,这里的话就简单理解方法,不会非常细致的展开说明,只要能够有助于我们立即Lockset方法就行。

Happens-Before方法:Threadset

     此方法和Djit+类似,Threadset为每一个共享变量x维护一个并发访问集Sx,并发访问集中的元素就是<t,Bt(t)>(t表示的就是线程t标志,而Bt(t)表示的就是线程t最近对x进行访问的时钟)。Sx中的元素数目会随着访问增加或是减少,这是因为Sx使用hb关系来检测两个访问操作是否并发,当线程t对x进行访问的时候,Threadset会将<t,Bt(t)>添加到Sx中,然后检查是否存在<u, k>∈Sx,使得k ≤ Bt(u),如果存在就表明<u,k>和当前的访问操作具有hb关系,所有从Sx中删除<u,k>,那么最后Sx中剩下的都是并发的访问。通过这个可以对Lockset报告的数据竞争进行检测,来判断到底哪些是真正的数据竞争。

     Threadset方法就简单的介绍一下(和后面的Epoch方法有点类似,后面文章会重点讲解)。下面的话我们就来看一下这篇文章中Lockset状态变迁图是怎么设计的:

      这些状态在前面三篇文章中反复出现过了,不过这里状态变迁和前面有很大的不同,那么首先就来认识一下这些状态所表达的信息:

      Virgin:初始化

      Exclusive0:同一个线程访问(不区分读和写),这个状态和前面的Virgin都不用跟踪Sx和Cx(共享变量的锁集)

      Exclusive1:第二个线程访问,和前面第二篇文章有点类似(不清楚同学可以再去回顾一下),这么设计的主要目的还是考虑的实际使用的过程中,类似于主线程初始化一些共享对象,然后交给子线程完成必要的工作(共享对象的ownership转交给子线程了)。因此的话这里使用|Sx|=1说明当前对这个共享变量并发的访问操作只有second thread,这个状态我们不用去跟踪Cx的变化。

      Shared-Read:这个状态和前面文章提到的状态的语义 是一致的(多个线程对共享变量读),在这个状态只需要关注Cx(我们在Exclusive1状态的时候,如果|Sx|>1并且访问操作是读,那么就会转到这个状态,此时Cx就是当前线程获得的锁集),不用关注Sx的变化。

      Shared-Modified:这个状态和前面文章中提到的状态语义一致的(多个线程对共享变量有写操作),在这个状态同样我们只需要关注Cx(如果我们在Exclusive1状态,由于一个其他线程的写操作导致 |Sx|>1 ,那么就会进入到这个状态,此时的Cx就是当前线程获得的锁集;如果我们在Shared-Read状态进行了一个写操作,只要Cx不为空,就会进入到这个状态,此时的Cx就是Shared-Read状态时的Cx)。

      Exclusive2:这个状态我们只需要关注Sx的变化,只有Shared-Read和Shared-Modified这两个状态才能够进入到这个状态,前面两个状态我们只关注了Cx,当Cx为空的时候,会进入到这个状态,此时的话,我们就会得到潜在的数据竞争,但是其中有很多的误报,因此我们还需要通过Sx来区分哪些是真正的数据竞争(就必须等到有并发操作发生),这里还有一点非常重要,由于当前状态不包括并发操作,因此我们还需要初始化Cx为当前线程获得的锁集。

     Shared-Modified2:在Exclusive2状态,如果|Sx|>1就会进入到这个状态,表明有并发操作发生。这个状态我们需要去关注Cx和Sx,如果Cx不为

{ },并且|Sx|>1 那么继续停留在这个状态,说明有并发操作,但是有公共的锁集保护;如果|Sx|=1,表明当前只有一个线程的操作,因此回到状态Exclusive2,;而如果Cx为空并且|Sx|>1的话,那么表示当前有并发操作但是没有公共的锁集,就会报数据竞争警告。

     看到这里的话,不知道有没有发现什么问题,如果按照我上面说得那样,Sx保存的都是并发操作,那么为什么还要结合Lockset方法呢,正如Shared-Modified状态描述的那样,发生数据竞争警告只有在Cx为空并且|Sx|>1???我看这张图的时候也是顿了一下,不过如果我们结合这个算法的伪代码来看的话,那么就一点不奇怪了。

通过伪代码可以发现,这里的时钟同步和我们在Djit+中的有很大的区别,Djit+中我们会在Release同步操作之后增加Vector Clock中的当前线程的clock值,但是此算法中只有在Fork(也就是创建线程)操作时会添加当前线程t的clock值,那么文章中所说的并行就不是真正意义上全局的并行,而是有可能的并行(没有考虑锁之间的同步操作,只有线程创建和等待之间的同步操作),这样的并行首先能够确保每个线程内部对共享变量x的最新访问,同时利用Fork和Join操作可以同步一部分多个线程对共享变量x的最新访问,由于hb关系没有包含Lockset,因此最后我们还要用Lockset方法再检测一下。

      看到这里的话,我想有关Lockset中的状态转换大家应该有比较清楚的了解。另外这篇文章也是给了一个很好的启示就是对于hb关系,我们使用的过程中可以选择部分同步关系,然后最后用其他同步关系再去验证之前的并行是否有效。

到这里的话,有关Lockset方法就要告一段落了,后续工作将会主要放在使用Happens-Before方法的运用上,如果有相关Lockset

方法还会继续更新,敬请期待!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xcywt

《Linux命令行与shell脚本编程大全》第十九章 初识sed和gawk

这两个工具能够极大简化需要进行的数据处理任务。 19.1 文本处理 能轻松实现自动格式化、插入、修改或删除文本元素的简单命令行编辑。 sed和gawk就具备上述...

2055
来自专栏简书专栏

基于Excel2013的PowerQuery入门

所有要进行操作的文件下载链接: https://pan.baidu.com/s/10VtUZw8G-Ly-r4VypntjiA 密码: y5qu 下载成功后,...

3.4K4
来自专栏编程

ThinkPHP3.2和5.0的区别

5.0 版本和之前版本的差异较大,本篇对熟悉3.2 版本的用户给出了一些5.0 的主要区别。 URL和路由 5.0 的URL访问不再支持普通URL 模式,路由也...

2199
来自专栏技术博文

Linux系统中ls命令用法详解

linux系统中ls命令的用法 ls命令是linux下最常用的命令。ls命令就是list的缩写,缺省下ls用来打印出当前目录的清单,如果ls指定其他目录,那么就...

3624
来自专栏H2Cloud

C++任务队列与多线程

摘要:       很多场合之所以使用C++,一方面是由于C++编译后的native code的高效性能,另一方面是由于C++优秀的并发能力。并行方式有多进程 ...

6054
来自专栏生信宝典

Linux学习 - 管道、标准输入输出

Linux下的标准输入、输出、重定向、管道 在Linux系统中,有4个特殊的符号,<, ‘>’, ‘|’, ‘-‘,在我们处理输入和输出时存在重要但具有迷惑性的...

3295
来自专栏Linux驱动

Linux-hexdump命令调试event驱动—详解(13)

hexdump: 查看文件的内容,比如二进制文件中包含的某些字符串,通常用来调试驱动用 描述: 我们以event1为例,当我们insmod挂载了键盘驱动后,出现...

2739
来自专栏python百例

101-多进程基础

fork()后会出现子进程,父子进程都打印Hello World!,所以会有两行相同的内容输出。

982
来自专栏小二的折腾日记

Linux的fork使用

功能:fork函数是从一个已经存在的进程中创建一个新的进程,新的进程称为子进程,原来的进程称为父进程。 参数:无 返回值: 成功:子进程中返回 0,父进程中返回...

1823
来自专栏Java后端技术

谈谈Linux下的数据流重定向和管道命令

  1.标准输入(stdin)是指令数据的输入,代码为0,使用<或者<<,默认是键盘。

902

扫码关注云+社区

领取腾讯云代金券