〈Concurrency Primer〉導讀

注意資訊科技詞彙翻譯

使用 atomic 與否差異

#include <stdatomic.h>

int v = 0;
atomic_bool v_ready = false;
int bv;

void *threadA() {
	v = 42;
	v_ready = true;
}

void *threadB() {
	while(!v_ready);
	bv = v;
}

以下使用 gcc 搭配 -O3 最佳化等級

在 threadA 裡頭

若將 v_ready 定義為 amtomic_bool 則編譯器將會插入 memory fence，從而使得所有在之前寫入的暫存器內含值都被更新至主記憶體中。

    threadA:				threadA:
    .LFB40:					.LFB40:
        .cfi_startproc				.cfi_startproc
        endbr64					endbr64
        movl	$42, v(%rip)			movl	$42, v(%rip)
        movb	$1, v_ready(%rip)		movb	$1, v_ready(%rip)
        mfence			     <
        ret					ret

在 threadB 裡頭

若不是使用 atomic_bool，編譯器會對 while 迴圈裡頭的讀取操作進行最佳化，造成無限迴圈而無法正常執行。(留意第 7 和第 8 行)

















threadB:				threadB:
.LFB41:					.LFB41:
	.cfi_startproc				.cfi_startproc
	endbr64					endbr64
				     >		cmpb	$0, v_ready(%rip)
				     >		jne	.L4
				     >	.L5:
				     >		jmp	.L5
	.p2align 4,,10				.p2align 4,,10
	.p2align 3				.p2align 3
.L4:					.L4:
	movzbl	v_ready(%rip), %eax  <
	testb	%al, %al	     <
	je	.L4		     <
	movl	v(%rip), %eax			movl	v(%rip), %eax
	movl	%eax, bv(%rip)			movl	%eax, bv(%rip)
	ret					ret

Check if atomic element is lock free

C/C++ 中分別定義atomic_is_lock_free/std::atomic<T>::is_lock_free 可用以檢驗此 atomic 變數是否可以在 lock free 的情況下做到 atomic operation。

struct foo {
	int a, b, c;
	char *s;
};

atomic_bool v_ready = false;
struct foo f;

int main() {
	printf("foo is lock free? %s\n", atomic_is_lock_free(&f) ? "true" : "false");
	printf("v_ready is lock free? %s\n", atomic_is_lock_free(&v_ready) ? "true" : "false");
	return 0;
}

該測試程式執行結果如下：

foo is lock free? false
v_ready is lock free? true

若定義的 atomic 變數佔用的空間大於一個暫存器之大小且變數 aligned，則需要使用 mutex lock 確保操作本身的 atomicity。反之，若變數並未 aligned，則是否為 lock free，取決於硬體架構的設計方式。

Read-modify-write

當需要 atomically 完成讀取、修改、寫入的一系列指令時，可用以下指令

atomic_<type>: atomic_compare_exchange 和 atomic_exchange
atomic_flag: atomic_flag_test_and_set 和 atomic_flag_clear

利用 `atomic_flag` 實作 mutex lock

atomic_flag f = ATOMIC_FLAG_INIT;
void atomic_operation()
{
    while (atomic_flag_test_and_set(&f))
        nop;
    /* critical section */
    atomic_flag_clear(&f);
    return;
}

原本的 C 程式:

    void *threadA() {
        while(atomic_flag_test_and_set(&f));
        t1.a++;
        atomic_flag_clear(&f);
        return NULL;
    }

對應的組合語言輸出：

    .L2:
        movl	%edx, %eax
        xchgb	f(%rip), %al
        testb	%al, %al
        jne	.L2
        addl	$1, t1(%rip)
        xorl	%eax, %eax
        movb	$0, f(%rip)
        mfence
        ret

atomic_flag_test_and_set 使用 x86 的 exchange 指令 xchgb 設定 flag 的值。atomic_flag_clear 則在寫入值之後還加上 memory fence，以確保所有數值變更，都可被其他處理器核所見 (visible)。

compare and exchange (CAS)

考慮以下程式碼：

atomic_int ai = 0;
void cas()
{
    atomic_int exp = 0;
    atomic_compare_exchange_strong(&ai, &exp, 1);
}

對應的組合語言輸出：








    cas:
    .LFB24:
        .cfi_startproc
        endbr64
        xorl	%eax, %eax
        movl	$1, %edx
        lock cmpxchgl	%edx, ai(%rip)
        ret

第 7 行的 lock 使得在做 cmpxchgl 時同時只能有一個 cpu 獲得此變數的存取權。並且 cmpxchgl 先比較 %eax 以及 destination register (ai(%rip)，值相等時才將 %edx 中的值與 ai(%rip) 互換。

load-link and store-conditional (LL/SC)

在某些 cpu 架構之下 (如 MIPS, RISC-V, Arm)，提供指令追蹤此次要 store 的目標值是否被修改過，以避免 load modfiy store 覆蓋已經被更新的值。

`atomic_compare_exchange_weak` 存在意義

考慮以下：

void addone(int val)
{
    int expected = val;
    while(!atomic_compare_exchange_?(&val, &expected, val + 1))
        nop;
}

我們可能經常使用以上方式進行 CAS 動作，但是若硬體支援 LL/SC 的話，則有可能錯誤發生在 SC，而非一開始比較 val 及 expected 時，但其實我們不在乎什麼時候出現錯誤，所以定義 weak 版本的 CAS 只要動作沒有正確的完成就會回傳 true。

Memory ordering

時候不用所有的指令都在一定的順序下執行，部分指令可提前或延後執行。因此，在 stdatomic.h 規範 6 種 memory ordering model，可讓編譯器清楚各指令可以接受的最佳化策略。

Sequentially consistent

在各個執行緒中，所有的指定為 memory_order_seq_cst 指令都是 sequentially 執行，所有的執行順序跟程式被撰寫的順序相同，因此沒有重排指令造成執行結果錯誤的可能性。

void *threadFunc()
{
	atomic_int val = atomic_load_explicit(&a, memory_order_seq_cst);
	val += 1;
	atomic_store_explicit(&a, val, memory_order_seq_cst);
	return NULL;
}

若同時讓多個執行緒執行以上函式，指令的執行順序按照執行緒建立時間以及指令順序執行。

使用 sequentially consistent 的缺點為即使使用多個執行緒還是按照 sequential 執行，使得執行效率低落，甚至可能比單執行緒表現更差。

Acquire

只能用在 atomic_load。所有在此 load 之後的指令都不能被重排到此指令的前面。

Release

只能用在 atomic_store。與 Acquire 相反，所有在此 store 之前的指令都不能被重排到此指令的後面。

Acquire Release

可以用在 atomic_load 以及 atomic_store。必須同時滿足 Acquire 以及 Release 條件

Relaxed

所有 atomic operation 都 atomically 執行，但是不同執行緒之間對於相同變數的執行順序沒有固定。

Consume

相似於 Acquire，不同點在於只需要保證相同變數的順序，其他不相關的變數可以做前後順序的調換，且 memory barrier 的加入為非必要。