本文转载自微信公众号《极客重生》，作者极客重生。转载本文请联系极客重生公众号。大家好，今天给大家介绍一下无锁编程的基础知识。希望你能理解无锁编程的基本原理。无锁编程是一个挑战，不仅因为任务本身的复杂性，还因为很难从一开始就深入理解主题，因为主题与底层技术（编译器、CPU、记忆）并且需要深入的基础知识。我从BruceDawson的优秀而全面的白皮书LocklessProgrammingConsiderations中学习了无锁编程。与许多技术一样，需要将理论付诸实践，以在平台上开发和调试无锁代码。在这篇文章中，我想重新介绍无锁编程，首先定义它，然后将大部分信息提炼成几个关键概念。我将使用流程图来展示这些概念如何相互关联，然后我们将深入探讨细节。至少，任何进行无锁编程的程序员都应该已经了解如何使用互斥体和其他高级同步对象（如信号量和事件）编写正确的多线程代码。它是什么？人们常把无锁编程描述为没有互斥锁的编程，也称为锁。这是真的，但这只是故事的一部分。基于学术文献的普遍接受的定义更为广泛。本质上，无锁是一种用于描述某些代码的属性，而无需过多说明该代码的实际编写方式。基本上，如果您的程序的某些部分满足以下条件，那么该部分就可以被认为是无锁的。相反，如果给定的代码部分不满足这些条件，则该部分不是无锁的。从这个意义上说，lock-free中的锁并不是直接指互斥量，而是指以某种方式“锁定”整个应用程序的可能性，无论是死锁、活锁——甚至是由于最坏的敌人。最后一点听起来很有趣，但这是关键。共享互斥锁被简单地排除了，因为一旦一个线程获得了一个互斥锁，你最大的敌人就再也不能调度那个线程了。当然，真正的操作系统不是这样工作的——我们只是定义术语。下面是一个不涉及互斥量且仍然不是无锁操作的简单示例。最初，X=0。作为读者的练习，考虑如何安排两个线程以使两个线程都不退出循环。while(X==0){X=1-X;}没有人期望大型应用程序是完全无锁的。通常，我们会在代码库中识别一组特定的无锁操作。比如在一个无锁队列中，可能会有极少数的push、pop、isEmpty等无锁操作。TheArtofMultiprocessorProgramming的作者Herlihy&Shavit更喜欢将此类操作表达为类方法，并提供了以下简洁的无锁定义：“在无限执行中，某些方法调用将无限频繁地结束”换句话说，只要该程序能够继续调用那些无锁操作，无论发生什么情况，完成的调用次数都会不断增加。在这些操作期间，系统在算法上是不可能锁定的。无锁编程的一个重要结论是，如果你挂起一个线程，它永远不会阻止其他线程作为一个整体通过它们自己的无锁操作取得进展。这暗示了在编写中断处理程序和实时系统时无锁编程的价值，其中某些任务必须在特定时间限制内完成，无论程序的其余部分处于什么状态。最后一点：只是因为某些操作被设计为被阻止并不意味着它们不是无锁的。例如，当队列为空时，队列中的弹出操作可能会故意阻塞。代码路径的其余部分仍然可以被认为是无锁的。无锁编程技术事实证明，当您试图满足无锁编程的非阻塞条件时，会出现一整套技术：原子操作、内存屏障、避免ABA问题等等。这是事情很快变得邪恶的地方。那么这些技术如何相互关联呢？为了说明，我整理了以下流程图。下面我一一详述。原子读-修改-写操作原子操作是以一种看起来不可分割的方式操纵内存的操作：没有线程可以观察到半完成的操作。在现代处理器上，许多操作已经是原子的。例如，简单类型的对齐读取和写入通常是原子的。读-修改-写(RMW)操作更进一步，允许您以原子方式执行更复杂的事务。当无锁算法必须支持多个写入器时，它们特别有用，因为当多个线程在同一地址上尝试RMW时，它们将有效地排队并立即执行这些操作。我在这篇博文中介绍了RMW操作，例如在实现轻量级互斥锁、递归互斥锁和轻量级日志系统时。RMW操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS和std::atomic::fetch_addC++11。请注意，C++11原子标准不保证每个平台上的实现都是无锁的，因此最好了解您的平台和工具链的能力。您可以使用std::atomic<>::is_lock_free检查。不同的CPU系列以不同的方式支持RMW。PowerPC和ARM等处理器公开加载链接/存储条件）条件指令，这些指令有效地允许您在低级别实现自己的RMW原语，尽管这并不常见。常见的RMW操作通常就足够了。如流程图所示，即使在单处理器系统上，原子RMW也是无锁编程的重要组成部分。如果没有原子性，线程可能会在事务处理过程中中断，从而可能导致不一致的状态。比较和交换循环也许最常讨论的RMW操作是比较和交换(CAS)。在Win32上，CAS是通过一系列内部函数提供的，例如_InterlockedCompareExchange。CASLoops通常用来完成事务的原子处理：voidLockFreeQueue::push(Node*newHead){for(;;){//Copysharedvariable(m_Head)toalocal.Node*oldHead=m_Head;//做一些推测工作，notyetvisibletootherthreads.newHead->next=oldHead;,oldHead)==oldHead)return;}}这样的循环仍然是无锁的，因为如果在一个线程上测试失败，则意味着它必须在另一个线程上成功——尽管一些架构提供了CASWeaker变体，它是不一定是真的。每当实施CAS循环时，必须特别注意避免ABA问题。顺序一致性顺序一致性意味着所有线程都同意内存操作发生的顺序，并且该顺序与程序源代码中的操作顺序一致。实现顺序一致性的一种简单（但显然不切实际）的方法是禁用编译器优化并强制所有线程在单个处理器上运行。处理器永远不会发现其自身内存效应的问题，即使线程在任意时间被抢占和调度也是如此。一些编程语言甚至为在多处理器环境中运行的优化代码提供顺序一致性。在C++11中，您可以将所有共享变量声明为具有默认内存排序约束的C++11原子类型。在Java中，您可以将所有共享变量标记为易变的。这是我以前的帖子中的一个示例，以C++11风格重写：std::atomic
