C++11 :原子变量: lock_free属性:它是什么意思？

Question

我想要理解c++11中原子变量的lock_free属性是什么意思，我用谷歌搜索了一下，在这个论坛上看到了其他相关的问题，但仍然有部分理解。如果有人能用简单的方式完整地解释一下，我将不胜感激。

Answer 1

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

锁的另一个危险是你失去了关于执行时间的确定性:如果获得锁的线程被延迟(例如，被操作系统取消调度，或者“换出”)，那么整个程序很可能因为它正在等待锁而被延迟。相比之下，一个无锁的算法总是能取得一些进展，即使在其他地方有许多线程被阻塞。

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

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

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

要测试原子对象是否无锁，可以使用is_lock_free成员函数。此外，还有一些ATOMIC_*_LOCK_FREE宏可以告诉您原子原语类型是否可能具有无锁的实例化。如果您正在编写希望是无锁的并发算法，则应该包括一个断言，即您的原子对象确实是无锁的，或者在宏上包含一个具有值2的静态断言(这意味着相应类型的每个对象始终是无锁的)。

Answer 2

从讨论如果它不是无锁的会发生什么开始可能是最简单的。

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

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

有各种各样的策略来避免它们(例如，所有线程总是试图以相同的顺序获得互斥锁，或者在合理的时间段内无法获得互斥锁时，每个线程释放它持有的互斥锁，等待一段随机的时间，然后重试)。

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

现在，至于具体如何做到这一点:答案很简单:它有很大的不同。在许多情况下，您正在寻找特定的硬件支持，以原子方式执行特定的操作。您的代码或者直接使用它们，或者扩展它们以提供仍然是原子的和无锁的更高级别的操作。甚至可以在没有硬件支持的情况下实现无锁的原子操作(但考虑到它的不切实际，我将继续尝试更多细节，至少现在是这样)。

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)

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