c++ - 无锁 "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

您正在实现的构造是一个计数锁，或 counting semaphore .使用具有 trylock 版本的库中的一个，而不是滚动您自己的版本，这样您可以获得优化的操作系统支持的 sleep /唤醒。或者，如果 trylock(又名 take)失败，您是否总是有有用的工作要做？

请注意，您可以在实现自己的锁时避免使用任何传统锁，但“无锁”是一个技术术语，其含义不同于无锁。几乎根据定义，消费者不可能是 lock-free在计算机科学意义上，因为如果生产者线程被阻塞，它可能会永远等待。相关:Lock-free Progress Guarantees

---

CAS 很好。如果您的函数在纯负载(通常是 memory_order_relaxed)下看到计数器已经为 0，请确保您的函数根本不运行 compare_exchange_weak。您不希望您的 CPU 在其他线程尝试递增该位置时敲打该位置，这样您的线程将看到一个非零值。

另一种选择是有符号计数器，并将比较更改为>= 0。检查 fetch_add(-1) 的结果是否超调，如果是则更正它。 (将计数器视为暂时为负的线程只是将其“锁定”)。但这通常并不比 CAS 重试循环好；失败的 CAS 很少见，除非争用非常高。用于纠正超调的额外原子操作的成本可能与 CAS 重试成本一样多(或更多)。