源地址： http://pre shing.com/2012 06 12/an-introduction-to-lock-free-programming
文章目录无锁编程是指，对于何种无锁编程技术原子的读写操作Compare-And-Swap循环顺序一致性存储器保证顺序不同的处理器，有不同存储器型号的参考文献
无锁编程是一个挑战，不仅关系到自身的复杂性，还关系到首次探索其课题的难度。
幸运的是，我第一次介绍了诺瓦克(3358www.Sina.com)、http://www.Sina.com)编程。 这是Bruce Dawson出色的全面白皮书《无锁编程注意事项》。 和大多数人一样，您有机会使用Bruce建议来创建和调试未锁定的代码，例如在Xbox360平台上开发。
自那时以来，出现了很多好素材，包括抽象理论、实例正确性证明、硬件细节等。 脚注中有几处引用。 在某些情况下，数据可能因源而异。 例如，一些材料假设顺序一致性，从而避免了困扰C/C未锁定代码的内存排序问题。 新的C 11原子操作库标准提供了新的工具，这将挑战现有的无锁定算法。
本文重新介绍了无锁编程，首先对其进行了定义，然后从大量信息中提取少数重要概念。 用流程图展示了各个概念之间的关系，然后着手一些详细的问题。 学习无锁编程的程序员应该了解如何在多线程代码中使用互斥量，并了解高级同步机制，如信号和事件。
什么是无锁编程？ 人们经常将无锁编程描述为不使用http://www.Sina.com/(mutex，一种锁定机制)的程序。 这种说法是正确的，但并不全面。 基于广泛接受的学术报告的定义，含有更广义的含义。 本质上，无锁编程是编写一些代码的属性，很少编写代码。
基本上，如果你的代码的某些部分满足以下条件，就会被视为无锁定。 相反，如果部分代码不满足以下条件，则认为不是自由锁定。
在此方案中，“未锁定”下的“锁定”不是直接指向独占量，而是指向可能“锁定”整个APP应用程序的所有方法。 死锁、活块甚至线程调度的方法可能也是你最大的敌人。 最后一点听起来很有趣，但很重要。 首先，共享独占量被排除。 因为一旦线程获得独占量，最大的敌人就无法重新调度该线程。 当然，实际的操作系统不是这样做的，只是我们这么定义的。
以下简单示例没有使用互斥量，但不是没有锁定。 x的初始值为0。 作为练习问题，请考虑如何安排两个线程，以避免两个线程都退出循环。
while(x==0) { X=1 - X； }没有人期望整个大型APP应用程序没有完全锁定。 通常，可以从整个代码库中识别一系列无锁定操作。 未锁定的队列中有一点未锁定的操作，例如，推式、pop和isEmpty。
《多处理器编程艺术》的作者Herlihy和Shavit倾向于将这些操作表示为类的方法，并提出了“在无限执行期间，调用持续结束”的简单免锁定定义。 也就是说，程序可以不断调用这些未锁定的操作，同时许多调用不断完成。 从算法上讲，在执行这些操作的过程中，无法锁定系统。
无锁编程的一个重要特性是，锁定一个线程不会干扰其他线程的执行。 作为一组线程，使用特定的无锁定操作来执行此功能。 这表明了无锁编程在中断处理程序和实时系统中的价值。 因为在这些情况下，无论程序状态如何，特定操作都必须在特定时间内完成。
最后准确说明：为分块设计的操作不影响算法的执行。 这个代码才是未锁定的。 例如，对于未锁定的队列操作，如果队列为空，则有意阻止弹出队列操作。 但是，其他代码路径被认为尚未锁定。
无锁编程技术的事实证明，纯真的钢铁侠想要满足无锁编程的无阻塞条件，就会出现原子操作、内存屏障、避免ABA问题等一系列技术。 从这里开始，事情很快就变得麻烦了。
那么，这些技术是如何相互关联的呢？ 将这些放入以下流程图进行展示。 以下逐一叙述。
原子读取修改写入操作原子操作是指以看起来不可分割的方式操作内存。 线程无法看到原子操作的中间进程。 现代处理器中，操作本身有很多原子性质的东西。 例如，对简单类型对齐的读写通常是原子的。
读修改-写(rmw )操作将更进一步，使您可以像处理原子一样处理更复杂的事务。 当未锁定的算法需要支持多个编写器时，原子操作特别有用。 这是因为，如果多个线程尝试使用同一地址运行RMW，则这些操作将“一次一个”排队。 在我的博客中，我参与了RMW操作，包括实现轻量排他量、递归排他量和轻量日志系统。
RMW操作的示例包括Win32的_InterlockedIncrement、iOS的OSAtomicAdd32和C 11的STD 33603360 atomic int 33603360 fetch _ add。 需要注意的是，C 11的原子标准并不保证没有在各平台上实现
锁的，因此最好要清楚你的平台和工具链的能力。你可以调用 std::atomic<>::is_lock_free 来确认一下。不同的 CPU 系列支持 RMW 的方式也是不同的。例如，PowerPC 和 ARM 提供 load-link/store-conditional 指令，这实际上是允许你实现你自定义的底层 RMW 操作。常用的 RMW 操作就已经足够了。
如上面流程图所述，即使在单处理器系统上，原子的 RMW 操作也是无锁编程的必要部分。没有原子性的话，一个线程的事务会被中途打断，这可能会导致一个错误的状态。
Compare-And-Swap 循环或许，最常讨论的 RMW 操作是 compare-and-swap (CAS)。在Win32上，CAS 是通过如 _InterlockedCompareExchange 等一系列指令来提供的。通常，程序员会在一个事务中使用 CAS 循环。这个模式通常包括：复制一个共享的变量至本地变量，做一些特定的工作（改动），再试图使用 CAS 发布这些改动。
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 问题。
顺序一致性顺序一致性（Sequential consistency）意味着，所有线程就内存操作的顺序达成一致。这个顺序是和操作在程序源代码中的顺序是一致的。在顺序一致性的要求下，像我 另一篇文章 演示的那样的有意的内存重排序不再可能了。
一种实现顺序一致性的简单（但显然不切实际）的方法是禁用编译器优化，并强制所有线程在单个处理器上运行。 即使线程在任意时间被抢占和调度，处理器也永远不会看到自己的内存影响。
某些编程语言甚至可以为在多处理器环境中运行的优化代码提供顺序一致性。 在C ++ 11中，可以将所有共享变量声明为具有默认内存排序约束的C ++ 11原子类型。 在Java中，您可以将所有共享变量标记为volatile。下面是 我之前一个案例 用C++11风格重写的例子。
std::atomic 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 处理器可以相对于指令本身更改内存存储的顺序，但是通常，英特尔和 AMD 的 x86 / 64 系列处理器不会。 我们说以前的处理器具有更宽松的内存模型。
有人倾向于将这些特定于平台的细节抽象出来，尤其是C ++ 11为我们提供了编写可移植的无锁代码的标准方法。 但是目前，我认为大多数无锁程序员至少对平台差异有所了解。 如果需要记住一个关键的区别，那就是在x86 / 64指令级别上，每次从内存中加载都会获取语义，并且每次存储到内存都将提供释放语义–至少对于非SSE指令和非写组合内存 。 因此，过去通常会编写可在x86 / 64上运行但 在其他处理器上无法运行 的无锁代码。
如果你对硬件如何处理内存重新排序的细节感兴趣，我建议看看《Is Pararllel Programming Hard》的附录C。无论如何，请记住，由于编译器对指令的重新排序，也会发生内存重新排序。
在这篇文章中，我没有对无锁编程的实际方面说太多，例如：什么时候做？ 我们真正需要多少？ 我也没有提到验证无锁算法的重要性。 尽管如此，我希望对某些读者来说，本入门对无锁概念有基本的了解，因此您可以继续阅读其他内容而不会感到困惑。
参考文献[1] 无锁编程注意事项
[2] Locks Aren’t Slow; Lock Contention Is
[3] 实现自己的轻量级互斥量
[4] 实现一个递归互斥量
[5] 一个轻量级内存日志系统