多線程編程那些事

標(biāo)簽：HPC、多線程、JMM、Volatile、鎖、CPU多核構(gòu)架、Happens before、LOCK指令

先看一段代碼：

package jvm.valatile;

public class VolatileTest extends Thread {
    boolean flag = true;
    long i = 0L;

    @Override
    public void run() {
        while (flag) {
            i++;
        }
    }

    public static void main(String[] args) throws Exception {
        VolatileTest vt = new VolatileTest();
        vt.start();
        Thread.sleep(1000);//掛起下主線程，確保子線程完成初始化并啟動成功。
        setFlag(vt);//設(shè)置flag，嘗試停止線程
        System.out.println("vt value: " + vt.i);
        vt.join();
        System.out.println("stop and final flag is:" + vt.flag);
    }

    private static void setFlag(VolatileTest vt) {
        vt.flag = false;
    }
}

對多線程并發(fā)編程比較熟悉的人大概一眼就能看出這段代碼的問題，以及背后的技術(shù)。

我們看結(jié)果：

root@moon-light:~/share/java# java VolatileTest
vt value: 744337091

是的，風(fēng)扇已經(jīng)開始轉(zhuǎn)了，后臺線程沒有停下來，此時如果運行top會看到用戶態(tài)的CPU時間是99.5%以上，程序陷入了死循環(huán)。

image.png

我們稍微改一行代碼，就能讓子線程收到主線程的消息，停下來，加上volatile關(guān)鍵字：

volatile boolean flag = true;

結(jié)果：

root@moon-light:~/share/java# java VolatileTest
vt value: 763169009
stop and final flag is:false

是的java中靠volatile關(guān)鍵字來保證線程間的共享變量的可見，那么為什么volatile能夠保證共享變量的可見性呢？這可能要從java的內(nèi)存模型JMM說起了。

JMM

JMM有個公開文檔來說明java內(nèi)存模型的設(shè)計目的、用意與特性，我這里總結(jié)下：

首先，為什么要有JMM？

1. 因為java運行在jvm基礎(chǔ)上，既然是虛擬機，而且一次編譯還要處處運行，那么首要任務(wù)必須能屏蔽掉所有的可能的計算平臺（Intel、AMD、PowerPC以及各種大中小型機），而不同的機器在運行程序的時候有不同的特性，比如：亂序執(zhí)行、分支預(yù)測、以及CPU級別的內(nèi)存模型；不同的緩存構(gòu)架（不同的緩存行同步協(xié)議）；所以為了統(tǒng)一并對下進行屏蔽，要為java字節(jié)碼運行掃清障礙，定義一個虛擬的機器——jvm以及運行在這種機器上的內(nèi)存訪問模型——jmm；所以，jvm控制字節(jié)碼的執(zhí)行，相當(dāng)于CPU，jmm相當(dāng)于內(nèi)存；

2. CPU、編譯器都會對程序的執(zhí)行順序進行修改以使用CPU的各種加速技術(shù)，那么在多線程的情況下，程序的運行結(jié)果就能難預(yù)測，特別是在多核構(gòu)架下的CPU運行多線程程序，事情就變得更加復(fù)雜了。而多線程程序之間的通信歸根結(jié)底只有一種方式——共享變量；而共享變量是存在內(nèi)存中的，加上不同CPU對內(nèi)存的訪問是有區(qū)別的，所以需要JMM制定規(guī)則來通過控制內(nèi)存的訪問來控制程序的執(zhí)行預(yù)期。不然，同一段開嗎在A機器得到的結(jié)果很可能在B機器就是另一個不同的結(jié)果。引用一下原文：

   A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program.

   The memory model predicts the possible behaviors of a program. An implementation is free to produce any code it likes, as long as all resulting executions of a program produce a result that can be predicted by the memory model.

一句話：JVM通過JMM來控制（多線程）程序的執(zhí)行順序。

那么什么是JVM定義的執(zhí)行順序呢？簡單的說就是一個單線程程序的執(zhí)行順序。原文：

Program Order Among all the inter-thread actions performed by each thread t, the program order of t is a total order that reflects the order in which these actions would be performed according to the intra-thread semantics of t.

以前面的例子來說，我們的預(yù)期順序是：

1. 啟動主線程；
2. 主線程啟動一個子線程，子線程運行一個循環(huán)來對共享變量進行累加；
3. 主線程關(guān)閉子線程；
4. 子線程退出；
5. 打印累加結(jié)果。

但是，如果不加volatile關(guān)鍵字的共享變量是不會按照這個順序得到預(yù)期的結(jié)果的。所以，JMM的作用就是通過volatile關(guān)鍵字來保證程序按照預(yù)期輸出結(jié)果。

Happens-Before

JMM為了保證大家寫的程序能夠獲得預(yù)期的結(jié)果，特別是多線程程序也能按照正常順序也就是”Program Order“來執(zhí)行，引入了一些控制執(zhí)行順序的規(guī)則，統(tǒng)一叫做Happens-Before的規(guī)則，簡寫成hb。

簡單說就是，加持了hb屬性的讀寫操作，在執(zhí)行的時候，甚至是多線程執(zhí)行的時候，jmm會保證按照你的意思來執(zhí)行。就上面的例子，volatile boolean flag = true; flag就被jmm加持了hb屬性，jmm會保證對它的寫操作完成后，其他擁有這個變量的線程會立即同步到最新的寫入結(jié)果，也就是能立馬結(jié)束線程的運行。

其實除開volatile關(guān)鍵字有hb語義，還有幾種情況，引自原文：

?1、Each action in a thread happens before every subsequent action in that thread.

?2、An unlock on a monitor happens before every subsequent lock on that monitor.

? 3、A write to a volatile field happens before every subsequent read of that volatile.

? 4、A call to start() on a thread happens before any actions in the started thread.

? 5、All actions in a thread happen before any other thread successfully returns from a join() on that thread.

? 6、If an action a happens before an action b, and b happens before an action c, then a happens before c.

我們例子中是命中了第3條規(guī)則。

問題

大家發(fā)現(xiàn)了一個問題嗎？兩個線程其實共享了兩個變量的，一個是flag還有一個i。問題是，i如果沒有被volatile加持，為啥最后在主線程中輸出i的累加結(jié)果時不是主線程的本地變量0呢？也就是說，主線程執(zhí)行System.out.println("vt value: " + vt.i);的時候，子線程已經(jīng)將i的累加值同步回主線程了。怎么做到的？

我想，問題肯定出在println這個函數(shù)上，它肯定也被加持了hb的屬性了。我們跟進去看看println的實現(xiàn)：

public void println(String x) {
        synchronized (this) {
            print(x);
            newLine();
        }
    }

我們發(fā)現(xiàn)了synchronized關(guān)鍵字，結(jié)合hb規(guī)則第2條，我覺可能是這樣的：

1. synchronized在jvm底層C++代碼中對應(yīng)一個monitor對象；
2. 因為monitor對象有hb語義，也就是在打印x之前，從堆上給我同步下其他線程的結(jié)果。

所以能夠每次打印出正確的i值結(jié)果來。

至于，如果有超過一個線程對i累加，到底同步哪個線程的值，就取決于jvm特定平臺的實現(xiàn)了。

引伸下

既然println有hb的屬性加持，那么是不是可以將程序稍微改下，不用volatile也可以達到讓線程停下來的目的？改一下程序：

public class VolatileTest extends Thread {
    boolean flag = true;
    long count = 0L;

    public void run() {
        while (flag) {
            if (count % 4300000000L == 0 && count != 0L) {//讓程序運行久一點
                System.out.println(count);
            }
            count++;
        }
    }

    public static void main(String[] args) throws Exception {
        VolatileTest vt = new VolatileTest();
        vt.start();
        Thread.sleep(1000);
        setFlag(vt);
        vt.join();
        System.out.println("vt value: " + vt.count);
        System.out.println("stop and final flag is:" + vt.flag);
    }

    private static void setFlag(VolatileTest vt) {
        vt.flag = false;
    }
}

結(jié)果也能停下來：

root@moon-light:~/share/java# java VolatileTest
4300000000
vt value: 4300000001
stop and final flag is:false

也是符合預(yù)期的。

再引伸下

我們知道，jmm的hb就那6種條件，我大膽的猜測下，如果我讓子線程主動切換出去休息，是不是回來后也會同步共享變量呢？如果我是jmm的某個平臺的實現(xiàn)者我會這么做的；因為，發(fā)生線程上下文切換肯定是驚動了內(nèi)核，到內(nèi)核去玩資源了，一定是做了什么不得了的事情，比如網(wǎng)絡(luò)數(shù)據(jù)包來了，文件讀寫了，這么一來大概率會對共享變量有所修改，所以不如同步一把，以免程序員報編譯器bug。

我們就測試一下

public class VolatileTest extends Thread {
    boolean flag = true;
    long count = 0L;

    public void run() {
        while (flag) {
            if (count % 4300000000L == 0 && count != 0L) {
               try {
                 Thread.sleep(1);
               } catch (InterruptedException e) {
                  e.printStackTrace();
               }
            }
            count++;
        }
    }

    public static void main(String[] args) throws Exception {
        VolatileTest vt = new VolatileTest();
        vt.start();
        Thread.sleep(1000);
        setFlag(vt);
        vt.join();
        System.out.println("vt value: " + vt.count);
        System.out.println("stop and final flag is:" + vt.flag);
    }

    private static void setFlag(VolatileTest vt) {
        vt.flag = false;
    }
}

嗯，結(jié)果是也能停下來：

root@moon-light:~/share/java# java VolatileTest
vt value: 4300000001
stop and final flag is:false

一種可能的JMM的內(nèi)存布局

JMM

可以看到，主線程與子線程的線程棧中都有變量i，但是他們并不共享緩存行(CacheLine)，而是通過JMM+執(zhí)行引擎來完成線程同步；實際上JMM的工作機制更像是緩存行一致性協(xié)議負責(zé)在各個線程之間同步信息。所以，JVM的線程并不直接收到CPU的控制，而是受控于JVM，JMM本身。

這也能解釋為啥setFlag(vt);//設(shè)置flag，嘗試停止線程不工作的原因。因為：

1. 兩個線程不共享緩存行；
2. JMM會在合適的時候（那6個hb規(guī)則）更新i在線程棧的值，已同步線程。

問題2

如果真是這樣，那么，對于編譯型語言那豈不是不用加volatile也能同步共享變量了？因為，我知道，多核構(gòu)架下CPU核心之間是有緩存行一致性協(xié)議存在的。比如，Intel就是MESI（modified, exclu- sive, shared, invalid）協(xié)議就是干這個的。這是個很大的話題，不細講了。簡單來說，可以把CPU類比成微服務(wù)中的服務(wù)緩存，當(dāng)擁有多個實例的時候，就要配置緩存的刷新或者一致性協(xié)議，當(dāng)一個服務(wù)實例更新了緩存數(shù)據(jù)，就必須要廣播到其他實例，以免讀臟。

那么，對于C++來說，這個問題的內(nèi)存模型應(yīng)該是：

C++

我們測試下C++的代碼：

#include <iostream>
#include <string>
#include <thread>
#include <mutex>
std::mutex g_display_mutex;

const int TC = 4;
int count = 0;
bool flag = true;
void inc_count()
{
    count += 1;
}
void testRun()
{
    while (flag)
    {
        inc_count();
    }
    g_display_mutex.lock();
    std::cout << "child thread id:" << std::this_thread::get_id() <<" count is:" <<count<<std::endl;
    std::cout << "terminated\n";
    g_display_mutex.unlock();
}

int main()
{
    std::thread threads[TC]; // 默認構(gòu)造線程
    for (int i = 0; i < TC; ++i)
    {
        threads[i] = std::thread(testRun); // move-assign threads
    }

    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "main thread id:" << std::this_thread::get_id() << std::endl;
    flag = false;//終止線程
    for (auto &thread : threads)
    {
        thread.join();
    }

    std::cout << "All threads joined!"
              << " count:" << count;
}

結(jié)果為：

root@moon-light:~/share# g++ -std=c++11 -pthread -g test_volatile_1.cpp -o test_volatile_1
root@moon-light:~/share# ./test_volatile_1
main thread id:140351807989568
child thread id:140351782807296 count is:72319772
terminated
child thread id:140351807985408 count is:72319772
terminated
child thread id:140351799592704 count is:72319772
terminated
child thread id:140351791200000 count is:72319772
terminated

完美的停下來了。

多運行幾次試試

All threads joined! count:62006648root@moon-light:~/share# ./test_volatile_1
main thread id:140251589162816
child thread id:140251563980544 count is:61286071
terminated
child thread id:140251580765952 count is:61262101
terminated
child thread id:140251589158656 count is:61262101
terminated
child thread id:140251572373248 count is:61282797
terminated  

All threads joined! count:70375805root@moon-light:~/share# ./test_volatile_1
main thread id:140332342216512
child thread id:140332333819648 count is:65634928
terminated
child thread id:140332317034240 count is:65634929
terminated
child thread id:140332325426944 count is:65634929
terminated
child thread id:140332342212352 count is:65460361

發(fā)現(xiàn)，確實都停下來了，但是這個累加的結(jié)果好像并不是一樣的，也就是，當(dāng)我設(shè)置完flag = false，如果每個core都實時收到主線程對flag的更新，那么理論上來講每個線程count的結(jié)果是一樣的，為啥會出現(xiàn)差別呢？

而且，我發(fā)現(xiàn)這個差別并不大，鑒于CPU的速度，應(yīng)該只是”卡了“那么一丟丟。

CPU多核構(gòu)架與緩存行一致性協(xié)議

查了很多資料，我發(fā)現(xiàn)很可能跟intel CPU的多核構(gòu)架有關(guān)，有興趣的人可以看看Intel CPU手冊。

簡單來說就是（intel cpu）：

1. 緩存行一致性協(xié)議(MESI)類似于微服務(wù)中的多實例+kafka的模型；

2. 在多核構(gòu)架下，每個核心中的線程共享L1與L2，共享變量會通過L3進行廣播、共享（L3作用類似于Kafka）

3. 在通過L3同步本地變量時，在CPU中還有讀寫buffer，這會影響同步的及時性，也就是可見性的延遲，這個優(yōu)化也是”萬惡之源“（直接導(dǎo)致了cpu也有所謂的happens before屬性的存在）

4. CPU的hb屬性主要是一些內(nèi)存屏障指令最常見的是LOCK指令。

   注：使用讀寫buffer來延遲發(fā)送更新命令很好理解，可以提高系統(tǒng)的吞吐量，但是弊端就是出現(xiàn)同步不及時的問題，這個問題需要使用特殊的CPU指令來規(guī)避；這跟我們平時設(shè)計高并發(fā)讀多寫少時的策略差不多，可見處理IO的策略在各個層次都是一致的。

好了，我們畫個圖來說明。

MESI

說明：

1、CPU不直接跟內(nèi)存打交道，而是通過L1-L3來訪問；

2、CPU每次從內(nèi)存加載一個Cacheline大小的數(shù)據(jù)（跟局部性原理相關(guān)，可以優(yōu)化程序運行速度）；

3、MESI協(xié)議作用在緩存行這個級別，這也是最小的內(nèi)存訪問粒度；

4、L3之上還有個環(huán)形互聯(lián)的總線，MESI用它來廣播數(shù)據(jù)；（類似消息隊列）

5、每個緩存行都有自己的狀態(tài)，MESI通過這些狀態(tài)來在不同的核心之間同步數(shù)據(jù)；

6、當(dāng)T1讀入C1緩存行的時候，會發(fā)送指令到環(huán)形互聯(lián)ring，看看是否有其他核心有C1這個緩存行，如果有，則從ring上拉取下來（從L2）標(biāo)記為S；如果沒有則從L3上?。ɑ蛘邠舸┑絻?nèi)存）并標(biāo)記為Exclusive狀態(tài)；

7、當(dāng)T1要寫C1緩存行的時候，會發(fā)送invalid消息到ring，通知其他core我要寫了，狀態(tài)同步成功后，其他核心中C1變成Invalid狀態(tài)，自己的C1變成Modified狀態(tài)，并發(fā)送指令更新L3與內(nèi)存；

8、當(dāng)其他core要訪問C1，發(fā)現(xiàn)C1狀態(tài)為Invalid，則發(fā)送消息到ring獲取最新的C1值；然后Core1嗅探到這個消息，就將最新的值從L2通知到ring，并將C1狀態(tài)改成Shared；

9、而這個MESI協(xié)議也有同步問題。因為性能問題，不可能每次讀寫都發(fā)送如此多的嗅探消息，性能太低，因此每個核心并不是每次讀寫都會發(fā)送消息，而是在讀端加入讀buffer；寫端加入寫buffer來做緩沖，因此Core對Cacheline的讀寫都有延遲；

10、正是因為這個buffer的存在——core的流水線去讀取buffer有延遲，所以會造成上述例子中每次運行后，每個線程（core）的累加最終結(jié)果不同的原因。這個延遲的存在使得有些core會多運行”幾次“。

猜測

我們稍微改一下程序，讓4個線程做加法，每個線程累加10000次，然后預(yù)期的結(jié)果是4個線程都結(jié)束時，count的值是40000；我想因為有這個buffer的存在，應(yīng)該是加不到40000的。

#include <iostream>
#include <string>
#include <thread>
#include <mutex>
std::mutex g_display_mutex;

const int TC = 4;
int count = 0;
bool flag = true;
void inc_count()
{
    count += 1;
}
void testRun()
{
    for(int i=0; i<10000;i++)
    {
        inc_count();
    }
    g_display_mutex.lock();
    std::cout << "child thread id:" << std::this_thread::get_id() <<" count is:" <<count<<std::endl;
    std::cout << "terminated\n";
    g_display_mutex.unlock();
}

int main()
{
    std::thread threads[TC]; // 默認構(gòu)造線程
    for (int i = 0; i < TC; ++i)
    {
        threads[i] = std::thread(testRun); // move-assign threads
    }

    std::this_thread::sleep_for(std::chrono::seconds(2));
    std::cout << "main thread id:" << std::this_thread::get_id() << std::endl;
    flag = false;
    for (auto &thread : threads)
    {
        thread.join();
    }

    std::cout << "All threads joined!"
              << " count:" << count<<std::endl;
}

運行結(jié)果：

child thread id:139688286332672 count is:10000
terminated
child thread id:139688277939968 count is:20000
terminated
child thread id:139688269547264 count is:31117
terminated
child thread id:139688261154560 count is:37526
terminated
main thread id:139688286336832
All threads joined! count:37526

嗯，不錯，果然加不到40000，

很簡單嘛，因為沒有加鎖，加鎖就行了啊。

對，加鎖當(dāng)然可以解決這個問題，但是鎖是什么呢？鎖是怎么實現(xiàn)的呢？

經(jīng)過我們前面的分析，產(chǎn)生這個現(xiàn)象的根本原因是MESI協(xié)議因為有buffer，所以導(dǎo)致多線程程序在多核運行時共享變量并不能達到強一致性，那么如果最底層都沒法達到強一致性，那么我們寫程序時的鎖又是從哪來的呢？或者說怎么實現(xiàn)的呢？是否有什么操作可以保證強一致性呢？

HACK

我不想寫mutex、synchronized、ReentryLock來同步程序，因為那樣會索然無味，于是，我試圖從Intel手冊中找到答案。

我真的找到了，不然就不會有這篇文章了吧。

在手冊的第三章第8章MULTIPLE-PROCESSOR MANAGEMENT中，我找到了一個叫做LOCK的指令，它可以實現(xiàn)多核多線程的原子指令：

8.1 LOCKED ATOMIC OPERATIONS

The 32-bit IA-32 processors support locked atomic operations on locations in system memory. These operations are typically used to manage shared data structures (such as semaphores, segment descriptors, system segments, or page tables) in which two or more processors may try simultaneously to modify the same field or flag. The processor uses three interdependent mechanisms for carrying out locked atomic operations:

?Guaranteed atomic operations ?Bus locking, using the LOCK# signal and the LOCK instruction prefix

?Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

簡單來說就是：LOCK是一種指令前綴，能夠加這個前綴的指令就能保證操作的原子性（多核下），可以實現(xiàn)對內(nèi)存的原子訪問，是實現(xiàn)鎖的基礎(chǔ)。

哪些指令可以加這個前綴呢？繼續(xù)翻手冊。

To explicitly force the LOCK semantics, software can use the LOCK prefix with the following instructions when they are used to modify a memory location. An invalid-opcode exception (#UD) is generated when the LOCK prefix is used with any other instruction or when no write operation is made to memory (that is, when the destination operand is in a register).
?The bit test and modify instructions (BTS, BTR, and BTC).
?The exchange instructions (XADD, CMPXCHG, and CMPXCHG8B).
?The LOCK prefix is automatically assumed for XCHG instruction.
?The following single-operand arithmetic and logical instructions: INC, DEC, NOT , and NEG.
?The following two-operand arithmetic and logical instructions: ADD, ADC, SUB, SBB, AND, OR, and XOR.

可以看到有個ADD指令，是的count+=1不就是Add操作嗎？那我們不就有辦法用這個最原始的鎖來實現(xiàn)多線程累加程序了嗎？

我們知道，CPU上層是匯編，我想java肯定干不成這事了，只能用C++了。

void inc_count()
{
    asm("movl   $1, %eax");
    asm("lock addl %eax,count(%rip)");
}

我們只需要修改inc_count函數(shù)即可，在這個函數(shù)中顯式的調(diào)用LOCK指令來強制同步下緩存行即可。

編譯、鏈接、運行...

root@moon-light:~/share# ./test_volatile_2
main thread id:139873222453056
child thread id:139873222448896 count is:17628
terminated
child thread id:139873214056192 count is:24639
terminated
child thread id:139873205663488 count is:35229
terminated
child thread id:139873197270784 count is:40000
terminated
All threads joined! count:40000
root@moon-light:~/share# ./test_volatile_2
main thread id:140615447291712
child thread id:140615447287552 count is:13509
terminated
child thread id:140615430502144 count is:24803
terminated
child thread id:140615422109440 count is:33008
terminated
child thread id:140615438894848 count is:40000
terminated
All threads joined! count:40000
root@moon-light:~/share# ./test_volatile_2
main thread id:140172760246080
child thread id:140172760241920 count is:17644
terminated
child thread id:140172751849216 count is:29650
terminated
child thread id:140172743456512 count is:32806
terminated
child thread id:140172735063808 count is:40000
terminated
All threads joined! count:40000

不管運行了多少次都是正確的結(jié)果——40000。

去掉LOCK再試試？

void inc_count()
{
    asm("movl   $1, %eax");
    asm("addl %eax,count(%rip)");
}

結(jié)果是：

root@moon-light:~/share# ./test_volatile_2
main thread id:child thread id:140026343032640140026343028480 count is:
15217
terminated
child thread id:140026326243072 count is:26761
terminated
child thread id:140026334635776 count is:26761
terminated
child thread id:140026317850368 count is:26761
terminated
All threads joined! count:26761
root@moon-light:~/share# ./test_volatile_2
main thread id:child thread id:140632667023168140632658626304 count is:
12776
terminated
child thread id:140632667019008 count is:33191
terminated
child thread id:140632650233600 count is:33191
terminated
child thread id:140632641840896 count is:33191
terminated
All threads joined! count:33191
root@moon-light:~/share# ./test_volatile_2
main thread id:child thread id:140121883453248140121883449088 count is:
10000
terminated
child thread id:140121875056384 count is:29073
terminated
child thread id:140121866663680 count is:32190
terminated
child thread id:140121858270976 count is:37510
terminated
All threads joined! count:37510

結(jié)果又回到了最初。

有了這個指令，我想什么synchronized、CAS、volatile不就都能理解了嗎？它們都依賴這個最底層的指令，而且據(jù)說這個指令是所有CPU都必須實現(xiàn)的，所以Linux、JVM都在大量使用。在底層代碼中看到這個就不足為奇了。

具體怎么用這個指令實現(xiàn)這些鎖，那就到下篇文章講解了。

另外不管什么語言，框架如果說自己是最快的、最好的，多半是假的，可以想想Intel有幾千頁的文檔，你最好的方案永遠都出自硬件的支持；應(yīng)該只有在某些方面表現(xiàn)比其他工具更好而已，不存在絕對性。

總結(jié)

多線程編程，有趣而又深邃。

往大了說能夠提升性能，有著化腐朽為神奇的力量；

往深了說涉及到CPU、操作系統(tǒng)與編程語言的精準(zhǔn)操控

總之，趣味十足。