- 背景
- 例子
- 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等)语句中同时操作两次内存。访问内存的时间远远大于访问寄存器的时间，会使得执行速度变慢。
我们考虑一下下面这种线程交错情况：
两个线程对同一个 Add 对象的 x 变量两次自增操作只让 x 从 0 变成了 1，我们找到了多线程中的错误源头，我们再来观察下正常情况：
不难看出，两次调度的区别在于语句 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）。
- 静态检测处于软件编码阶段，可以尽早地发现错误，利于软件开发。
