动态数据竞争验证方法(一)

动态数据竞争检测算法可以在不知道程序中是否存在数据竞争前提下执行,而动态数据竞争验证方法则是在知道程序中可能存在的数据竞争前提下,对这部分可疑的数据竞争进行验证,看这些数据竞争是否真的发生,同时也可以验证这些数据竞争是否对程序造成有害的影响。

Reference http://web2.cs.columbia.edu/~junfeng/09fa-e6998/papers/racefuzz.pdf 这篇文章提出的RaceFuzzer采取随机调度的方式来验证数据竞争是否是有害的,主要分为如下几个阶段:

Phase1 首先利用hybrid的动态数据竞争检测方法找到程序中所有的数据竞争,这些数据竞争将会构成一个数据竞争语句对集合。之前的文章已经分析很多hybrid的动态数据竞争检测方法,这里就不再重复。

Phase2 根据Phase1中得到的数据竞争语句对,在动态的时候调度线程尽量让这些数据竞争语句对能够临时地相遇(同时发生)。相关的算法如下所示,为了方便描述,这里给出相关的一些定义: • s:程序在执行过程中的状态 • Enabled(s):当前状态s下可用的线程集合,线程不可用表明当先线程阻塞在一些同步操作上 • Alive(s):当前状态s下还没有结束的线程集合 • Execute(s,t):返回线程t在当前状态s下执行语句之后的状态 • NextStmt(s,t):返回线程t在当前状态s下即将要执行的语句

首先输入RaceSet为Phase1中的竞争语句对集合,并且程序当前状态为s为初始状态s0。其中postponed集合用来保存认为干预中止的线程,初始的时候同样是空集。

从while循环也可以发现,只要当前有可用的线程,那么就会一直执行下去。否则的话,一旦当前状态存在没有结束的线程就表明程序陷入了死锁(L30)。

该算法调度线程的核心就是每次只让一个线程执行,并且是随机的挑选可用的线程(L5)。

当被选择的线程即将执行的语句在RaceSet中,也就是数据竞争语句。 • 如果此时postponed中存在其他的线程即将访问的操作和当前线程t即将访问的操作构成数据竞争,那么此时机会随机是否当当前的线程继续执行还是让postponed中的线程继续执行(如果有多个阻塞的线程那么会让所有参与数据竞争的被阻塞的线程都继续执行)。 • 否则的话,当前线程就会被阻塞中止执行。 下图展示的是一个数据竞争的例子:

其中存在两个数据竞争[5,7]和[1,10]。对于数据竞争[1,10]来说,如果线程1先到达1,那么此时会被阻塞等待线程2到达10,线程1被加入到postponed中,但是由于y初始为0,因此线程2会一直执行到结束,此时线程1就会从postponed中被移除。对于数据竞争[5,7]来说,如果线程1先到达5,此时就会被阻塞,当线程到达7时,此时就会被验证为一个数据竞争。而一旦随机挑选线程1继续执行,那么此时就会执行6导致程序出现错误,此时,数据竞争[5,7]就是一个有害的数据竞争。

上述数据竞争验证方法每次只能够允许一个线程执行,使得数据竞争验证较慢。并且由于其使用确定性阻塞来中止线程的执行,因此可能会引入新的死锁。同时该方法每次执行程序能够验证的数据竞争很少。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

操作系统核心原理-4.线程原理(上):线程基础与线程同步

我们都知道,进程是运转中的程序,是为了在CPU上实现多道编程而发明的一个概念。但是进程在一个时间只能干一件事情,如果想要同时干两件或者多件事情,例如同时看两场...

1203
来自专栏Java编程技术

Java 并发编程之美-线程相关的基础知识-chat

借用 Java 并发编程实践中的话;编写正确的程序并不容易,而编写正常的并发程序就更难了;相比于顺序执行的情况,多线程的线程安全问题是微妙而且出乎意料的,因为在...

722
来自专栏栗霖积跬步之旅

1.11守护线程

在Java中有两种线程,一种为用户线程,一种为守护线程。 守护线程是一种特殊的线程,它具有“陪伴”的含义,当进程中不存在非守护线程时,则守护线程自动销毁。 典型...

18410
来自专栏Java Edge

Java多线程中join方法的理解

3396
来自专栏JAVA技术zhai

天下无难试之多线程面试刁难大全

多线程技术在互联网技术方面使用如此广泛,几乎所有的后端技术面试官都要在并发编程的使用和原理方面对小伙伴们进行各种刁难。作为一名在互联网技术行业打击过成百上千名【...

2839
来自专栏北京马哥教育

计算机操作系统学习笔记_进程管理--死锁

进程管理 --死锁 一、死锁的概念 1.死锁的概念   系统中两个或两个以上的进程无限期地相互等待永远不会发生的条件,系统处于一种停滞状态,这种情况称为死锁。 ...

2677
来自专栏企鹅FM

形形色色的锁

java中有各种同步机制,尤其是JDK1.5以后引入Lock后,衍生出各种功能不一的锁,比如ReentrantLock、Semaphore、CountDownL...

1183
来自专栏项勇

回昨天的美女面试官问题

1004
来自专栏我是攻城师

理解Java并发同步框架AbstractQueuedSynchronizer的设计

Java并发包里面的大多数工具框架大部分都是基于AbstractQueuedSynchronizer(简称AQS后面不再区分)框架实现的,这个框架提供了通用的机...

783
来自专栏java技术学习之道

java线程-看这一篇就够了

1143

扫码关注云+社区