c - C11无锁乒乓球

Question

我对 C 中的并发非常陌生，并尝试做一些基础工作来了解它是如何工作的。

我想编写一个无锁乒乓的一致实现，即一个线程打印ping，然后另一个线程打印pong并使其无锁。这是我的尝试:

#if ATOMIC_INT_LOCK_FREE != 2
    #error atomic int should be always lock-free
#else
    static _Atomic int flag;
#endif

static void *ping(void *ignored){
    while(1){
        int val = atomic_load_explicit(&flag, memory_order_acquire);
        if(val){
            printf("ping\n");
            atomic_store_explicit(&flag, !val, memory_order_release);
        }
    }
    return NULL;
}
static void *pong(void *ignored){
    while(1){
        int val = atomic_load_explicit(&flag, memory_order_acquire);
        if(!val){
            printf("pong\n");
            atomic_store_explicit(&flag, !val, memory_order_release);
        }
    }
    return NULL;
}

int main(int args, const char *argv[]){
    pthread_t pthread_ping;
    pthread_create(&pthread_ping, NULL, &ping, NULL);

    pthread_t pthread_pong;
    pthread_create(&pthread_pong, NULL, &pong, NULL);
}

我测试了几次，它有效，但有些事情看起来很奇怪:

1. 它要么无锁，要么无法编译

由于标准将无锁属性定义为等于 2，以便原子类型上的所有操作始终都是无锁的。特别是我检查了编译代码，它看起来像

sub    $0x8,%rsp
nopl   0x0(%rax)
mov    0x20104e(%rip),%eax        # 0x20202c <flag>
test   %eax,%eax
je     0xfd8 <ping+8>
lea    0xd0(%rip),%rdi        # 0x10b9
callq  0xbc0 <puts@plt>
movl   $0x0,0x201034(%rip)        # 0x20202c <flag>
jmp    0xfd8 <ping+8>

这看起来没问题，我们甚至不需要某种围栏，因为 Intel CPU s 不允许使用较早的加载对存储进行重新排序。这种假设仅在我们知道不可移植的硬件内存模型的情况下才有效

将 stdatomics 与 pthread 结合使用

我陷入了 glibc 2.27 的困境，其中 threads.h 尚未实现。问题是这样做是否严格遵守？无论如何，如果我们有原子但没有线程，这有点奇怪。那么，stdatomic 在多线程应用程序中的一致用法是什么？

Answer 1

术语“无锁”有 2 个含义:

1. 计算机科学含义:一个线程被卡住不能妨碍其他线程。 此任务不可能实现无锁，您需要线程相互等待。 (https://en.wikipedia.org/wiki/Non-blocking_algorithm)

2. 使用无锁原子。您基本上是在创建自己的机制来创建线程 block ，在令人讨厌的自旋循环中等待，并且最终不会放弃 CPU。

各个标准原子加载和存储操作都是独立的无锁操作，但您使用它们来创建某种 2 线程锁。

---

我认为你的尝试是正确的。我不认为线程会“错过”更新，因为另一个线程在该更新完成之前不会写入另一个更新。而且我没有找到让两个线程同时进入其临界区的方法。

一个更有趣的测试是使用解锁的 stdio 操作，例如
fputs_unlocked("ping\n", stdio); 利用(并依赖)您已经保证线程之间互斥的事实。请参阅unlocked_stdio(3) .

并使用重定向到文件的输出进行测试，因此 stdio 是完全缓冲的而不是行缓冲的。 (像 write() 这样的系统调用无论如何都是完全序列化的，就像 atomic_thread_fence(mo_seq_cst)。)

---

It either lock-free or does not compile

好吧，为什么这么奇怪？你选择这样做。这不是必需的;该算法仍然适用于 C 实现，无需始终无锁 atomic_int。

atomic_bool 可能是一个更好的选择，在更多平台上是无锁的，包括 int 需要 2 个寄存器的 8 位平台(因为它必须至少为 16 位)。在效率更高的平台上，实现可以自由地将 atomic_bool 设为 4 字节类型，但 IDK 如果确实这样做的话。 (在某些非 x86 平台上，字节加载/存储会花费额外的延迟周期来在缓存中读/写。这里可以忽略不计，因为您总是在处理内核间缓存未命中的情况。)

你会认为atomic_flag对此来说，这将是正确的选择，但它只提供测试和设置，并且与 RMW 操作一样清晰。 不是普通加载或存储。

Such assumptions works only in case we know the hardware memory model which is not portable

是的，但是这种无障碍的 asm 代码生成仅在针对 x86 进行编译时才会发生。编译器可以而且应该应用 as-if 规则来创建在编译目标上运行的 asm，就像 C 源代码在 C 抽象机上运行一样。

---

Using stdatomics with pthreads

Does the ISO C Standard guarantee the atomic's behavior to be well-defined with all threading implementations (like pthreads, earlier LinuxThreads, etc...)

不，ISO C 对于 POSIX 等语言扩展没有任何规定。

它确实在脚注(非规范性)中指出，无锁原子应该是无地址的，因此它们可以在访问同一共享内存的不同进程之间工作。 (或者也许这个脚注只有ISO C++，我没有去重新检查)。

这是我能想到的 ISO C 或 C++ 尝试规定扩展行为的唯一情况。

但是 POSIX 标准有望说明有关 stdatomic 的内容!那就是你应该看的地方；它扩展了 ISO C，而不是相反，因此 pthreads 是必须指定其线程像 C11 thread.h 一样工作并且原子工作的标准。

当然，在实践中，stdatomic 对于所有线程共享相同虚拟地址空间的任何线程实现都是 100% 良好。这包括非无锁的东西，例如 _Atomic my_large_struct foo; .