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

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

但是，其他情况则比较微妙，在某些情况下，老实说我无法真正判断算法是否符合无锁要求，因为“取得进步”的概念有时对我而言是主观的。

一种这样的情况在（广受好评的afaik）并发库 liblfds中
。我正在研究liblfds中多生产者/多消费者有界队列的实现-该实现非常简单，但是我无法真正确定它是否应视为无锁。

相关算法在中lfds711_queue_bmm_enqueue.c。Liblfds使用自定义原子和内存屏障，但是该算法非常简单，足以让我在一段左右的时间内进行描述。

队列本身是一个有界的连续数组（ringbuffer）。有一个共享read_index和write_index。队列中的每个插槽都包含一个用于用户数据的字段和一个sequence_number值，该值基本上类似于纪元计数器。（这避免了ABA问题）。

PUSH算法如下：

1. 以原子方式加载 write_index
2. 尝试write_index % queue_size使用CompareAndSwap循环尝试将其设置write_index为，以在队列中保留一个插槽write_index + 1。
3. 如果CompareAndSwap成功，则将用户数据复制到保留的插槽中。
4. 最后，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因为它认为队列为EMPTY。对于我来说，这是否真正属于“取得进展”的定义似乎值得商de。

通常，真正的无锁算法涉及一个阶段，在该阶段，抢占线程实际上会尝试在完成操作时协助另一个线程。因此，为了真正实现无锁定，我认为观察到正在进行的PUSH的POP线程实际上需要尝试并完成PUSH，然后才执行原始的POP操作。如果在进行PUSH时POP线程简单地返回队列为EMPTY，则基本上
阻塞
POP线程，直到PUSH线程完成操作为止。如果PUSH线程死亡，进入睡眠状态1,000年或以其他方式被遗忘，则POP线程将无能为力，除非连续报告该队列为EMPTY。

那么这是否适合无锁的定义？从一个角度来看，您可以辩称POP线程总是可以取得进展，因为它可以始终报告队列为EMPTY（我猜这至少是某种形式的进展。）但是对我而言，这并不是真正的进展，因为观察到队列为空的唯一原因是因为我们被并发的PUSH操作
阻塞 。

所以， 我的问题是 ：这个算法真的是无锁的吗？还是索引保留系统基本上是变相的互斥体？