How can I achieve something similar to a semaphore using boost in c++? [duplicate]

Question

I noticed that boost does not seem to support semaphores. What's the easiest way to achieve a similar effect?

Iridescence

Could you be more specific about what behavior you're looking for? Given that people have come up with about 14 different types of semaphores. – Dyaus

Right now, something that will let me, for example, solve the dining philosopher's problem (with 5 philosophers) by limiting the number of people dining to at most 4. With semaphores, I could just set an initial value of 4 and have each philosopher wait on the semaphore and signal when done. – Iridescence

Answer 1

You either need Boost Interprocess semaphore or Boost Thread synchronization primitives.

Mutex/Lock and condition are primitives that are commonly used to synchronize access to shared resources across multiple threads of a single process. There are exclusive, readers-writer and recursive/reentrant types of mutexes. Mutex, in other words, is an exclusive lock. Condition is used to achieve atomicity when you need to unlock the mutex and wait for object to change. When you start waiting on a condition, it unlocks the mutex and guarantees than unlock + call to wait is atomic and no other threads can modify a resource between those two operations.

Semaphore, on another case, is a mix of condition and mutex, and is used for exactly the same purpose but to synchronize access across processes.

See Mutex vs Semaphore.

There is also such thing as non-blocking/lock-free synchronization that is becoming very popular these days. I personally use it in high-frequency trading applications when amount of data is relatively very large and low latency does matter a lot.

In your case, I assume 5 philosophers can have a dinner inside a single process with 5 threads. In that case you have to use a mutex, not a semaphore. You might or might not use condition though. It depends on what exactly and how exactly you want to implement that dining procedure.

I am not sure how to describe it better as I will end up writing a book about it. So I'd recommend you find some book that is already written to understand the basic concepts. Once you know basics, you can use APIs/libraries/frameworks like POSIX threads, Boost Interprocess or Thread, ACE or even non-blocking algorithms to achieve what you want.

Good luck!

Lamdin

So, just out of curiosity, the name "interprocess semaphore" suggests it is meant to be shared between processes rather than threads. Does this imply that it costs additional overhead above what a introprocess semaphore would theoretically use? I'm not sure how to easily use thread conditions for applications such as the toy application mentioned in my comment on the question. – Iridescence

@jonderry: OK, I thought I can get away with a simple answer, but you got me. I've started replying in a comment but it was too large with lots of links so I ended up editing my answer. Please see updated version. Thanks. – Lamdin

Thanks, Vlad. It is true that the dining philosophers problem uses mutexes on the adjacent forks, but if you don't add something more, you get deadlock. One standard way to solve this is to only allow 4 philosophers to dine at once so one can always make progress. The natural way to achieve this is with a semaphore. – Iridescence

@jonderry: Semaphore is an equivalent of mutex + condition inside the process. Look at the code in Doug's answer, he've got an idea. I'd recommend you read some good book on thread. – Lamdin

It really is a shame that pthreads only provides mutexes and condition variables. Yes, they are a complete set of primitives onto which other primitives can be built, but they are not the most efficient way to build those primitives. Counting semaphore and resettable event are two very common use cases. – Amend

The difference between Semaphore and Mutex is not that Semaphore is interprocess sync while is not (your answer kind of implies this). A Mutex is effectively the same thing as a binary Semaphore (count 1). Also nothing stops you from implementing interprocess Mutexes (in fact boost provides an interprocess Mutex) – Selfsacrifice

@Selfsacrifice There are significant differences between a mutex and binary semaphore. In particular, a mutex can only be unlocked by the thread that locked it. This complicates its use for signaling from one thread to another because you cannot setup the mutex in the desired (locked) state before starting the signaling thread. You generally have to combine it with other primitives like condition variables to use it as a semaphore. – Ladin

Both the boost interprocess_semaphore and the C++20 semaphore implementation in libstdc++ use POSIX semaphores for Linux. So if you don't have access to C++20 yet I would not be concerned about interprocess_semaphore having more overhead than a thread-based synchronization primitive - it is likely more efficient than a mutex+condition variable. – Ladin

Answer 2

This is one way of implementing a very simple semaphore using Boost.Thread. It's an inter-thread semaphore, not an interprocess one. No warranties implied, etc. - I haven't even compiled the code. It illustrates how mutexes and condition variables interact, and assumes a reasonably recent version of Boost.

Notice how the mutex and condition variable are "paired" - threads must have a lock to the mutex to wait on the condition variable, and re-acquire the lock when they're woken up. Also, the code that changes the data needs to explicitly wake up other code that might be waiting. This means that the mutex, condition variable, data, and the condition(s) that cause the wakeup, are all closely coupled. The tight coupling also means that the data, mutex, and condition variable should be encapsulated if possible - any external modification can break the code in strange ways, including deadlocks, missed wakeups, and other strange bugs.

All this is really meant as a complement to Vlad Lazarenko's answer - understanding the theory and principles are at least as important as having "working" code, in multi-threaded programming.

#include <boost/thread/condition_variable.hpp>
#include <boost/thread/mutex.hpp>    
#include <boost/thread/lock_types.hpp>


class semaphore
{
    //The current semaphore count.
    unsigned int count_;

    //mutex_ protects count_.
    //Any code that reads or writes the count_ data must hold a lock on
    //the mutex.
    boost::mutex mutex_;

    //Code that increments count_ must notify the condition variable.
    boost::condition_variable condition_;

public:
    explicit semaphore(unsigned int initial_count) 
       : count_(initial_count),
         mutex_(), 
         condition_()
    {
    }

    unsigned int get_count() //for debugging/testing only
    {
        //The "lock" object locks the mutex when it's constructed,
        //and unlocks it when it's destroyed.
        boost::unique_lock<boost::mutex> lock(mutex_);
        return count_;
    }

    void signal() //called "release" in Java
    {
        boost::unique_lock<boost::mutex> lock(mutex_);

        ++count_;

        //Wake up any waiting threads. 
        //Always do this, even if count_ wasn't 0 on entry. 
        //Otherwise, we might not wake up enough waiting threads if we 
        //get a number of signal() calls in a row.
        condition_.notify_one(); 
    }

    void wait() //called "acquire" in Java
    {
        boost::unique_lock<boost::mutex> lock(mutex_);
        while (count_ == 0)
        {
             condition_.wait(lock);
        }
        --count_;
    }

};

Cestar

Works like a charm. Too bad this is no longer part of Boost itself. – Nitride

+ 1 for the code. Are there any point to the mutex in get count? The count will be "old" when received anyway, won't it? – Ainslee

Correct, the count will be old when returned. Getting the count of a semaphore for reasons other than debugging is likely a bug in your program. – Amend

Dough could you please use this in an example. I am confused on how to use it and how it allows access to multiple threads at a time – Flocculate

Answer 3

I made a semaphore class compatible with boosts TimedLockable concept, so it can be used with locks like boost::unique_lock<semaphore>. Its not a semaphore in a classical definition of one, but can be used as one. Still, hope it can be useful for someone.

Its somehow tested, but there is great possibility, that I did something wrong. Would be great if someone could prove it correctness.

class semaphore
{
private:
   semaphore(const semaphore & other);
   semaphore & operator = (const semaphore & other);

   boost::mutex _mutex;
   boost::condition_variable _condVar;
   size_t _count;

   class wait_predicate
   {
   private:
      const size_t & _countRef;
   public:
      wait_predicate(const size_t & countRef) : _countRef(countRef) {}
      bool operator()() { return _countRef > 0; }
   };

   // must be used inside a locked scope!
   inline wait_predicate getWaitPredicate() const 
   {
      return wait_predicate(_count);
   }

public:
   semaphore(size_t size): _count(size)
   {}

   void lock()
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      _condVar.wait(local_lock, getWaitPredicate());
      _count--;
   }

   void unlock()
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      _count++;
      _condVar.notify_one();
   }

   bool try_lock()
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      if (0 == _count)
         return false;

      _count--;
      return true;
   }

   template <typename Duration>
   bool try_lock_for(const Duration & duration)
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      if (!_condVar.wait_for(local_lock, duration, getWaitPredicate()))
         return false;

      _count--;
      return true;
   }

   template <class TimePoint>
   bool try_lock_until(const TimePoint & timePoint)
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      if (!_condVar.wait_until(local_lock, timePoint, getWaitPredicate()))
         return false;

      _count--;
      return true;
   }

   template <class WaitCriteria>
   bool timed_lock(const WaitCriteria & criteria)
   {
      boost::unique_lock<boost::mutex> local_lock(_mutex);
      if (!_condVar.timed_wait(local_lock, criteria, getWaitPredicate()))
         return false;

      _count--;
      return true;
   }
};

Lanni