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 CPUs不允许使用早期负载重新排序商店。这种假设仅在我们知道不可移植的硬件存储器模型的情况下才有效

2. 使用stdatomics和pthreads

我坚持使用glibc 2.27，其中threads.h尚未实施。问题是它是否严格遵守这样做？无论如何，如果我们有原子，但是没有线程，这有点奇怪。那么多线程应用程序中stdatomics的符合性用法是什么？

Answer 1

锁无名有两个含义：

1. 计算机科学的意义：一个线程卡住不能阻碍其他线程。这个任务不可能无锁，你需要线程互相等待。 （https://en.wikipedia.org/wiki/Non-blocking_algorithm）
2. 使用无锁原子。你基本上是在创建一个自己的机制来制作一个线程块，等待一个令人讨厌的自旋循环，没有后退，最终放弃了CPU。

单独的stdatomic加载和存储操作都是单独锁定的，但您使用它们来创建一个双线程锁定。

---

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

一个更有趣的测试是使用解锁的stdio操作，比如 fputs_unlocked("ping\n", stdio);利用（并依赖）你已经保证线程之间相互排斥的事实。见unlocked_stdio(3)。

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

---

它无锁或无法编译

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

atomic_bool可能是更好的选择，在更多平台上无锁，包括8位平台，其中int需要2个寄存器（因为它必须至少为16位）。实现可以自由地使atomic_bool在更高效的平台上使用4字节类型，但IDK实际上是有效的。 （在一些非x86平台上，字节加载/存储在缓存中读取/写入的延迟成本增加了一个周期。这里可以忽略不计，因为你总是在处理核心间缓存未命中情况。）

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

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

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

---

使用stdatomics和pthreads

ISO C标准是否保证使用所有线程实现（如pthread，早期的LinuxThreads等）定义原子的行为？

不，ISO C对POSIX等语言扩展没什么好说的。

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

这是我能想到的唯一一种ISO C或C ++试图规定扩展行为的案例。

但是POSIX标准希望能说一些关于stdatomic的东西！这就是你应该看的地方;它扩展了ISO C，而不是相反，所以pthreads是必须指定其线程像C11 thread.h一样工作的标准。

当然，在实践中，stdatomic在任何线程实现中都是100％罚款，其中所有线程共享相同的虚拟地址空间。这包括非锁定的东西，如_Atomic my_large_struct foo;。