Data Races, Critical Sections

Learning Outcomes

• Define a data race.
• Specify critical sections in OpenMP to synchronize threads.

As discussed earlier, threads operate under a shared memory model, where different threads can read from and write to the same locations in memory.

Consider the below program. What are possible values of x after running this program with four OpenMP threads?

#include <stdio.h>
#include <omp.h>
int main() {
  int x = 0;                        /* shared variable */
  #pragma omp parallel
  {
    x += 1;
  }
}

Data Race

Two memory accesses form a data race if:

• They are from different threads to the same location;
• At least one is a write; and
• They occur one after another.

In our multi-thread execution model, instructions from different threads have their execution interleaved in time, thus causing data races.¹

Let us translate the parallel section of our example code into the three RISC-V instructions below. With four OpenMP threads, there are four sets of three sections to execute. Each thread accesses the same variable x in (shared) memory but has its copy of register t0 used in arithmetic, resulting in the data race.

lw t0 0(sp)   # x @ sp
addi t0 t0 1
sw t0 0(sp)

Because of the many possibilities of interleaving the execution of these twelve instructions, the final value of x is not always the same.² Consider the cases below.

Critical Sections in OpenMP

To enforce multithreaded program correctness, we often need to synchronize threads, i.e., coordinate their execution. Most commonly, we must identify when one thread is finished writing so that it is safe for another to read.

Synchronization can be specified in user-level routines, i.e., in higher-level languages. A critical section is a segment of code that must be executed by a single thread at a time, thereby enforcing synchronization. Once a thread enters a critical section, it can safely execute all code in that critical section, knowing that it is the only thread that can execute that section at that time.

We discuss two OpenMP synchronization constucts:

• #pragma omp critical: Creates a critical section within a parallel code segment. OpenMP docs
• #pragma omp barrier: Forces all threads to wait until all threads have hit the barrier. OpenMP docs

Returning to our example code, we can specify a critical section and prevent any data races:

#include <stdio.h>
#include <omp.h>
int main() {
  int x = 0;                        /* shared variable */
  #pragma omp parallel
  {
    #pragma omp critical    
    {
      x += 1;
    }
  }
}

Data Race Examples

OpenMP Hello World: Add

#include <stdio.h>
#include <omp.h>
int main() {
  int x = 0;                        /* shared variable */
  #pragma omp parallel
  {
    int tid = omp_get_thread_num(); /* private variable */
    #pragma omp critical    
    {
      x++;
    }
    printf("Hello World from thread = %d, x = %d\n", tid, x);

    #pragma omp barrier
    if (tid == 0) {
      printf("Number of threads = %d\n", omp_get_num_threads());
    }
  }
}

Hello World from thread = 11, x = 10
Hello World from thread = 01, x = 1
Hello World from thread = 06, x = 11
Hello World from thread = 07, x = 7
Hello World from thread = 09, x = 8
Hello World from thread = 03, x = 9
Hello World from thread = 04, x = 5
Hello World from thread = 10, x = 3
Hello World from thread = 08, x = 2
Hello World from thread = 00, x = 12
Number of threads = 12
Hello World from thread = 02, x = 6
Hello World from thread = 05, x = 4
Final value of x: 12