Assigning return value of an atomic function

Question

I'm trying to implement a barrier function, such that when a thread calls waitBarrier() it will wait until all other n threads have called the function, after which all will proceed, i.e. a sort of synchronization construct.

I have following code:

int i = 0; // Shared variable. Initialized as 0 at the beginning.

waitBarrier() {

  // CAS = Compare-and-swap, the first argument holds "old_val" the second the new
  i = CAS(i, i+1);

  // Spin until all n threads (number of all threads known prior) have been "here"
  while (i != n) {}

}

If this gets accessed by n threads, will this function work? Is the assignment of the return value of an atomic function atomic? Or could race conditions occur?

Answer 1

First of all you would have to specify the address of a register, the value of which you are comparing and swapping with. This can be done with either of the following:

CAS(int* reg, int oldValue, int newValue)

or

reg.CAS(int oldValue, int newValue)

Assuming your line now would be:

i = i.CAS(i, i+1)

Imagine two threads calling waitBarrier() at the same time. Assuming arguments of an atomic function are being evaluated non-atomically, i.e. both threads will actually call i.CAS(0,1)

Whoever atomic call is being executed first will successfully set the shared variable i to 1. Since CAS does always return the old value, by having an assignment i = OLD_VALUE_OF_i you're actually resetting the shared variable back to 0. Not only that but imagine you would omit that assignment completely and just made the CAS call, whoever thread executes CAS second will compare the value of the shared value (which now would be 1) with the initial value of i (at evaluation time of the arguments that was 0) which will fail and therefore the shared variable will only be incremented once!

Taking those two aspects into consideration, your code would have to look as following:

int i = 0;

waitBarrier() {
  // Atomically increment the shared value i by 1
  do {
    int value = i;
  } while (CAS(i, value, value + 1));

  // Wait until all threads have passed the barrier
  while (i != n) {}
}