c、openmp的CAS实现

Question

我正在尝试实现比较和交换操作，以便我的线程知道是否根据 value 进入特定区域u_parent。我只是想知道这是否是正确的实现方法以及我是否在某个地方出错了。

int *u_parent;
u_parent = &graph->parents[u]; 

if (*u_parent < 0) { 
    // This region should only be entered by each thread
    // if the value of u_parent is < -1.   

    graph->parents[u] = v;
    // ^-- If region is entered, this value is modified
    // by some variable v

    //Swap:
    u_parent = &graph->parents[u];

    DO_SOMETHING();
}

这个实现是否正确，因为我仍然看到其他线程在 CAS 操作后进入该区域？

Answer 1

我正在尝试实现比较和交换操作

您无法在 C 中实现这一点。这样的操作必须是原子的，才能有意义地用于线程之间的同步目的。注意序列点和内存模型。

一些编译器为此提供了内置函数。（另见这个问题）。最近的 GCC 提供了原子内置函数，其中__atomic_compare_exchange通常会编译成单个机器代码指令。阅读关于比较和交换的维基页面

在 Linux 上，还要注意futex(7)。对于像CMPXCHG这样的机器指令，它们是许多pthreads(7)操作的构建块（因此需要一些汇编代码）。另请阅读一个很好的pthread 教程。C11 标准（读取n1570）提供<stdatomic.h>（实际上，标准原子操作内置于编译器中，或使用现有的内置函数）。

还可以研究现有自由软件C 标准库的源代码，例如 GNU glibc或musl-libc。您将看到许多同步原语是在 futex、汇编代码和/或编译器内置函数之上构建的。

此外，OpenMP（当它由编译器实现时）正在改变编译器（当然还有生成的可执行文件）的行为。