循环缓冲区队列中的无锁进度保证
Lock-free Progress Guarantees in a circular buffer queue
有趣的是，我发现很多程序员错误地认为 "lock-free" 就是 "concurrent programming without mutexes"。通常，还有一个相关的误解，认为编写无锁代码的目的是为了获得更好的并发性能。当然，无锁的正确定义其实是关于进度保证。无锁算法保证至少有一个线程能够向前推进，而不管其他线程在做什么。
这意味着无锁算法永远不会有一个线程依赖另一个线程才能继续的代码。例如，无锁代码不能出现这样的情况：线程 A 设置一个标志，然后线程 B 在等待线程 A 取消设置标志时一直循环。像这样的代码基本上是在实现一个锁（或者我称之为伪装的互斥体）。
然而，其他情况更微妙，在某些情况下，老实说，我无法真正判断算法是否符合无锁条件，因为 "making progress" 的概念有时对我来说显得主观.
一个这样的例子出现在（广受好评的 afaik）并发库中，liblfds。我正在研究 liblfds 中 multi-producer/multi-consumer 有界队列的实现 - 实现非常简单，但我无法确定它是否应该符合无锁条件。
相关算法在lfds711_queue_bmm_enqueue.c中。 Liblfds 使用自定义原子和内存屏障，但该算法足够简单，我可以用一段左右的时间来描述。
队列本身是一个有界连续数组（ringbuffer）。有一个共享的 read_index 和 write_index。队列中的每个槽都包含一个用户数据字段和一个 sequence_number 值，这基本上就像一个纪元计数器。 （这避免了 ABA 问题）。
PUSH算法如下：
- 原子加载
write_index
- 尝试使用尝试将
write_index 设置为 write_index + 1 的 CompareAndSwap 循环在 write_index % queue_size 处的队列中保留一个插槽。
- 如果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 的插槽中 POP 元素的线程将无法执行此操作，直到它观察到插槽的 sequence_number 等于 read_index + 1 .
好的，所以这里没有互斥锁，而且该算法可能表现良好（对于 PUSH 和 POP，它只有一个 CAS），但是这是无锁的吗？我不清楚的原因是 "making progress" 的定义似乎很模糊，如果观察到队列已满或为空，则 PUSH 或 POP 可能总是会失败。
但对我来说有疑问的是 PUSH 算法本质上 保留 一个插槽，这意味着在推送线程开始更新序列之前，该插槽永远不会被 POP数字。这意味着想要弹出值 的 POP 线程取决于 已完成操作的 PUSH 线程。否则，POP 线程将始终 return false 因为它认为队列是 EMPTY。这是否真的属于 "making progress".
的定义对我来说似乎值得商榷
通常，真正的无锁算法涉及一个阶段，在该阶段中，被抢占的线程实际上会尝试协助其他线程完成操作。因此，为了真正实现无锁，我认为观察正在进行的 PUSH 的 POP 线程实际上需要尝试并完成 PUSH，然后才执行原始的 POP 操作。如果 POP 线程只是 return 在 PUSH 进行时队列为 EMPTY，则 POP 线程基本上 阻塞 直到 PUSH 线程完成操作。如果 PUSH 线程死掉，或者进入休眠状态 1000 年，或者被遗忘，POP 线程除了不断报告队列为 EMPTY 之外什么也做不了。
那么这符合无锁的定义吗？从一个角度来看，您可以争辩说 POP 线程总能取得进展，因为它总能报告队列为空（我猜这至少是某种形式的进步。）但对我来说，这并不是真正的进步，因为观察到队列为空的唯一原因是我们被并发 PUSH 操作阻塞。
那么，我的问题是：这个算法真的是无锁的吗？或者索引保留系统基本上是变相的互斥体？
如果 POP 立即调用 returns FALSE，则在下一次更新完成之前调用 POP 的线程不是 "effectively blocked"。线程可以关闭并做其他事情。我会说这个队列是无锁的。
但是，我不会说它符合 "queue" 的条件——至少不是那种你可以在图书馆或其他地方发布为队列的队列——因为它不保证您通常可以从队列中期望的许多行为。特别是，您可以 PUSH 和元素，然后尝试 POP 失败，因为其他线程正忙于推送较早的项目。
即便如此，这个队列在一些无锁解决方案中仍然有用，可以解决各种问题。
但是，对于许多应用程序，我会担心在生产者线程被抢占时消费者线程可能会饿死。也许 liblfds 对此做了些什么？
"Lock-free" 是算法 的属性，实现了一些功能。 属性 与程序如何使用 给定功能 的方式无关。
当谈论 mcmp_queue::enqueue 函数时，如果底层队列已满，returns FALSE，它的实现（在问题 post 中给出）是 无锁的.
然而，以无锁方式实现 mcmp_queue::dequeue 会很困难。例如，这个模式显然不是无锁的，因为它在其他线程更改的变量上自旋：
while(s.sequence_number.load(std::memory_order_acquire) == read_index);
data = s.user_data;
...
return data;
根据我认为最合理的定义，这个队列数据结构不是严格无锁。该定义类似于：
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.
当然，这意味着 usable 的合适定义，但对于大多数结构而言，这相当简单：结构应继续遵守其合同并允许插入和删除元素不出所料。
在这种情况下，已成功递增 m_write_increment 但尚未写入 s.sequence_number 的线程使容器处于很快将无法使用的状态。如果这样的线程被杀死，容器最终会把"full"和"empty"分别报告给push和pop，违反了固定大小队列的约定。
这里 是 一个隐藏的互斥体（m_write_index 和相关联的 s.sequence_number 的组合）——但它基本上像每个元素的互斥体一样工作.因此，一旦您循环并且新的编写器试图获取互斥锁，失败只会对编写器变得明显，但实际上所有后续编写器实际上未能将他们的元素插入队列，因为没有 reader 会看到它。
现在这并不意味着这是一个不好的并发队列实现。对于某些用途，它可能主要表现得好像它是无锁的。例如，此结构可能具有真正无锁结构的大部分有用的性能属性，但同时它缺少一些有用的正确性属性。基本上术语 lock-free 通常意味着一大堆属性，通常只有其中的一个子集对于任何特定用途都很重要。让我们一一来看，看看这个结构是如何工作的。我们会将它们大致分为性能和功能类别。
性能
无可争议的表现
无竞争或 "best case" 性能对许多结构很重要。虽然您需要一个并发结构来确保正确性，但您通常仍会尝试设计您的应用程序以便将争用保持在最低限度，因此非争用成本通常很重要。一些无锁结构在这里提供帮助，通过减少无竞争快速路径中昂贵的原子操作的数量，或避免 syscall.
这个队列实现在这里做了一个合理的工作：只有一个 "definitely expensive" 操作：compare_exchange_weak，以及几个可能昂贵的操作（memory_order_acquire 加载和 memory_order_release store)1, 以及很少的其他开销。
这与 std::mutex 之类的东西相比，这意味着类似于一个用于锁定的原子操作和另一个用于解锁的原子操作，并且实际上在 Linux 上，pthread 调用也具有不可忽略的开销。
所以我希望这个队列在无竞争的快速路径中表现得相当好。
竞争表现
无锁结构的一个优点是当结构竞争激烈时，它们通常允许更好的缩放。这不一定是 固有的 优势：一些具有多个锁或读写锁的基于锁的结构可能表现出匹配或超过某些无锁方法的缩放，但通常是在这种情况下，无锁结构表现出比简单的单锁规则所有替代方案更好的扩展性。
此队列在这方面表现合理。 m_write_index 变量由所有 reader 自动更新，这将成为争论的焦点，但只要底层硬件 CAS 实现合理，行为就应该是合理的。
请注意，队列通常是一个相当差的并发结构，因为插入和删除都发生在相同的位置（头部和尾部），所以竞争是固有的结构的定义。将此与并发映射进行比较，其中不同的元素没有特定的顺序关系：如果访问不同的元素，这种结构可以提供有效的无争用同步突变。
上下文切换免疫
与上述核心定义（以及功能保证）相关的无锁结构的一个性能优势是，正在改变结构的线程的上下文切换不会延迟所有其他改变器.在负载很重的系统中（尤其是当可运行线程 >> 可用内核时），一个线程可能会被关闭数百毫秒或几秒。在此期间，任何并发的修改器都会阻塞并产生额外的调度成本（或者它们会自旋，这也可能产生不良行为）。尽管这种 "unluckly scheduling" 可能很少见，但当它确实发生时，整个系统可能会出现严重的延迟峰值。
无锁结构避免了这种情况，因为没有 "critical region" 线程可以被上下文切换并随后阻止其他线程前进的进程。
此结构在此区域提供部分 保护 — 具体取决于队列大小和应用程序行为。即使在 m_write_index 更新和序号写入之间的临界区有一个线程被切换出去，其他线程只要不一路换行就可以继续向队列中 push 元素从停滞的线程转到 进行中 元素。线程也可以 pop 元素，但最多只能达到 进行中 元素。
虽然 push 行为对于高容量队列可能不是问题，但 pop 行为可能是个问题：如果队列的吞吐量高于线程的平均时间上下文切换，并且平均充满度，队列将很快对所有消费者线程显示为空，即使在 in-progress 元素之外添加了许多元素。这不受队列容量的影响，而仅受应用程序行为的影响。这意味着当这种情况发生时，消费者端可能会完全停止。在这方面，队列看起来根本就不是无锁的！
功能方面
异步线程终止
利用无锁结构，它们可以安全地供 asynchronously canceled 或可能在临界区异常终止的线程使用。在任何时候取消线程会使结构处于一致状态。
如上所述，此队列不是这种情况。
来自中断或信号的队列访问
一个相关的优点是无锁结构通常可以从中断或信号中检查或改变。这在中断或信号与常规进程线程共享结构的许多情况下很有用。
这个队列主要支持这个用例。即使当另一个线程在临界区时发生信号或中断，异步代码仍然可以 push 一个元素到队列中（只有稍后消费线程才能看到）并且仍然可以 pop队列中的一个元素。
该行为不像真正的无锁结构那样完整：想象一个信号处理程序可以告诉剩余的应用程序线程（被中断的线程除外）停止，然后耗尽所有剩余的元素的队列。使用真正的无锁结构，这将允许信号处理程序完全耗尽所有元素，但如果线程在临界区被中断或切换，则此队列可能无法做到这一点。
1 特别是，在 x86 上，这只会对 CAS 使用原子操作，因为内存模型足够强大，可以避免对另一个原子操作或屏蔽的需要操作。最近的 ARM 也可以相当有效地进行获取和释放。
大多数时候人们在真正指无锁时使用无锁。无锁意味着不使用锁的数据结构或算法，但不能保证前进。还要检查 this question。所以 liblfds 中的队列是无锁的，但正如 BeeOnRope 提到的，它不是无锁的。
我是liblfds的作者。
OP 对此队列的描述是正确的。
库中唯一的非无锁数据结构
这在队列的文档中有描述；
"It must be understood though that this is not actually a lock-free data structure."
这个队列是 Dmitry Vyukov (1024cores.net) 的一个想法的实现，我在使测试代码工作时才意识到它不是无锁的。
到那时它已经可以正常工作了，所以我把它收录了。
我确实想删除它，因为它不是无锁的。
几年前我在并发测试课程中使用 Spin 对同一代码进行了形式验证，它绝对不是无锁的。
仅仅因为没有明确的 "locking"，并不意味着它是无锁的。说到进度条件的推理，从单个线程的角度来思考：
Blocking/locking：如果另一个线程被取消调度并且这会阻止我的进度，那么它正在阻塞。
Lock-free/non-blocking：如果我能够在没有其他线程争用的情况下最终取得进展，那么它最多是无锁的。
如果没有其他线程可以无限期地阻止我的进度，那么它是免等待的。
有趣的是，我发现很多程序员错误地认为 "lock-free" 就是 "concurrent programming without mutexes"。通常，还有一个相关的误解，认为编写无锁代码的目的是为了获得更好的并发性能。当然，无锁的正确定义其实是关于进度保证。无锁算法保证至少有一个线程能够向前推进，而不管其他线程在做什么。
这意味着无锁算法永远不会有一个线程依赖另一个线程才能继续的代码。例如，无锁代码不能出现这样的情况：线程 A 设置一个标志，然后线程 B 在等待线程 A 取消设置标志时一直循环。像这样的代码基本上是在实现一个锁（或者我称之为伪装的互斥体）。
然而，其他情况更微妙，在某些情况下，老实说，我无法真正判断算法是否符合无锁条件，因为 "making progress" 的概念有时对我来说显得主观.
一个这样的例子出现在（广受好评的 afaik）并发库中，liblfds。我正在研究 liblfds 中 multi-producer/multi-consumer 有界队列的实现 - 实现非常简单，但我无法确定它是否应该符合无锁条件。
相关算法在lfds711_queue_bmm_enqueue.c中。 Liblfds 使用自定义原子和内存屏障，但该算法足够简单，我可以用一段左右的时间来描述。
队列本身是一个有界连续数组（ringbuffer）。有一个共享的 read_index 和 write_index。队列中的每个槽都包含一个用户数据字段和一个 sequence_number 值，这基本上就像一个纪元计数器。 （这避免了 ABA 问题）。
PUSH算法如下：
- 原子加载
write_index - 尝试使用尝试将
write_index设置为write_index + 1的 CompareAndSwap 循环在write_index % queue_size处的队列中保留一个插槽。 - 如果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 的插槽中 POP 元素的线程将无法执行此操作，直到它观察到插槽的 sequence_number 等于 read_index + 1 .
好的，所以这里没有互斥锁，而且该算法可能表现良好（对于 PUSH 和 POP，它只有一个 CAS），但是这是无锁的吗？我不清楚的原因是 "making progress" 的定义似乎很模糊，如果观察到队列已满或为空，则 PUSH 或 POP 可能总是会失败。
但对我来说有疑问的是 PUSH 算法本质上 保留 一个插槽，这意味着在推送线程开始更新序列之前，该插槽永远不会被 POP数字。这意味着想要弹出值 的 POP 线程取决于 已完成操作的 PUSH 线程。否则，POP 线程将始终 return false 因为它认为队列是 EMPTY。这是否真的属于 "making progress".
通常，真正的无锁算法涉及一个阶段，在该阶段中，被抢占的线程实际上会尝试协助其他线程完成操作。因此，为了真正实现无锁，我认为观察正在进行的 PUSH 的 POP 线程实际上需要尝试并完成 PUSH，然后才执行原始的 POP 操作。如果 POP 线程只是 return 在 PUSH 进行时队列为 EMPTY，则 POP 线程基本上 阻塞 直到 PUSH 线程完成操作。如果 PUSH 线程死掉，或者进入休眠状态 1000 年，或者被遗忘，POP 线程除了不断报告队列为 EMPTY 之外什么也做不了。
那么这符合无锁的定义吗？从一个角度来看，您可以争辩说 POP 线程总能取得进展，因为它总能报告队列为空（我猜这至少是某种形式的进步。）但对我来说，这并不是真正的进步，因为观察到队列为空的唯一原因是我们被并发 PUSH 操作阻塞。
那么，我的问题是：这个算法真的是无锁的吗？或者索引保留系统基本上是变相的互斥体？
如果 POP 立即调用 returns FALSE，则在下一次更新完成之前调用 POP 的线程不是 "effectively blocked"。线程可以关闭并做其他事情。我会说这个队列是无锁的。
但是，我不会说它符合 "queue" 的条件——至少不是那种你可以在图书馆或其他地方发布为队列的队列——因为它不保证您通常可以从队列中期望的许多行为。特别是，您可以 PUSH 和元素，然后尝试 POP 失败，因为其他线程正忙于推送较早的项目。
即便如此，这个队列在一些无锁解决方案中仍然有用，可以解决各种问题。
但是，对于许多应用程序，我会担心在生产者线程被抢占时消费者线程可能会饿死。也许 liblfds 对此做了些什么？
"Lock-free" 是算法 的属性，实现了一些功能。 属性 与程序如何使用 给定功能 的方式无关。
当谈论 mcmp_queue::enqueue 函数时，如果底层队列已满，returns FALSE，它的实现（在问题 post 中给出）是 无锁的.
然而，以无锁方式实现 mcmp_queue::dequeue 会很困难。例如，这个模式显然不是无锁的，因为它在其他线程更改的变量上自旋：
while(s.sequence_number.load(std::memory_order_acquire) == read_index);
data = s.user_data;
...
return data;
根据我认为最合理的定义，这个队列数据结构不是严格无锁。该定义类似于：
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.
当然，这意味着 usable 的合适定义，但对于大多数结构而言，这相当简单：结构应继续遵守其合同并允许插入和删除元素不出所料。
在这种情况下，已成功递增 m_write_increment 但尚未写入 s.sequence_number 的线程使容器处于很快将无法使用的状态。如果这样的线程被杀死，容器最终会把"full"和"empty"分别报告给push和pop，违反了固定大小队列的约定。
这里 是 一个隐藏的互斥体（m_write_index 和相关联的 s.sequence_number 的组合）——但它基本上像每个元素的互斥体一样工作.因此，一旦您循环并且新的编写器试图获取互斥锁，失败只会对编写器变得明显，但实际上所有后续编写器实际上未能将他们的元素插入队列，因为没有 reader 会看到它。
现在这并不意味着这是一个不好的并发队列实现。对于某些用途，它可能主要表现得好像它是无锁的。例如，此结构可能具有真正无锁结构的大部分有用的性能属性，但同时它缺少一些有用的正确性属性。基本上术语 lock-free 通常意味着一大堆属性，通常只有其中的一个子集对于任何特定用途都很重要。让我们一一来看，看看这个结构是如何工作的。我们会将它们大致分为性能和功能类别。
性能
无可争议的表现
无竞争或 "best case" 性能对许多结构很重要。虽然您需要一个并发结构来确保正确性，但您通常仍会尝试设计您的应用程序以便将争用保持在最低限度，因此非争用成本通常很重要。一些无锁结构在这里提供帮助，通过减少无竞争快速路径中昂贵的原子操作的数量，或避免 syscall.
这个队列实现在这里做了一个合理的工作：只有一个 "definitely expensive" 操作：compare_exchange_weak，以及几个可能昂贵的操作（memory_order_acquire 加载和 memory_order_release store)1, 以及很少的其他开销。
这与 std::mutex 之类的东西相比，这意味着类似于一个用于锁定的原子操作和另一个用于解锁的原子操作，并且实际上在 Linux 上，pthread 调用也具有不可忽略的开销。
所以我希望这个队列在无竞争的快速路径中表现得相当好。
竞争表现
无锁结构的一个优点是当结构竞争激烈时，它们通常允许更好的缩放。这不一定是 固有的 优势：一些具有多个锁或读写锁的基于锁的结构可能表现出匹配或超过某些无锁方法的缩放，但通常是在这种情况下，无锁结构表现出比简单的单锁规则所有替代方案更好的扩展性。
此队列在这方面表现合理。 m_write_index 变量由所有 reader 自动更新，这将成为争论的焦点，但只要底层硬件 CAS 实现合理，行为就应该是合理的。
请注意，队列通常是一个相当差的并发结构，因为插入和删除都发生在相同的位置（头部和尾部），所以竞争是固有的结构的定义。将此与并发映射进行比较，其中不同的元素没有特定的顺序关系：如果访问不同的元素，这种结构可以提供有效的无争用同步突变。
上下文切换免疫
与上述核心定义（以及功能保证）相关的无锁结构的一个性能优势是，正在改变结构的线程的上下文切换不会延迟所有其他改变器.在负载很重的系统中（尤其是当可运行线程 >> 可用内核时），一个线程可能会被关闭数百毫秒或几秒。在此期间，任何并发的修改器都会阻塞并产生额外的调度成本（或者它们会自旋，这也可能产生不良行为）。尽管这种 "unluckly scheduling" 可能很少见，但当它确实发生时，整个系统可能会出现严重的延迟峰值。
无锁结构避免了这种情况，因为没有 "critical region" 线程可以被上下文切换并随后阻止其他线程前进的进程。
此结构在此区域提供部分 保护 — 具体取决于队列大小和应用程序行为。即使在 m_write_index 更新和序号写入之间的临界区有一个线程被切换出去，其他线程只要不一路换行就可以继续向队列中 push 元素从停滞的线程转到 进行中 元素。线程也可以 pop 元素，但最多只能达到 进行中 元素。
虽然 push 行为对于高容量队列可能不是问题，但 pop 行为可能是个问题：如果队列的吞吐量高于线程的平均时间上下文切换，并且平均充满度，队列将很快对所有消费者线程显示为空，即使在 in-progress 元素之外添加了许多元素。这不受队列容量的影响，而仅受应用程序行为的影响。这意味着当这种情况发生时，消费者端可能会完全停止。在这方面，队列看起来根本就不是无锁的！
功能方面
异步线程终止
利用无锁结构，它们可以安全地供 asynchronously canceled 或可能在临界区异常终止的线程使用。在任何时候取消线程会使结构处于一致状态。
如上所述，此队列不是这种情况。
来自中断或信号的队列访问
一个相关的优点是无锁结构通常可以从中断或信号中检查或改变。这在中断或信号与常规进程线程共享结构的许多情况下很有用。
这个队列主要支持这个用例。即使当另一个线程在临界区时发生信号或中断，异步代码仍然可以 push 一个元素到队列中（只有稍后消费线程才能看到）并且仍然可以 pop队列中的一个元素。
该行为不像真正的无锁结构那样完整：想象一个信号处理程序可以告诉剩余的应用程序线程（被中断的线程除外）停止，然后耗尽所有剩余的元素的队列。使用真正的无锁结构，这将允许信号处理程序完全耗尽所有元素，但如果线程在临界区被中断或切换，则此队列可能无法做到这一点。
1 特别是，在 x86 上，这只会对 CAS 使用原子操作，因为内存模型足够强大，可以避免对另一个原子操作或屏蔽的需要操作。最近的 ARM 也可以相当有效地进行获取和释放。
大多数时候人们在真正指无锁时使用无锁。无锁意味着不使用锁的数据结构或算法，但不能保证前进。还要检查 this question。所以 liblfds 中的队列是无锁的，但正如 BeeOnRope 提到的，它不是无锁的。
我是liblfds的作者。
OP 对此队列的描述是正确的。
库中唯一的非无锁数据结构
这在队列的文档中有描述；
"It must be understood though that this is not actually a lock-free data structure."
这个队列是 Dmitry Vyukov (1024cores.net) 的一个想法的实现，我在使测试代码工作时才意识到它不是无锁的。
到那时它已经可以正常工作了，所以我把它收录了。
我确实想删除它，因为它不是无锁的。
几年前我在并发测试课程中使用 Spin 对同一代码进行了形式验证，它绝对不是无锁的。
仅仅因为没有明确的 "locking"，并不意味着它是无锁的。说到进度条件的推理，从单个线程的角度来思考：
Blocking/locking：如果另一个线程被取消调度并且这会阻止我的进度，那么它正在阻塞。
Lock-free/non-blocking：如果我能够在没有其他线程争用的情况下最终取得进展，那么它最多是无锁的。
如果没有其他线程可以无限期地阻止我的进度，那么它是免等待的。