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("pingn");
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("pongn");
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>

这似乎没问题，我们甚至不需要某种围栏，因为英特尔 CPU 不允许使用早期负载重新排序商店。这种假设仅在我们知道不可移植的硬件内存模型的情况下才有效

2. 将标准与线程一起使用

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

Answer 1

无锁一词有 2 种含义：

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

2. 使用无锁原子。 你基本上是在创建自己的机制来制作线程块，在一个讨厌的旋转循环中等待，没有回退最终放弃CPU。

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

---

你的尝试在我看来是正确的。 我看不到线程可以"错过"更新的方法，因为另一个线程不会在此线程完成之前写入另一个线程。 而且我看不到两个线程同时进入其关键部分的方法。

一个更有趣的测试是使用未锁定的 stdio 操作，如
fputs_unlocked("pingn", stdio);来利用(并依赖于)您已经保证线程之间相互排斥的事实。 见unlocked_stdio(3)。

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

---

它要么无锁，要么不编译

好吧，为什么这很奇怪？ 你选择这样做。 没有必要;该算法仍然可以在没有始终无锁atomic_int的情况下在 C 实现上工作。

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

您可能会认为atomic_flag是正确的选择，但它仅提供测试和设置，并且清晰，作为 RMW 操作。不是普通加载或存储。

这种假设仅在我们知道不可移植的硬件内存模型的情况下才有效

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

---

将标准符号与线程一起使用

ISO C 标准是否保证原子的行为在所有线程实现(如 pthreads、早期的 LinuxThreads 等)中得到很好的定义？

不，ISO C对像POSIX这样的语言扩展没有什么可说的。

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

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

但POSIX标准希望能说明一些关于标准的东西！ 那是你应该看的地方;它扩展了ISO C，而不是相反，因此pthreads是必须指定其线程像C11thread.h一样工作并且原子工作的标准。

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