algorithm - 如何使用信号量实现条件变量？

Question

不久前，我在考虑如何相互实现各种同步原语。例如，在 pthread 中，您可以获得互斥锁和条件变量，并且可以从中构建信号量。

在 Windows API（或者至少是旧版本的 Windows API）中有互斥锁和信号量，但没有条件变量。我认为应该可以从互斥锁和信号量中构建条件变量，但对于我的生活，我就是想不出办法。

有谁知道这样做的好结构？

Answer 1

这是来自 Microsoft Research [pdf] 的一篇论文，正是针对这一点的。

Answer 2

给定信号量实现 X 的一种方法是向系统添加一个服务器进程，使用信号量与其通信，并让该进程完成实现 X 的所有艰苦工作。作为一项学术练习，这可能是作弊，但确实如此完成工作，对于客户端进程的不当行为或突然死亡，它可能会更加稳健。

Answer 3

我可能在这里遗漏了一些东西，但似乎有一种比论文中描述的方式更简单的方法来从信号量和锁实现条件。

class Condition {
    sem_t m_sem;
    int   m_waiters;
    int   m_signals;
    pthread_mutex_t *m_mutex;
public:

    Condition(pthread_mutex_t *_mutex){
        sem_init(&this->m_sem,0,0);
        this->m_waiters = 0;
        this->m_signals = 0;
        this->m_mutex = _mutex;
    }
    ~Condition(){}
    void wait();
    void signal();
    void broadcast();
};

void Condition::wait() {
    this->m_waiters++;
    pthread_mutex_unlock(this->m_mutex);
    sem_wait(&this->m_sem);
    pthread_mutex_lock(this->m_mutex);
    this->m_waiters--;
    this->m_signals--;
}

void Condition::signal() {
    pthread_mutex_lock(this->m_mutex);
    if (this->m_waiters && (this->m_waiters > this->m_signals)) {
        sem_post(&this->m_sem);
        this->m_signals++;
    }
    pthread_mutex_unlock(this->m_mutex);
}