Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Non-blocking semaphores in C++11?

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.)

like image 599
kassiopeia Avatar asked Feb 16 '17 09:02

kassiopeia


People also ask

What is blocking semaphore?

a blocking semaphore is initialised to zero rather than one. You set the initial number of permits. If you set permits to 1 ( new Semaphore(1) ), you can acquire once before you release . If the value is > 0 , some acquire s may happen before release s.

What is difference between semaphore and mutex?

A Mutex is different than a semaphore as it is a locking mechanism while a semaphore is a signalling mechanism. A binary semaphore can be used as a Mutex but a Mutex can never be used as a semaphore.

What are the two kinds of semaphores?

Critical Semaphores and System Semaphores.

Does C++ support semaphore?

Counting Semaphores in C++20. C++20 supports a std::binary_semaphore , which is an alias for a std::counting_semaphore<1> . In this case, the least maximal value is 1. std::binary_semaphores can be used to implement locks.


1 Answers

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).

like image 151
OutOfBound Avatar answered Sep 24 '22 12:09

OutOfBound