Barrier與多線程

程序世界的barrier

同步屏障(Barrier)是并行計算中的一種同步方法。對于一群進程或線程，程序中的一個同步屏障意味著任何線程/進程執(zhí)行到此后必須等待，直到所有線程/進程都到達此點才可繼續(xù)執(zhí)行下文。-wiki

關于barrier的理解

barrier字面意思是柵欄、屏障，它們起到隔離或者保護的作用。就好比特朗普要修建的墨西哥墻便是一種barrier。


image

CPU和編譯器的亂序優(yōu)化

接下來要講的是Memory barrier，這個還得從頭說起。CPU和編譯器都會對程序做一定程度的優(yōu)化，但是總會遵循一個原則：代碼在單線程運行時不會改變程序的結果，有依賴關系的語句不會被重排。在提高性能的同時，也使得代碼的執(zhí)行過程與源碼不太一樣，多線程環(huán)境下能夠觀測到一些亂序現(xiàn)象。

  • CPU的內(nèi)存亂序
    以下兩種特性造成了內(nèi)存亂序

    • 亂序執(zhí)行（out-of-orderexecution）：
      是指CPU允許將多條指令不按程序規(guī)定的順序分開發(fā)送給各相應電路單元處理的技術。這樣將根據(jù)個電路單元的狀態(tài)和各指令能否提前執(zhí)行的具體情況分析后，將能提前執(zhí)行的指令立即發(fā)送給相應電路單元執(zhí)行，在這期間不按規(guī)定順序執(zhí)行指令，然后由重新排列單元將各執(zhí)行單元結果按指令順序重新排列。采用亂序執(zhí)行技術的目的是為了使CPU內(nèi)部電路滿負荷運轉(zhuǎn)并相應提高了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)容載入到高速緩存或者將結果寫入高速緩存，再由高速緩存寫入主存（計算機內(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下面指令重排后，下一條指令不必等待前一條的結果, 從而減少了停頓

    ```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)化不會影響程序的運行結果，程序員也不需要關心優(yōu)化對程序的影響。

但是在多線程情況下，編譯器和多處理器沒有辦法自動發(fā)現(xiàn)線程間的協(xié)作關系。影響程序運行結果的是兩點：一個是輸入，它決定初始條件，一個是輸出，它決定對外的結果，而計算機中的數(shù)據(jù)都以存儲器為載體，所以最終各種優(yōu)化帶來的副作用表現(xiàn)為內(nèi)存讀寫順序與源碼不一致。

這段代碼是一個無鎖編程的場景：

子線程處理任務，并在任務完成時將標記改為true，finished存在多線程訪問，因此聲明為原子類型，存取操作也是用原子操作。主線程自旋等待直到任務標記完成，接下來讀取任務的結果，經(jīng)過多次循環(huán)，產(chǎn)生了不可思議的結果，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;
            
            // 標記任務為已執(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++;
    }
}
memoryOrdering

分析下原因，在多線程環(huán)境下，變量task和變量finished在處理器或者編譯器眼里是兩個獨立的變量不存在任何聯(lián)系，（盡管程序員認為它們是有關聯(lián)的，task賦值發(fā)生在finished賦值之前，finished用來反映task的狀態(tài)），因此在編譯器和CPU在優(yōu)化過程中沒有義務保證task和finished的內(nèi)存讀寫順序和源碼一致，目前我們對現(xiàn)象至少可以做幾點歸納：

  1. 造成當前狀況源于CPU的優(yōu)化，因為debug情況下沒有使用編譯優(yōu)化
  2. finished和task的賦值操作應該和代碼不一致
  3. 在模擬器上運行沒有問題，但是在手機上卻能走到assert？

Memory models

多線程環(huán)境下，普通代碼往往發(fā)生的各種各樣的非預期的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)存亂序：


569506-9212c5b887c

從上圖看出ARM處理器允許大部分亂序（weak memory model），而X86則允許少部分亂序（strong memory model），也就是說，在ARM上能被觀測到異常的代碼，可能不做任何處理就可以在X86上正常運行。

如何解決亂序問題呢，系統(tǒng)提供了一些工具鏈，在軟件層面制定了Memory Model規(guī)范，程序員通過工具鏈中的同步設施(各種內(nèi)存屏障(Memory Barrier)和Atomic指令)來標記多個線程間的協(xié)作關系。

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_cst

    OSATOMIC_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)存排序，相對于前后的代碼而言，當前原子操作可能被提前或者延遲。而barrier版本使用的是memory_order_seq_cst則表示執(zhí)行到當前原子操作代碼時，之前的讀寫操作都完成了，之后的讀寫操作還沒開始，嚴格保證代碼間的相對順序。

  • 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;

  1. memory_order_relaxed
    表示不約束內(nèi)存讀寫順序，僅僅保證操作的原子性和修改的順序性
    (A線程修改后，改動對于B線程不是立即可見，常用于不需要考慮線程關系的場景，比如多線程操作計數(shù)器)

  2. memory_order_consume
    該類型配合讀來使用，當前線程中，當前consume操作之后的所有的對于當前原子變量的讀和寫都被限定在當前consume操作之后。當前線程可以看到其他線程在release相同原子變量之前的所有關于當前原子變量的內(nèi)存寫入操作。

    例如：其他線程計算得到結果r=1，并且緊接著release原子變量f=a（a.status等于"finished"），標識任務完成，那么當前線程consume變量f并且當f存時，一定有status == "finished"，但是此時并不能保證r=1，因為consume不能保證r的讀取順序，r的讀取理論上可能先于f的讀取。

  3. memory_order_acquire
    該類型配合讀來使用，當前線程中，當前acquire操作之后的所有的讀和寫都被限定在當前原子變量的acquire操作之后。當前線程可以看到其他線程在release相同原子變量之前的所有內(nèi)存寫入操作。

    例如：其他線程計算得到結果r=1，并且緊接著release變量f=1，標識任務完成，那么當前線程acquire變量f并且當f==1時，一定能讀取到其他線程的結果r=1;

  4. memory_order_release
    該類型配合寫入使用，當前線程中，release操作之前的所有的讀和和寫都被限定在release之前，其他線程在acquire相同原子變量后可以看到當前線程的所有寫入操作， 其他線程在consume相同原子變量時可以看到當前線程對于該變量的寫入操作，acquire和consume和release組合使用的區(qū)別是，其他線程可以看到當前線程在release之前的所有修改，另一個是只能看到當前線程對于當前原子變量的修改

  5. memory_order_acq_rel
    該類型配合讀寫改函數(shù)使用，因為函數(shù)包含三個操作，沒辦法只用acquire或者release。

    例如：atomic_compare_exchange_strong，相當于讀使用acquire和寫使用release。

  6. memory_order_seq_cst
    該類型是一個復合類型，寫操作時使用release，讀使用acquire，讀寫改操作使用acq_rel

使用acquire和release實現(xiàn)一個自旋鎖，acquire的特點是，下面的讀寫不能越過acquire，release的特點是上面的讀寫不能越過release，這樣acquire和release就把關鍵代碼給包裹起來了，代碼塊中的讀寫都被限制在區(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側重于內(nèi)存粒度的控制，而dispatch barrier側重于宏觀上的任務約束。

支持并發(fā)的隊列在執(zhí)行任務時，任務的執(zhí)行時間線會產(chǎn)生重疊，如下圖，同一個時間內(nèi)，Task 1，2，3在同時執(zhí)行，有利于發(fā)揮多核優(yōu)勢，但容易引起數(shù)據(jù)競爭。


Concurrent-Queue-Swift

對于一個串行隊列，任務執(zhí)行的時間線是有序的，一個時刻只有一個任務在運行，缺點是不能充分利用多核資源。


Serial-Queue-Swift

dispatch barrier則較好地結合了二者的優(yōu)勢，可并發(fā)可獨占。向隊列中插入barrier任務時，會等當前正在執(zhí)行的任務執(zhí)行完，再去執(zhí)行barrier任務，barrier任務從等待執(zhí)行到執(zhí)行結束這段時間內(nèi)新進的任務都會被排在barrier任務之后執(zhí)行。


Dispatch-Barrier-Swift

注意點：隊列必須要支持并發(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);
            });
        }
    }];
}

多線程問題分析

  1. 多線程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++;
    }
}
releaseObjectInUse

原因分析：

if(!task) {
    task = [[NSObject alloc]init];
}

該代碼邏輯，極端情況下兩個線程可能同時走到，當主線程調(diào)用[task description]過程中，子線程調(diào)用了task = [[NSObject alloc]init]，主線程正在使用的task對象內(nèi)存會被立即釋放，繼續(xù)使用將會造成內(nèi)存訪問錯誤。

解決方案：1、避免多線程訪問，2、子線程需要讀取的數(shù)據(jù)可以通過臨時變量傳入，避免直接訪問，3、對公共變量的訪問加鎖
  1. 多線程Data race，造成讀寫不符合預期，比如我們的計數(shù)器變量有時候不準確或者值異常。
- (void)dataRaceTestNotMeetExpectations {
    
    // 數(shù)據(jù)競爭導致的讀寫結果不符合預期
    // 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);
    }
}
notMeetExpectations

發(fā)現(xiàn)a讀到的是個-4294967295，我們對比下這幾個值的二進制
1


binary1

-1


binary-1

-4294967295


binaryerro

很明顯可以看到-4294967295是-1的高32位+1的低32位也就是ts變量被寫了一半的結果。在64位機器上則沒有問題，推測是64機器對于64位的讀寫是原子的中間沒有中斷，而32位機器則需要分兩步完成。

這也提醒我們，對于基本數(shù)據(jù)類型變量的多線程讀寫并非是安全的，大部分情況下看起來沒問題，但是并不代表沒有問題，因為多線程的安全性與硬件與操作系統(tǒng)有太大的關系，標準的做法是使用原子庫提供的原子類型變量，當我們對技術細節(jié)不是十分有把握的情況下，不要過分追求無鎖編程，建議關鍵代碼加鎖處理。

3.dispatch_group存在的bug，至少在iOS11上dispatch_group是不安全的，目前測試發(fā)現(xiàn)iOS12上已經(jīng)修復。

- (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);
        }
    }
}
dispatchGroup

理論上來講ddd一定會是2，但是在iPhone 6s iOS 11.3環(huán)境下，大概百萬次循環(huán)后，跑出了1的結果。進入asset時，通過調(diào)用棧發(fā)現(xiàn)，另一個線程確實還沒有完成任務。

bugReport

目前得到蘋果的回復是說該問題已經(jīng)被報告過，并且已測試發(fā)現(xiàn)iOS12已經(jīng)修復。

引用：
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/

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • Swift1> Swift和OC的區(qū)別1.1> Swift沒有地址/指針的概念1.2> 泛型1.3> 類型嚴謹 對...
    cosWriter閱讀 11,689評論 1贊 32
  • 寫這篇博文主要源于幾個月前的一條微博，大概講的是“在一些數(shù)據(jù)結構中，需要修改某個數(shù)據(jù)，對整個數(shù)據(jù)結構加鎖實現(xiàn)，然而...
    fooboo閱讀 2,371評論 -3贊 0
  • 除了充分利用計算機處理器的能力外，一個服務端同時對多個客戶端提供服務則是另一個更具體的并發(fā)應用場景。衡量一個服務性...
    胡二囧閱讀 1,468評論 0贊 12
  • Update Note: 18.07.15 initial version 18.07.26 修訂，改了些明顯的錯...
    Quasars閱讀 5,846評論 0贊 7
  • Java SE 基礎： 封裝、繼承、多態(tài) 封裝： 概念：就是把對象的屬性和操作（或服務）結合為一個獨立的整體，并盡...
    Jayden_Cao閱讀 2,259評論 0贊 8

友情鏈接更多精彩內(nèi)容