哈伊先生，你好。 今天介绍无锁编程的基础知识。 我想让你知道无锁编程的基本原理。
无锁编程是一个挑战，不仅是因为任务本身的复杂性，而且因为从一开始就很难深入理解这个主题。 因为这个主题与基础技术(编译器、CPU、内存)密切相关，需要深化基础基础工作。
我正在学习无锁编程或Bruce Dawson优秀的全面白皮书locklessprogrammingconsiderations (免锁定编程思维)。 和许多技术一样，需要实践理论，在平台上开发和调试无锁代码。
本文想再次介绍无锁编程。 首先对其进行定义，然后将大部分信息提取为几个重要概念。 使用流程图说明这些概念是如何相互关联的，并讨论细节。 至少，进行无锁编程的程序员应该知道如何使用互斥锁、信号和事件等高级同步对象编写正确的多线程代码。
它是什么？
自由锁定编程通常被描述为没有互斥锁的编程，互斥锁也称为锁定。 这是真的，但这是故事的一部分。 基于学术文献的普遍接受的定义更广泛。 本质上，无锁定是编写特定代码的属性，不需要过多地描述代码的实际编写方式。
基本上，如果部分程序满足以下条件，则该部分当然不会被锁定： 相反，如果代码的特定部分不满足这些条件，则该部分未锁定。
从这个意义上说，无锁的锁定并不直接指排他锁定，而是指死锁、生锁——，甚至是你最大的敌人可能会以某种方式“锁定”整个APP应用程序最后一点我觉得很有趣，这是关键。 共享互斥锁只是被排除。 因为线程获得独占锁后，最大的敌人将不再调度该线程。 当然，真正的操作系统只是定义术语而不是这样运行的——。
这是一个不包含互斥但尚未锁定的操作的简单示例。 一开始，X=0。 作为读者的练习，我们将考虑一种方法来调度两个线程，以防止两个线程退出循环。
while(x==0) { X=1 – X； }没有人希望大型APP应用程序未完全锁定。 通常，我们从整个代码库中识别一组特定的未锁定操作。 例如，在非锁定队列中，可能存在非锁定操作，如极少数推式、pop或isEmpty。
Herlihy Shavit是The Art of Multiprocessor Programming(多处理器编程艺术)的作者，倾向于将此类操作表达为类方法，为以下免锁定提供简洁的定义：
“在无限执行中，一些方法调用无限频繁地结束. ”
这意味着，如果程序可以继续调用未锁定的操作，则无论发生什么，完成的调用次数都将持续增加。 在这些操作期间，系统无法在算法上锁定。
无锁编程的一个重要结论是，挂起一个线程决不会阻止其他线程作为组在自己的无锁定操作中取得进展。这暗示了在编写中断处理程序和实时系统时无锁编程的价值其中一些程序的其余部分处于任何状态，都必须在一定的时间限制内完成任务。
最后一个说明：某些操作被设计为阻止，并不意味着这不是锁定自由。 例如，如果队列为空，则可能有意阻止弹出队列操作。 剩下的代码路径被认为尚未锁定。
无锁编程技术
事实证明，当试图满足无锁编程的非阻塞条件时，会出现一系列技术：原子操作、内存屏障和避免ABA问题。 让我举几个例子。 这就是事情很快变得邪恶的地方。
那么这些技术是如何关联的呢？ 为了说明，整理了以下流程图。 以下，逐一详细说明。
原子读取-修改-写入操作原子操作是以看起来不可分割的方式操作内存的操作。 没有线程可以观察半完成的操作。 在现代处理器中，许多操作已经是原子的。 例如，简单类型的对齐读取和写入通常是原子。
读-修改-写(RMW )操作将更进一步，允许更复杂的事务在原子上执行。 在需要支持多个编写器时，无锁算法特别有用。 这是因为，当多个线程在同一个地址上尝试RMW时，它们会有效地排成一列一次执行这些操作。 本博客介绍了RMW操作，包括实现轻量级排他锁、递归排他锁和轻量级日志系统。
RMW操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS和STD 33603360 atomic int 33603360 fetch _ addc 11。 C 11原子标准并不保证实现不会在所有平台上锁定，因此建议您了解平台和工具链的功能。 请通过STD :3360 atomic 33603360 is _ lock _ free进行确认。
p>不同的 CPU 系列以不同的方式支持 RMW。诸如 PowerPC 和 ARM 之类的处理器公开了load-link/store-conditional）条件指令，这有效地允许您在低级别实现自己的 RMW 原语，尽管这并不常见。常见的 RMW 操作通常就足够了。
如流程图所示，即使在单处理器系统上，原子 RMW 也是无锁编程的必要部分。如果没有原子性，线程可能会在事务中途中断，从而可能导致状态不一致。
Compare-And-Swap Loops
也许最常讨论的 RMW 操作是compare-and-swap(CAS)。在 Win32 上，CAS 是通过一系列内在函数提供的，例如_InterlockedCompareExchange. 通常使用 CAS Loops 来完成对事务的原子处理：
void LockFreeQueue::push(Node* newHead){ for (;;) { // Copy a shared variable (m_Head) to a local. Node* oldHead = m_Head; // Do some speculative work, not yet visible to other threads. newHead->next = oldHead; // Next, attempt to publish our changes to the shared variable. // If the shared variable hasn’t changed, the CAS succeeds and we return. // Otherwise, repeat. if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead) return; }}
这样的循环仍然符合无锁的条件，因为如果一个线程的测试失败，则意味着它必须在另一个线程上成功——尽管某些架构提供了CAS的较弱变体，而这不一定是真的。每当实现 CAS 循环时，必须特别注意避免ABA 问题。
顺序一致性
顺序一致性是指所有线程都同意内存操作发生的顺序，并且该顺序与程序源代码中的操作顺序一致。
实现顺序一致性的一种简单（但显然不切实际）的方法是禁用编译器优化并强制所有线程在单个处理器上运行。处理器永远不会看到它自己的内存效果出问题，即使线程在任意时间被抢占和调度。
一些编程语言即使对于在多处理器环境中运行的优化代码也提供顺序一致性。在 C++11 中，您可以将所有共享变量声明为具有默认内存排序约束的 C++11 原子类型。在 Java 中，您可以将所有共享变量标记为volatile. 这是我上一篇文章中的示例，以 C++11 风格重写：
std::atomic< int > X( 0 ), Y( 0 );int r1, r2;void thread1(){ X.store( 1 ); r1 = Y.load();}void thread2(){ Y.store( 1 ); r2 = X.load(); }
因为 C++11 原子类型保证顺序一致性，结果 r1 = r2 = 0 是不可能的。为了实现这一点，编译器会在幕后输出额外的指令——通常是内存栅栏和/或 RMW 操作。与程序员直接处理内存排序的指令相比，这些附加指令可能会降低实现的效率。
内存排序
正如流程图所暗示的那样，任何时候您对多核（或任何对称多处理器）进行无锁编程，并且您的环境不保证顺序一致性，您必须考虑如何防止内存重新排序。
在当今的体系结构中，强制执行正确内存排序的工具通常分为三类，它们可以防止编译器重新排序和处理器重新排序：
轻量级同步或栅栏指令；
一个完整的内存栅栏指令；
提供获取或释放语义的内存操作。
获取语义防止在程序顺序中跟随它的操作的内存重新排序，并且释放语义防止在它之前的操作的内存重新排序。这些语义特别适用于存在生产者/消费者关系的情况，即一个线程发布一些信息而另一个线程读取它。
不同的处理器有不同的内存模型
不同的 CPU 系列在内存重新排序方面有不同的习惯。这些规则由每个 CPU 供应商记录，并由硬件严格遵守。例如，PowerPC 和 ARM 处理器可以更改相对于指令本身的内存存储顺序，但通常情况下，Intel 和 AMD 的 x86/64 系列处理器不会。我们说前者的处理器具有更宽松的内存模型。
人们很容易抽象出这些特定于平台的细节，尤其是 C++11 为我们提供了一种编写可移植无锁代码的标准方法。但是目前，我认为大多数无锁程序员至少对平台差异有一些了解。如果要记住一个关键区别，那就是在 x86/64 指令级别，每次从内存加载都带有获取语义，并且每次存储到内存都提供释放语义——至少对于非 SSE 指令和非写组合内存. 因此，过去常常编写能在x86/64 上运行成功但在其他处理器上失败的无锁代码。
如果你对处理器需要内存排序的硬件细节感兴趣，我推荐附录的并行编程困难吗？ 请记住在任何情况下,由于编译器指令重排序也会导致内存重新排序。
在这篇文章中，我没有过多地谈论无锁编程的实际方面，例如：我们什么时候做？我们真正需要多少？我也没有提到验证无锁算法的重要性。尽管如此，我希望对于一些读者来说，这篇介绍已经提供了对无锁概念的基本熟悉，因此您可以继续深入阅读其他文章而不会感到太困惑。
参考资料 & 扩展阅读
xhdsy Williams’ blog and his book, C++ Concurrency in Action
Dmitriy V’jukov’s website and various forum discussions
Bartosz Milewski’s blog
Charles Bloom’s Low-Level Threading series on his blog
Doug Lea’s JSR-133 Cookbook
Howells and McKenney’s memory-barriers.txt document
Hans Boehm’s collection of links about the C++11 memory model
Herb Sutter’s Effective Concurrency series
http://preshing.com/20120612/an-introduction-to-lock-free-programming/
– END –