无锁"decrement if not zero"

Question

我目前正在重新发明C 中线池的轮子。除了以下构造的多个实例：

，我已经从代码中删除了几乎所有锁。

std::atomic_size_t counter;
void produce() {
    ++counter;
}
void try_consume() {
    if (counter != 0) {
        --counter;
        // ...
    }
    else {
        // ...
    }
}

所以，我需要此功能的无线安全锁定版本：

bool take(std::atomic_size_t& value) {
    if (value != 0) {
        --value;
        return true;
    }
    return false;
}

有一个我知道的解决方案：使用boost::lockfree::queue<std::monostate>，其中pop()在其中完成工作。有更好/更快的解决方案吗？

Answer 1

您要实现的结构是计数锁定或计数信号量。使用具有trylock版本而不是滚动的库中的一个，以便获得优化的OS支持的睡眠/唤醒。或者，如果trylock（又称take）失败，您总是有有用的工作？

请注意，您可以在实施自己的时避免使用任何传统锁，但是"免费锁定"是一个技术术语，其含义与无锁定。从定义上讲，消费者几乎不能在计算机科学意义上没有锁定，因为如果生产者线程被阻止，它可能会永远等待。相关：无锁的进度保证

---

cas很好。只需确保您的函数完全不运行compare_exchange_weak，如果它已经看到纯负载的计数器（通常使用memory_order_relaxed）。当其他线程试图将其递增时，您不希望在位置上敲击CPU，以便您的线程会看到非零值。

另一个选项是签名计数器，然后更改与>= 0相比。检查fetch_add(-1)的结果是否过时，如果是这样，请对其进行纠正。（将计数器视为暂时负面的线程只是将其视为"锁定"）。但这通常不比CAS重试循环更好。除非竞争非常高，否则失败的CAS是罕见的。纠正额外冲动的额外原子操作可能比CAS重新恢复大约（或更多）。