互斥锁是如何实现的？

Question

一些实现在特定应用方面比其他实现更好吗？自己开展有什么收益？

- static_rtti

---

自己推出产品是否有所收益？知识方面的？ - Chris Lutz

自己编写代码有什么好处吗？是的，会得到有缺陷的代码！;) - Mitch Wheat

@Mitch Wheat - 当然，生产代码不应该使用自制的互斥锁库，但很多人喜欢通过实践学习，并编写自己的[应用程序 x]非常有启发性。 - Chris Lutz

原文：Atomic CAS has to be done in the hardware, so truly rolling your own is impossible. 翻译：原子比较并交换指令必须在硬件上执行，所以完全自己编写是不可能的。 - daveb

很多人提到了测试和设置以及比较和交换...但在许多RISC架构中，有一种称为load-link store-conditional的东西。这是一种非常有趣的替代方式，在这些CPU上实现原子基元，其中您有一个特殊的加载指令来设置“保留”和可以“失败”的存储操作。在此期间，您可以使用普通操作码进行计算。如果存储失败，则可以假定存在竞争并重试。 - asveikau

Answer 1

查看维基百科上Test-and-set机器指令的描述，这暗示了原子操作是如何在机器级别实现的。我可以想象大多数语言级别的互斥锁实现都依赖于诸如Test-and-set之类的机器级别支持。

- Adamski

---

例如，在x86上，您可以使用“xchg”指令来原子交换寄存器和内存。存储部分是“设置”，而加载部分+根据寄存器值进行分支是测试和设置操作的“测试”一半。是的，这或多或少是您在实践中所做的。请参见此最小化的汇编自旋锁实现，它执行了除在旋转一段时间后未获取锁而回退到系统调用睡眠之外的大部分重要操作。链接 - Peter Cordes

测试和设置仅允许尝试锁定，而不是锁定等待。您需要一个系统调用来实际挂起线程，而不是忙等待。 - undefined

Answer 2

在Adamski的test-and-set建议的基础上，你还应该了解"快速用户空间互斥锁"或futexes的概念。

Futexes具有理想的属性，即在锁定或解锁未争用的互斥锁的常见情况下，它们不需要内核系统调用。在这些情况下，用户模式代码成功使用原子比较并交换（CAS）操作来锁定或解锁互斥锁。

如果CAS失败，则互斥锁被争用，并且必须使用内核系统调用--在Linux下是sys_futex--以等待互斥锁（在锁定情况下）或唤醒其他线程（在解锁情况下）。

如果你认真考虑自己实现这个功能，请确保还阅读Ulrich Drepper的paper。

- David Joyner

Answer 3

一个互斥锁最好在操作系统内核中运行，同时尽可能使其周围的代码量尽可能少，这样它就可以避免在切换到另一个进程时被截断。因此，确切的实现有点秘密。但它并不复杂。基本上，它是一个具有布尔字段的对象，它获取和设置该字段。

• 使用计数器时，它可以变成一个信号量。
• 互斥锁是临界区的起点，它在内部使用互斥锁来查看是否可以进入代码区域。如果互斥锁是空闲的，它会设置互斥锁并执行代码，完成后释放互斥锁。当临界区注意到互斥锁被锁定时，它可以等待互斥锁被释放。

在基本互斥逻辑周围，有包装器将其包装成一个对象。然后有更多的包装器对象将其在内核外可用。然后又有另一个包装器将其在.NET中可用。然后几个程序员将编写自己的包装器代码以满足自己的逻辑需求。包装器周围的包装器使它们成为一个混沌的领域。

现在，有了关于互斥锁内部的基本知识，我希望您将使用依赖于内核和底层硬件的实现。这些将是最可靠的。（如果硬件支持这些。）如果您使用的互斥锁不在此内核/硬件级别上工作，则仍然可以可靠，但我建议不要使用它，除非没有其他选择。

据我所知，Windows、Linux和.NET都将在内核/硬件级别上使用互斥锁。

我已经链接的维基百科页面更详细地解释了内部逻辑和可能的实现。最好是由硬件控制互斥锁，从而使整个获取/设置互斥锁成为一个不可分割的步骤。(只是为了确保系统在其中不会切换任务。)

- Wim ten Brink

---

你是什么意思？这难道不是整个 Linux 内核源代码都在 GitHub 上可用吗？ - Sri Hari Vignesh

哦，天啊。我写那个已经8年了！ :) 但是，是一个秘密，因为没有人真正检查Linux内核中互斥锁的源代码。而那些检查它的人通常会发现解密其背后的逻辑很困难。请参见https://github.com/torvalds/linux/blob/master/kernel/locking/mutex.c以获取Linux中Mutex代码...幸运的是，它有很好的注释。尽管如此，仍然很复杂。就像我说的，*有点*秘密... - Wim ten Brink

是的。而且这个很棒的答案在许多其他答案下面有点秘密 :D - hqt

Answer 4

展示原子锁的一点汇编代码：

以下是一些汇编代码，用于演示原子锁：

; BL is the mutex id
; shared_val, a memory address

CMP [shared_val],BL ; Perhaps it is locked to us anyway
JZ .OutLoop2
.Loop1:
CMP [shared_val],0xFF ; Free
JZ .OutLoop1 ; Yes
pause ; equal to rep nop.
JMP .Loop1 ; Else, retry

.OutLoop1:

; Lock is free, grab it
MOV AL,0xFF
LOCK CMPXCHG [shared_val],BL
JNZ .Loop1 ; Write failed

.OutLoop2: ; Lock Acquired

- Michael Chourdakis

Answer 5

Interlocked.CompareExchange足以实现自旋锁。但要正确地进行此操作相当困难。请参考Joe Duffy的博客，了解其涉及的微妙之处。

- Joren

---

我们在谈论与语言无关的解决方案，但感谢您的努力。 - static_rtti

哦，你说得对。我不知道为什么会想到.NET。也许是因为其他答案的缘故。 - Joren

Answer 6

我使用Reflector.NET反编译了System.Threading.ReaderWriterLockSlim的源代码，这个类是最近版本的.NET框架中添加的。

它主要使用Interlocked.CompareExchange、Thread.SpinWait和Thread.Sleep来实现同步。在某些情况下，会使用一些EventWaitHandle（内核对象）实例。

还有一些复杂性被添加以支持单线程上的可重入性。

如果你对这个领域感兴趣并且在.NET中工作（或者至少能够阅读它），那么你可能会发现检查这个类非常有趣。

- Drew Noakes