10

This is a follow-up to Can C++11 condition_variables be used to synchronize processes?.

Can std::condition_variable objects be used as counting semaphores?

Methinks not because the object seems bound to a std::mutex, which implies it can only be used as a binary semaphore. I've looked online, including here, here, and here, but can't find reference or example of using these objects as counting semaphores.

Community
  • 1
  • 1
StoneThrow
  • 5,314
  • 4
  • 44
  • 86
  • 1
    Why are you looking for a semaphore-like object? Reading the above text makes me think that you might have a requirement to build a program for a single core machine and would like to use that semaphore mechanism OR you have really old code that used wrappers around the OS semaphore and you are looking to preserve that behavior. Is that kinda close? – AhiyaHiya Oct 31 '16 at 04:27
  • 1
    @AhiyaHiya: This is an academic exercise for personal learning. I'm writing code for fun, and am trying to migrate from posix-based synchronization mechanisms (pthread_mutex_t, sem_t) to C++11-native mechanisms. I saw that C++11 provides `std::mutex` then was puzzled why there's no semaphore. Some further reading led me to learn that `std::condition_variable` is used to achieve semi-semaphore functionality, but I'm trying to learn/understand its capabilities and limitations. It seems it's not fully equivalent to semaphores, but I'm not sure yet...still studying. – StoneThrow Oct 31 '16 at 04:38
  • 1
    If you are studying and would like to see some well grounded multi-core concurrent/parallel programming guides, you should review Herb Shutter's Pillars of Concurrent Programming in his "Effective Concurrency" series: https://herbsutter.com/category/effective-concurrency/ – AhiyaHiya Oct 31 '16 at 04:45

1 Answers1

6

Yes.

struct counting_sem {
  counting_sem(std::ptrdiff_t init=0):count(init) {}
  // remove in C++17:
  counting_sem(counting_sem&& src) {
    auto l = src.lock(); // maybe drop, as src is supposed to be dead
    count = src.count;
  }
  counting_sem& operator=(counting_sem&& src) = delete;
  void take( std::size_t N=1 ) {
    if (N==0) return;
    auto l = lock();
    cv.wait(l, [&]{
      if (count > 0 && count < (std::ptrdiff_t)N) {
        N -= count;
        count = 0;
      } else if (count >= (std::ptrdiff_t)N) {
        count -= N;
        N = 0;
      }
      return N == 0;
    });
  }
  void give( std::size_t N=1 ) {
    if (N==0) return;
    {
      auto l = lock();
      count += N;
    }
    cv.notify_all();
  }
  // reduce the count without waiting for it
  void reduce(std::size_t N=1) {
    if (N==0) return;
    auto l = lock();
    count -= N;
  }
private:
  std::mutex m;
  std::condition_variable cv;
  std::ptrdiff_t count;

  auto lock() {
    return std::unique_lock<std::mutex>(m);
  }
  auto unlocked() {
    return std::unique_lock<std::mutex>(m, std::defer_lock_t{});
  }
};

Code not tested or compiled, but the design is sound.

take(7) is not equivalent to for(repeat 7 times) take(): instead, it takes as much as it can then blocks if that wasn't enough.

Modifying so that it doesn't take anything until there is enough is easy:

      if (count >= (std::ptrdiff_t)N) {
        count -= N;
        N = 0;
      }
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • I get the gist of your code example, thank you. So the impression I get is that `std::condition_variable` isn't really _equivalent_ to a semaphore, but it can be used to create an object functionally equivalent to a semaphore. I wonder why the C++ standards body went this way instead of outright providing plain old semaphores...after all, they're foundational computer science objects. – StoneThrow Nov 01 '16 at 04:23
  • @stone because condition variables map efficiently to hardware (I assume) and permit much more than semaphores (the message above is the integer count being <= 0: but you can use it to relay almost any message: nodes in a queue, a future is ready, etc). Abstract what the metal provides in an easier portable wrapper. – Yakk - Adam Nevraumont Nov 01 '16 at 04:47
  • @Yakk _It does not take all 7 "atomically"._ Er... But it does... Perhaps you meant `if` instead of `while`. With a `while`, the predicate will be called once and if `count` is higher than `N`, it will loop `count` times and return `true`. – screwnut Nov 01 '16 at 19:56
  • @screwnut Well, sort of. Suppose you want 7, and someone gives 4. It will take 4 and then give up, still wanting 3. In the "atomic" case, it will see only 4 are there, and refuse to take any. – Yakk - Adam Nevraumont Nov 01 '16 at 20:10
  • @Yakk, I guess I'm just confused by this statement: `for(repeat 7 times) take()` which, to me, implied that `cv` will be locked and unlocked N times but it doesn't. Either way, the `while` loop is truly pointless. Both "wait-until-N" and "take-until-N" scenarios should be done with an `if`. – screwnut Nov 02 '16 at 19:03
  • 1
    @screwnut The loop was there because doing the math is ... tricky to get exactly right. I tried to fix it so there is no loop, but I am not nearly as convinced it is correct. – Yakk - Adam Nevraumont Nov 02 '16 at 20:27