Synchronization

Talking about the race condition and the synchronization methods.

Table of contents

• Synchronization
  • Race condition
  • Traditional Solution: Lock
  • Modern Solution - Lockfree : Atomic operations
    • TAS (for Lock)

Race condition

When using the shared memory / resources, race condition can occur. In the diagram Thread1 and Thread2 tries to increase the shared variable a, but if the data captured both Thread 1 and Thread 2 and not returned yet from those threads, in this case, we can see the unexpected behavior that a=3 not a=4. In this case, attempting to accessing the shared variable a causes this race, and this kind of operation is called as a critical section. Dealing with this race conditions safely and efficiency is the key stone of the multithreading(multiprocessing), which is called as synchronization.

#include <array>
#include <chrono>
#include <iostream>
#include <thread>

#include "Timer.h"

void IncreaseA(const int numIter, int* shared_ptr)
{
   int i = 0;
   using namespace std::chrono_literals;
   for (int i = 0; i < numIter; ++i) {
       ++(*shared_ptr);
       std::this_thread::sleep_for(10us);
   }
}

int main()
{
  
   Timer timer;
   constexpr int NUM_THREADS = 4;
   constexpr int NUM_ITERATIONS = 10'000;

   int shared_value = 0;
  
   std::array<std::thread, NUM_THREADS> threads;
  
   for(int i=0; i<NUM_THREADS; ++i)
   {
       threads[i] = std::thread(IncreaseA, NUM_ITERATIONS, &shared_value);
   }

   for(int i=0; i<NUM_THREADS; ++i)
   {
       threads[i].join();
   }
  
   std::cout << shared_value << "\n";

}

Traditional Solution: Lock

Once one Thread enters a Critical Section to perform a task, a lock prevents other Threads from performing that task.

• Lock: An abstract concept for a critical section. It refers to a mechanism that prevents all processes from touching resources or code blocks that one or more threads are simultaneously accessing.

• Mutex: It is one of the concrete tools that implement the Lock concept. As its name implies, it is the most representative way to allow only one thread to access at a given time by providing mutual exclusion

Modern Solution - Lockfree : Atomic operations

In modern computers, atomic operations supports in hardware / OS levels. These atomic operation ensures the un-breakable operations such as ordering memories in store and load memories, CAS (compare and swap), and TAS (test and set).

Here’s the example of Lock in C++

#include <array>
#include <chrono>
#include <iostream>
#include <thread>
#include <mutex>

#include "Timer.h"

void IncreaseA(const int numIter, int* shared_ptr, std::mutex& mtx)
{
   int i = 0;
   using namespace std::chrono_literals;
   for (int i = 0; i < numIter; ++i)
   {
       { // mtx was given by reference, lock_guard is RAII Wrapper, when the lock is out of the code block, it safely unlock the mutex.
           std::lock_guard<std::mutex> lk(mtx);
           ++(*shared_ptr);
       } // unlock occurred - RAII
       std::this_thread::sleep_for(10us);
   }
}

int main()
{
  
   std::mutex mtx;
  
   constexpr int NUM_THREADS = 4;
   constexpr int NUM_ITERATIONS = 10'000;

   int shared_value = 0;
  
   std::array<std::thread, NUM_THREADS> threads;
   {
       Timer timer;
       for(int i=0; i<NUM_THREADS; ++i)
       {
           threads[i] = std::thread(IncreaseA, NUM_ITERATIONS, &shared_value, std::ref(mtx));
       }

       for(int i=0; i<NUM_THREADS; ++i)
       {
           threads[i].join();
       }
   }
   std::cout << shared_value << "\n";

}

TAS (for Lock)

The following TAS algorithm is just for the understanding TAS (mutex). Since the following code is not actually hardware system, it causes data race.

// TAS
// This TAS is not actually working because of the following TAS not atomic operation. 
bool TestAndSet(bool *p)
{
   if (*p)
   {
       return true;
   }
   else
   {
       *p = true;
       return false;
   }

}

class Mutex
{   
public:
   void Lock() {
       while (TestAndSet(&m_IsLocked)) {
          // Since TAS, if m_IsLocked starts with false,
          // it returning false and at the same time, it locks the
          // member variable with m_IsLocked = true;
       }
       // If it is not unlocked in the same code block,
       // Because of the pointer, m_IsLocked keep as true.
       // This makes the others be keep waiting.
   }
   void Unlock() {
       // Must Lock first then Unlock 
       m_IsLocked = false;
   }

private:
   bool m_IsLocked = false; // false: unlocked, true: locked

};

In C++, we can use std::atomic stl for the atomic operation system calls.

#include <atomic>

class Mutex {
public:
   void Lock() {
       while (m_IsLocked.exchange(true)) {} // TAS
   }
   void Unlock() {
       m_IsLocked.store(false);
   }
private:
   std::atomic<bool> m_IsLocked = false;
};

for the real lock free pattern, C++ std::atomic offers std::atomic<T> for the shared variables.

#include <array>
#include <chrono>
#include <iostream>
#include <thread>
#include <atomic> // Include for atomic operations

#include "Timer.h" // Assuming Timer is defined elsewhere

// Function using std::atomic
void IncreaseAAtomic(const int numIter, std::atomic<int>* shared_atomic_ptr)
{
    using namespace std::chrono_literals;
    for (int i = 0; i < numIter; ++i) {
        (*shared_atomic_ptr)++; // Atomic increment
        std::this_thread::sleep_for(10us);
    }
}

int main()
{
    constexpr int NUM_THREADS = 4;
    constexpr int NUM_ITERATIONS = 10'000;

    std::atomic<int> shared_atomic_value = 0; // Use std::atomic

    std::array<std::thread, NUM_THREADS> threads;
    {
        Timer timer; // Assuming Timer works here
        for(int i=0; i<NUM_THREADS; ++i)
        {
            threads[i] = std::thread(IncreaseAAtomic, NUM_ITERATIONS, &shared_atomic_value);
        }

        for(int i=0; i<NUM_THREADS; ++i)
        {
            threads[i].join();
        }
    }
    std::cout << shared_atomic_value << "\n"; // Access atomic value
    return 0;
}