在没有 XCHG 的情况下实现自旋锁？

Question

C++ 自旋锁可以使用std::atomic_flag轻松实现，它可以粗略地编码（没有特殊功能），如下所示：

std::atomic_flag f = ATOMIC_FLAG_INIT;

while (f.test_and_set(std::memory_order_acquire)); // Acquire lock
// Here do some lock-protected work .....
f.clear(std::memory_order_release); // Release lock

可以看到在线汇编，说明获取是通过XCHG指令原子实现的。

另外，正如人们在 uops.info（此处的屏幕）上看到的那样，XCHG 可能会占用30相当流行的 Skylake 上的 CPU 周期。这是相当慢的。

通过这样的程序可以测量自旋锁的整体速度。

是否可以在没有 XCHG 的情况下实现自旋锁定？主要关心的是速度，而不仅仅是使用另一条指令。

最快的自旋锁是什么？是否可以将其改为 10 个周期而不是 30 个？还有5个周期？也许是一些平均运行速度很快的概率自旋锁？

它应该以严格的方式实施，这意味着在 100% 的情况下它可以正确保护代码和数据。如果它是概率性的，那么它应该运行可能的时间，但每次运行后仍能 100% 正确地保护。

对我来说，这种自旋锁的主要目的是保护多个线程内非常小的操作，这些操作运行十几个或两个周期，因此 30 个周期的延迟太大了。当然可以说我可以使用原子或其他无锁技术来实现所有操作。但这种技术并不适用于所有情况，并且还需要花费大量工作才能在许多类和方法的庞大代码库中严格实现。因此，还需要一些通用的东西，比如常规的自旋锁。

Answer 1

是否可以在没有 XCHG 的情况下实现自旋锁定？

是的。对于 80x86，您可以lock bts或lock cmpxchg或lock xadd或 ...

最快的自旋锁是什么？

“快”的可能解释包括：

a) 在无争议的情况下速度快。在这种情况下，你做什么并不重要，因为大多数可能的操作（交换、添加、测试......）都很便宜，真正的成本是缓存一致性（将包含锁的缓存行获取到“独占”） “当前 CPU 缓存中的状态，可能包括从 RAM 或其他 CPU 缓存中获取它）和序列化。

b) 在有争议的情况下快速。在这种情况下，您确实需要一种“无锁测试；然后带锁测试和设置”的方法。简单自旋循环（对于有争议的情况）的主要问题是，当多个 CPU 旋转时，高速缓存行将快速从一个 CPU 的高速缓存跳到下一个 CPU，并白白消耗大量互连带宽。为了防止这种情况，您需要一个循环来测试锁定状态而不修改它，以便在这些 CPU 旋转时，缓存行可以同时保留在所有 CPU 缓存中作为“共享”。

但请注意，一开始测试只读可能会损害无竞争的情况，从而导致更多的一致性流量：首先对缓存行进行共享请求，如果另一个核心最近解锁，则只会获得 MESI S 状态，然后当您尝试获取锁定时会收到 RFO（读取所有权）。因此，最佳实践可能是从 RMW 开始，如果失败，则旋转只读，pause直到看到可用的锁，除非在您关心的系统上分析代码表明不同的选择更好。

c) 获取锁后快速退出自旋循环（争用后）。在这种情况下，CPU 可以推测性地执行循环的多次迭代，并且当获取锁时，所有 CPU 都必须耗尽那些“推测性地执行循环的多次迭代”，这会花费一点时间。为了防止这种情况，您需要一条pause指令来防止推测执行循环的多次迭代。

d) 对于其他不接触锁的 CPU 来说速度很快。对于某些情况（超线程），核心的资源在逻辑处理器之间共享；当一个逻辑进程旋转时，它会消耗其他逻辑处理器本可以用来完成有用工作的资源（特别是对于“自旋锁推测性地执行循环的多次迭代”情况）。为了最大限度地减少这种情况，您需要pause在 spinloop/s 中使用一个（这样旋转逻辑处理器就不会消耗尽可能多的核心资源，并且核心中的其他逻辑处理器可以完成更多有用的工作）。

e) 最小“最坏情况下的获取时间”。对于简单的锁，在争用情况下，某些 CPU 或线程可能很幸运并且总是获得锁，而其他 CPU/线程则非常不幸并且需要​​很长时间才能获得锁；并且“最坏情况下的获取时间”理论上是无限的（CPU 可以永远旋转）。要解决这个问题，您需要一个公平锁 - 确保只有等待/旋转时间最长的线程才能在释放锁时获取锁。请注意，可以设计一个公平锁，使每个线程在不同的缓存行上旋转；这是解决我在“b) 在竞争情况下快速”中提到的“CPU 之间缓存行弹跳”问题的不同方法。

f) 最小“锁释放前的最坏情况”。这必须涉及最差临界区的长度；但在某些情况下，还可能包括任意数量的 IRQ 的成本、任意数量的任务切换的成本以及代码不使用任何 CPU 的时间。完全有可能出现这样的情况：线程获取锁，然后调度程序进行线程切换；那么许多CPU都在一个无法释放的锁上旋转（浪费大量时间）（因为锁持有者是唯一可以释放锁的人，而且它甚至没有使用任何CPU）。解决/改进这个问题的方法是禁用调度程序和 IRQ；这在内核代码中很好，但在正常的用户空间代码中“出于安全原因可能不可能”。这也是为什么自旋锁可能永远不应该在用户空间中使用的原因（以及为什么用户空间可能应该使用互斥锁，其中线程处于“阻塞等待锁”状态，并且调度程序不会给定 CPU 时间，直到/除非线程实际上可以获取锁）。

请注意，对于“快”的一种可能解释来说，使其变快可能会使“快”的其他解释变慢/更差。例如; 其他一切都使无争议案件的速度变得更糟。

自旋锁示例

此示例未经测试，并以（NASM 语法）汇编语言编写。

;Input
; ebx = address of lock

;Initial optimism in the hope the lock isn't contended
spinlock_acquire:
    lock bts dword [ebx],0      ;Set the lowest bit and get its previous value in carry flag
                                ;Did we actually acquire it, i.e. was it previously 0 = unlocked?
    jnc .acquired               ; Yes, done!

;Waiting (without modifying) to avoid "cache line bouncing"

.spin:
    pause                       ;Reduce resource consumption
                                ; and avoid memory order mis-speculation when the lock becomes available.
    test dword [ebx],1          ;Has the lock been released?
    jne .spin                   ; no, wait until it was released

;Try to acquire again

    lock bts dword [ebx],0      ;Set the lowest bit and get its previous value in carry flag
                                ;Did we actually acquire it?
    jc .spin                    ; No, go back to waiting

.acquired:

自旋解锁可以是mov dword [ebx], 0，也可以不是lock btr，因为您知道您拥有该锁并且在 x86 上具有释放语义。您可以先阅读它以捕获双重解锁错误。

笔记：

A）lock bts比其他可能性慢一点；但它不会干扰或依赖于锁的其他 31 位（或 63 位），这意味着这些其他位可用于检测编程错误（例如存储“当前持有锁的线程 ID”的 31 位）在获取锁时检查它们，并在释放锁时检查它们以自动检测“错误的线程释放锁”和“从未获取锁时释放锁”错误）和/或用于收集性能信息（例如设置位） 1 当存在争用时，以便其他代码可以定期扫描以确定哪些锁很少争用以及哪些锁争用严重）。使用锁的错误通常非常阴险且难以发现（不可预测且不可重现的“Heisenbug”，一旦您试图找到它们，它们就会消失）；所以我更喜欢“自动错误检测速度较慢”。

b) 这不是公平锁，这意味着它不太适合可能发生争用的情况。

c) 用于记忆；内存消耗/缓存未命中和错误共享之间存在折衷。对于很少竞争的锁，我喜欢将锁放在与锁保护的数据相同的缓存行中，这样获取锁就意味着锁持有者想要的数据已经在缓存中（并且不会发生后续缓存未命中） ）。对于竞争激烈的锁，这会导致错误共享，应该通过为锁保留整个缓存行而不做任何其他事情来避免（例如，在实际锁使用的 4 个字节之后添加 60 个字节的未使用填充，就像在 C++ 中一样alignas(64) struct { std::atomic<int> lock; };）。当然，像这样的自旋锁不应该用于激烈竞争的锁，因此可以合理地假设最小化内存消耗（并且没有任何填充，并且不关心错误共享）是有意义的。

对我来说，这种自旋锁的主要目的是保护多个线程内非常小的操作，这些操作运行十几个或两个周期，因此 30 个周期的延迟太大了开销

在这种情况下，我建议尝试用原子、无块算法和无锁算法来替换锁。一个简单的例子是跟踪统计信息，您可能想要这样做lock inc dword [number_of_chickens]而不是获取锁来增加“ number_of_chickens”。

除此之外，很难说太多 - 对于一种极端情况，程序可能将大部分时间花在不需要锁的情况下完成工作，并且锁定的成本可能对整体性能几乎没有影响（即使获取/释放比获取/释放更昂贵）微小的关键部分）；对于另一个极端，程序可能将大部分时间花费在获取和释放锁上。换句话说，获取/释放锁的成本介于“无关紧要”和“重大设计缺陷（使用太多锁并需要重新设计整个程序）”之间。