- 背景
- 例子
- Data Race 數(shù)據(jù)競爭
- 靜態(tài)檢測
- 局限性
一绷蹲、背景
多線程的bug一直都是難以發(fā)現(xiàn)的，在之前的JMCR系列中顾孽，介紹了一種動態(tài)檢測多線程程序錯誤的方法祝钢，然而這種動態(tài)方法在實(shí)際生產(chǎn)應(yīng)用中存在一些局限性，需要軟件動態(tài)運(yùn)行若厚，軟件工程指導(dǎo)我們：一個錯誤發(fā)現(xiàn)的越晚拦英，為改正它所付出的代價越大，而一個產(chǎn)品/模塊得到可運(yùn)行的時期時测秸，已經(jīng)是整個軟件過程的晚期了疤估。如果有一種方法可以在編碼階段就提示用戶潛在的多線程bug及時修復(fù)灾常，則可以將錯誤扼殺于搖籃之中。
二铃拇、例子
靜態(tài)檢測所檢測到內(nèi)容钞瀑，就是程序中的所有數(shù)據(jù)競爭，在介紹檢測的原理之前慷荔，我們來詳細(xì)了解一下數(shù)據(jù)競爭仔戈。
來觀察一下下面的程序
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，分別調(diào)用 1000 次 increment() 函數(shù)拧廊，將 add 中的成員變量 x 增加 2000，然而這段程序運(yùn)行結(jié)果是：
出現(xiàn)了非 2000 的結(jié)果晋修，這是為什么呢吧碾？
// 完成x自增操作
public void increment() {
// x++ 等價于 temp = x; x = temp+1;
x++;
}
我們來關(guān)注一下在Add類中的 increment() 函數(shù)，值得一提的是墓卦，x++ 這一操作倦春，并非原子操作，實(shí)際上是先將 x 的值讀取到臨時變量 temp 中落剪，再將 temp + 1 的值賦值給 x睁本。
x 不能直接等于 x + 1 的原因是匯編語言（機(jī)器碼）不允許賦值(mov)、計(jì)算(add/sub等)語句中同時操作兩次內(nèi)存忠怖。訪問內(nèi)存的時間遠(yuǎn)遠(yuǎn)大于訪問寄存器的時間呢堰，會使得執(zhí)行速度變慢。
我們考慮一下下面這種線程交錯情況：
兩個線程對同一個 Add 對象的 x 變量兩次自增操作只讓 x 從 0 變成了 1凡泣，我們找到了多線程中的錯誤源頭枉疼，我們再來觀察下正常情況：
不難看出，兩次調(diào)度的區(qū)別在于語句 x = temp + 1; 和 'temp = x;' 的順序不同鞋拟。這兩個語句骂维，就是一個 Data Race，數(shù)據(jù)競爭贺纲。
三航闺、Data Race 數(shù)據(jù)競爭
數(shù)據(jù)競爭總是由一對操作構(gòu)成，且是兩個線程對于同一個線程內(nèi)共享變量進(jìn)行操作猴誊。數(shù)據(jù)競爭有兩種潦刃，一種是讀寫沖突，一種是寫寫沖突：
-
讀寫沖突
考慮只有讀寫兩句話的情況稠肘，可能的交錯序列如下
possible interleavings
交錯序列的不同導(dǎo)致了線程1讀到了不同的 x福铅。
-
寫寫沖突
考慮只有讀寫兩句話的情況，可能的交錯序列如下
3.png
交錯序列的不同導(dǎo)致了接下來任何一個線程讀 x 會不同项阴。
我們發(fā)現(xiàn)：Race condition 的兩個操作如果顛倒順序滑黔，會導(dǎo)致程序狀態(tài)不同【1】笆包。 程序運(yùn)行中可能會出現(xiàn)多種狀態(tài)，導(dǎo)致了多線程程序運(yùn)行的不確定性略荡，從而導(dǎo)致出錯的可能庵佣。如果可以適當(dāng)?shù)丶渔i防止互為數(shù)據(jù)競爭的兩個操作交換順序執(zhí)行，則可以預(yù)防多線程的錯誤汛兜。
四巴粪、靜態(tài)檢測
-
指針圖（Point To Graph，PTG）
Java 程序中的每一個賦值語句a = b;粥谬，表示了將 b 的指針賦給 a肛根，此時 a 和 b 同時指向同一片內(nèi)存，在指針圖中表示為 b 指向 a漏策。將上面的程序轉(zhuǎn)化為如下的指針圖：
PTG
可以看到 a 同時指向了 a1.add 和 a2.add派哲，因此我們得知 main 函數(shù)中的 add 是共享變量，a1.add 和 a2.add 同時指向 main 函數(shù)的 add掺喻。即芭届，在 PTG 中，從某一個節(jié)點(diǎn)出發(fā)感耙，通過兩條不同的路徑可以分別到達(dá)的兩個節(jié)點(diǎn)共享同一片內(nèi)存褂乍。 -
happens-before關(guān)系圖（Happens Before Graph，HBG）
將上面的實(shí)例程序抽象為執(zhí)行順序圖如下即硼，特別的逃片，一個線程的開始和結(jié)束分別記錄為 begin 和 end 事件：
4.png一個程序中中的部分節(jié)點(diǎn)和節(jié)點(diǎn)之間存在happens-before關(guān)系。類型如下：
-
Must Happens Before
begin 事件只能作為線程中的第一個事件發(fā)生只酥，并且只能在該線程被另一個線程 fork 之后發(fā)生题诵。 end 事件只能作為線程中的最后一個事件發(fā)生，而 join 事件只能在被 join 線程的 end 事件之后發(fā)生层皱。main 線程的 a1.start() Happens Before 于 a1 線程 begin 事件
a2 線程 end 事件 Happens Before 于 main 線程的 a2.join() -
線程內(nèi)串行
線程內(nèi)的第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草冈。
-
檢測
對于一個程序，我們進(jìn)行靜態(tài)分析瓮增，可以得到其 PTG 和 HBG怎棱，PTG可以讓我們知道Java中的兩個變量是否引用了同一片內(nèi)存，HBG可以判斷兩個操作有無happens-before關(guān)系绷跑。
檢測的思路為：如果兩個對于同一個變量x拳恋，可以存在相鄰的讀讀/讀寫操作，且兩個操作沒有明確的 happensbefore 關(guān)系砸捏，就可以認(rèn)為這兩個操作形成了數(shù)據(jù)競爭谬运。
這里的相鄰指的是隙赁，兩個操作之間沒有對于 x 的其他讀寫操作。
五梆暖、 局限性與優(yōu)勢
局限性
- 靜態(tài)檢測目前（state of the art）僅限于data race的檢測伞访。data race本身存在良性和惡性之分。
- 靜態(tài)檢測基于的是代碼靜態(tài)掃描轰驳，對于if分支厚掷、for循環(huán)等邏輯性強(qiáng)的程序表現(xiàn)不佳，可能對于某種程序類型出現(xiàn)大量 false positive级解。
優(yōu)勢
- 靜態(tài)檢測可以進(jìn)行增量檢測冒黑，使得靜態(tài)檢測速度遠(yuǎn)快于動態(tài)，可以集成進(jìn)入IDE做成實(shí)時監(jiān)測插件（D4 's work）勤哗。
- 靜態(tài)檢測處于軟件編碼階段薛闪，可以盡早地發(fā)現(xiàn)錯誤，利于軟件開發(fā)俺陋。
