реализовать семафор без мьютекса

есть наивная реализация семафора...

#include <cerrno>
#include <cstring>

#include <cstdint>
#include <mutex>
#include <atomic>
#include <condition_variable>
#include <exception>
#include <string>
#include <iostream>
#include <thread>

extern int errno;

struct semaphore_exception : public std::exception
{
    semaphore_exception(const char* msg) noexcept {}
};


//! Simple semaphore realization with std::mutex and std::condional_variable
class simple_semaphore
{
public:
    simple_semaphore(std::uint32_t scount, std::uint32_t timeout_msec)
    : m_limit(scount)
    , m_waiters(0u)
    {
        if (m_limit == 0u)
            throw semaphore_exception("Semaphore count must be greather than 0");

        m_timeout_msec = std::chrono::milliseconds(timeout_msec);
    }

    void wait(int id)
    {

        std::unique_lock< decltype(m_mutex) > lk(m_mutex);
        if (!m_cond.wait_for(lk, m_timeout_msec, [=](){ return m_waiters.load() < m_limit; }))
        {
            std::cout << "Timeout in milliseconds: " << std::chrono::duration_cast< std::chrono::milliseconds >(m_timeout_msec).count() << " was occured\n";
            return;
        }

        m_waiters++;
    }

    void post(int id)
    {
        std::unique_lock< decltype(m_mutex) > lk(m_mutex);
        if (m_waiters == 0u)
            return;

        m_waiters--;
        m_cond.notify_one();
    }

private:
    const std::uint32_t m_limit;
    std::atomic< std::uint32_t > m_waiters;
    std::mutex m_mutex;
    std::condition_variable m_cond;
    std::chrono::milliseconds m_timeout_msec;
};


int main(int argc, char *argv[])
{
    //4 simultaneous worker threads, 1 - waited
    simple_semaphore sem{4, 4000};
    auto locker = [&sem](int id){
        sem.wait(id);
        std::cout << "sleep id: " << id << "\n";
        std::this_thread::sleep_for(std::chrono::seconds(3u));
        sem.post(id);
    };
    std::thread thrd1(locker, 1), thrd2(locker, 2), thrd3(locker, 3), thrd4(locker, 4), thrd5(locker, 5);
    thrd1.join(); thrd2.join(); thrd3.join(); thrd4.join(); thrd5.join();
    return 0;
}

Вроде работает. Но есть два вопроса:

  1. есть ли грубые ошибки в реализации?
  2. можно ли реализовать семафору без мьютекса, чисто только на атомарном счетчике и condition variable? Или даже без condition variable? Изучал вопрос какое-то время, но код с использованием чистой магии атомарных операций слишком сложен и квалификации недостаточно, чтобы понять(особенно когда что-то про когерентность кэшей и мультипроцессорность). Можно ли как-то "на пальцах", для тех кто в танке, так сказать?

Ответы (2 шт):

Автор решения: Fat-Zer

есть ли грубые ошибки в реализации?

Прям грубых ошибок на беглый взгляд я не вижу, но реализация странная, что её сложно назвать «семафором»:

  • Во-первых, он перевёрнут: wait() должен уменьшать значение счётчика, а post() — увеличивать.
  • При создании семафора задаётся его начальное значение, а не «лимит»; и post() может увеличивать это значение больше изначального.

А также более мелкие замечания:

  • timeout_msec, скорей всего, следует передаваться в качестве опционально параметра в wait() (или аналогичную функцию). Задавать его при создании семафора — крайне странно.
  • если wait() может завершиться ошибкой, то у вызывающего должна быть возможность проверить это.
  • Параметры post() и wait() не используются (обычно они задают, на сколько нужно увеличить/уменьшить значение семафора).
  • Если значение семафора подходящее, то при использовании атомарных переменных его можно изменить без захвата блокировки (надо делать аккуратно, с применением CAS-операций, см. std::atomic<T>::compare_exchange_weak/_strong ).

можно ли реализовать семафору без мьютекса, чисто только на атомарном счетчике и condition variable?

Без мьютекса условная переменная не работает.

Или даже без condition variable?

В стандартном c++17 условная переменная — единственный способ остановить поток и дождаться наступления события в другой нитке, так что в качестве альтернативы только:

  • использовать активное ожидание на процессоре
  • воспользоваться средствами ОС (по сути реализовать примитив аналогичный условной переменной)
→ Ссылка
Автор решения: Alex Guteniev

В c++20 можно ожидать на атомарной переменной - std::atomic<T>::wait. Ожидание на атомарной переменной не требует захвата мьютекса, поэтому требует меньшего количества операций, в результате такой способ реализации своих примитивов синхронизации будет эффективнее, чем используя условную переменную.

В c++20 есть стандартные counting_semaphore и binary_semaphore. Реализации могут использовать std::atomic<T>::wait, или примитив, лежащий в его основе, или, если ОС предоставляет эффективный готовый семафор, то примитив ОС.

→ Ссылка