并发线程和数据竞争

Question

我正在阅读 paper 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;
}

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

我有没有误解什么？

Answer 1

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

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

基于 Java 的操作系统由 Sun Labs 开发，但所有有机会试一试的人都公开 mock 它。它留在一个没有标记的坟墓里。

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

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