无锁的“如果不为零则递减". [英] Lock-free "decrement if not zero"

问题描述

我目前正在重塑C ++中的线程池.除了以下构造的多个实例之外，我几乎消除了代码中的所有锁:

I'm currently reinventing the wheel of a thread pool in C++. I've eliminated almost all locks from the code, except for multiple instances of the following construct:

std::atomic_size_t counter;

void produce() {
    ++counter;
}

void try_consume() {
    if (counter != 0) {
        --counter;
        // ...
    }
    else {
        // ...
    }
}

因此，我需要此函数的线程安全无锁版本:

So, I need a thread-safe lock-free version of this function:

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

我知道一个解决方案:使用boost::lockfree::queue<std::monostate>，其中pop()可以完成任务.有没有更好/更快的解决方案?

There is one solution that I know of: use boost::lockfree::queue<std::monostate>, where pop() does the job. Is there any better/faster solution?

推荐答案

您正在实现的构造是计数锁定，或

The construct you're implementing is a counting lock, or counting semaphore. Use one from a library that has a trylock version instead of rolling your own, so you can get optimized OS-supported sleep / wakeup. Or do you always have useful work to do if the trylock (aka take) fails?

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

Note that you can avoid using any traditional locks while implementing your own, but "lock free" is a technical term with a different meaning than lockless. A consumer almost by definition can't be lock-free in the computer-science sense, because it can be stuck waiting forever if the producer thread(s) are blocked. Related: Lock-free Progress Guarantees

CAS很好.只要确保函数在纯负载下(通常是memory_order_relaxed)已经看到计数器已经为0的情况下，就完全不要运行compare_exchange_weak.您不希望CPU在其他线程试图递增该位置时对其进行锤击，以使您的线程将看到非零值.

CAS is good. Just make sure that your function doesn't run compare_exchange_weak at all if it sees the counter already 0 with a pure load (typically with memory_order_relaxed). You don't want your CPU hammering on the location while other threads are trying to increment it so your thread will see a non-zero value.

另一个选项是带符号计数器，并将比较值更改为>= 0.检查fetch_add(-1)结果中是否存在过冲，如果是，则对其进行更正. (将计数器视为暂时为负的线程只会看到它被锁定").但这通常不比CAS重试循环更好.除非竞争非常严重，否则失败的CAS很少发生.而且纠正超调的额外原子操作可能要比CAS重试花费大约(或更多).

Another option is a signed counter, and change the compare to >= 0. Check for overshoot in the result of fetch_add(-1), and if so correct it. (Threads that see the counter as temporarily negative just see it "locked"). But this is typically not better than a CAS retry loop; failed CAS is rare unless contention is very high. And extra atomic ops to correct overshoot will probably cost about as much (or more) than CAS retries.

这篇关于无锁的“如果不为零则递减".的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！