Controlling concurrent access to a shared resource

Content

In our previous examples we followed the fork and join pattern in a manner where the threads operated strictly independently from each other, i.e. none of the threads attempted to access directly or indirectly shared resources or data structures. To uphold this, we were enforced to create individual pseudo-number generators for each thread with different seed values. This does not come cheap. On our computer Thales, the generation of a single uniformely distributed pseudo-random number using std::mt19937 takes in average 8.4 nano seconds whereas the construction and preparation of a std::mt19937 object takes about 9 micro seconds. You need even more time when you want more entropy than just from one 32-bit value.

Mutex variables

Examples like this might lead us to the question whether concurrent accesses to a shared resource like a pseudo-random generator are possible. The thread interfaces of POSIX and C++11 provide so-called mutex variables for this purpose where mutex is a shortname for mutual exclusion. Mutex variables can be used to make sure that at maximum just one thread accesses a shared resource. Other threads that want to access the resource at the same time have to wait until the other thread has finished its access.

Mutex variables of the type std::mutex out of <mutex> can be easily used:

The access of a shared pseudo-random number generator could be wrapped as shown in following example:

struct MyRandomGenerator {
   MyRandomGenerator() : mt(std::random_device()()), uniform(-100, 100) {
   }
   double gen() {
      mutex.lock();
      double val = uniform(mt);
      mutex.unlock();
      return val;
   }
   std::mutex mutex;
   std::mt19937 mt;
   std::uniform_real_distribution<double> uniform;
};

The gen method assures exclusive access using mutex.lock(), retrieves a value from the pseudo-random generator, and finally releases its exclusive access to the resource.

However, the variables of the MyRandomGenerator class are publically accessible, i.e. anyone is free to access mt directly without using the gen method or even without getting exclusive access first through mutex. So far, we were not bothered when classes provided public access to all of its internal variables. In this case, however, we would like to make sure to keep the variables mutex, mt and uniform private such that gen has to be used. This is possible by declaring these variables private:

struct MyRandomGenerator {
      MyRandomGenerator() : mt(std::random_device()()), uniform(-100, 100) {
      }
      double gen() {
	 mutex.lock();
	 double val = uniform(mt);
	 mutex.unlock();
	 return val;
      }
   private:
      std::mutex mutex;
      std::mt19937 mt;
      std::uniform_real_distribution<double> uniform;
};

This code is still not safe as we are unfortunately unable to assure that mutex.unlock() is guaranteed to be called after mutex.lock().

Is this actually possible in this case where mutex.lock() and mutex.unlock() are so nicely paired within a method? Unfortunately, this can indeed happen when the invocation of uniform(mt) leads to an exception that causes the stack to be unwound until an exception handler is found. In the course of this stack unwinding the gen() method invocation is abandoned and mutex.unlock() gets never invoked. Because of this problem, the above presented solution is not exception safe.

The only approach in C++ to achieve exception safeness works on base of destructors. As C++ guarantees that even in case of an unwound stack all destructors are properly called we need to move the invocation of mutex.unlock() to a destructor. Hence, we need again to apply the RAII principle (resource acquisition is initialization) where an object that is responsible for the mutex variable

Exercise

Write a simple and minimalistic RAII class as described for mutex variables, use this within the MyRandomGenerator example, and test it by applying this solution in random_init8.cpp which is similar to the one we used on last Monday but uses UniformSlices from <hpc/aux/slices.hpp>.

The header-only library for this session is available in the directory /home/numerik/pub/hpc/ws18/session16 on our hosts.

#include <cstdlib>
#include <random>
#include <thread>
#include <vector>
#include <hpc/matvec/gematrix.hpp>
#include <hpc/matvec/iterators.hpp>
#include <hpc/matvec/print.hpp>
#include <hpc/matvec/traits.hpp>

using namespace hpc;
using namespace hpc::matvec;

template<typename T>
struct Slices {
   Slices(T nof_threads, T problem_size) :
	 nof_threads((assert(nof_threads > 0), nof_threads)),
	 problem_size(problem_size),
	 remainder(problem_size % nof_threads),
	 slice_size(problem_size / nof_threads) {
   }
   T offset(T index) {
      assert(index < nof_threads);
      if (index < remainder) {
	 return index * (slice_size + 1);
      } else {
	 return remainder * (slice_size + 1) +
	        (index - remainder) * slice_size;
      }
   }
   T size(T index) {
      assert(index < nof_threads);
      if (index < remainder) {
	 return slice_size + 1;
      } else {
	 return slice_size;
      }
   }
   T nof_threads; T problem_size;
   T remainder; T slice_size;
};

template <
   template<typename> class MatrixA, typename T,
   Require< Ge<MatrixA<T>> > = true
>
void randomInit(MatrixA<T>& A) {
   std::random_device random;
   std::mt19937 mt{random()};
   std::uniform_real_distribution<T> uniform(-100, 100);
   
   for (auto [i, j, Aij]: A) {
      Aij = uniform(mt);
   }
}

int main() {
   GeMatrix<double> A(51, 7);
   auto nof_threads = std::thread::hardware_concurrency();

   std::vector<std::thread> threads(nof_threads);
   Slices<std::size_t> slices(nof_threads, A.numRows());
   for (int index = 0; index < nof_threads; ++index) {
      auto firstRow = slices.offset(index);
      auto numRows = slices.size(index);
      threads[index] = std::thread(
	 [A_ = A.block(firstRow, 0).dim(numRows, A.numCols())]() mutable {
	    randomInit(A_);
	 }
      );
   }
   for (int index = 0; index < nof_threads; ++index) {
      threads[index].join();
   }
   fmt::printf("A:\n"); print(A);
}
theon$ g++ -O3 -g -I/home/numerik/pub/hpc/ws18/session16 -std=c++17 -o random_init8 random_init8.cpp
theon$ ./random_init8
   97.86   17.59  -91.52   73.19  -69.23  -50.02  -31.78
  -15.73  -82.54   12.64  -43.60  -22.57   82.24   39.87
  -58.58   90.10   75.47   84.50  -94.86   -6.04   10.71
   79.01   23.38   22.38  -65.44  -83.31  -32.49   54.63
   74.69  -43.38    9.61   -0.66   98.31   96.11   15.15
  -33.92   55.53   78.29  -71.89  -57.39  -82.39   63.96
  -74.38  -87.01  -98.85   45.86   88.93  -59.28  -20.36
   56.11  -44.10   95.57  -53.11   60.93   77.63   68.75
   13.85   89.07  -89.26   26.52  -33.89  -50.85  -30.07
  -76.54   20.03  -22.26   28.60   43.13   34.34   97.04
  -58.29   -3.99   39.73  -60.01  -16.51   19.95   27.91
   73.66   72.64   14.57  -77.04   93.35   -5.42  -91.27
   -8.24  -56.55   37.06  -23.91    9.04   93.10   18.11
  -84.98   79.58   77.39  -57.97  -76.17   68.51  -54.76
  -55.64   89.31   24.75  -30.06  -90.62   -9.74   41.75
  -58.42   59.06    9.86   76.19  -23.40  -68.25  -97.23
   49.31  -64.83   31.68  -29.36  -61.79   42.55  -63.10
  -17.75   14.44  -38.72   60.03  -40.47   97.35   90.99
  -99.14  -15.54   56.08  -29.80  -83.62  -82.57  -76.37
   33.64  -48.83  -32.92  -65.27   55.24  -20.35   79.26
   58.68   47.96   34.96  -77.45  -81.82   -3.33  -19.16
   45.91   23.25  -78.17  -67.31   69.62   79.44  -88.35
   94.29   72.91   -3.43  -61.77   23.43  -27.52   38.26
  -23.55  -24.14   78.02   31.61  -55.77   -5.47   59.74
  -97.57   45.28   24.52   51.47  -59.59   70.98   19.69
   23.84   24.10   38.53   73.49   94.18   37.97  -57.67
  -46.99   29.88  -15.20  -21.70  -90.22   94.30  -12.10
  -17.30  -58.12   92.44   76.62  -65.78   58.05   94.30
  -36.71  -56.20  -16.51  -96.59  -95.86   21.65   73.14
   47.09   53.30  -57.32   43.54  -41.14   -5.28   25.77
   87.42   35.47   -6.24  -77.88  -71.67  -52.10   35.67
   28.19  -87.06  -22.78  -13.79  -18.11  -90.46   89.70
  -14.72   22.04   -9.35  -73.58   53.53   32.69  -13.87
   36.13  -94.60  -23.94   51.44  -80.01  -95.86   98.52
  -43.31  -31.48   74.43  -39.30  -40.68   16.30   71.06
  -88.37   82.09  -36.94  -23.59  -67.50  -41.50   76.73
   82.82   87.41   -7.18  -85.55  -12.67   27.16  -44.73
   72.98   84.56  -30.71   97.33   61.30   13.06   21.17
   24.57   30.85   25.21   70.51  -63.18  -29.82   92.95
   50.17   70.82   67.41   96.07   25.24   37.05   65.80
  -67.63  -84.42   71.07  -65.14   11.78   79.89  -43.33
  -10.11  -37.18   99.89  -24.61  -93.08   61.62   42.72
   49.56  -63.17  -10.96  -27.37  -98.91  -90.34  -81.36
   12.14   41.29  -91.78   23.80  -75.52  -92.31   99.22
   86.49  -98.76  -64.46   82.19  -50.90   78.06   61.81
   46.28   -1.68  -44.11   -5.93   74.09   91.04   -6.03
  -84.94  -66.81  -38.87  -16.13  -14.85  -96.78   26.36
  -93.79  -80.72  -99.96  -77.83   19.19   20.20  -29.30
   85.85   62.69  -47.37  -86.29  -27.37   45.71   72.44
   96.43   91.34   97.89    9.40   58.23  -64.95  -97.26
   77.13   55.64   86.72   52.97  -97.56   87.88  -13.88
theon$