C11 中的无锁乒乓
Lock-free ping-pong in C11
我对 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);
}
我测试了几次都成功了,但有些地方看起来很奇怪:
- 无锁或者不编译
因为标准定义无锁 属性 等于 2,所以原子类型上的所有操作总是无锁的。特别是我检查了编译代码,它看起来像
sub [=11=]x8,%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 [=11=]x0,0x201034(%rip) # 0x20202c <flag>
jmp 0xfd8 <ping+8>
这似乎没问题,我们甚至不需要某种围栏,因为 Intel CPUs 不允许使用较早的加载对商店进行重新排序。这种假设仅在我们知道不可移植的硬件内存模型的情况下才有效
- 将 stdatomics 与 pthreads 结合使用
我坚持使用 glibc 2.27,其中 threads.h
尚未实现。问题是这样做是否严格符合要求?无论如何,如果我们有原子,但没有线程,这有点奇怪。那么stdatomic
在多线程应用程序中的符合用法是什么?
无锁一词有两种含义:
计算机科学意义:一个线程卡住不能阻碍其他线程。 这个任务不可能无锁,你需要线程互相等待。 (https://en.wikipedia.org/wiki/Non-blocking_algorithm)
使用无锁原子。你基本上是在创建自己的线程块机制,在一个讨厌的自旋循环中等待,没有回退,最终放弃 CPU。
单独的 stdatomic 加载和存储操作各自都是无锁的,但您正在使用它们来创建某种 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 平台上,字节加载/存储会在缓存中花费 read/write 额外的延迟周期。这里可以忽略不计,因为您总是在处理内核间缓存未命中的情况。)
你会认为 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% 好的 space。 这包括非无锁_Atomic my_large_struct foo;
.
之类的东西
我对 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);
}
我测试了几次都成功了,但有些地方看起来很奇怪:
- 无锁或者不编译
因为标准定义无锁 属性 等于 2,所以原子类型上的所有操作总是无锁的。特别是我检查了编译代码,它看起来像
sub [=11=]x8,%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 [=11=]x0,0x201034(%rip) # 0x20202c <flag>
jmp 0xfd8 <ping+8>
这似乎没问题,我们甚至不需要某种围栏,因为 Intel CPUs 不允许使用较早的加载对商店进行重新排序。这种假设仅在我们知道不可移植的硬件内存模型的情况下才有效
- 将 stdatomics 与 pthreads 结合使用
我坚持使用 glibc 2.27,其中 threads.h
尚未实现。问题是这样做是否严格符合要求?无论如何,如果我们有原子,但没有线程,这有点奇怪。那么stdatomic
在多线程应用程序中的符合用法是什么?
无锁一词有两种含义:
计算机科学意义:一个线程卡住不能阻碍其他线程。 这个任务不可能无锁,你需要线程互相等待。 (https://en.wikipedia.org/wiki/Non-blocking_algorithm)
使用无锁原子。你基本上是在创建自己的线程块机制,在一个讨厌的自旋循环中等待,没有回退,最终放弃 CPU。
单独的 stdatomic 加载和存储操作各自都是无锁的,但您正在使用它们来创建某种 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 平台上,字节加载/存储会在缓存中花费 read/write 额外的延迟周期。这里可以忽略不计,因为您总是在处理内核间缓存未命中的情况。)
你会认为 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% 好的 space。 这包括非无锁_Atomic my_large_struct foo;
.