CODEWITHSUNDEEP
c++11atomiclock-free
Javi
Javi

Reputation: 11

lock free programming - c++ atomic

I am trying to develop the following lock free code (c++11):

int val_max;
std::array<std::atomic<int>, 255> vector;

    if (vector[i] > val_max) {
    val_max =vector[i];
    }

The problem is that when there are many threads (128 threads), the result is not correct, because if for example val_max=1, and three threads ( with vector[i] = 5, 15 and 20) will execute the code in the next line, and it will be a data race..

So, I don't know the best way to solve the problem with the available functions in c++11 (I cannot use mutex, locks), protecting the whole code.

Any suggestions? Thanks in advance!

Upvotes: 1

Views: 738

Answers (2)

David Schwartz
David Schwartz

Reputation: 182753

  1. Do an atomic fetch of val_max.
  2. If the value fetched is greater than or equal to vector[i], stop, you are done.
  3. Do an atomic compare exchange -- compare val_max to the value you read in step 1 and exchange it for the value of vector[i] if it compares.
  4. If the compare succeeded, stop, you are done.
  5. Go to step 1, you raced with another thread that made forward progress.

Upvotes: 1

Sebastian Redl
Sebastian Redl

Reputation: 71899

You need to describe the bigger problem you need to solve, and why you want multiple threads for this.

If you have a lot of data and want to find the maximum, and you want to split that problem, you're doing it wrong. If all threads try to access a shared maximum, not only is it hard to get right, but by the time you have it right, you have fully serialized accesses, thus making the entire thing an exercise in adding complexity and thread overhead to a serial program.

The correct way to make it parallel is to give every thread a chunk of the array to work on (and the array members are not atomics), for which the thread calculates a local maximum, then when all threads are done have one thread find the maximum of the individual results.

Upvotes: 3

Related Questions