Race Condition in C++

1. What are Threads
2. What is a Race Condition
3. Avoid Race Condition
4. Avoid Race Condition Using Mutex
5. Avoid Race Condition Using Semaphore
6. Conclusion

In this tutorial, we will learn about the concept of a race condition. First, we will take an introduction of threads, and then we will discuss the race condition in threads with examples.

Lastly, we will see solutions to avoid/control the race condition.

What are Threads

Threads are lightweight processes. Processes can have multiple threads, which share many resources of the process.

Threads are meant to cooperate; therefore, they share memory/variables among other resources.

Threads are used to run concurrent tasks within a process. For example, an MS Word processing process has multiple tasks performed simultaneously.

These tasks include spelling, grammar, auto-saving, labeling keywords, indentation, and formatting. We can use separate threads to run these simultaneous tasks concurrently.

Concurrent Sorting and Printing

Here, we will discuss one coding example to understand the threads better. Assume that we have to sort and print many values.

First, we must sort them out completely before we can print them.

However, there are some sorting techniques like selection sort, which sorts numbers such that in each iteration, we will get smaller elements at the start of the list. Therefore, we can start printing in parallel.

Here is the code:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define SIZE 1000
int x[SIZE];
void init() {
  int i;
  for (i = 0; i < SIZE; i++) x[i] = rand() % 1000;
}
void* print(void* a) {
  int i;
  for (i = 0; i < SIZE; i++) printf("%d ", x[i]);
  printf("\n");
}
void* sort(void* b) {
  int i, j, temp;
  for (i = 0; i < SIZE - 1; i++)
    for (j = SIZE - 1; j >= 1; j--)
      if (x[j] < x[j - 1]) {
        temp = x[j];
        x[j] = x[j - 1];
        x[j - 1] = temp;
      }
}
int main() {
  srand(time(0));
  init();
  pthread_t tSort, tPrint;
  pthread_create(&tSort, NULL, sort, NULL);
  pthread_create(&tPrint, NULL, print, NULL);
  pthread_join(tSort, NULL);
  pthread_join(tPrint, NULL);
  return 0;
}

In this code, the sort and print functions are running in parallel; however, if you see the output, it will not be correct.

The reason is that the sorting thread is slower than the printing thread, and there is no synchronization between them. Therefore, the printing thread quickly prints values that are not sorted yet; therefore, the output is unsorted.

A multi-thread program is prone to these synchronization issues and some other issues. Next, we will discuss one such issue called race condition.

What is a Race Condition

A race condition is an unwanted condition that can occur when multiple processes or threads access some shared data simultaneously.

The final value depends on the process/thread which accesses the data at last. Let us explain it with an example.

Suppose we have two threads, A and B, and a shared variable x. Both threads are running an instruction x++ in parallel.

If you critically examine this instruction in a low-level language, this instruction is composed of three instructions. The three instructions are:

read x inc x write x

The first instruction reads the variable from memory into a register (inside the processor). In the second instruction, a variable is incremented by 1, and the result is in a register.

The variable is written back to memory in the third and last instruction.

Suppose two threads are running these instructions in parallel. We have no idea about their execution sequence; it depends on various factors like scheduling algorithm, time slice, the priority of the processes, and set of running/new processes, etc.

We may have multiple possible sequences executing these instructions, and a different sequence can occur each time. For example, thread A may execute the first two instructions, and the operating system switches the context.

Suppose the variable’s value is 5, thread A has read 5 and incremented it by 1, so now the value is 6 (but inside the register). When the context switches and thread B starts its execution, it will also read the same value, 5.

Thread B will increment the value by 1. The value becomes 6.

Thread B completes the last instruction and writes a 6 value into memory.

The context switches again, and control eventually comes to thread A; now, thread A will execute the last instruction, write x.

Recall that thread A has read value 5 and increments it by 1. Thread A will also write 6 into memory.

As a result, the value will be 6 instead of 7 because two threads have performed the increment operation, and the value should be 7. Therefore, due to unexpected context switching, the result is incorrect.

Producer-Consumer Problem

Let’s see the following coding example before discussing the Producer-Consumer problem.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) count++;
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) count--;
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  printf("Count = %d\n", count);
  return 0;
}

This code demonstrates the classic operating system problem called the Producer-Consumer problem. This code has a global (shared) variable count, initialized by 0.

The producer function increments the count by 1, and the consumer function decrements the count by 1.

However, both functions are run by two different threads, where context switching can occur anytime. You can easily experience this by running the code.

If there is no race condition, the result should be 0 because both functions are doing increment and decrement the same number of times. The unit increment and decrement mean the value of the count should be zero at the end.

However, when you run this code, you will observe that the value is not zero. Rather, different values will come in each iteration, clearly showing that scheduling is unpredictable.

Some Practical Producer-Consumer Examples

The increment example of the two threads discussed above is not a hypothetical problem; many such practical scenarios exist when working with multi-threading.

For example, in the banking system, a customer has two choices to withdraw an amount. One is to present a cheque to the bank, whereas, in parallel, someone can withdraw the amount from ATM using the customer’s ATM card.

Similarly, it is possible that two or more teachers, by chance, update/post the marks of the same students, which in turn increases/decreases students’ total marks. Two or more companies may simultaneously deduct the customer’s weekly, monthly, or annual subscription.

The race condition may result in incorrect results, which is not affordable. Therefore, should we announce that due to race condition problems, the applicability of multi-threading is not practical in many scenarios?

No, we have the solution to avoid/control the race condition.

Avoid Race Condition

We have both hardware and software solutions for race conditions. The hardware solution is to provide related atomic instructions as a part of the CPU instructions set (e.g., CMPXCHG in x86 architecture).

The software solution uses mutex or semaphores to regularize the entry of the process to the critical sections.

Atomic Operation

The manufacturer can implement atomic operations in the hardware. After implementing atomic operation in the hardware, such instruction will complete their execution without context switching. In other words, the process/thread execution should not be divided into parts.

However, this solution is for manufacturers and not possible to implement by common users.

Mutual Exclusion

A mutual exclusion means that if one process/thread is accessing some shared variable, then no other process/thread should be allowed to access the shared variable already held by another process/thread.

Mutual Exclusion can be implemented using a mutex (lock) or semaphore. You may click to read about Mutex vs. Semaphore to clarify the concepts.

Avoid Race Condition Using Mutex

Mutex is a concept of a special lock. This lock is shared among threads; however, if multiple threads want to lock the mutex, only one (first) thread will succeed in locking and enter into the critical section.

The remaining threads trying to lock the mutex will be blocked until the first thread comes out of the critical section and unlock the mutex.

An unlocked mutex can be locked by one thread at any time. On unlocking the mutex, any of the blocking threads can get the opportunity to lock the mutex and enter into the critical section.

There is no concept of the queue in mutex. Any of the blocking/awaiting threads can get a chance to get the mutex and lock it.

It is a very simple solution and extremely useful when we have two threads in race conditions or multiple threads in race conditions, and there is no issue of turn/queue.

Let’s realize the solution using the following C example implementing a mutex lock using the pthread Linux library.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;
pthread_mutex_t lock;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    pthread_mutex_lock(&lock);
    count++;
    pthread_mutex_unlock(&lock);
  }
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    pthread_mutex_lock(&lock);
    count--;
    pthread_mutex_unlock(&lock);
  }
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  pthread_mutex_init(&lock, NULL);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  pthread_mutex_destroy(&lock);
  printf("Count = %d\n", count);
  return 0;
}

You may run this code multiple times. Each time, it will give the value of count 0.

The code has a shared variable lock of a special type, pthread_mutex_t. Producer and consumer functions are locked before executing critical section instructions count++ and count--.

Again, both release mutex by calling unlock function after the end of their critical section.

In the main function, we are initializing mutex and destroying mutex after the use of mutex.

Avoid Race Condition Using Semaphore

Semaphore is a solution provided by the operating system. Semaphore is a solution for thread synchronization.

We may want some specific sequence of execution of instructions; however, we may use it to avoid race conditions, but it is not an exact solution; later, we will discuss why.

Here, we are avoiding the long and detailed topic of synchronization and coming towards using semaphores to avoid race conditions. Using a semaphore is stopping the thread at some specific point and waiting for a signal from another thread.

We will initialize the semaphore by zero and call the wait function, decreasing the semaphore by 1 and going into a sleep state.

Later, another thread will call signal operation, incrementing the semaphore by 1 and awake some sleeping thread in the queue.

In Linux, the semaphore is available in the library semaphore.h. We have wait and post functions for the wait and signal operations.

See the code:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;
sem_t semaphore1, semaphore2;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    count++;
    sem_post(&semaphore1);
    sem_wait(&semaphore2);
  }
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    sem_wait(&semaphore1);
    count--;
    sem_post(&semaphore2);
  }
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  sem_init(&semaphore1, 0, 0);
  sem_init(&semaphore1, 0, 0);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  sem_destroy(&semaphore1);
  sem_destroy(&semaphore2);
  printf("Count = %d\n", count);
  return 0;
}

Again, you can run this code and get a shared variable’s exact/correct value. Implementation is similar to a mutex; however, one major difference is the initialization step.

There are three parameters in the initialization function. The first is the semaphore variable.

The second is either 0 or 1. Here, 0 means the semaphore is shared between threads of the same process, whereas 1 means the semaphore is shared among threads of different processes.

The third parameter is the value of the semaphore; if you want that multiple threads (but limited to some count) can enter into the critical section together, you can initialize the semaphore value with the count.

The second difference in this implementation is that we are using two semaphores, whereas we used only one lock in the case of the mutex.

The mutex code puts the lock before using a shared variable and releases the lock after using a shared variable. Whenever a customer is going to operate a locker in the bank locker room, the staff gives a key to the customer to lock the locker before opening the locker and opening the locker room after the locker is locked.

However, in semaphore, we use two semaphores; both are initialized by 0, which means the calling thread wait will be blocked until some other thread gives a signal. Here, the consumer is waiting on semaphore 1, signaled by the producer thread, after incrementing the count.

At the same time, the producer thread is waiting on semaphore 2, which is to be signaled by the consumer thread after decrementing the count.

This way, the producer and consumer will increment and decrease the count one by one, which is synchronization. Using semaphore, we keep the count correct; however, we restrict the threads to execute in sequence.

In the case of mutex, both threads can execute in any sequence without impairing the value of the shared variable count.

Conclusion

The threads are very useful for running codes/functions in parallel; however, there are some issues with threads, like a race condition. The condition can cause unexpected results.

Luckily, we can use mutex locks and semaphores to avoid race conditions. The best and right way to handle race conditions is a mutex.