Non-blocking semaphores in C++11?

Question

A number of questions on this site deal with the lack of a semaphore object in the multi-threading support introduced in C++11. Many people suggested implementing semaphores using mutexes or condition variables or a combination of both.

However, none of these approaches allows to increment and decrement a semaphore while guaranteeing that the calling thread is not blocked, since usually a lock must be acquired before reading the semaphore's value. The POSIX semaphore for instance has the functions sem_post() and sem_trywait(), both of which are non-blocking.

Is it possible to implement a non-blocking semaphore with the C++11 multi-threading support only? Or am I necessarily required to use an OS-dependent library for this? If so, why does the C++11 revision not include a semaphore object?

A similar question has not been answered in 3 years. (Note: I believe the question I am asking is much broader though, there are certainly other uses for a non-blocking semaphore object aside from a producer/consumer. If despite this someone believes my question is a duplicate, then please tell me how I can bring back attention to the old question since this is still an open issue.)

Answer 1

I don't see a problem to implement a semaphore. Using C++11 atomics and mutextes it should be possible.

class Semaphore
{
private:
    std::atomic<int> count_;

public:
    Semaphore() :
        count_(0) // Initialized as locked.
    {

    }
    void notify() {
        count_++;
    }

    void wait() {
        while(!try_wait()) {
            //Spin Locking
        }
    }

    bool try_wait() {
        int count = count_;
        if(count) {
            return count_.compare_exchange_strong(count, count - 1);
        } else {
            return false;
        }
    }
};

Here is a little example of the usage:

#include <iostream>
#include "Semaphore.hpp"
#include <thread>
#include <vector>

Semaphore sem;
int counter;

void run(int threadIdx) {
    while(!sem.try_wait()) {
        std::this_thread::sleep_for(std::chrono::milliseconds(1));
    }
    //Alternative use wait
    //sem.wait()
    std::cout << "Thread " << threadIdx << " enter critical section" << std::endl;
    counter++;
    std::cout << "Thread " << threadIdx << " incresed counter to " << counter << std::endl;

    // Do work;
    std::this_thread::sleep_for(std::chrono::milliseconds(30));

    std::cout << "Thread " << threadIdx << " leave critical section" << std::endl;
    sem.notify();
}
int main() {
    std::vector<std::thread> threads;
    for(int i = 0; i < 15; i++) {
        threads.push_back(std::thread(run, i));
    }

    sem.notify();


    for(auto& t : threads) {
        t.join();
    }
    std::cout << "Terminate main." << std::endl;
    return 0;
}

Of course, the wait is a blocking operation. But notify and try_wait are both non-blocking, if the compare and exchange operation is non blocking (can be checked).