SPSC锁定自由队列没有原子 [英] SPSC lock free queue without atomics

问题描述

我有一个SPSC队列给我的记录器。

I have below a SPSC queue for my logger.

这当然不是一个通用的SPSC无锁队列。

It is certainly not a general-use SPSC lock-free queue.

然而，考虑到如何使用它，目标架构等一系列假设，以及一些可接受的折衷，我将在下面详细讨论，我的问题是

However, given a bunch of assumptions around how it will be used, target architecture etc, and a number of acceptable tradeoffs, which I go into detail below, my questions is basically, is it safe / does it work?

• 它只能用于 x86_64 结构，因此写入 uint16_t 将是原子。


• 只有生产者更新 code>。


• 只有消费者更新头。


• 生产者读取 head 的旧值，它将看起来像队列中的空间少于现实，这在使用is的上下文中是可接受的限制。 / li>
  
• 如果消费者读取 tail 的旧值，看起来队列中等待的数据少于现实，

• It will only be used on x86_64 architecture, so writes to uint16_t will be atomic.
• Only the producer updates the tail.
• Only the consumer updates the head.
• If the producer reads an old value of head, it will look like there is less space in the queue than reality, which is an acceptable limitation in the context in which is is used.
• If the consumer reads an old value of tail, it will look like there is less data waiting in the queue than reality, again an acceptable limitation.

上述限制是可以接受的，因为：

The limitations above are acceptable because:

• 消费者可能不会立即获得最新的尾，但最终会到达最新的尾排队的数据将被记录。


• 生产者可能不会立即获得最新的头，所以队列看起来更真实是。在我们的负载测试中，我们发现我们记录的数量与队列的大小以及记录器排队的速度，这个限制没有效果 - 队列中总是有空间。

• the consumer may not get the latest tail immediately, but eventually the latest tail will arrive, and queued data will be logged.
• the producer may not get the latest head immediately, so the queue will look more full than it really is. In our load testing we have found the amount we log vs the size of the queue, and the speed at which the logger drains the queue, this limitation has no effect - there is always space in the queue.

最后一点，使用 volatile 是必要的，以防止每个线程只读取的变量优化了。

A final point, the use of volatile is necessary to prevent the variable which each thread only reads from being optimised out.

我的问题：

• 这个逻辑是否正确？


• 队列线程是否安全？


• 是 volatile


• 是否需要 volatile ？

• Is this logic correct?
• Is the queue thread safe?
• Is volatile sufficient?
• Is volatile necessary?

我的队列：

class LogBuffer
{
public:
    bool is_empty() const { return head_ == tail_; }
    bool is_full()  const { return uint16_t(tail_ + 1) == head_; }
    LogLine& head()       { return log_buffer_[head_]; }
    LogLine& tail()       { return log_buffer_[tail_]; }
    void advance_head()   { ++head_; }
    void advance_hail()   { ++tail_; }
private:
    volatile uint16_t tail_ = 0;     // write position
    LogLine log_buffer_[0xffff + 1]; // relies on the uint16_t overflowing
    volatile uint16_t head_ = 0;     // read position
};

推荐答案

？

Is this logic correct?

是的。

队列线程是否安全？

Is the queue thread safe?

否。

挥发性足够吗？是否需要波动？

Is volatile sufficient? Is volatile necessary?

不，两者。 Volatile不是一个神奇的关键字，使任何变量线程安全。您仍然需要对索引使用原子变量或内存屏障，以确保在生成或使用项目时内存排序正确。

No, to both. Volatile is not a magic keyword that makes any variable threadsafe. You still need to use atomic variables or memory barriers for the indexes to ensure memory ordering is correct when you produce or consume an item.

更具体地说，在为队列生成或使用项目之后，您需要发出内存屏障，以确保其他线程将看到更改。许多原子库将在您更新原子变量时为您执行此操作。

To be more specific, after you produce or consume an item for your queue you need to issue a memory barrier to guarantee that other threads will see the changes. Many atomic libraries will do this for you when you update an atomic variable.

另外，使用was_empty而不是is_empty来清楚它的功能。这个调用的结果是一个实例的时间，它可能已经改变了你的时间行动的价值。

As an aside, use "was_empty" instead of "is_empty" to be clear about what it does. The result of this call is one instance in time which may have changed by the time you act on its value.

这篇关于SPSC锁定自由队列没有原子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！