无锁 "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() 可以完成这项工作。有什么better/faster解决方案吗？

Answer 1

您正在实施的构造是一个计数锁，或 counting semaphore。使用具有 trylock 版本的库中的一个，而不是滚动你自己的版本，这样你就可以获得优化的 OS 支持的睡眠/唤醒。或者，如果 trylock（又名 take）失败，您总是有有用的工作要做吗？

请注意，您可以在实现自己的锁时避免使用任何传统锁，但 "lock free" 是一个技术术语，其含义不同于无锁。几乎根据定义，消费者不能 lock-free in the computer-science sense, because it can be stuck waiting forever if the producer thread(s) are blocked. Related:

CAS 很好。只要确保您的函数在纯负载（通常为 memory_order_relaxed）下看到计数器已经为 0 时根本不会运行 compare_exchange_weak。您不希望您的 CPU 在其他线程试图增加它时敲击该位置，这样您的线程将看到一个非零值。

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

无锁 "decrement if not zero"

Lock-free "decrement if not zero"

c++

thread-safety

atomic

lock-free