Mutex的实现原理 - 21ic电子网

推荐阅读这份资料：OSTEP锁章节(https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf)

这份文档是关于并发编程中锁（Locks）的详细介绍和讨论。文档从锁的基本概念出发，探讨了如何在多线程环境中保护共享资源，避免竞态条件。以下是文档的详细翻译：

锁：基本概念

在并发编程中，我们希望一系列指令能够原子性地执行，但由于单个处理器上的中断存在（或者多个线程在多个处理器上并发执行），我们无法实现。本章直接解决这个问题，介绍了锁的概念。程序员在源代码中使用锁来标注临界区，确保这些临界区的执行就像是单个原子指令一样。

举例来说，假设我们的临界区是这样的，对共享变量的典型更新：

balance = balance + 1;

当然，还有其他可能的临界区，比如向链表添加元素或其他更复杂的共享结构更新，但我们现在只保持这个简单的例子。使用锁，我们在临界区周围添加一些代码，如下所示：

lock_t mutex; // 一些全局分配的锁 'mutex' ...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

锁只是一个变量，因此要使用它，你必须声明某种类型的锁变量（如上面的mutex）。这个锁变量（或简称"锁"）保存了锁在任何时刻的状态。它要么是可用的（或未锁定或空闲），这意味着没有线程持有锁，要么是已获取的（或锁定或持有），这意味着恰好有一个线程持有锁，并且假定它处于临界区。我们还可以在数据类型中存储其他信息，比如哪个线程持有锁，或者一个用于锁定获取顺序的队列，但这些信息对锁的用户是隐藏的。lock()和unlock()例程的语义很简单。调用lock()例程尝试获取锁；如果没有其他线程持有锁（即它是空闲的），线程将获取锁并进入临界区；这个线程有时被称为锁的拥有者。

如果另一个线程然后对同一个锁变量（本例中的mutex）调用lock()，它将在锁被另一个线程持有时不会返回；这样，其他线程就被阻止在第一个持有锁的线程在里面时进入临界区。一旦锁的拥有者调用unlock()，锁现在又可用（空闲）了。如果没有其他线程在等待锁（即没有其他线程调用lock()并卡在那里），锁的状态就简单地变为自由。

如果有等待线程（卡在lock()中），它们中的一个将（最终）注意到（或被告知）锁状态的变化，获取锁，并进入临界区。锁为程序员提供了一些最基本的调度控制。一般来说，我们认为线程是由程序员创建但由操作系统调度的实体，以操作系统选择的任何方式。锁将其中一些控制权还给了程序员；通过在代码段周围放置一个锁，程序员可以保证不会有多个线程同时在该代码中活跃。因此，锁帮助将传统的操作系统调度混乱转变为更有控制的活动。

Pthread 锁

POSIX库中锁的名称是互斥锁（mutex），因为它用于在多个线程之间提供互斥，即如果一个线程处于临界区，它会排除其他线程进入，直到它完成该部分。因此，当你看到以下POSIX线程代码时，你应该理解它与上面做的是同一件事（我们再次使用我们的包装器，在锁和解锁时检查错误）：

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
...
Pthread_mutex_lock(&lock); // 包装器；在失败时退出 balance = balance + 1;
Pthread_mutex_unlock(&lock);

你可能还会注意到这里POSIX版本传递了一个变量来锁定和解锁，因为我们可能使用不同的锁来保护不同的变量。这样做可以增加并发性：而不是使用一个大锁（粗粒度锁定策略），每当任何临界区被访问时，我们通常会用不同的锁来保护不同的数据和数据结构，从而允许更多的线程同时处于锁定代码中（更细粒度的方法）。

构建一个锁

到目前为止，你应该已经从程序员的角度理解了锁的工作原理。但我们应该如何构建一个锁？需要什么硬件支持？需要什么操作系统支持？在本章的其余部分，我们将解决这个问题。

关键问题：如何构建一个锁？有效的锁以低成本提供互斥，并且可能获得我们在下面讨论的其他一些属性。需要什么硬件支持？需要什么操作系统支持？

要构建一个工作的锁，我们将需要我们老朋友硬件的帮助，以及我们好朋友操作系统。多年来，各种计算机架构的指令集中添加了许多不同的硬件原语；虽然我们不会研究这些指令是如何实现的（毕竟，那是计算机体系结构课程的主题），但我们将研究如何使用它们来构建像锁这样的互斥原语。我们还将研究操作系统如何参与其中，完成整个画面，使我们能够构建一个复杂的锁定库。

评估锁

在构建任何锁之前，我们应该首先理解我们的目标是什么，因此我们问如何评估特定锁实现的有效性。评估锁是否有效（并且工作得很好），我们应该建立一些基本标准。第一个是锁是否完成了它的基本任务，即提供互斥。

基本上，锁是否有效，防止多个线程进入临界区？第二个是公平性。每个争夺锁的线程在锁空闲时都有公平的机会获取它吗？另一种看待这个问题的方式是通过检查更极端的情况：是否有线程在争夺锁时饿死了，因此从未获得它？最后的标准是性能，特别是使用锁增加的时间开销。这里有几个值得考虑的不同情况。

一个是无争用的情况；当单个线程运行并获取和释放锁时，这样做有什么开销？

另一个是多个线程在单个CPU上争夺锁的情况；在这种情况下，是否有性能问题？最后，当有多个CPU参与，每个CPU上的线程都在争夺锁时，锁的性能如何？通过比较这些不同的场景，我们可以更好地理解使用各种锁定技术的性能影响，如下所述。

控制中断

最早用于提供互斥的解决方案之一是为临界区禁用中断；这种解决方案是为单处理器系统发明的。代码如下所示：

void lock() {
 DisableInterrupts();
} void unlock() {
 EnableInterrupts();
}

假设我们运行在这样的单处理器系统上。通过在进入临界区之前关闭中断（使用某种特殊的硬件指令），我们确保临界区内的代码不会被中断，因此将像原子操作一样执行。当我们完成时，我们重新启用中断（再次通过硬件指令），因此程序照常进行。

这种方法的主要优点是其简单性。你肯定不必太费劲就能弄清楚为什么这有效。没有中断，线程可以确信它执行的代码将被执行，没有其他线程会干扰它。不幸的是，缺点很多。首先，这种方法要求我们允许任何调用线程执行特权操作（打开和关闭中断），因此相信这种设施不会被滥用。正如你已经知道的，任何时候我们被要求相信任意程序，我们可能都有麻烦了。

在这里，麻烦以多种方式表现出来：一个贪婪的程序可以在执行开始时调用lock()，从而垄断处理器；更糟的是，一个出错或恶意的程序可以在调用lock()后进入无限循环。在这种情况下，操作系统永远不会重新获得系统的控制权，只有一个解决办法：重新启动系统。使用中断禁用作为通用同步解决方案需要对应用程序过于信任。

其次，这种方法在多处理器上不起作用。如果多个线程在不同的CPU上运行，并且每个都试图进入同一个临界区，不管是否禁用了中断；线程将能够在其他处理器上运行，因此可能进入临界区。由于多处理器现在已经很常见，我们的通用解决方案将不得不做得比这更好。第三，长时间关闭中断可能导致中断丢失，这可能导致严重的系统问题。例如，想象一下，如果CPU错过了磁盘设备完成读请求的事实。操作系统将如何知道唤醒等待所述读取的进程？

一个失败的尝试：仅使用加载/存储

要超越基于中断的技术，我们将不得不依赖CPU硬件和它为我们提供的指令来构建一个合适的锁。让我们首先尝试使用一个标志变量来构建一个简单的锁。在这个失败的尝试中，我们将看到构建锁所需的一些基本思想，并（希望）看到为什么仅使用单个变量并通过正常的加载和存储访问它是不够的。在这个第一次尝试（图28.1）中，想法非常简单：使用一个简单的变量（标志）来指示某个线程是否拥有锁。第一个进入临界区的线程将调用lock()，它测试标志是否等于1（在这种情况下，不是），然后将标志设置为1，以表明该线程现在持有锁。当完成临界区后，线程调用unlock()并清除标志，从而表明锁不再被持有。

如果另一个线程恰好在第一个线程在临界区时调用lock()，它将简单地在while循环中自旋等待，等待该线程调用unlock()并清除标志。一旦第一个线程这样做，等待的线程将退出while循环，为自己将标志设置为1，并继续进入临界区。不幸的是，代码有两个问题：一个是正确性问题，另一个是性能问题。一旦你习惯了并发编程的思考，正确性问题就很容易看到。想象一下图28.2中的代码交错；假设标志=0开始。正如你从这个交错中看到的，通过及时（不合时宜？）的中断，我们很容易产生一个情况，两个线程都设置标志为1，因此两个线程都能够进入临界区。这种行为是专业人士所说的"糟糕"——我们显然未能提供最基本的要求：提供互斥。

我们将在后面更详细地解决性能问题，即线程等待获取已经持有的锁的方式：它不断地检查标志的值，这种技术被称为自旋等待。自旋等待浪费了等待另一个线程释放锁的时间。在单处理器上，浪费尤其高，因为等待的线程等待的线程甚至不能运行（至少，直到上下文切换发生！）。因此，随着我们向前发展并开发出更复杂的解决方案，我们也应该考虑避免这种浪费的方法。

使用测试和设置构建工作的自旋锁

因为禁用中断在多个处理器上不起作用，而且简单的使用加载和存储的方法（如上所示）也不起作用，系统设计者开始发明锁定的硬件支持。最早的多处理器系统，如1960年代初的Burroughs B5000 [M82]，有这样的支持；今天所有系统都提供这种类型的支持，即使是单CPU系统。最简单的硬件支持是众所周知的测试和设置（或原子交换1）指令。我们通过以下C代码片段定义测试和设置指令的作用：

int TestAndSet(int *old_ptr, int new) { int old = *old_ptr; // 获取old_ptr处的旧值 *old_ptr = new; // 将'new'存储到old_ptr return old; // 返回旧值 }

每个支持测试和设置的架构都用不同的名称来称呼它。在SPARC上，它被称为加载/存储无符号字节指令（ldstub）；在x86上，它是原子交换（xchg）的锁定版本。

评估自旋锁

鉴于我们的基本自旋锁，我们现在可以沿着我们之前描述的轴评估它的有效性。锁最重要的方面是正确性：它是否提供互斥？答案是肯定的：自旋锁只允许单个线程一次进入临界区。因此，我们有一个正确的锁。下一个轴是公平性。自旋锁对等待线程有多公平？你能保证等待线程最终会进入临界区吗？不幸的是，这里的答案是坏消息：自旋锁不提供任何公平性保证。事实上，一个自旋的线程可能会永远自旋，在争用中。简单的自旋锁（到目前为止讨论的）是不公平的，可能导致饥饿。最后一个轴是性能。

使用自旋锁的成本是什么？为了更仔细地分析这个问题，我们建议考虑几种不同的情况。首先，想象线程在单个处理器上争夺锁；其次，考虑线程分布在许多CPU上。对于自旋锁，在单个CPU的情况下，性能开销可能相当痛苦；想象一下，持有锁的线程在临界区内被抢占。调度器可能会运行每个其他线程（想象有N-1个其他线程），每个线程都试图获取锁。在这种情况下，这些线程中的每一个都会在时间片期间自旋，然后放弃CPU，浪费CPU周期。然而，在多个CPU上，自旋锁工作得相当好（如果线程的数量大致等于CPU的数量）。

思考如下：想象线程A在CPU 1上，线程B在CPU 2上，都争夺一个锁。如果线程A（CPU 1）抓住了锁，然后线程B尝试，B将在（CPU 2上）自旋。然而，假设临界区很短，很快锁就可用，被线程B获取。在这种情况下，等待另一个处理器上持有的锁并不会浪费太多周期，因此可以是有效的。

比较和交换

一些系统提供的另一个硬件原语被称为比较和交换指令（例如，在SPARC上），或比较和交换（在x86上）。这个单指令的C伪代码可以在图28.4中找到。基本思想是比较和交换测试ptr指定的地址处的值是否等于expected；如果是，用新值更新ptr指向的内存位置。

如果不是，什么也不做。在这两种情况下，返回该内存位置的原始值，从而允许调用比较和交换的代码知道它是否成功。有了比较和交换指令，我们可以以与测试和设置非常相似的方式构建锁。例如，我们可以简单地将上面的lock()例程替换为以下内容：

void lock(lock_t *lock) { while (CompareAndSwap(&lock->flag, 0, 1) == 1)
 ; // 自旋 }

其余代码与上面的测试和设置示例相同。这段代码的工作方式相当相似；它只是检查标志是否为0，如果是，则原子地交换1，从而获取锁。试图在持有锁时获取锁的线程将被卡住自旋，直到锁最终被释放。

如果你想看看如何真正制作一个C可调用的x86版本的比较和交换，代码序列（来自[S05]）可能很有用2。最后，正如你可能已经感觉到的，比较和交换是一个比测试和设置更强大的指令。我们将在未来简要探讨锁无关同步[H91]等主题时利用这种力量的一些用途。然而，如果我们只是用它构建一个简单的自旋锁，它的行为与我们上面分析的自旋锁相同。

加载链接和存储条件

一些平台提供了一对指令，它们协同工作以帮助构建临界区。例如，在MIPS架构[H93]上，加载链接和存储条件指令可以一起使用来构建锁和其他并发结构。这些指令的C伪代码可以在图28.5中找到。Alpha、PowerPC和ARM提供了类似的指令[W09]。加载链接的操作与典型的加载指令非常相似，它只是从内存中获取一个值并将其放入寄存器中。

存储条件的关键区别在于，它只有在没有对地址进行干预存储的情况下才会成功（并更新刚刚从加载链接中加载的地址处的值）。在成功的情况下，存储条件返回1并更新ptr处的值为value；如果失败，ptr处的值不会更新，返回0。作为对自己的挑战，尝试思考如何使用加载链接和存储条件构建锁。然后，当你完成时，看看下面的代码，它提供了一个简单的解决方案。去做吧！lock()代码是唯一有趣的部分。首先，线程自旋等待标志被设置为0（从而表明锁没有被持有）。

一旦如此，线程尝试通过存储条件获取锁；如果成功，线程已经原子地将标志的值更改为1，因此可以继续进入临界区。注意存储条件失败可能发生的情况。一个线程调用lock()并执行加载链接，返回0，因为锁没有被持有。在它可以尝试存储条件之前，它被中断，另一个线程进入锁代码，也执行加载链接指令，

int LoadLinked(int *ptr) { return *ptr;
} int StoreConditional(int *ptr, int value) { if (no update to *ptr since LL to this addr) {
 *ptr = value; return 1; // 成功！ } else { return 0; // 更新失败 }
}

并且也得到0并继续。此时，两个线程都已经执行了加载链接，每个线程都即将尝试存储条件。这些指令的关键特性是，只有其中一个线程会成功更新标志为1并因此获得锁；第二个尝试存储条件的线程将失败（因为另一个线程在其加载链接和存储条件之间更新了标志的值），因此不得不尝试再次获取锁。几年前在课堂上，本科生David Capel提出了上述更简洁的形式，供那些喜欢短路布尔条件的人使用。看看你能否弄清楚为什么它等价。它当然更短！

void lock(lock_t *lock) { while (LoadLinked(&lock->flag) ||
 !StoreConditional(&lock->flag, 1))
 ; // 自旋 }

获取和添加

最后一个硬件原语是获取和添加指令，它原子地递增一个值，同时返回特定地址的旧值。获取和添加指令的C伪代码如下所示：

int FetchAndAdd(int *ptr) { int old = *ptr;
 *ptr = old + 1; return old;
}

在这个例子中，我们将使用获取和添加来构建一个更有趣的票锁，由Mellor-Crummey和Scott [MS91]引入。锁和解锁代码可以在图28.7（第14页）中找到。与单个值不同，这种解决方案结合了票和轮次变量来构建锁。基本操作非常简单：当线程希望获取锁时，它首先对票值进行原子获取和添加；该值现在被认为是该线程的"轮次"（myturn）。

全局共享的lock->turn用于确定哪个线程的轮次；当（myturn == turn）对于给定线程时，就是该线程进入临界区的时候。通过简单地递增turn来解锁，以便下一个等待的线程（如果有）现在可以进入临界区。

注意这个解决方案与我们之前的尝试的一个重要区别：它为所有线程确保了进展。一旦线程被分配了它的票值，它将在未来的某个时候被调度（一旦前面的线程通过临界区并释放了锁）。在我们之前的尝试中，没有这样的保证；一个在测试和设置上自旋的线程（例如）可能会永远自旋，即使其他线程获取和释放锁。

太多自旋：现在怎么办？

我们的基于硬件的锁很简单（只有几行代码），它们有效（如果你愿意，你甚至可以证明这一点，通过编写一些代码），这是任何系统或代码的两个极好的属性。然而，在某些情况下，这些解决方案可能非常低效。

想象一下你在单个处理器上运行两个线程。现在想象一个线程（线程0）在临界区内，因此持有锁，不幸的是被中断了。第二个线程（线程1）现在试图获取锁，但发现它被持有。因此，它开始自旋。然后它再自旋。然后它再自旋一些。最后，定时器中断发生，线程0再次运行，释放了锁，最后（下一次运行时，比如说），线程1不需要那么多自旋就能获取锁。

因此，任何时候线程被卡在自旋中，就像这样，它都会浪费整个时间片，什么都不做，只是检查一个不会改变的值！当N个线程争夺锁时问题变得更糟；N-1个时间片可能会以类似的方式被浪费，只是自旋等待一个线程释放锁。因此，我们接下来的问题：关键问题：如何避免在CPU上无谓地浪费时间自旋？

仅靠硬件支持无法解决问题。我们还需要操作系统支持！现在让我们弄清楚这可能如何工作。

一个简单的方法：只是让步，宝贝

硬件支持让我们走得相当远：工作的锁，甚至（如票锁的情况）在锁获取中的公平性。然而，我们仍然有一个问题：当上下文切换发生在临界区内，线程开始无休止地自旋等待被中断的（持有锁的）线程再次运行时，该怎么办？我们第一次尝试是一个简单而友好的方法：当你即将自旋时，相反，放弃CPU让另一个线程运行。正如Al Davis可能会说的，"只是让步，宝贝！"[D91]。图28.8（第15页）展示了这种方法。

在这个方法中，我们假设操作系统原始的yield()，当线程想要放弃CPU并让另一个线程运行时可以调用。线程可以处于三种状态之一（运行、就绪或阻塞）；yield只是一个系统调用，将调用者从运行状态移动到就绪状态，从而提升另一个线程到运行状态。因此，让步的线程基本上是自我调度的。考虑两个线程在单个CPU上的例子；在这种情况下，我们的基于让步的方法相当好。如果线程碰巧调用lock()并发现锁被持有，它将简单地让出CPU，因此另一个线程将运行并完成其临界区。

在这个简单的案例中，让步方法工作得很好。现在让我们考虑有许多线程（比如说100个）反复争夺锁的情况。在这种情况下，如果一个线程获取了锁并在释放它之前被抢占，其他99个将各自调用lock()，发现锁被持有，并让出CPU。假设某种轮询调度器，99个中的每一个都将执行这个运行和让步模式，然后持有锁的线程再次运行。

虽然比我们的自旋方法更好（这将浪费99个时间片自旋），这种方法仍然成本很高；上下文切换的成本可能相当大，因此有很多浪费。更糟的是，这种方法没有解决饥饿问题。线程可能会陷入无尽的让步循环，而其他线程反复进入和退出临界区。我们显然需要一种直接解决饥饿问题的方法。

使用队列：睡眠而不是自旋

一些先前方法（除了票锁）的真正问题是，它们留给机会太多。调度器决定了下一个运行的线程；如果调度器做出了错误的选择，运行的线程必须要么自旋等待锁（我们的第一种方法），要么立即让出CPU（我们的第二种方法）。无论如何，都有浪费的潜力，也没有防止饥饿的方法。

因此，我们必须明确控制哪个线程在当前持有者释放锁后下一个获得锁。为此，我们将需要更多的操作系统支持，以及一个队列来跟踪哪些线程正在等待获取锁。为简单起见，我们将使用Solaris提供的支持，以两个调用的形式：park()让调用线程睡眠，unpark(threadID)唤醒由threadID指定的特定线程。这两个例程可以一起使用，构建一个锁，如果调用者试图获取一个被持有的锁，就让调用者睡眠，并在锁空闲时唤醒它。让我们看看图28.9中的代码，以理解这种原始的一种可能用途。

不同的操作系统，不同的支持

到目前为止，我们已经看到了操作系统可以提供的一种支持，以构建线程库中更有效的锁。其他操作系统提供了类似的支持；细节各不相同。例如，Linux提供了futex，它与Solaris接口类似，但提供了更多的内核功能。具体来说，每个futex都有一个与之相关的特定物理内存位置，以及一个每futex的内核队列。调用者可以使用futex调用（下面描述）来睡眠和唤醒，如需。具体来说，有两个调用可用。调用futex wait(address, expected)让调用线程睡眠，假设address处的值等于expected。如果它不相等，调用立即返回。调用例程futex wake(address)唤醒等待在队列上的一个线程。

图28.10（第19页）中展示了这些调用在Linux互斥锁中的使用。这个代码片段来自nptl库（GNU libc库的一部分）[L09]中的lowlevellock.h，由于几个原因很有趣。首先，它使用一个整数来跟踪锁是否被持有（整数的最高位）以及锁上的等待者数量（所有其他位）。因此，如果锁是负数，它就被持有（因为最高位被设置，而该位决定了整数的符号）。

其次，代码片段展示了如何针对常见情况进行优化，特别是当没有锁争用时；只有一个线程获取和释放锁时，做的工作很少（原子位测试和设置以锁定和原子加以释放锁）。看看你能否弄清楚这个"真实世界"锁的其余部分是如何工作的。去做吧，成为Linux锁定的大师，或者至少是当一本书告诉你去做某事时会听的人3。

两阶段锁

最后一点：Linux方法有一种旧方法的味道，多年来时而使用，至少可以追溯到1960年代初的Dahm锁[M82]，现在被称为两阶段锁。两阶段锁意识到自旋可能是有用的，特别是如果锁即将被释放。因此，在第一阶段，锁自旋一段时间，希望它可以获取锁。然而，如果在第一阶段自旋期间没有获取锁，则进入第二阶段，在此阶段，调用者被放入睡眠状态，只有在锁稍后变为空闲时才会被唤醒。

上面的Linux锁是一种这样的锁，但它只自旋一次；这种锁的一般化可以在使用futex支持睡眠之前，在循环中自旋固定时间。两阶段锁是混合方法的另一个实例，结合两个好主意确实可能产生一个更好的主意。当然，是否如此取决于许多事情，包括硬件环境、线程数量和其他工作负载细节。像往常一样，制造一个适用于所有可能用例的通用锁是非常具有挑战性的。

总结

上述方法展示了如今如何构建真正的锁：一些硬件支持（以更强大的指令形式）加上一些操作系统支持（例如，在Solaris上的park()和unpark()原语，或Linux上的futex）。当然，细节各不相同，执行这种锁定的确切代码通常高度优化。如果你想了解更多细节，可以查看Solaris或Linux代码库；它们是非常有趣的阅读[L09, S09]。还可以查看David等人的优秀工作，比较现代多处理器上不同的锁定策略[D+13]。

文档的最后部分提供了一些参考文献，以及一些关于并发编程和锁的实验性问题，这些问题旨在帮助读者更好地理解锁的工作原理和它们在并发环境中的行为。

现在不少朋友都在准备校招，常规的技术学习只是提高了代码能力，还没有提升从 0 到 1 整体做项目和解决问题的能力！

为此我们特别推出了C++训练营，带着你从 0 到 1 做 C++ 项目（你可以从项目池中任选项目），帮助你提升做项目的能力，提升从0到1的能力，熟悉做项目的完整流程，比如开发环境、编译脚本、架构设计、框架搭建、代码发布、问题调试、单元测试。

除了上面的，还有需求分析、项目规划、架构设计、任务拆解、时间规划、版本管理。另外做项目的过程中必然会遇到种种问题，可以逐步提升你的调试能力，分析问题的能力，掌握更多的调试手段。

遇到棘手的问题，我们还有专门的导师1V1答疑解惑，给出具体建议。

项目池里面的项目，是导师团队花费大量时间完成的，不仅有完整的代码及清晰的注释还有详细的文档和视频，并且有专门的项目导师答疑，完全不用担心自己学不会。