c++ - 无锁进度保证

Question

有趣的是，我发现很多程序员错误地认为“无锁”只是意味着“没有互斥锁的并发编程”。通常，还有一个相关的误解，即编写无锁代码的目的是为了更好的并发性能。当然，无锁的正确定义实际上是关于进度保证的。无锁算法保证至少一个线程能够向前推进，而不管其他线程在做什么。

这意味着无锁算法永远不会有一个线程依赖另一个线程才能继续的代码。例如，无锁代码不能出现线程 A 设置标志，然后线程 B 在等待线程 A 取消设置标志的同时不断循环的情况。像这样的代码基本上实现了一个锁(或者我称之为变相的互斥锁)。

然而，其他情况更微妙，在某些情况下，老实说，我无法真正判断算法是否符合无锁条件，因为“取得进步”的概念有时对我来说是主观的。

一个这样的案例是在(备受推崇的，afaik)并发库中，liblfds .我正在研究 liblfds 中多生产者/多消费者有界队列的实现 - 实现非常简单，但我无法确定它是否应该符合无锁条件。

相关算法在 lfds711_queue_bmm_enqueue.c . Liblfds 使用自定义原子和内存屏障，但算法很简单，我可以用一段左右的时间来描述。

队列本身是一个有界连续数组(环形缓冲区)。有一个共享read_index和 write_index .队列中的每个槽都包含一个用户数据字段和一个 sequence_number值，这基本上就像一个纪元计数器。 (这避免了 ABA 问题)。

PUSH算法如下:

以原子方式加载 write_index

尝试在 write_index % queue_size 处保留队列中的一个插槽使用尝试设置 write_index 的 CompareAndSwap 循环至 write_index + 1 .

如果 CompareAndSwap 成功，则将用户数据复制到
预留插槽。

最后，更新 sequence_index在
使其等于 write_index + 1 .

实际的源代码使用自定义原子和内存屏障，因此为了更清楚地了解这个算法，我将它简要地翻译成(未经测试的)标准 C++ 原子以获得更好的可读性，如下所示:

bool mcmp_queue::enqueue(void* data)
{
    int write_index = m_write_index.load(std::memory_order_relaxed);

    for (;;)
    {
        slot& s = m_slots[write_index % m_num_slots];
        int sequence_number = s.sequence_number.load(std::memory_order_acquire);
        int difference = sequence_number - write_index;

        if (difference == 0)
        {
            if (m_write_index.compare_exchange_weak(
                write_index,
                write_index + 1,
                std::memory_order_acq_rel
            ))
            {
                break;
            }
        }

        if (difference < 0) return false; // queue is full
    }

    // Copy user-data and update sequence number
    //
    s.user_data = data;
    s.sequence_number.store(write_index + 1, std::memory_order_release);
    return true;
}

现在，一个线程想要从 read_index 处的插槽中弹出一个元素。将无法这样做，直到它观察到插槽的 sequence_number等于 read_index + 1 .

好的，所以这里没有互斥体，而且该算法可能表现良好(它只是用于 PUSH 和 POP 的单个 CAS)，但这是无锁的吗？我不清楚的原因是因为如果观察到队列已满或空，PUSH 或 POP 可能总是失败，那么“取得进展”的定义似乎很模糊。

但对我来说有问题的是 PUSH 算法本质上保留了一个插槽，这意味着在推送线程开始更新序列号之前，该插槽永远不会被 POP 处理。这意味着想要弹出值的 POP 线程取决于完成操作的 PUSH 线程。否则，POP 线程将始终返回 false因为它认为队列是空的。我觉得这是否真的属于“取得进展”的定义是值得商榷的。

一般来说，真正的无锁算法涉及一个阶段，在这个阶段，一个被抢占的线程实际上试图协助另一个线程完成一个操作。因此，为了真正实现无锁，我认为观察正在进行的 PUSH 的 POP 线程实际上需要尝试完成 PUSH，然后才执行原始 POP 操作。如果 POP 线程在 PUSH 进行时简单地返回队列为 EMPTY，则 POP 线程基本上被阻塞，直到 PUSH 线程完成操作。如果 PUSH 线程死亡，或休眠 1,000 年，或以其他方式被安排被遗忘，则 POP 线程除了不断报告队列为空外，什么也做不了。

那么这符合无锁的定义吗？从一个角度来看，您可以争辩说 POP 线程总是可以取得进展，因为它总是可以报告队列为空(我猜这至少是某种形式的进展。)但对我来说，这并没有真正取得进展，因为观察到队列为空的唯一原因是我们被并发 PUSH 操作阻塞。

所以， 我的问题是 : 这个算法真的是无锁的吗？或者索引预留系统基本上是变相的互斥锁？

Answer 1

这个队列数据结构是不是 我认为最合理的定义是严格无锁的。该定义类似于:

A structure is lock-free if only if any thread can be indefinitely suspended at any point while still leaving the structure usable by the remaining threads.

当然，这意味着对可用的合适定义，但对于大多数结构来说，这相当简单:结构应该继续遵守其契约，并允许按预期插入和删除元素。

在这种情况下，一个线程成功地增加了 m_write_increment ，但还没有写 s.sequence_number使容器处于很快将无法使用的状态。如果这样的线程被杀死，容器最终会向 push 报告“满”和“空”。和 pop分别违反了固定大小队列的约定。

这里有一个隐藏的互斥锁( m_write_index 和相关联的 s.sequence_number 的组合) - 但它基本上就像一个每个元素的互斥锁。因此，只有在您进行循环并且新的作者试图获取互斥锁时，写入者才会发现失败，但实际上，所有后续写入者实际上都未能将其元素插入队列，因为没有读者会看到它。

现在这并不意味着这是一个 坏 并发队列的实现。对于某些用途，它可能表现得好像它是无锁的。比如这个结构可能有大部分 有用的性能属性 一个真正的无锁结构，但同时它缺少一些 有用的正确性属性 .基本上，无锁一词通常意味着一大堆属性，其中只有一个子集对于任何特定用途通常很重要。让我们一一看看它们，看看这个结构是如何做的。我们将它们大致分为性能和功能类别。

表现

无与伦比的性能

无竞争或“最佳情况”的性能对许多结构都很重要。虽然您需要一个并发结构来确保正确性，但您通常仍会尝试设计您的应用程序，以便将争用保持在最低限度，因此无竞争成本通常很重要。一些无锁结构在这里有所帮助，通过减少无竞争快速路径中昂贵的原子操作的数量，或避免 syscall .

这个队列实现在这里做了一个合理的工作:只有一个“绝对昂贵”的操作: compare_exchange_weak ，以及一些可能昂贵的操作( memory_order_acquire 加载和 memory_order_release 存储)1，其他开销很小。

这与 std::mutex 类似这意味着类似于锁定的原子操作和解锁的另一个原子操作，实际上在 Linux 上，pthread 调用也具有不可忽略的开销。

所以我希望这个队列在无竞争的快速路径中表现得相当好。

竞争性能

无锁结构的一个优点是，当结构竞争激烈时，它们通常允许更好的扩展。这不一定是一个固有的优势:一些具有多个锁或读写锁的基于锁的结构可能表现出匹配或超过某些无锁方法的扩展，但通常情况下，无锁结构表现出更好的扩展性一个简单的一键通规则的替代方案。

这个队列在这方面表现合理。 m_write_index变量由所有读者自动更新，这将是一个争论点，但只要底层硬件 CAS 实现是合理的，行为应该是合理的。

请注意，队列通常是一种相当差的并发结构，因为插入和删除都发生在相同的位置(头部和尾部)，因此竞争是结构定义中固有的。将此与并发映射进行比较，其中不同的元素没有特定的有序关系:如果正在访问不同的元素，则这种结构可以提供有效的无争用同时突变。

上下文切换免疫

与上述核心定义(以及功能保证)相关的无锁结构的一个性能优势是，正在改变结构的线程的上下文切换不会延迟所有其他修改器。在负载很重的系统中(特别是当可运行线程>>可用内核时)，一个线程可能会被关闭数百毫秒或数秒。在此期间，任何并发突变器都会阻塞并产生额外的调度成本(或者它们会旋转，这也可能产生不良行为)。尽管这种“不幸的调度”可能很少见，但当它确实发生时，整个系统可能会导致严重的延迟峰值。

无锁结构避免了这种情况，因为没有“临界区”，线程可以在其中被上下文切换出来并随后阻止其他线程的前进。

这种结构在这方面提供了部分保护——具体取决于队列大小和应用程序行为。即使线程在 m_write_index 之间的临界区中被切出更新和序列号写入，其他线程可以继续 push元素到队列中，只要它们没有从停顿的线程一直环绕到进行中的元素。线程也可以 pop元素，但仅限于进行中的元素。

而 push对于高容量队列，行为可能不是问题， pop行为可能是一个问题:如果与线程被上下文切换的平均时间相比，队列具有高吞吐量和平均填充度，则队列将很快对所有消费者线程显示为空，即使添加了许多元素超出了进行中的元素。这不受队列容量的影响，而只是受应用程序行为的影响。这意味着当发生这种情况时，消费者端可能会完全停止。在这方面，队列看起来根本不是无锁的!

功能方面

异步线程终止

凭借无锁结构的优势，它们可以安全地由可能是 asynchronously canceled 的线程使用。否则可能会在临界区异常终止。在任何时候取消线程都会使结构保持一致状态。

如上所述，该队列不是这种情况。

从中断或信号队列访问

一个相关的优点是通常可以从中断或信号中检查或改变无锁结构。这在中断或信号与常规进程线程共享结构的许多情况下很有用。

此队列主要支持此用例。即使当另一个线程处于临界区时发生信号或中断，异步代码仍然可以 push队列中的一个元素(只有稍后通过使用线程才能看到)并且仍然可以 pop队列中的一个元素。

这种行为不像真正的无锁结构那么完整:想象一个信号处理程序，它有一种方法可以告诉剩余的应用程序线程(除了被中断的线程)停顿，然后排空队列中的所有剩余元素。使用真正的无锁结构，这将允许信号处理程序完全耗尽所有元素，但在线程在临界区中断或切换的情况下，该队列可能无法做到这一点。

1 特别是，在 x86 上，这只会对 CAS 使用原子操作，因为内存模型足够强大，可以避免其他操作需要原子或防护。最近的 ARM 也可以相当有效地进行获取和发布。