时间戳

首页 > 解决方案 > 并发线程和数据竞争

c - 并发线程和数据竞争

问题描述

我正在阅读Boehm 的一篇论文：“Threads Cannot be Implemented as a Library”，但我正在努力举一个例子说明为什么基于库的线程解决方案没有帮助。

该示例为两者都提供了初始化零x，y然后有两个线程

// thread 0
if (x == 1) ++y;

// thread 1
if (y == 1) ++x;

我知道没有数据竞争，因为在顺序一致性下，任何线程总是会看到彼此，因为比较（即数据加载）发生在分配（即数据存储）之前。

所以没办法，比如出现下面这种情况：

// thread 0 assigns y
++y;            // that means x is already 1

// thread 1 is checking
if (y == 1)     // that means x is still 0

因此，结果x = 0; y = 0是有根据的。

但是，仅识别单线程代码的编译器可以自由地将这些线程重新排序为

// thread 0
++y; if (x != 1) --y;

// thread 1
++x; if (y != 1) --x;

然后是数据竞争，例如

// thread 0 stores y
--y;

// thread 1 load y
if (y != 1)

但是我仍然不明白为什么线程库不能提供帮助，我能想到的最简单的实现就是简单地使用互斥锁来避免数据竞争：

int x, y = 0;
mtx_t m;

int thread0(void *arg)
{
  mtx_lock(&m); if (x == 1) ++y; mtx_unlock(&m);
  return y;
}

int thread1(void *arg)
{
  mtx_lock(&m); if (y == 1) ++x; mtx_unlock(&m);
  return x;
}

int main()
{
  thrd_t t0, t1;
  int r0, r1;

  mtx_init(&m, mtx_plain);

  thrd_create(&t0, thread0, NULL);
  thrd_create(&t1, thread1, NULL);

  thrd_join(t0, &r0);
  thrd_join(t1, &r1);

  printf("x = %d, y = %d\n", r1, r0);

  return 0;
}

有一个类似的问题，答案是关于 pthreads 中数据竞争的循环定义。但是对于上面的实现，我不关心内存模型是什么，编译器可以根据需要自由地重新排序代码，但输出x = 0, y = 0总是有保证的。

我有什么误解吗？

标签： cmultithreadingconcurrencypthreadsmemory-model

解决方案

虽然您可能误解了某些事情，但您的分析很好。引用的论文夸大了它的论点。

UNIX 和 Linux 内核（以及许多其他内核）本身是大型多线程程序，它们仅在（相当于）基于库的线程支持下运行。从基于 pdp 的微型计算机到大型超级计算机，这些大型多线程程序展现了令人震惊的性能、可靠性和可扩展性。

Sun Labs 开发了一个基于 Java 的操作系统，所有有机会试一试的人都对此嗤之以鼻。它仍然在一个没有标记的坟墓里。

次要推理，即忙等待比锁定原语更有效，在该论文之前至少已经存在了十年。每个人都喜欢无锁，因为它可以做出很好的基准测试，而无限制的非确定性竞争条件会让那些想要好的安全系统的人感到害怕。问题是，有时活泼的比较和交换 (CAS) 是好的，有时是坏的。一些聪明的系统使用乐观的 CAS 来实现互斥锁，从而为一些可读的代码和良好的基准留下机会。

同样，不可能的大胆声明是双曲线的，基于编译器反复无常的想法，因此会做出危险的假设并随意覆盖内存。值得庆幸的是，“免费且足够好”的技术杀死了这些巨龙。

推荐阅读