并发线程和数据竞争

Question

我正在阅读 Boehm 的 paper："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中data-race的循环定义。但是对于上面的实现，我不关心内存模型是什么，编译器可以根据需要自由地重新排序代码，但输出 x = 0, y = 0 总是有保证的。

我是不是误会了什么？

Answer 1

虽然你可能误解了一些东西，但你的分析是好的。引用的论文夸大了它的论点。

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

基于 Java 的 OS 由 Sun Labs 制作，公开嘲笑所有有机会试一试的人。它留在一个没有标记的坟墓里。

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

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

并发线程和数据竞争

Concurrent threads and data race

c

multithreading

concurrency

pthreads

memory-model