为c，openmp实现CAS [英] Implementation of CAS for c, openmp

问题描述

我正在尝试实现比较和交换操作，以便我的线程基于值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操作后仍然看到其他线程进入该区域?

解决方案

我正在尝试执行比较和交换操作

您无法在C语言中实现该操作.此类操作必须原子有意义地用于线程之间的同步目的.请注意序列点和此问题).最近的GCC提供了原子内建，其中包括__atomic_compare_exchange通常会被编译成单个机器代码指令.阅读比较并交换

上的Wiki页.

在Linux上，还要注意 futex(7).使用 CMPXCHG 这样的机器指令，它们是许多 pthread教程. C11标准(阅读 n1570 )提供了免费软件 C标准库的源代码. GNU glibc 或 musl-libc .您会看到许多同步原语是在futex，汇编代码和/或编译器内置文件之上构建的.

此外， OpenMP (由编译器实施时)正在改变以下行为:编译器(当然还有生成的可执行文件).

I'm trying to implement the compare and swap operation so that my threads know whether or not to enter a particular region based on a value u_parent. I just want to know if this is the correct way to implement it and if I am going wrong somewhere.

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();
}

Is this implementation correct because I am still seeing other threads enter this region after the CAS operation?

解决方案

I'm trying to implement the compare and swap operation

You cannot implement that in C. Such an operation has to be atomic to be meaningfully usable for synchronization purposes between threads. Be aware of sequence points and memory models.

Some compilers provide a builtin for that. (See also this question). Recent GCC provide atomic builtins including __atomic_compare_exchange which generally gets compiled into a single machine code instruction. Read the wikipage on compare-and-swap

On Linux, be also aware of futex(7). With machine instructions like CMPXCHG they are the building blocks of many pthreads(7) operations (so require some assembler code). Read also a good pthread tutorial. The C11 standard (read n1570) provides <stdatomic.h> (in practice, the standard atomic operations are builtin to the compiler, or uses existing builtins).

Study also the source code of existing free software C standard libraries, e.g. GNU glibc or musl-libc. You'll see that many synchronization primitives are built above futexes, assembler code, and/or compiler builtins.

Also, OpenMP (when it is implemented by the compiler) is changing the behavior of the compiler (and of course of the generated executable).

这篇关于为c，openmp实现CAS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！