使用互斥操作和原语实现信号量

Question

前段时间接受采访，被要求仅使用互斥操作和原语来实现 Semaphore（他允许将 int 视为原子）。我在下面提供了解决方案。他不喜欢忙/等待部分—— while (count >= size) {} 并要求通过使用更多原始类型和互斥锁来实现锁定。我没有设法提出改进的解决方案。有什么想法可以做到吗？

 struct Semaphore {
int size;
atomic<int> count;
mutex updateMutex;

Semaphore(int n) : size(n) { count.store(0); }

void aquire() {
    while (1) {
        while (count >= size) {}
        updateMutex.lock();
        if (count >= size) {
            updateMutex.unlock();
            continue;
        }
        ++count;
        updateMutex.unlock();
        break;
    }
}

void release() {
    updateMutex.lock();
    if (count > 0) {
        --count;
    } // else log err
    updateMutex.unlock();
}
};

原文由 user2890398 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我敢打赌，如果没有 仅使用互斥锁 的繁忙循环，这是不可能实现的。

如果不是忙循环，则必须在某个地方阻塞。您拥有的唯一阻塞原语是互斥体。因此，当信号量计数器为零时，您必须阻止某些互斥锁。您 只能 由该互斥锁的单一所有者唤醒。但是，只要 任意线程 向信号量返回计数器，您就 应该 醒来。

现在，如果允许使用条件变量，那就完全不同了。

原文由 chill 发布，翻译遵循 CC BY-SA 3.0 许可协议