摘要：從視角理解系統(tǒng)結(jié)構(gòu)連載關(guān)注我的微博鏈接了解最新動(dòng)態(tài)從我的前一篇博文中我們知道了緩存及緩存行的概念同時(shí)用一個(gè)例子說(shuō)明了編寫(xiě)單線程代碼時(shí)應(yīng)該注意的問(wèn)題下面我們討論更為復(fù)雜而且更符合現(xiàn)實(shí)情況的多核編程時(shí)將會(huì)碰到的問(wèn)題這些問(wèn)題更容易犯連包作者大師的

從Java視角理解系統(tǒng)結(jié)構(gòu)連載, 關(guān)注我的微博(鏈接)了解最新動(dòng)態(tài)

從我的前一篇博文中, 我們知道了CPU緩存及緩存行的概念, 同時(shí)用一個(gè)例子說(shuō)明了編寫(xiě)單線程Java代碼時(shí)應(yīng)該注意的問(wèn)題. 下面我們討論更為復(fù)雜, 而且更符合現(xiàn)實(shí)情況的多核編程時(shí)將會(huì)碰到的問(wèn)題. 這些問(wèn)題更容易犯, 連j.u.c包作者Doug Lea大師的JDK代碼里也存在這些問(wèn)題.

從前一篇我們知道, 典型的CPU微架構(gòu)有3級(jí)緩存, 每個(gè)核都有自己私有的L1, L2緩存. 那么多線程編程時(shí), 另外一個(gè)核的線程想要訪問(wèn)當(dāng)前核內(nèi)L1, L2 緩存行的數(shù)據(jù), 該怎么辦呢?

有人說(shuō)可以通過(guò)第2個(gè)核直接訪問(wèn)第1個(gè)核的緩存行. 這是可行的, 但這種方法不夠快. 跨核訪問(wèn)需要通過(guò)Memory Controller(見(jiàn)上一篇的示意圖), 典型的情況是第2個(gè)核經(jīng)常訪問(wèn)第1個(gè)核的這條數(shù)據(jù), 那么每次都有跨核的消耗. 更糟的情況是, 有可能第2個(gè)核與第1個(gè)核不在一個(gè)插槽內(nèi).況且Memory Controller的總線帶寬是有限的, 扛不住這么多數(shù)據(jù)傳輸. 所以, CPU設(shè)計(jì)者們更偏向于另一種辦法: 如果第2個(gè)核需要這份數(shù)據(jù), 由第1個(gè)核直接把數(shù)據(jù)內(nèi)容發(fā)過(guò)去, 數(shù)據(jù)只需要傳一次。

那么什么時(shí)候會(huì)發(fā)生緩存行的傳輸呢? 答案很簡(jiǎn)單: 當(dāng)一個(gè)核需要讀取另外一個(gè)核的臟緩存行時(shí)發(fā)生.
但是前者怎么判斷后者的緩存行已經(jīng)被弄臟(寫(xiě))了呢?

下面將詳細(xì)地解答以上問(wèn)題.

首先我們需要談到一個(gè)協(xié)議–MESI協(xié)議(鏈接). 現(xiàn)在主流的處理器都是用它來(lái)保證緩存的相干性和內(nèi)存的相干性. M,E,S和I代表使用MESI協(xié)議時(shí)緩存行所處的四個(gè)狀態(tài):

M(修改, Modified): 本地處理器已經(jīng)修改緩存行, 即是臟行, 它的內(nèi)容與內(nèi)存中的內(nèi)容不一樣. 并且此cache只有本地一個(gè)拷貝(專有).

E(專有, Exclusive): 緩存行內(nèi)容和內(nèi)存中的一樣, 而且其它處理器都沒(méi)有這行數(shù)據(jù)

S(共享, Shared): 緩存行內(nèi)容和內(nèi)存中的一樣, 有可能其它處理器也存在此緩存行的拷貝

I(無(wú)效, Invalid): 緩存行失效, 不能使用

上圖源自于內(nèi)核開(kāi)發(fā)者Ulrich Drepper著名的What Every Programmer Should Know About Memory一書(shū)(下載), 簡(jiǎn)要地展示了緩存行的四種狀態(tài)轉(zhuǎn)換. 不過(guò)他的書(shū)中沒(méi)有說(shuō)明白這四個(gè)狀態(tài)是怎么轉(zhuǎn)換的, 下面我用小段文字來(lái)說(shuō)明一下.

初始?一開(kāi)始時(shí), 緩存行沒(méi)有加載任何數(shù)據(jù), 所以它處于I狀態(tài).

本地寫(xiě)(Local Write)如果本地處理器寫(xiě)數(shù)據(jù)至處于I狀態(tài)的緩存行, 則緩存行的狀態(tài)變成M.

本地讀(Local Read)?如果本地處理器讀取處于I狀態(tài)的緩存行, 很明顯此緩存沒(méi)有數(shù)據(jù)給它. 此時(shí)分兩種情況:

其它處理器的緩存里也沒(méi)有此行數(shù)據(jù), 則從內(nèi)存加載數(shù)據(jù)到此緩存行后,
再將它設(shè)成E狀態(tài), 表示只有我一家有這條數(shù)據(jù), 其它處理器都沒(méi)有

其它處理器的緩存有此行數(shù)據(jù), 則將此緩存行的狀態(tài)設(shè)為S狀態(tài).

P.S.如果處于M狀態(tài)的緩存行, 再由本地處理器寫(xiě)入/讀出, 狀態(tài)是不會(huì)改變的.

遠(yuǎn)程讀(Remote Read)?假設(shè)我們有兩個(gè)處理器c1和c2. 如果c2需要讀另外一個(gè)處理器c1的緩存行內(nèi)容, c1需要把它緩存行的內(nèi)容通過(guò)內(nèi)存控制器(Memory Controller)發(fā)送給c2, c2接到后將相應(yīng)的緩存行狀態(tài)設(shè)為S. 在設(shè)置之前, 內(nèi)存也得從總線上得到這份數(shù)據(jù)并保存.

遠(yuǎn)程寫(xiě)(Remote Write)?其實(shí)確切地說(shuō)不是遠(yuǎn)程寫(xiě), 而是c2得到c1的數(shù)據(jù)后, 不是為了讀, 而是為了寫(xiě). 也算是本地寫(xiě), 只是c1也擁有這份數(shù)據(jù)的拷貝, 這該怎么辦呢? c2將發(fā)出一個(gè)RFO(Request For Owner)請(qǐng)求, 它需要擁有這行數(shù)據(jù)的權(quán)限, 其它處理器的相應(yīng)緩存行設(shè)為I, 除了它自已, 誰(shuí)不能動(dòng)這行數(shù)據(jù). 這保證了數(shù)據(jù)的安全, 同時(shí)處理RFO請(qǐng)求以及設(shè)置I的過(guò)程將給寫(xiě)操作帶來(lái)很大的性能消耗.

以上只是列舉了一些狀態(tài)轉(zhuǎn)換, 為下文做鋪墊. 如果全部描述,需要非常大量的文字, 大家參考這張圖就知道原因了, 可以通過(guò)此圖了解MESI協(xié)議更詳細(xì)的信息.

我們從上節(jié)知道, 寫(xiě)操作的代價(jià)很高, 特別當(dāng)需要發(fā)送RFO消息時(shí). 我們編寫(xiě)程序時(shí), 什么時(shí)候會(huì)發(fā)生RFO請(qǐng)求呢? 有以下兩種:

線程的工作從一個(gè)處理器移到另一個(gè)處理器, 它操作的所有緩存行都需要移到新的處理器上. 此后如果再寫(xiě)緩存行, 則此緩存行在不同核上有多個(gè)拷貝, 需要發(fā)送RFO請(qǐng)求了.

兩個(gè)不同的處理器確實(shí)都需要操作相同的緩存行

由上一篇我們知道, 在Java程序中,數(shù)組的成員在緩存中也是連續(xù)的. 其實(shí)從Java對(duì)象的相鄰成員變量也會(huì)加載到同一緩存行中. 如果多個(gè)線程操作不同的成員變量, 但是相同的緩存行, 偽共享(False Sharing)問(wèn)題就發(fā)生了. 下面引用Disruptor項(xiàng)目Lead的博文中的示例圖和實(shí)驗(yàn)例子(偷會(huì)懶,但會(huì)加上更詳細(xì)的profile方法).

一個(gè)運(yùn)行在處理器core 1上的線程想要更新變量X的值, 同時(shí)另外一個(gè)運(yùn)行在處理器core 2上的線程想要更新變量Y的值. 但是, 這兩個(gè)頻繁改動(dòng)的變量都處于同一條緩存行. 兩個(gè)線程就會(huì)輪番發(fā)送RFO消息, 占得此緩存行的擁有權(quán). 當(dāng)core 1取得了擁有權(quán)開(kāi)始更新X, 則core 2對(duì)應(yīng)的緩存行需要設(shè)為I狀態(tài). 當(dāng)core 2取得了擁有權(quán)開(kāi)始更新Y, 則core 1對(duì)應(yīng)的緩存行需要設(shè)為I狀態(tài)(失效態(tài)). 輪番奪取擁有權(quán)不但帶來(lái)大量的RFO消息, 而且如果某個(gè)線程需要讀此行數(shù)據(jù)時(shí), L1和L2緩存上都是失效數(shù)據(jù), 只有L3緩存上是同步好的數(shù)據(jù).從前一篇我們知道, 讀L3的數(shù)據(jù)非常影響性能. 更壞的情況是跨槽讀取, L3都要miss,只能從內(nèi)存上加載.

表面上X和Y都是被獨(dú)立線程操作的, 而且兩操作之間也沒(méi)有任何關(guān)系.只不過(guò)它們共享了一個(gè)緩存行, 但所有競(jìng)爭(zhēng)沖突都是來(lái)源于共享.

引用Martin的例子, 稍做修改,代碼如下:

public final class FalseSharing implements Runnable {
    public static int NUM_THREADS = 4; // change
    public final static long ITERATIONS = 500L * 1000L * 1000L;
    private final int arrayIndex;
    private static VolatileLong[] longs;

    public FalseSharing(final int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }

    public static void main(final String[] args) throws Exception {
        Thread.sleep(10000);
        System.out.println("starting....");
        if (args.length == 1) {
            NUM_THREADS = Integer.parseInt(args[0]);
        }

        longs = new VolatileLong[NUM_THREADS];
        for (int i = 0; i < longs.length; i++) {
            longs[i] = new VolatileLong();
        }
        final long start = System.nanoTime();
        runTest();
        System.out.println("duration = " + (System.nanoTime() - start));
    }

    private static void runTest() throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(new FalseSharing(i));
        }
        for (Thread t : threads) {
            t.start();
        }
        for (Thread t : threads) {
            t.join();
        }
    }

    public void run() {
        long i = ITERATIONS + 1;
        while (0 != --i) {
            longs[arrayIndex].value = i;
        }
    }

    public final static class VolatileLong {
        public volatile long value = 0L;
        public long p1, p2, p3, p4, p5, p6; // 注釋
    }
}

代碼的邏輯是默認(rèn)4個(gè)線程修改一數(shù)組不同元素的內(nèi)容.? 元素的類型是VolatileLong, 只有一個(gè)長(zhǎng)整型成員value和6個(gè)沒(méi)用到的長(zhǎng)整型成員. value設(shè)為volatile是為了讓value的修改所有線程都可見(jiàn). 在一臺(tái)Westmere(Xeon E5620 8core*2)機(jī)器上跑一下看

$ java FalseSharing
starting....
duration = 9316356836

$ java FalseSharing
starting....
duration = 59791968514

兩個(gè)邏輯一模一樣的程序, 前者只需要9秒, 后者跑了將近一分鐘, 這太不可思議了! 我們用偽共享(False Sharing)的理論來(lái)分析一下. 后面的那個(gè)程序longs數(shù)組的4個(gè)元素,由于VolatileLong只有1個(gè)長(zhǎng)整型成員, 所以整個(gè)數(shù)組都將被加載至同一緩存行, 但有4個(gè)線程同時(shí)操作這條緩存行, 于是偽共享就悄悄地發(fā)生了. 讀者可以測(cè)試一下2,4,8, 16個(gè)線程分別操作時(shí)分別是什么效果, 什么樣的趨勢(shì).

那么怎么避免偽共享呢? 我們未注釋的代碼就告訴了我們方法. 我們知道一條緩存行有64字節(jié), 而Java程序的對(duì)象頭固定占8字節(jié)(32位系統(tǒng))或12字節(jié)(64位系統(tǒng)默認(rèn)開(kāi)啟壓縮, 不開(kāi)壓縮為16字節(jié)), 詳情見(jiàn)?鏈接. 我們只需要填6個(gè)無(wú)用的長(zhǎng)整型補(bǔ)上6*8=48字節(jié), 讓不同的VolatileLong對(duì)象處于不同的緩存行, 就可以避免偽共享了(64位系統(tǒng)超過(guò)緩存行的64字節(jié)也無(wú)所謂,只要保證不同線程不要操作同一緩存行就可以). 這個(gè)辦法叫做補(bǔ)齊(Padding).

如何從系統(tǒng)層面觀察到這種優(yōu)化是切實(shí)有效的呢? 很可惜, 由于很多計(jì)算機(jī)的微架構(gòu)不同, 我們沒(méi)有工具來(lái)直接探測(cè)偽共享事件(包括Intel Vtune和Valgrind). 所有的工具都是從側(cè)面來(lái)發(fā)現(xiàn)的, 下面通過(guò)Linux利器OProfile來(lái)證明一下. 上面的程序的數(shù)組只是占64 * 4 = 256字節(jié), 而且在連續(xù)的物理空間, 照理來(lái)說(shuō)數(shù)據(jù)會(huì)在L1緩存上就命中, 肯定不會(huì)傳入到L2緩存中, 只有在偽共享發(fā)生時(shí)才會(huì)出現(xiàn). 于是, 我們可以通過(guò)觀察L2緩存的IN事件就可以證明了,步驟如下:

# 設(shè)置捕捉L2緩存IN事件
$ sudo  opcontrol --setup --event=L2_LINES_IN:100000
# 清空工作區(qū)
$ sudo opcontrol --reset
# 開(kāi)始捕捉
$ sudo opcontrol --start
# 運(yùn)行程序
$ java FalseSharing
# 程序跑完后, dump捕捉到的數(shù)據(jù)
$ sudo opcontrol --dump
# 停止捕捉
$ sudo opcontrol -h
# 報(bào)告結(jié)果
$ opreport -l `which java`

比較一下兩個(gè)版本的結(jié)果, 慢的版本:

$ opreport -l `which java`
CPU: Intel Westmere microarchitecture, speed 2400.2 MHz (estimated)
Counted L2_LINES_IN events (L2 lines alloacated) with a unit mask of 0x07 (any L2 lines alloacated) count 100000
samples  %        image name               symbol name
34085    99.8447  anon (tgid:18051 range:0x7fcdee53d000-0x7fcdee7ad000) anon (tgid:18051 range:0x7fcdee53d000-0x7fcdee7ad000)
51        0.1494  anon (tgid:16054 range:0x7fa485722000-0x7fa485992000) anon (tgid:16054 range:0x7fa485722000-0x7fa485992000)
2         0.0059  anon (tgid:2753 range:0x7f43b317e000-0x7f43b375e000) anon (tgid:2753 range:0x7f43b317e000-0x7f43b375e000)

快的版本:

$ opreport -l `which java`
CPU: Intel Westmere microarchitecture, speed 2400.2 MHz (estimated)
Counted L2_LINES_IN events (L2 lines alloacated) with a unit mask of 0x07 (any L2 lines alloacated) count 100000
samples  %        image name               symbol name
22       88.0000  anon (tgid:18873 range:0x7f3e3fa8a000-0x7f3e3fcfa000) anon (tgid:18873 range:0x7f3e3fa8a000-0x7f3e3fcfa000)
3        12.0000  anon (tgid:2753 range:0x7f43b317e000-0x7f43b375e000) anon (tgid:2753 range:0x7f43b317e000-0x7f43b375e000)

慢的版本由于False Sharing引發(fā)的L2緩存IN事件達(dá)34085次, 而快版本的為0次.

偽共享在多核編程中很容易發(fā)生, 而且比較隱蔽. 例如, 在JDK的LinkedBlockingQueue中, 存在指向隊(duì)列頭的引用head和指向隊(duì)列尾的引用last. 而這種隊(duì)列經(jīng)常在異步編程中使有,這兩個(gè)引用的值經(jīng)常的被不同的線程修改, 但它們卻很可能在同一個(gè)緩存行, 于是就產(chǎn)生了偽共享. 線程越多, 核越多,對(duì)性能產(chǎn)生的負(fù)面效果就越大. 某些Java編譯器會(huì)將沒(méi)有使用到的補(bǔ)齊數(shù)據(jù), 即示例代碼中的6個(gè)長(zhǎng)整型在編譯時(shí)優(yōu)化掉, 可以在程序中加入一些代碼防止被編譯優(yōu)化。

public static long preventFromOptimization(VolatileLong v) {
    return v.p1 + v.p2 + v.p3 + v.p4 + v.p5 + v.p6;
}

另外, 由于Java的GC問(wèn)題. 數(shù)據(jù)在內(nèi)存和對(duì)應(yīng)的CPU緩存行的位置有可能發(fā)生變化,
所以在使用pad的時(shí)候應(yīng)該注意GC的影響.

最后感謝同事撒迦,?長(zhǎng)仁在Java對(duì)象內(nèi)存布局及Profile工具上給予的幫助.

更新:

發(fā)現(xiàn)netty和grizzly的代碼中的LinkedTransferQueue中都使用了PaddedAtomicReference來(lái)代替原來(lái)的Node, 使用了補(bǔ)齊的辦法解決了隊(duì)列偽共享的問(wèn)題. 不知道是不是JSR-166的人開(kāi)發(fā)的, 看來(lái)他們?cè)缇鸵庾R(shí)到這個(gè)問(wèn)題了. 但是從Doug Lea JSR-166的cvs看不到這個(gè)變化, 不知道究竟是誰(shuí)改的? 他們的repository到底是在哪?

by MinZhou via ifeve