用于 c，openmp 的 CAS 实现

Question

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?

转载于:https://stackoverflow.com/questions/53147982/implementation-of-cas-for-c-openmp

Answer 1

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.