c++ - C++11：原子变量：lock_free 属性：这是什么意思？

Question

我想了解 c++11 中原子变量的 lock_free 属性是什么意思。我确实用谷歌搜索并看到了这个论坛上的其他相关问题，但仍然有部分理解。欣赏是否有人可以以简单的方式端到端地解释它。

Answer 1

从谈论如果它不是无锁的会发生什么开始可能是最容易的。

处理大多数原子任务的最明显方法是锁定。例如，要确保一次只有一个线程写入变量，您可以使用互斥锁来保护它。任何要写入变量的代码都需要在写入之前获取互斥锁（然后释放它）。一次只有一个线程可以拥有互斥锁，因此只要所有线程都遵循协议，在任何给定时间最多只能有一个线程可以写入。

但是，如果您不小心，这可能会陷入僵局。例如，假设您需要将两个不同的变量（每个都受互斥锁保护）作为原子操作写入——即，您需要确保在写入一个变量时，您也写入另一个变量）。在这种情况下，如果不小心，可能会导致死锁。比如我们调用两个互斥量A和B。线程1获取互斥量A，然后尝试获取互斥量B。同时，线程2获取互斥量B，然后尝试获取互斥量A。由于每个人都持有一个互斥量，谁都不能兼得，也不能朝着自己的目标前进。

有多种策略来避免它们（例如，所有线程总是尝试以相同的顺序获取互斥锁，或者在合理的时间内未能获得互斥锁时，每个线程释放它持有的互斥锁，等待一些随机数量的时间，然后再试一次）。

然而，对于无锁编程，我们（显然）不使用锁。这意味着像上面这样的死锁根本不会发生。正确完成后，您可以保证所有线程不断朝着它们的目标前进。与流行的看法相反，这并不意味着代码一定会比使用锁的编写良好的代码运行得更快。然而，这确实意味着消除了上述死锁（以及一些其他类型的问题，如活锁和某些类型的竞争条件）。

现在，至于你是如何做到这一点的：答案很简短：它变化很大——范围很广。在很多情况下，您正在查看特定的硬件支持以原子地执行某些特定操作。您的代码要么直接使用它们，要么扩展它们以提供仍然是原子且无锁的更高级别的操作。在没有硬件支持的情况下实现无锁原子操作甚至是可能的（尽管很少实用）（但鉴于其不切实际，我将继续尝试更详细地介绍它，至少现在是这样）。

Answer 2

Jerry 已经提到了锁的常见正确性问题，即它们很难理解和正确编程。

锁的另一个危险是您失去了关于执行时间的确定性：如果获得锁的线程被延迟（例如，被操作系统取消调度，或“换出”），那么整个程序可能会被延迟，因为它正在等待锁。相比之下，无锁算法总是可以保证取得一些进展，即使任何数量的线程在其他地方被阻塞。

总的来说，无锁编程通常比使用非原子操作的锁定编程要慢（有时明显慢），因为原子操作会对缓存和流水线造成重大影响；但是，它提供了延迟的确定性和上限（至少是您进程的整体延迟；正如@J99 所观察到的，只要有足够多的其他线程正在取得进展，单个线程可能仍然处于饥饿状态）。您的程序可能会变得慢很多，但它永远不会完全锁定并且总是会取得一些进展。

硬件架构的本质允许某些小操作本质上是原子的。事实上，这对于任何支持多任务和多线程的硬件来说都是非常必要的。在任何同步原语（例如互斥锁）的核心，您都需要某种原子指令来保证正确的锁定行为。

因此，考虑到这一点，我们现在知道某些类型（如布尔值和机器大小的整数）可以原子地加载、存储和交换。因此，当我们将这样的类型包装到std::atomic模板中时，我们可以预期生成的数据类型确实会提供不使用锁的加载、存储和交换操作。相比之下，您的库实现始终允许将原子实现为由锁保护Foo的普通。Foo

要测试一个原子对象是否是无锁的，可以使用is_lock_free成员函数。此外，还有一些ATOMIC_*_LOCK_FREE宏可以告诉您原子原始类型是否可能具有无锁实例化。如果您正在编写想要无锁的并发算法，那么您应该包含一个断言您的原子对象确实是无锁的，或者对宏进行静态断言以使其具有价值2（意味着相应类型的每个对象总是无锁的）。

Answer 3

无锁是非阻塞技术之一。对于算法，它涉及全局进度属性：每当程序的线程处于活动状态时，它可以在其动作中向前迈出一步，为自己或最终为另一个。

无锁算法应该在激烈的争用下具有更好的行为，其中线程在共享资源上可能花费大量时间等待它们的下一个活动时间片。在您无法锁定的上下文中，它们也几乎是强制性的，例如中断处理程序。

无锁算法的实现几乎总是依赖于比较和交换（有些可能使用诸如 ll/sc 之类的东西）和策略，其中可见的修改可以简化为一个值（主要是指针）更改，使其成为线性化点，然后循环如果值发生变化，则超过此修改。大多数时候，这些算法会尽可能地尝试完成其他线程的工作。一个很好的例子是 Micheal&Scott ( http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html ) 的无锁队列。

对于比较和交换这样的低级指令，这意味着实现（可能是相应指令的微代码）是免等待的（参见http://www.diku.dk/OLD/undervisning/2005f/ dat-os/skrifter/lockfree.pdf )

为了完整起见，无等待算法对每个线程强制执行进程：每个操作都保证在有限数量的步骤中终止。