Condition variables

Content

Let us return to the pool pattern. There are two variants, one with dynamically added objects when necessary and one with a fixed number of objects. Let us see how the latter variant can be implemented.

The template class std::vector comes handy when we have a fixed number of objects:

std::vector<T> engines;

The dimension of the vector can be configured in the constructor. If we follow this approach, we “keep” all maintained objects in our pool and lend objects by providing a lvalue reference, i.e. get returns T& instead of T. And in case of free we would no longer need an rvalue reference but a lvalue reference. We would have just the problem to locate the returned object within the array. This can be done by comparing addresses with \(O(n)\) operations (it is possible to improve this but let us keep this example simple). An implementation could be done as follows:

template<typename T>
struct RandomEnginePool {
      using EngineType = T;
      RandomEnginePool(std::size_t size) :
	    size(size), inuse(size), engines(size) {
	 std::random_device r;
	 for (std::size_t i = 0; i < size; ++i) {
	    engines[i].seed(r()); inuse[i] = false;
	 }
      }
      T& get() {
	 std::lock_guard<std::mutex> lock(mutex);
	 for (std::size_t i = 0; i < size; ++i) {
	    if (!inuse[i]) {
	       inuse[i] = true; --nof_free_engines;
	       return engines[i];
	    }
	 }
	 /* problem: no free engine found */
      }
      void free(T& engine) {
	 std::lock_guard<std::mutex> lock(mutex);
	 bool found = false;
	 for (std::size_t i = 0; i < size; ++i) {
	    if (&engine == &engines[i]) {
	       inuse[i] = false; ++nof_free_engines;
	       found = true; break;
	    }
	 }
	 assert(found);
      }
   private:
      std::mutex mutex;
      std::size_t size;
      std::vector<bool> inuse;
      std::vector<T> engines;
};

This works quite well but we do not know yet how to handle the problem that we do not find a free engine. In this case we would like to suspend the invoking thread until an engine becomes free again.

C++ provides so-called condition variables for this kind of synchronization. Condition variables provide a wait method that allows to wait until an event occurs. This event can be signalled using the notify_one or notify_all method.

Following point is very important in regard to condition variables: An invocation of notify_one or notify_all is without effect when there is no thread waiting for it. The notification methods are able to awake threads only which are already waiting. In case of notify_one just one of the waiting threads is awoken, in case of notify_all all waiting threads resume execution.

In principle, we could implement a possibly waiting method as follows:

std::lock_guard<std::mutex> lock(mutex);
if (/* need to wait */) {
   lock.unlock();
   cv.wait(); /* cv is a condition variable */
   lock.lock();
}
/* we do not need to wait (any longer) */

It is important to release the mutex variable. If we do not release it, all methods that process returned objects will wait endlessly for mutual access. Hence we would end up with a deadlock.

A possibly signalling method could be implemented as follows:

std::lock_guard<std::mutex> lock(mutex);
/* ... */
if (/* someone waits */) {
   cv.notify_one();
}

This technique has a serious problem: The invocation of lock.unlock() causes a thread to resume execution that was waiting in std::lock_guard<std::mutex> lock(mutex). If in the now following race the resumed thread is faster in notifying with cv.notify_one() than the other thread with waiting using cv.wait(), the signalling remains without effect and the suspended thread will possibly wait endlessly for a notification.

This problem can only be solved by making the combination of releasing the mutex variable and waiting for the condition variable atomic, i.e. there must be no notification in-between these two operations. This is the reason why the wait method of condition variables always expects a mutex object (or a lock that wraps a mutex) as otherwise the wait method cannot be implemented atomically. A minor point is that std::lock_guard does not support temporary releases of the mutex. Instead std::unique_lock is to be used:

template<typename T>
struct RandomEnginePool {
      using EngineType = T;
      RandomEnginePool(std::size_t size) :
            size(size), nof_free_engines(size),
            inuse(size), engines(size) {
         std::random_device r;
         for (std::size_t i = 0; i < size; ++i) {
            engines[i].seed(r()); inuse[i] = false;
         }
      }
      T& get() {
         std::unique_lock<std::mutex> lock(mutex);
         if (nof_free_engines == 0) {
            cv.wait(lock);
         }
         for (std::size_t i = 0; i < size; ++i) {
            if (!inuse[i]) {
               inuse[i] = true; --nof_free_engines;
               return engines[i];
            }
         }
         assert(false);
      }
      void free(T& engine) {
         {
            std::unique_lock<std::mutex> lock(mutex);
            bool found = false;
            for (std::size_t i = 0; i < size; ++i) {
               if (&engine == &engines[i]) {
                  inuse[i] = false; ++nof_free_engines;
                  found = true; break;
               }
            }
            assert(found);
         }
         cv.notify_one();
      }
   private:
      std::mutex mutex;
      std::condition_variable cv;
      std::size_t size;
      std::size_t nof_free_engines;
      std::vector<bool> inuse;
      std::vector<T> engines;
};

Exercise

Adapt RandomEngineGuard to the new pool and test it.