Implementation of CAS for c, openmp

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?

Wrong thinking. CAS is a *primitive* operation, above which multi-threading is built — Basile Starynkevitch, Nov 05 '18 at 06:07
If using OpenMP is a given for your situation--and you don't want to involve another specification or standard for threading to get atomic features--it seems [OpenMP has its own atomic operations](https://stackoverflow.com/questions/7798010/what-is-the-difference-between-atomic-and-critical-in-openmp) you might use. — HostileFork says dont trust SE, Nov 05 '18 at 06:21

Basile Starynkevitch · Answer 1 · 2018-11-05T15:00:42.217

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).

Implementation of CAS for c, openmp

1 Answers1

Linked