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>

这似乎还可以，我们甚至不需要某种类型的栅栏，因为英特尔CPUs不允许商店重新排序与早期的负载。这样的假设只有在我们知道不可移植的硬件内存模型时才有效。

1. 使用stdatomics和pthreads

我只能使用glibc2.27，其中还没有实现threads.h。问题是，这样做是否严格一致？无论如何，如果我们有atomics，但是没有线程，这是有点奇怪的。那么，stdatomic在多线程应用程序中的一致用法是什么呢？

Answer 1

“无锁”一词有两个含义：

1. 计算机科学的意思是:一条线卡住不能阻碍另一条线。这个任务是不可能实现无锁的，您需要线程来等待对方的。(算法)
2. 使用无锁原子。您基本上是在创建自己的机制来创建线程块，在没有退路的情况下等待一个讨厌的自旋循环来最终放弃CPU。

单独的stdatomic和存储操作都是单独的无锁操作，但是您正在使用它们来创建某种类型的2线程锁。

在我看来你的尝试是正确的。我看不出线程会“错过”更新，因为在这个更新完成之前，另一个线程不会再写另一个更新。我不认为这两个线程可以同时进入它们的关键部分。

更有趣的测试是使用未锁定的stdio操作，如

fputs_unlocked("ping\n", stdio);可以利用(并依赖)已经保证线程间互斥的事实。见stdio(3)。

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

它要么没有锁定，要么不编译。

好吧，为什么这么奇怪？你选择了那样做。这是不必要的；该算法仍然可以在C实现上工作，而不需要始终没有锁的atomic_int。

atomic_bool可能是一个更好的选择，在更多的平台(包括int需要2个寄存器的8位平台)上是无锁的(因为它必须是至少16位的)。在效率更高的平台上，实现可以使atomic_bool成为一个4字节的类型，但如果确实存在，则可以使用IDK。(在一些非x86平台上，在缓存中读取/写入字节负载/存储需要额外的延迟周期。这里可以忽略不计，因为您总是在处理内核间缓存丢失的情况。)

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

这样的假设只有在我们知道不可移植的硬件内存模型时才有效。

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

在p线程中使用stdat组学 ISO C标准是否保证原子的行为在所有线程实现中都得到了很好的定义(比如线程、早期的LinuxThreads等等)

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

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

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

但是POSIX标准希望能说明一些关于stdatomic的内容！这就是您应该查看的地方；它扩展了ISO，而不是反过来，因此p线程是必须指定其线程像C11 thread.h那样工作的标准，并且是atomics工作的标准。

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