绝色狂妃仙魅小说,神武八荒一颗小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

關(guān)于多線程同步的一切：偽共享

```c++
const size_t shm_size = 16*1024*1024; //16M
static char shm[shm_size];
std::atomic shm_offset{0};


void f() {
   for (;;) {
       auto off = shm_offset.fetch_add(sizeof(long));
       if (off >= shm_size) break;
       *(long*)(shm + off) = off;
   }
}
```

考察上面的程序，shm是一塊16M字節(jié)的內(nèi)存，我測試機(jī)器的L3 Cache是32M，所以挑選16M這個值確保shm數(shù)組在Cache里能存放得下。

在招遠(yuǎn)等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都做網(wǎng)站網(wǎng)站設(shè)計制作按需設(shè)計網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)整合營銷推廣,外貿(mào)網(wǎng)站建設(shè),招遠(yuǎn)網(wǎng)站建設(shè)費(fèi)用合理。

f()函數(shù)在循環(huán)里，把shm視為long類型的數(shù)組，依次給每個元素賦值，shm_offset用于記錄偏移位置，shm_offset.fetch_add(sizeof(long))原子性的增加shm_offset的值（因為x86_64系統(tǒng)上long的長度為8，所以shm_offset每次增加8字節(jié)），并返回增加前的值，對shm上long數(shù)組的每個元素賦值后，結(jié)束循環(huán)從函數(shù)返回。

因為shm_offset是atomic類型變量，所以多線程調(diào)用f()依然能正常工作，雖然多個線程會競爭shm_offset，但每個線程會排他性的對各long元素賦值，多線程并行會加快對shm的賦值操作。

我們加上多線程調(diào)用，代碼如下：

```c++
std::atomic step{0};


const int THREAD_NUM = 2;


void work_thread() {
   const int N = 10;
   for (int n = 1; n <= N; ++n) {
       f();
       ++step;
       while (step.load() < n * THREAD_NUM) {}
       shm_offset = 0;
   }
}


int main() {
   std::thread threads[THREAD_NUM];
   for (int i = 0; i < THREAD_NUM; ++i) {
       threads[i] = std::move(std::thread(work_thread));
   }
   for (int i = 0; i < THREAD_NUM; ++i) {
       threads[i].join();
   }
   return 0;
}
```

main函數(shù)里啟動2個工作線程work_thread
工作線程對shm共計賦值N（10）輪，后面的每一輪會訪問Cache里的shm數(shù)據(jù)，step用于work_thread之間每一輪的同步
工作線程調(diào)用完f()后會增加step，等2個工作線程都調(diào)用完之后，step的值增加到n * THREAD_NUM后，while()循環(huán)結(jié)束，重置shm_offset，重新開始新一輪對shm的賦值

編譯后執(zhí)行上面的程序，產(chǎn)生如下的結(jié)果：

```
time ./a.out

real 0m3.406s
user 0m6.740s
sys 0m0.040s
```

time命令用于時間測量，在a.out程序運(yùn)行完成，會打印耗時，real行顯式耗時3.4秒。

改進(jìn)版f_fast

我們稍微修改一下f函數(shù)，改進(jìn)版f函數(shù)取名f_fast：

```c++
void f_fast() {
   for (;;) {
       const long inner_loop = 16;
       auto off = shm_offset.fetch_add(sizeof(long) * inner_loop);
       for (long j = 0; j < inner_loop; ++j) {
           if (off >= shm_size) return;
           *(long*)(shm + off) = j;
           off += sizeof(long);
       }
   }
}
```

for循環(huán)里，shm_offset不再是每次增加8字節(jié)（sizeof(long)），而是8*16=128字節(jié)，然后在內(nèi)層的循環(huán)里，依次對16個long連續(xù)元素賦值，然后下一輪循環(huán)又再次增加128字節(jié)，直到完成對整個shm的賦值。

編譯后重新執(zhí)行程序，結(jié)果顯示耗時降低到0.06秒，對比前一種耗時3.4秒，f_fast性能大幅提升。

```
time ./a.out

real 0m0.062s
user 0m0.110s
sys 0m0.012s
```

f和f_fast的行為差異

shm數(shù)組總共有2M個long元素，因為16M / sizeof(long) => 2M，

1. f()函數(shù)行為邏輯

線程1和線程2的work_thread里會交錯地對shm元素賦值，shm的2M個long元素，會順序的一個接一個的派給2個線程去賦值。

例如：

可能元素1由線程1賦值，元素2由線程2賦值，然后元素3和元素4由線程1賦值，然后元素5由線程2賦值...
每次派元素的時候，shm_offset都會atomic的增加8字節(jié)，所以不會出現(xiàn)2個線程給1個元素賦值的情況

2. f_fast()函數(shù)行為邏輯

每次派元素的時候，shm_offset原子性的增加128字節(jié)（16個元素）
這16個字節(jié)作為一個整體，派給線程1或者線程2；雖然線程1和線程2還是會交錯的操作shm元素，但是以16個元素（128字節(jié)）為單元，這16個連續(xù)的元素不會被分派到不同線程
一次派發(fā)的16個元素，會在內(nèi)部循環(huán)里被一個接著一個的賦值，在一個線程里執(zhí)行

為什么f_fast更快？

第一眼感覺是f_fast()里shm_offset.fetch_add()調(diào)用頻次降低到了原來的1/16，我們有理由懷疑是原子變量的競爭減少導(dǎo)致程序執(zhí)行速度加快。

為了驗證，讓我們在內(nèi)層的循環(huán)里加一個原子變量test的fetch_add，test原子變量的競爭會像f()函數(shù)里shm_offset.fetch_add()一樣被激烈競爭，修改后的f_fast代碼變成下面這樣：

```c++
void f_fast() {
   for (;;) {
       const long inner_loop = 16;
       auto off = shm_offset.fetch_add(sizeof(long) * inner_loop);
       for (long j = 0; j < inner_loop; ++j) {
           test.fetch_add(1);
           if (off >= shm_size) return;
           *(long*)(shm + off) = j;
           off += sizeof(long);
       }
   }
}
```

為了避免test.fetch_add(1)的調(diào)用被編譯器優(yōu)化掉，我們在main函數(shù)的最后把test的值打印出來。

編譯后測試一下，結(jié)果顯示：執(zhí)行時間只是稍微增加到`real 0m0.326s`。所以，很顯然，并不是atomic的調(diào)用頻次減少導(dǎo)致性能飆升。

我們重新審視f()循環(huán)里的邏輯：f()循環(huán)里的操作很簡單：原子增加、判斷、賦值。

會不會是賦值太慢？

我們把f()的里賦值注釋掉，再測試一下，發(fā)現(xiàn)它的速度得到了很大提升，看來是`*(long*)(shm + off) = off;`這一行代碼執(zhí)行慢，但這明明只是一行賦值。

我們把它反匯編來看，它只是一個mov指令，源操作數(shù)是寄存器，目標(biāo)操作數(shù)是內(nèi)存地址，從寄存器拷貝數(shù)據(jù)到一個內(nèi)存地址，而這個內(nèi)存數(shù)據(jù)應(yīng)該被cache住了，為什么會這么慢呢？

答案

現(xiàn)在揭曉原因，導(dǎo)致f()性能底下的元兇是偽共享（false sharing），那什么是偽共享？

要說清這個問題，還得聯(lián)系CPU的架構(gòu)，以及CPU怎么訪問數(shù)據(jù)，我們回顧一下關(guān)于多核Cache結(jié)構(gòu)：

背景知識

我們知道現(xiàn)代CPU可以有多個核，每個核有自己的L1-L2緩存，L1又區(qū)分?jǐn)?shù)據(jù)緩存（L1-DCache）和指令緩存（L1-ICache），L2不區(qū)分?jǐn)?shù)據(jù)和指令Cache，而L3跨核共享，L3通過內(nèi)存總線連接到內(nèi)存，內(nèi)存被所有CPU所有Core共享。

CPU訪問L1 Cache的速度大約是訪問內(nèi)存的100倍，Cache作為CPU與內(nèi)存之間的緩存，減少CPU對內(nèi)存的訪問頻率。

從內(nèi)存加載數(shù)據(jù)到Cache的時候，是以Cache Line為長度單位的，Cache Line的長度通常是64字節(jié)。

所以，那怕只讀一個字節(jié)，但是包含該字節(jié)的整個Cache Line都會被加載到緩存，同樣，如果修改一個字節(jié)，那么最終也會導(dǎo)致整個Cache Line被沖刷到內(nèi)存。

如果一塊內(nèi)存數(shù)據(jù)被多個線程訪問，假設(shè)多個線程在多個Core上并行執(zhí)行，那么它便會被加載到多個Core的的Local Cache中；這些線程在哪個Core上運(yùn)行，就會被加載到哪個Core的Local Cache中，所以，內(nèi)存中的一個數(shù)據(jù)，在不同Core的Cache里會同時存在多份拷貝。

如果我們修改了Core1緩存里的某個數(shù)據(jù)，則該數(shù)據(jù)所在的Cache Line的狀態(tài)需要同步給其他Core的緩存，Core之間可以通過核間消息同步狀態(tài)，比如通過發(fā)送Invalidate消息給其他核，接收到該消息的核會把對應(yīng)Cache Line置為無效，然后重新從內(nèi)存里加載最新數(shù)據(jù)。

被加載到多個Core緩存中的同一Cache Line，會被標(biāo)記為共享（Shared）狀態(tài)，對共享狀態(tài)的緩存行進(jìn)行修改，需要先獲取緩存行的修改權(quán)（獨(dú)占），MESI協(xié)議用來保證多核緩存的一致性，更多的細(xì)節(jié)可以參考MESI資料。

示例分析

現(xiàn)在來看看我們的程序。

假設(shè)線程1運(yùn)行在Core1，線程2運(yùn)行在Core2。

因為shm被線程1和線程2這兩個線程并發(fā)訪問，所以shm的內(nèi)存數(shù)據(jù)會以Cache Line粒度，被同時加載到2個Core的Cache，因為被多核共享，所以該Cache Line被標(biāo)注為Shared狀態(tài)。

假設(shè)線程1在offset為64的位置寫入了一個8字節(jié)的數(shù)據(jù)（sizeof(long)），要修改一個狀態(tài)為Shared的Cache Line，Core1會發(fā)送核間通信消息到Core2，去拿到該Cache Line的獨(dú)占權(quán)，在這之后，Core1才能修改Local Cache。

線程1執(zhí)行完`shm_offset.fetch_add(sizeof(long))`后，shm_offset會增加到72。

這時候Core2上運(yùn)行的線程2也會執(zhí)行`shm_offset.fetch_add(sizeof(long))`，它返回72并將shm_offset增加到80。

線程2接下來要修改shm[72]的內(nèi)存位置，因為shm[64]和shm[72]在一個Cache Line，而這個Cache Line又被置為Invalidate，所以，它需要從內(nèi)存里重新加載這一個Cache Line，而在這之前，Core1上的線程1需要把Cache Line沖刷到內(nèi)存，這樣線程2才能加載最新的數(shù)據(jù)。

這種交替執(zhí)行模式，相當(dāng)于Core1和Core2之間需要頻繁的發(fā)送核間消息，收到消息的Core的對應(yīng)Cache Line被置為無效，并重新從內(nèi)存里加載數(shù)據(jù)到Cache，每次修改后都需要把Cache中的數(shù)據(jù)刷入內(nèi)存。

這其實相當(dāng)于廢棄掉了Cache，因為每次讀寫都直接跟內(nèi)存打交道，Cache的作用不復(fù)存在，性能下降。

多核多線程程序，因為并發(fā)讀寫同一個Cache Line的數(shù)據(jù)（臨近位置的內(nèi)存數(shù)據(jù)），導(dǎo)致Cache Line的頻繁失效，內(nèi)存的頻繁Load/Store，從而導(dǎo)致性能急劇下降的現(xiàn)象叫偽共享，偽共享是性能殺手。

另一個偽共享的例子

假設(shè)線程x和y，分別修改Data的a和b變量，如果被頻繁調(diào)用，根據(jù)前面的分析，也會出現(xiàn)性能低下的情況，怎么規(guī)避呢？

```c++
struct Data {
   int a;
   int b;
};

Data data; // global

void thread1() {
   data.a = 1;
}

void thread2() {
   data.b = 2;
}
```

**空間換時間**

避免Cache偽共享導(dǎo)致性能下降的思路是用空間換時間，通過在a和b成員之間增加填充，讓a、b兩個變量分布到不同的Cache Line，這樣對a和b的修改就會作用于不同Cache Line，就能避免Cache line失效的問題。

```c++
struct Data {
   int a;
   int padding[60];
   int b;
};
```

在Linux kernel中存在__cacheline_aligned_in_smp宏定義用于解決false sharing問題。

```c
#ifdef CONFIG_SMP
#define __cacheline_aligned_in_smp __cacheline_aligned
#else
#define __cacheline_aligned_in_smp
#endif

struct Data {
   int a;
   int b __cacheline_aligned_in_smp;
};
```

從上面的宏定義，我們可以看到：

在多核（MP）系統(tǒng)里，該宏定義是 __cacheline_aligned，也就是Cache Line的大小
在單核系統(tǒng)里，該宏定義是空的

偽共享的疑問

既然多CPU多核并發(fā)讀寫一個Cache Line里的內(nèi)存數(shù)據(jù)，會出現(xiàn)偽共享，那么，我們對`atomic shm_offset`的fetch_add()操作也滿足這個條件，多個線程同時對同一個shm_offset變量并發(fā)讀寫，那為什么性能不會很差呢？

我們反匯編發(fā)現(xiàn)`atomic.fetch_add`會被翻譯成`lock; xadd %rax (%rdx)`，lock是一個指令前綴，配合其他指令使用。

bus lock做的事情就是鎖住總線，然后執(zhí)行后面的xadd，在此期間，別的線程都不能訪問任何內(nèi)存數(shù)據(jù)。

實際上，鎖總線的操作比較重，相當(dāng)于全局的內(nèi)存總線鎖，lock前綴之后的指令操作就直接作用于內(nèi)存，bypass掉緩存，lock也相當(dāng)于內(nèi)存屏障。

但翻看Intel手冊發(fā)現(xiàn)，執(zhí)行l(wèi)ock指令，CPU會根據(jù)情況自行決定到底是鎖緩存，還是assert #LOCK signal（鎖總線）。

如果訪問的內(nèi)存區(qū)域已經(jīng)緩存在處理器的緩存行中，Intel的現(xiàn)代處理器則不會assert #LOCK信號，它會對CPU的緩存中的緩存行進(jìn)行鎖定，在鎖定期間，其它CPU不能同時緩存此數(shù)據(jù)，在修改之后，通過緩存一致性協(xié)議來保證修改的原子性，這個操作被稱為“緩存鎖”。

false sharing對應(yīng)的是多線程同時讀寫一個Cache Line的多個數(shù)據(jù)，Core-A修改數(shù)據(jù)x后，會置Cache Line為Invalid，Core-B讀該緩存行的另一個數(shù)據(jù)y，需要Core-A把Cache Line Store到內(nèi)存，Core-B再從內(nèi)存里L(fēng)oad對應(yīng)Cache Line，數(shù)據(jù)要過內(nèi)存。

而atomic，多個線程修改的是同一個變量。lock指令前綴，應(yīng)該會用到緩存鎖（鎖Cache Line），atomic在Cache Line里的最新值通過核間消息發(fā)送給其他核就可以了，不需要頻繁的Store/Load，所以性能不會那么糟。

新聞標(biāo)題：關(guān)于多線程同步的一切：偽共享
新聞來源：http://m.fisionsoft.com.cn/article/coosesp.html