Data Races

Races are a major cause of bugs in parallel programs.

A determinacy race occurs when two parallel strands access the same memory location and at least one strand performs a write operation. The program result depends on which strand "wins the race" and accesses the memory first.

A data race is a special case of a determinacy race. A data race is a race condition that occurs when two parallel strands, holding no locks in common, access the same memory location and at least one strand performs a write operation. The program result depends on which strand "wins the race" and accesses the memory first.

If the parallel accesses are protected by locks, there is no data race. However, a program using locks may not produce deterministic results. A lock can ensure consistency by protecting a data structure from being visible in an intermediate state during an update, but does not guarantee deterministic results.

For example, consider the following program:

int a = 2; // declare a variable that is
          // visible to more than one worker

void Strand1()
{
   a = 1;
}

int Strand2()
{
   return a;
}

void Strand3()
{
   a = 2;
}
int main()
{
   int result;
   cilk_spawn Strand1();
   result = cilk_spawn Strand2();
   cilk_spawn Strand3();
   cilk_sync;
   std::cout << "a = " << a << ", result = "
             << result << std:endl;
}

Because Strand1(), Strand2() and Strand3() may run in parallel, the final value of a and result can vary, depending on the order in which they run.

Strand1() may write the value of a before or after Strand2() reads a, so there is a read/write race between Strand1() and Strand2().

Strand3() may write the value of a before or after Strand1() writes a, so there is a write/write race between Strand3() and Strand1().

Some data races are benign. In other words, although there is a race, the race does not affect the output of the program.

Here is a simple example:

bool bFlag = false;
cilk_for (int i=0; i<N; ++i)
{
   if (some_condition()) bFlag = true;
}
if (bFlag) do_something();

This program has a write/write race on the bFlag variable. However, all of the write operations are writing the same value (true) and the value is not read until after the cilk_sync that is implicit at the end of the cilk_for loop.

In this example, the data race is benign. No matter what order the loop iterations execute, the program produces the same result.