数据竞争及其静态检测

背景
例子
Data Race 数据竞争
静态检测
局限性

一、背景

多线程的bug一直都是难以发现的，在之前的JMCR系列中，介绍了一种动态检测多线程程序错误的方法，然而这种动态方法在实际生产应用中存在一些局限性，需要软件动态运行，软件工程指导我们：一个错误发现的越晚，为改正它所付出的代价越大，而一个产品/模块得到可运行的时期时，已经是整个软件过程的晚期了。如果有一种方法可以在编码阶段就提示用户潜在的多线程bug及时修复，则可以将错误扼杀于摇篮之中。

二、例子

静态检测所检测到内容，就是程序中的所有数据竞争，在介绍检测的原理之前，我们来详细了解一下数据竞争。
来观察一下下面的程序

public class Add {
    public int x = 0;
  
    // 完成x自增操作    
    public void increment() { 
        // x++ 等价于 temp = x;  x = temp+1;          
        x++; 
    }
}

class Action extends Thread{
    public Add add;
    int total;

    public Action(Add add, int total) {
        this.add = add;
        this.total = total;
    }

    @Override
    public void run() {
        for(int i = 0; i < total; i ++){
            this.add.increment();
        }
    }
}

public class Test{

    static final int COUNT = 1000;

    public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(test());
        }
        System.out.println(list);
    }

    public static int test() throws InterruptedException {
        Add add = new Add();
        Action a1 = new Action(add, COUNT);
        Action a2 = new Action(add, COUNT);

        a1.start(); a2.start();
        a1.join();  a2.join();

        return add.getX();
    }
}

上述代码的意图是 a1 和 a2 两个线程对于同一个 Add 类对象 add，分别调用 1000 次 increment() 函数，将 add 中的成员变量 x 增加 2000，然而这段程序运行结果是：

运行结果

出现了非 2000 的结果，这是为什么呢？

    // 完成x自增操作    
    public void increment() { 
        // x++ 等价于 temp = x;  x = temp+1;          
        x++; 
    }

我们来关注一下在Add类中的 increment() 函数，值得一提的是，x++ 这一操作，并非原子操作，实际上是先将 x 的值读取到临时变量 temp 中，再将 temp + 1 的值赋值给 x。

x 不能直接等于 x + 1 的原因是汇编语言（机器码）不允许赋值(mov)、计算(add/sub等)语句中同时操作两次内存。访问内存的时间远远大于访问寄存器的时间，会使得执行速度变慢。

我们考虑一下下面这种线程交错情况：

Bugly interleaving

两个线程对同一个 Add 对象的 x 变量两次自增操作只让 x 从 0 变成了 1，我们找到了多线程中的错误源头，我们再来观察下正常情况：

Expected Interleaving

不难看出，两次调度的区别在于语句 x = temp + 1; 和 'temp = x;' 的顺序不同。这两个语句，就是一个 Data Race，数据竞争。

三、Data Race 数据竞争

数据竞争总是由一对操作构成，且是两个线程对于同一个线程内共享变量进行操作。数据竞争有两种，一种是读写冲突，一种是写写冲突：

读写冲突
考虑只有读写两句话的情况，可能的交错序列如下

possible interleavings

交错序列的不同导致了线程1读到了不同的 x。
写写冲突
考虑只有读写两句话的情况，可能的交错序列如下

3.png

交错序列的不同导致了接下来任何一个线程读 x 会不同。

我们发现：Race condition 的两个操作如果颠倒顺序，会导致程序状态不同【1】。 程序运行中可能会出现多种状态，导致了多线程程序运行的不确定性，从而导致出错的可能。如果可以适当地加锁防止互为数据竞争的两个操作交换顺序执行，则可以预防多线程的错误。

四、静态检测

指针图（Point To Graph，PTG）
Java 程序中的每一个赋值语句 a = b;，表示了将 b 的指针赋给 a，此时 a 和 b 同时指向同一片内存，在指针图中表示为 b 指向 a。将上面的程序转化为如下的指针图：

PTG

可以看到 a 同时指向了 a1.add 和 a2.add，因此我们得知 main 函数中的 add 是共享变量，a1.add 和 a2.add 同时指向 main 函数的 add。即，在 PTG 中，从某一个节点出发，通过两条不同的路径可以分别到达的两个节点共享同一片内存。
happens-before关系图（Happens Before Graph，HBG）
将上面的实例程序抽象为执行顺序图如下，特别的，一个线程的开始和结束分别记录为 begin 和 end 事件：

4.png

一个程序中中的部分节点和节点之间存在happens-before关系。类型如下：
- Must Happens Before
  begin 事件只能作为线程中的第一个事件发生，并且只能在该线程被另一个线程 fork 之后发生。 end 事件只能作为线程中的最后一个事件发生，而 join 事件只能在被 join 线程的 end 事件之后发生。
  
  main 线程的 a1.start() Happens Before 于 a1 线程 begin 事件
  a2 线程 end 事件 Happens Before 于 main 线程的 a2.join()
- 线程内串行
  线程内的第n个事件 Happens Before 于第 n+1 个事件。
  
  a1 线程 begin 事件 Happens Before 于 a1 线程的 temp = x;
  a2 线程的 x = temp+1 Happens Before 于 a2 线程的 end 事件
- 传递性
  事件a Happens Before 于事件 b，且事件 b Happens Before 于事件 c。则事件 a Happens Before 于事件 c。
检测
对于一个程序，我们进行静态分析，可以得到其 PTG 和 HBG，PTG可以让我们知道Java中的两个变量是否引用了同一片内存，HBG可以判断两个操作有无happens-before关系。
检测的思路为：如果两个对于同一个变量x，可以存在相邻的读读/读写操作，且两个操作没有明确的 happensbefore 关系，就可以认为这两个操作形成了数据竞争。

这里的相邻指的是，两个操作之间没有对于 x 的其他读写操作。

五、局限性与优势

局限性

静态检测目前（state of the art）仅限于data race的检测。data race本身存在良性和恶性之分。
静态检测基于的是代码静态扫描，对于if分支、for循环等逻辑性强的程序表现不佳，可能对于某种程序类型出现大量 false positive。

优势

静态检测可以进行增量检测，使得静态检测速度远快于动态，可以集成进入IDE做成实时监测插件（D4 's work）。
静态检测处于软件编码阶段，可以尽早地发现错误，利于软件开发。