使用互斥操作和基元实现信号量

Question

前段时间进行了一次采访，并被要求仅使用互斥锁操作和基元来实现信号量（他允许将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();
}
};

Answer 1

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

如果不是忙循环，你必须在某处阻塞。您拥有的唯一阻塞原语是互斥锁。因此，当信号量计数器为零时，您必须阻塞某些互斥锁。你可以只通过互斥的单一所有者被唤醒。但是， 只要任意线程向信号量返回计数器，您就应该唤醒。

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