程序世界的barrier
同步屏障(Barrier)是并行計算中的一種同步方法。對于一群進程或線程专控，程序中的一個同步屏障意味著任何線程/進程執(zhí)行到此后必須等待，直到所有線程/進程都到達此點才可繼續(xù)執(zhí)行下文。-wiki
關(guān)于barrier的理解
barrier字面意思是柵欄悬襟、屏障布蔗，它們起到隔離或者保護的作用藤违。就好比特朗普要修建的墨西哥墻便是一種barrier。
CPU和編譯器的亂序優(yōu)化
接下來要講的是Memory barrier纵揍，這個還得從頭說起顿乒。CPU和編譯器都會對程序做一定程度的優(yōu)化，但是總會遵循一個原則：代碼在單線程運行時不會改變程序的結(jié)果泽谨，有依賴關(guān)系的語句不會被重排璧榄。在提高性能的同時，也使得代碼的執(zhí)行過程與源碼不太一樣吧雹，多線程環(huán)境下能夠觀測到一些亂序現(xiàn)象骨杂。
-
CPU的內(nèi)存亂序
以下兩種特性造成了內(nèi)存亂序-
亂序執(zhí)行（out-of-orderexecution）：
是指CPU允許將多條指令不按程序規(guī)定的順序分開發(fā)送給各相應(yīng)電路單元處理的技術(shù)。這樣將根據(jù)個電路單元的狀態(tài)和各指令能否提前執(zhí)行的具體情況分析后雄卷，將能提前執(zhí)行的指令立即發(fā)送給相應(yīng)電路單元執(zhí)行搓蚪，在這期間不按規(guī)定順序執(zhí)行指令，然后由重新排列單元將各執(zhí)行單元結(jié)果按指令順序重新排列丁鹉。采用亂序執(zhí)行技術(shù)的目的是為了使CPU內(nèi)部電路滿負荷運轉(zhuǎn)并相應(yīng)提高了CPU的運行程序的速度妒潭。亂序執(zhí)行的好處：
我們來看一個宏觀上的例子：
下載圖片A->展示圖片A->保存圖片A->下載圖片B->保存圖片B
這個流程需要5個時鐘周期
由于CPU可以同時處理多個指令悴能，并且A和B沒有依賴，于是優(yōu)化為：
下載圖片A->展示圖片A->保存圖片A
下載圖片B->保存圖片B
優(yōu)化后只要3個時鐘周期 -
CPU高速緩存(CPU caches)：
為了提高運行速度雳灾，CPU內(nèi)置多級高速緩存漠酿，我們常常聽到的L1，L2...高速緩存谎亩，高速緩存的讀寫速度要遠高于內(nèi)存炒嘲。在讀寫內(nèi)存時，則是提前將內(nèi)容載入到高速緩存或者將結(jié)果寫入高速緩存团驱，再由高速緩存寫入主存（計算機內(nèi)存）摸吠，這樣就減少CPU讀寫內(nèi)存時的等待時間，但同時造成了內(nèi)存讀寫的不同步嚎花，感官上形成了內(nèi)存讀寫亂序寸痢。
cpu-diagra
-
-
編譯器指令重排
compiler-reordering
我們知道編譯器的工作是把源代碼轉(zhuǎn)換為CPU可以讀的機器代碼，轉(zhuǎn)換過程中編譯器可以自主做很多優(yōu)化工作紊选。
編譯優(yōu)化舉例：
* 公共子表達式刪除(Common Subexpression Elimination)
```Objective-C
a = b * c + g; //----------> tmp = b * c;
d = b * c * e; // rewrite a = tmp + g;
// d = tmp * e;
```
* 死代碼刪除([Dead Code Elimination](https://en.wikipedia.org/wiki/Dead_code_elimination))
```Objective-C
int foo(void)
{
int a = 24;
int b = 25; /* Assignment to dead variable */
int c;
c = a * 4;
return c;
b = 24; /* Unreachable code */
return 0;
}
==>
int foo(void)
{
int a = 24;
int c;
c = a * 4;
return c;
}
```
* 指令調(diào)度(Instruction Scheduling)：目前的CPU下面指令重排后啼止，下一條指令不必等待前一條的結(jié)果, 從而減少了停頓
```Objective-C
load %r0, 0($mem0) // load %r0, 0($mem0)
mul %r1, %r1, %r0 //-----------> load %r2, 0($mem2)
store 0($mem1), %r1 // rewrite mul %r1, %r1, %r0
load %r2, 0($mem2) // mul %r3, %r3, %r2
mul %r3, %r3, %r2 // store 0($mem1), %r1
store 0($mem3), %r3 // store 0($mem3), %r3
```
Memory ordering wiki
編譯器和CPU的各種優(yōu)化會修改指令的執(zhí)行時機，造成存儲器訪問順序的變化兵罢；盡管如此献烦，在單線程程序中，這些優(yōu)化不會影響程序的運行結(jié)果卖词，程序員也不需要關(guān)心優(yōu)化對程序的影響巩那。
但是在多線程情況下，編譯器和多處理器沒有辦法自動發(fā)現(xiàn)線程間的協(xié)作關(guān)系此蜈。影響程序運行結(jié)果的是兩點：一個是輸入即横，它決定初始條件，一個是輸出裆赵，它決定對外的結(jié)果东囚，而計算機中的數(shù)據(jù)都以存儲器為載體，所以最終各種優(yōu)化帶來的副作用表現(xiàn)為內(nèi)存讀寫順序與源碼不一致战授。
這段代碼是一個無鎖編程的場景：
子線程處理任務(wù)页藻，并在任務(wù)完成時將標記改為true，finished存在多線程訪問植兰，因此聲明為原子類型份帐，存取操作也是用原子操作。主線程自旋等待直到任務(wù)標記完成钉跷，接下來讀取任務(wù)的結(jié)果弥鹦，經(jīng)過多次循環(huán)，產(chǎn)生了不可思議的結(jié)果，finished為true的情況下task的值竟然為0彬坏；
- (void)cpuReorderTest {
// Test at iPhone 6sPlus iOS 12.2
long long loop_count = 0;
while (1) {
__block atomic_bool finished = ATOMIC_VAR_INIT(false);
__block int task = 0;
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
task = 1;
// 標記任務(wù)為已執(zhí)行
atomic_store_explicit(&finished, true, memory_order_relaxed);
while (arc4random()%10);
});
while (!atomic_load_explicit(&finished, memory_order_relaxed));
int task_now = task;
if (task_now != 1) {
NSLog(@"assert at %lld", loop_count);
assert(0);
}
loop_count++;
}
}
分析下原因朦促，在多線程環(huán)境下，變量task和變量finished在處理器或者編譯器眼里是兩個獨立的變量不存在任何聯(lián)系栓始，（盡管程序員認為它們是有關(guān)聯(lián)的务冕，task賦值發(fā)生在finished賦值之前，finished用來反映task的狀態(tài)）幻赚，因此在編譯器和CPU在優(yōu)化過程中沒有義務(wù)保證task和finished的內(nèi)存讀寫順序和源碼一致禀忆，目前我們對現(xiàn)象至少可以做幾點歸納：
- 造成當(dāng)前狀況源于CPU的優(yōu)化，因為debug情況下沒有使用編譯優(yōu)化
- finished和task的賦值操作應(yīng)該和代碼不一致
- 在模擬器上運行沒有問題落恼，但是在手機上卻能走到assert箩退？
Memory models
多線程環(huán)境下，普通代碼往往發(fā)生的各種各樣的非預(yù)期的Memory ordering佳谦，取決于處理器和和使用的工具鏈（軟件層面用于控制編譯和CPU亂序問題的工具戴涝，比如，C11中引入的stdatomic.h钻蔑，apple的OSAtomic.h）啥刻。Memory models的作用就是定義運行時CPU會產(chǎn)生何種亂序，或者工具鏈可以實現(xiàn)何種亂序控制（具體下來就是一組原子操作和內(nèi)存屏障方法）咪笑。
對于內(nèi)存來說可帽，操作分為讀（Load）和寫（Store），Memory ordering就是讀寫操作的組合：
LoadLoad窗怒，
StoreStore映跟，
LoadStore，
StoreLoad
以cpuReorderTest代碼發(fā)生的狀況為例：
解釋1StoreStore亂序：
我們是先Store``task扬虚，再Store``finished申窘，由于高速緩存的存在，實際可能是Store``finished先寫入成功孔轴，Store``task后寫入成功，于是就形成了asset的狀況碎捺，這里兩個變量的寫入順序和源碼不一致路鹰，可以認為是StoreStore亂序。
在硬件層面不同的CPU收厨，允許不同程度的內(nèi)存亂序：
從上圖看出ARM處理器允許大部分亂序（weak memory model）晋柱，而X86則允許少部分亂序（strong memory model），也就是說诵叁，在ARM上能被觀測到異常的代碼雁竞，可能不做任何處理就可以在X86上正常運行。
如何解決亂序問題呢，系統(tǒng)提供了一些工具鏈碑诉，在軟件層面制定了Memory Model規(guī)范彪腔，程序員通過工具鏈中的同步設(shè)施(各種內(nèi)存屏障(Memory Barrier)和Atomic指令)來標記多個線程間的協(xié)作關(guān)系。
Memory barrier
Memory barrier我們可能不是很熟悉进栽，多線程開發(fā)中德挣，我們用的最多的是各種鎖或者信號量，鎖和信號量內(nèi)部都會用到Memory barrier來對內(nèi)存排序進行約束快毛。
// acquire和release便是指定了不同的內(nèi)存序
long
dispatch_semaphore_wait(dispatch_semaphore_t dsema, dispatch_time_t timeout)
{
long value = os_atomic_dec2o(dsema, dsema_value, acquire);
......
}
long
dispatch_semaphore_signal(dispatch_semaphore_t dsema)
{
long value = os_atomic_inc2o(dsema, dsema_value, release);
......
}
-
OSAtomic
OSAtomic是Apple提供的api格嗅，其中大部分是原子操作函數(shù)，原子操作函數(shù)有一個普通版本和一個barrier版本唠帝，前者使用的memory_order_relaxed后者是memory_order_seq_cstOSATOMIC_INLINE
int32_t
OSAtomicAdd32(int32_t __theAmount, volatile int32_t __theValue)
{
return (OSATOMIC_STD(atomic_fetch_add_explicit)(
(volatile _OSAtomic_int32_t) __theValue, __theAmount,
OSATOMIC_STD(memory_order_relaxed)) + __theAmount);
}
//
// barrier版本
OSATOMIC_INLINE
int32_t
OSAtomicAdd32Barrier(int32_t __theAmount, volatile int32_t __theValue)
{
return (OSATOMIC_STD(atomic_fetch_add_explicit)(
(volatile _OSAtomic_int32_t) __theValue, __theAmount,
OSATOMIC_STD(memory_order_seq_cst)) + __theAmount);
}
......
```
除了原子操作函數(shù)屯掖，還提供了一個OSMemoryBarrier函數(shù)
```Objective-C
OSATOMIC_INLINE
void
OSMemoryBarrier(void)
{
OSATOMIC_STD(atomic_thread_fence)(OSATOMIC_STD(memory_order_seq_cst));
}
```
普通版本的原子函數(shù)使用的內(nèi)存排序約束為memory_order_relaxed含義是不約束內(nèi)存排序，相對于前后的代碼而言襟衰，當(dāng)前原子操作可能被提前或者延遲贴铜。而barrier版本使用的是memory_order_seq_cst則表示執(zhí)行到當(dāng)前原子操作代碼時，之前的讀寫操作都完成了右蒲，之后的讀寫操作還沒開始阀湿，嚴格保證代碼間的相對順序。
- stdatomic/atomic
作為底層功能代碼瑰妄，C11和C++11標準對原子同步原語這塊做了統(tǒng)一定義陷嘴，避免不同平臺使用不同的實現(xiàn)，目前OSAtomic已經(jīng)標記為deprecated间坐，直接使用C11或C++11的接口灾挨。
stdatomic中的原子操作函數(shù)，可以指定memory order竹宋，它是一個枚舉類型typedef enum memory_order { memory_order_relaxed = __ATOMIC_RELAXED, memory_order_consume = __ATOMIC_CONSUME, memory_order_acquire = __ATOMIC_ACQUIRE, memory_order_release = __ATOMIC_RELEASE, memory_order_acq_rel = __ATOMIC_ACQ_REL, memory_order_seq_cst = __ATOMIC_SEQ_CST } memory_order;
memory_order_relaxed
表示不約束內(nèi)存讀寫順序劳澄，僅僅保證操作的原子性和修改的順序性
(A線程修改后，改動對于B線程不是立即可見蜈七，常用于不需要考慮線程關(guān)系的場景秒拔，比如多線程操作計數(shù)器)-
memory_order_consume
該類型配合讀來使用，當(dāng)前線程中飒硅，當(dāng)前consume操作之后的所有的對于當(dāng)前原子變量的讀和寫都被限定在當(dāng)前consume操作之后砂缩。當(dāng)前線程可以看到其他線程在release相同原子變量之前的所有關(guān)于當(dāng)前原子變量的內(nèi)存寫入操作。例如：其他線程計算得到結(jié)果r=1三娩，并且緊接著release原子變量f=a（a.status等于"finished"）庵芭，標識任務(wù)完成，那么當(dāng)前線程consume變量f并且當(dāng)f存時雀监，一定有status == "finished"双吆，但是此時并不能保證r=1，因為consume不能保證r的讀取順序，r的讀取理論上可能先于f的讀取好乐。
-
memory_order_acquire
該類型配合讀來使用匾竿，當(dāng)前線程中，當(dāng)前acquire操作之后的所有的讀和寫都被限定在當(dāng)前原子變量的acquire操作之后曹宴。當(dāng)前線程可以看到其他線程在release相同原子變量之前的所有內(nèi)存寫入操作搂橙。例如：其他線程計算得到結(jié)果r=1，并且緊接著release變量f=1笛坦，標識任務(wù)完成区转，那么當(dāng)前線程acquire變量f并且當(dāng)f==1時，一定能讀取到其他線程的結(jié)果r=1;
memory_order_release
該類型配合寫入使用版扩，當(dāng)前線程中废离，release操作之前的所有的讀和和寫都被限定在release之前，其他線程在acquire相同原子變量后可以看到當(dāng)前線程的所有寫入操作礁芦， 其他線程在consume相同原子變量時可以看到當(dāng)前線程對于該變量的寫入操作蜻韭，acquire和consume和release組合使用的區(qū)別是，其他線程可以看到當(dāng)前線程在release之前的所有修改柿扣，另一個是只能看到當(dāng)前線程對于當(dāng)前原子變量的修改-
memory_order_acq_rel
該類型配合讀寫改函數(shù)使用肖方，因為函數(shù)包含三個操作，沒辦法只用acquire或者release未状。例如：
atomic_compare_exchange_strong俯画，相當(dāng)于讀使用acquire和寫使用release。 memory_order_seq_cst
該類型是一個復(fù)合類型司草，寫操作時使用release艰垂，讀使用acquire，讀寫改操作使用acq_rel
使用acquire和release實現(xiàn)一個自旋鎖埋虹，acquire的特點是猜憎，下面的讀寫不能越過acquire，release的特點是上面的讀寫不能越過release搔课，這樣acquire和release就把關(guān)鍵代碼給包裹起來了胰柑，代碼塊中的讀寫都被限制在區(qū)域內(nèi)。
#include <stdatomic.h>
#include <pthread.h>
atomic_flag lock = ATOMIC_FLAG_INIT;
- (void)lock {
while (atomic_flag_test_and_set_explicit(&lock, memory_order_acquire)) {
pthread_yield_np();
}
}
- (void)unlock {
atomic_flag_clear_explicit(&lock, memory_order_release);
}
- (void)spinLockTest {
//Test at iPhone 6sPlus iOS 12.2
__block unsigned long long count = 0;
long long loop = 10000000;
void (^add)(void) = ^{
for (long long i = 0; i < loop; i++) {
[self lock];
count++;
[self unlock];
}
[self lock];
NSLog(@"%lld", count);
[self unlock];
};
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{
add();
});
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{
add();
});
}
Dispatch barrier
Dispatch barrier是GCD中的一組函數(shù)爬泥，Memory barrier側(cè)重于內(nèi)存粒度的控制旦事，而dispatch barrier側(cè)重于宏觀上的任務(wù)約束。
支持并發(fā)的隊列在執(zhí)行任務(wù)時急灭，任務(wù)的執(zhí)行時間線會產(chǎn)生重疊，如下圖谷遂，同一個時間內(nèi)葬馋，Task 1，2，3在同時執(zhí)行畴嘶，有利于發(fā)揮多核優(yōu)勢蛋逾，但容易引起數(shù)據(jù)競爭。
對于一個串行隊列窗悯，任務(wù)執(zhí)行的時間線是有序的区匣，一個時刻只有一個任務(wù)在運行，缺點是不能充分利用多核資源蒋院。
dispatch barrier則較好地結(jié)合了二者的優(yōu)勢亏钩，可并發(fā)可獨占鸟整。向隊列中插入barrier任務(wù)時翠勉，會等當(dāng)前正在執(zhí)行的任務(wù)執(zhí)行完，再去執(zhí)行barrier任務(wù)呀忧，barrier任務(wù)從等待執(zhí)行到執(zhí)行結(jié)束這段時間內(nèi)新進的任務(wù)都會被排在barrier任務(wù)之后執(zhí)行辞友。
注意點：隊列必須要支持并發(fā)栅哀，并且提交的隊列不能是global queue，否則和dispatch_async()/dispatch_sync()效果一樣称龙。
- (void)dispatchBarrierTest {
__block int count = 0;
dispatch_queue_t queue = dispatch_queue_create("", DISPATCH_QUEUE_CONCURRENT);
// 對count進行讀寫
[NSTimer scheduledTimerWithTimeInterval:0.2 repeats:YES block:^(NSTimer * _Nonnull timer) {
if (arc4random()%3 != 0) {
dispatch_async(queue, ^{
NSLog(@"read \tcount:%d", count);
});
}
else {
dispatch_barrier_async(queue, ^{
count++;
NSLog(@"write \tcount:%d", count);
});
}
}];
}
多線程問題分析
- 多線程Data race留拾，釋放正在使用的對象，經(jīng)驗中鲫尊，多線程崩潰問題大多數(shù)屬于此類問題
- (void)dataRaceTestReleaseObjectInUse {
// 釋放了正在使用的對象
// Test at iPhone 6sPlus iOS 12.2 or
// MacOS 10.14.5 simulator iPhoneSE 12.2
long long loop_count = 0;
while (1) {
__block NSObject *task = nil;
__block BOOL didFinishe = NO;
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
while (arc4random()%2);
if(!task) {
task = [[NSObject alloc]init];
}
didFinishe = YES;
});
while (arc4random()%2);
if(!task) {
task = [[NSObject alloc]init];
}
while (!didFinishe) {
[task description];
}
loop_count++;
}
}
原因分析：
if(!task) {
task = [[NSObject alloc]init];
}
該代碼邏輯痴柔，極端情況下兩個線程可能同時走到，當(dāng)主線程調(diào)用[task description]過程中马昨，子線程調(diào)用了task = [[NSObject alloc]init]竞帽，主線程正在使用的task對象內(nèi)存會被立即釋放，繼續(xù)使用將會造成內(nèi)存訪問錯誤鸿捧。
解決方案：1屹篓、避免多線程訪問，2匙奴、子線程需要讀取的數(shù)據(jù)可以通過臨時變量傳入堆巧，避免直接訪問，3泼菌、對公共變量的訪問加鎖
- 多線程Data race谍肤，造成讀寫不符合預(yù)期，比如我們的計數(shù)器變量有時候不準確或者值異常哗伯。
- (void)dataRaceTestNotMeetExpectations {
// 數(shù)據(jù)競爭導(dǎo)致的讀寫結(jié)果不符合預(yù)期
// MacOS 10.14.5 simulator iPhone4s 12.2(32位)
__block long long ts = 1;
dispatch_async(dispatch_queue_create("", DISPATCH_QUEUE_CONCURRENT), ^{
while (1) {
ts = 1;
while (arc4random()%2);
}
});
dispatch_async(dispatch_queue_create("", DISPATCH_QUEUE_CONCURRENT), ^{
while (1) {
ts = -1;
while (arc4random()%2);
}
});
while (1) {
long long a = ts;
assert(a == 1 || a == -1);
usleep(100);
}
}
發(fā)現(xiàn)a讀到的是個-4294967295荒揣，我們對比下這幾個值的二進制
1
-1
-4294967295
很明顯可以看到-4294967295是-1的高32位+1的低32位也就是ts變量被寫了一半的結(jié)果。在64位機器上則沒有問題焊刹，推測是64機器對于64位的讀寫是原子的中間沒有中斷系任，而32位機器則需要分兩步完成恳蹲。
這也提醒我們，對于基本數(shù)據(jù)類型變量的多線程讀寫并非是安全的俩滥，大部分情況下看起來沒問題嘉蕾，但是并不代表沒有問題，因為多線程的安全性與硬件與操作系統(tǒng)有太大的關(guān)系霜旧，標準的做法是使用原子庫提供的原子類型變量错忱，當(dāng)我們對技術(shù)細節(jié)不是十分有把握的情況下，不要過分追求無鎖編程挂据，建議關(guān)鍵代碼加鎖處理以清。
3.dispatch_group存在的bug，至少在iOS11上dispatch_group是不安全的棱貌，目前測試發(fā)現(xiàn)iOS12上已經(jīng)修復(fù)玖媚。
- (void)dispatchGroupTest {
// Test at iPhone 6s iOS 11.3
dispatch_group_t group = dispatch_group_create();
dispatch_queue_t queue = dispatch_queue_create("queue", DISPATCH_QUEUE_CONCURRENT);
dispatch_semaphore_t s1 = dispatch_semaphore_create(1);
dispatch_semaphore_t s2 = dispatch_semaphore_create(1);
for (long long i = 0; ; i++) {
__block atomic_int dd;
atomic_init(&dd, 0);
// Add task 1
dispatch_group_async(group, queue, ^{
while (arc4random()%100);
dispatch_semaphore_wait(s1, DISPATCH_TIME_FOREVER);
atomic_fetch_add_explicit(&dd, 1, memory_order_seq_cst);
dispatch_semaphore_signal(s1);
});
// Add task 2
dispatch_group_async(group, queue, ^{
while (arc4random()%100);
dispatch_semaphore_wait(s2, DISPATCH_TIME_FOREVER);
atomic_fetch_add_explicit(&dd, 1, memory_order_seq_cst);
dispatch_semaphore_signal(s2);
});
// Waiting for all tasks to be done.
dispatch_group_wait(group, DISPATCH_TIME_FOREVER);
long long ddd = atomic_load_explicit(&dd, memory_order_seq_cst);
// Generally the two tasks did finished when the code ran here and "dd" should be 2. But after several million cycles, the following conditions can be met.
if (ddd != 2) {
// Call “dispatch_semaphore_wait” to block the thread of the task in the group which is not start, so that we can observe the details of thread call.
dispatch_semaphore_wait(s1, DISPATCH_TIME_FOREVER);
dispatch_semaphore_wait(s2, DISPATCH_TIME_FOREVER);
// I found that there is indeed a task in the group that has not been executed.
NSLog(@"loop: %lld", i);
assert(0);
}
}
}
理論上來講ddd一定會是2，但是在iPhone 6s iOS 11.3環(huán)境下婚脱，大概百萬次循環(huán)后今魔，跑出了1的結(jié)果。進入asset時障贸，通過調(diào)用棧發(fā)現(xiàn)错森，另一個線程確實還沒有完成任務(wù)。
目前得到蘋果的回復(fù)是說該問題已經(jīng)被報告過篮洁，并且已測試發(fā)現(xiàn)iOS12已經(jīng)修復(fù)涩维。
引用：
https://preshing.com/20120930/weak-vs-strong-memory-models/#strong
https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Consume_ordering
https://preshing.com/20120913/acquire-and-release-semantics/
