在没有 XCHG 的情况下实现自旋锁？
Implementing spin-lock without XCHG?
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
一个可以see online assembly, it shows that acquiring is implemented atomically through XCHG指令。
还可以看到 on uops.info (screen here) XCHG 在相当流行的 Skylake 上可能需要 30 CPU 个周期。这很慢。
自旋锁的整体速度可以通过such program.
来衡量
是否可以在没有XCHG的情况下实现自旋锁定？主要关注的是速度，而不仅仅是使用另一条指令。
最快的自旋锁是什么？是否有可能使其成为 10 个周期而不是 30 个？ 5个周期？也许一些概率自旋锁 运行 平均速度很快？
它应该以严格的方式实现，这意味着在 100% 的情况下它正确地保护了一段代码和数据。如果它是概率性的，那么它应该 运行 可能的时间，但在每个 运行.
之后仍能正确保护 100%
对我来说，这种自旋锁的主要目的是保护多个线程内非常小的操作，运行 一打或两个周期，因此 30 个周期的延迟开销太大。当然可以说我可以使用原子或者其他无锁技术来实现所有的操作。但这种技术并非适用于所有情况，而且还需要大量工作才能在庞大的代码库中严格实施许多 类 和方法。因此，还需要一些通用的东西，比如常规的自旋锁。
Is it possible to implement spin locking without XCHG?
是的。对于 80x86，您可以 lock bts 或 lock cmpxchg 或 lock xadd 或 ...
What is the fastest possible spin lock?
“快”的可能解释包括：
a) 在无竞争的情况下速度很快。在这种情况下，你做什么并不重要，因为大多数可能的操作（交换、添加、测试......）都很便宜，而真正的成本是缓存一致性（将包含锁的缓存行放入“独占” " 当前 CPU 缓存中的状态，可能包括从 RAM 或其他 CPU 缓存中获取它）和序列化。
b) 在有争议的情况下速度很快。在这种情况下，您确实需要一种“无锁测试；然后带锁测试和设置”方法。一个简单的自旋循环（对于竞争案例）的主要问题是，当多个 CPU 正在旋转时，缓存行将快速从一个 CPU 的缓存跳转到下一个并消耗大量数据互连带宽免费。为防止这种情况，您将有一个循环来测试锁定状态而不修改它，以便缓存行可以同时保留在所有 CPUs 缓存中作为“共享”，而那些 CPUs正在旋转。
但请注意，开始时测试只读可能会损害非竞争情况，从而导致更多的一致性流量：首先是缓存行的共享请求，如果另一个核心有，它只会让你进入 MESI S 状态最近解锁，然后当您尝试获取锁时出现 RFO（Read For Ownership）。因此，最佳做法可能是从 RMW 开始，如果失败，则使用 pause 旋转只读直到您看到可用的锁，除非在您关心的系统上分析您的代码显示不同的选择更好。
c) 获取锁后快速退出自旋循环（争用后）。在这种情况下，CPU 可以推测性地执行循环的多次迭代，并且当获得锁时，所有 CPU 必须耗尽那些“推测性地执行循环的多次迭代”，这会花费一些时间。为防止您需要 pause 指令来防止 loop/s 的多次迭代被推测执行。
d) 其他 CPUs 不碰锁的快了。对于某些情况（超线程），核心资源在逻辑处理器之间共享；并且当一个逻辑进程正在旋转时，它会消耗另一个逻辑处理器本可以用来完成有用工作的资源（特别是对于“自旋锁推测性地执行循环的多次迭代”的情况）。为了最大限度地减少这种情况，您需要在自旋 loop/s 中使用 pause （这样旋转的逻辑处理器就不会消耗太多核心资源，并且核心中的其他逻辑处理器可以完成更多有用的工作).
e) 最小“最坏情况下的获取时间”。使用简单的锁，在争用下，一些 CPU 或线程可能很幸运并且总是获得锁，而其他 CPUs/threads 非常不幸并且需要很长时间才能获得锁;并且“最坏情况下的获取时间”在理论上是无限的（CPU 可以永远旋转）。要解决这个问题，您需要一个公平锁 - 确保只有 waiting/spinning 时间最长的线程才能在释放锁时获得锁。请注意，可以设计一个公平锁，使每个线程在不同的缓存行上旋转；这是解决我在“b) Fast in the contended case”中提到的“CPUs 之间的缓存行跳动”问题的不同方法。
f) 最小“锁释放前的最坏情况”。这不得不涉及到最坏临界区的长度；但在某些情况下，还可能包括任意数量的 IRQ 的成本、任意数量的任务切换的成本以及代码未使用任何 CPU 的时间。完全有可能出现线程获取锁然后调度程序进行线程切换的情况；然后许多 CPU 都在无法释放的锁上自旋（浪费了大量时间）（因为锁持有者是唯一可以释放锁的人，它甚至没有使用任何 CPU). fix/improve 的方法是禁用调度程序和 IRQ；这在内核代码中很好，但在普通用户 space 代码中“出于安全原因可能不可能”。这也是为什么 自旋锁可能永远不应该在 user-space 中使用的原因（以及为什么 user-space 应该在放置线程的地方使用互斥锁处于“阻塞等待锁”状态且调度程序未给 CPU 时间 until/unless 线程实际上可以获得锁）。
请注意，对于“快速”的一种可能解释使其快速可以使“快速”的其他解释slower/worse。例如;无竞争案例的速度因其他一切而变得更糟。
自旋锁示例
这个例子未经测试，用（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 位）在获取锁时在它们中并在释放锁时检查它们以自动检测“错误的线程释放锁”和“从未获取锁时释放锁”错误）and/or 用于收集性能信息（例如当存在争用时将位设置为 1，以便其他代码可以定期扫描以确定哪些锁很少争用，哪些锁争用很多）。使用锁的错误通常非常隐蔽且难以发现（不可预测且不可重现的“Heisenbugs”，一旦您试图找到它们就会消失）；所以我更喜欢“自动错误检测速度较慢”。
b) 这不是一个公平锁，这意味着它不太适合可能发生争用的情况。
c) 为了记忆；内存 consumption/cache 未命中和错误共享之间存在折衷。对于很少争用的锁，我喜欢把锁放在与锁保护的数据相同的缓存 line/s 中，这样获取锁意味着锁持有者想要的数据已经在缓存中（并且没有后续缓存错过发生）。对于竞争激烈的锁，这会导致虚假共享，应该通过为锁保留整个缓存行而不是其他任何东西来避免（例如，通过在实际锁使用的 4 个字节之后添加 60 个字节的未使用填充，就像在 C++ 中一样 alignas(64) struct { std::atomic<int> lock; };).当然，像这样的自旋锁不应该用于竞争激烈的锁，因此可以合理地假设最小化内存消耗（并且没有任何填充，并且不关心错误共享）是有意义的。
Main purpose for such spin lock for me is to protect very tiny operations inside multiple threads, that run a dozen or two of cycles, hence 30 cycles delay is too much overhead
在那种情况下，我建议尝试用原子、无块算法和无锁算法替换锁。一个简单的例子是跟踪统计信息，您可能想要执行 lock inc dword [number_of_chickens] 而不是获取锁来增加“number_of_chickens”。
除此之外很难说太多 - 对于一个极端情况，程序可能花费大部分时间在不需要锁的情况下完成工作，并且锁定的成本可能对整体性能几乎没有影响（即使 acquire/release 比微小的关键部分更昂贵）；对于另一个极端，程序可能将大部分时间花在获取和释放锁上。换句话说，acquiring/releasing 锁的成本介于“无关紧要”和“主要设计缺陷（使用太多锁并需要重新设计整个程序）”之间。
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
一个可以see online assembly, it shows that acquiring is implemented atomically through XCHG指令。
还可以看到 on uops.info (screen here) XCHG 在相当流行的 Skylake 上可能需要 30 CPU 个周期。这很慢。
自旋锁的整体速度可以通过such program.
来衡量是否可以在没有XCHG的情况下实现自旋锁定？主要关注的是速度，而不仅仅是使用另一条指令。
最快的自旋锁是什么？是否有可能使其成为 10 个周期而不是 30 个？ 5个周期？也许一些概率自旋锁 运行 平均速度很快？
它应该以严格的方式实现，这意味着在 100% 的情况下它正确地保护了一段代码和数据。如果它是概率性的，那么它应该 运行 可能的时间，但在每个 运行.
之后仍能正确保护 100%对我来说，这种自旋锁的主要目的是保护多个线程内非常小的操作，运行 一打或两个周期，因此 30 个周期的延迟开销太大。当然可以说我可以使用原子或者其他无锁技术来实现所有的操作。但这种技术并非适用于所有情况，而且还需要大量工作才能在庞大的代码库中严格实施许多 类 和方法。因此，还需要一些通用的东西，比如常规的自旋锁。
Is it possible to implement spin locking without XCHG?
是的。对于 80x86，您可以 lock bts 或 lock cmpxchg 或 lock xadd 或 ...
What is the fastest possible spin lock?
“快”的可能解释包括：
a) 在无竞争的情况下速度很快。在这种情况下，你做什么并不重要，因为大多数可能的操作（交换、添加、测试......）都很便宜，而真正的成本是缓存一致性（将包含锁的缓存行放入“独占” " 当前 CPU 缓存中的状态，可能包括从 RAM 或其他 CPU 缓存中获取它）和序列化。
b) 在有争议的情况下速度很快。在这种情况下，您确实需要一种“无锁测试；然后带锁测试和设置”方法。一个简单的自旋循环（对于竞争案例）的主要问题是，当多个 CPU 正在旋转时，缓存行将快速从一个 CPU 的缓存跳转到下一个并消耗大量数据互连带宽免费。为防止这种情况，您将有一个循环来测试锁定状态而不修改它，以便缓存行可以同时保留在所有 CPUs 缓存中作为“共享”，而那些 CPUs正在旋转。
但请注意，开始时测试只读可能会损害非竞争情况，从而导致更多的一致性流量：首先是缓存行的共享请求，如果另一个核心有，它只会让你进入 MESI S 状态最近解锁，然后当您尝试获取锁时出现 RFO（Read For Ownership）。因此，最佳做法可能是从 RMW 开始，如果失败，则使用 pause 旋转只读直到您看到可用的锁，除非在您关心的系统上分析您的代码显示不同的选择更好。
c) 获取锁后快速退出自旋循环（争用后）。在这种情况下，CPU 可以推测性地执行循环的多次迭代，并且当获得锁时，所有 CPU 必须耗尽那些“推测性地执行循环的多次迭代”，这会花费一些时间。为防止您需要 pause 指令来防止 loop/s 的多次迭代被推测执行。
d) 其他 CPUs 不碰锁的快了。对于某些情况（超线程），核心资源在逻辑处理器之间共享；并且当一个逻辑进程正在旋转时，它会消耗另一个逻辑处理器本可以用来完成有用工作的资源（特别是对于“自旋锁推测性地执行循环的多次迭代”的情况）。为了最大限度地减少这种情况，您需要在自旋 loop/s 中使用 pause （这样旋转的逻辑处理器就不会消耗太多核心资源，并且核心中的其他逻辑处理器可以完成更多有用的工作).
e) 最小“最坏情况下的获取时间”。使用简单的锁，在争用下，一些 CPU 或线程可能很幸运并且总是获得锁，而其他 CPUs/threads 非常不幸并且需要很长时间才能获得锁;并且“最坏情况下的获取时间”在理论上是无限的（CPU 可以永远旋转）。要解决这个问题，您需要一个公平锁 - 确保只有 waiting/spinning 时间最长的线程才能在释放锁时获得锁。请注意，可以设计一个公平锁，使每个线程在不同的缓存行上旋转；这是解决我在“b) Fast in the contended case”中提到的“CPUs 之间的缓存行跳动”问题的不同方法。
f) 最小“锁释放前的最坏情况”。这不得不涉及到最坏临界区的长度；但在某些情况下，还可能包括任意数量的 IRQ 的成本、任意数量的任务切换的成本以及代码未使用任何 CPU 的时间。完全有可能出现线程获取锁然后调度程序进行线程切换的情况；然后许多 CPU 都在无法释放的锁上自旋（浪费了大量时间）（因为锁持有者是唯一可以释放锁的人，它甚至没有使用任何 CPU). fix/improve 的方法是禁用调度程序和 IRQ；这在内核代码中很好，但在普通用户 space 代码中“出于安全原因可能不可能”。这也是为什么 自旋锁可能永远不应该在 user-space 中使用的原因（以及为什么 user-space 应该在放置线程的地方使用互斥锁处于“阻塞等待锁”状态且调度程序未给 CPU 时间 until/unless 线程实际上可以获得锁）。
请注意，对于“快速”的一种可能解释使其快速可以使“快速”的其他解释slower/worse。例如;无竞争案例的速度因其他一切而变得更糟。
自旋锁示例
这个例子未经测试，用（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 位）在获取锁时在它们中并在释放锁时检查它们以自动检测“错误的线程释放锁”和“从未获取锁时释放锁”错误）and/or 用于收集性能信息（例如当存在争用时将位设置为 1，以便其他代码可以定期扫描以确定哪些锁很少争用，哪些锁争用很多）。使用锁的错误通常非常隐蔽且难以发现（不可预测且不可重现的“Heisenbugs”，一旦您试图找到它们就会消失）；所以我更喜欢“自动错误检测速度较慢”。
b) 这不是一个公平锁，这意味着它不太适合可能发生争用的情况。
c) 为了记忆；内存 consumption/cache 未命中和错误共享之间存在折衷。对于很少争用的锁，我喜欢把锁放在与锁保护的数据相同的缓存 line/s 中，这样获取锁意味着锁持有者想要的数据已经在缓存中（并且没有后续缓存错过发生）。对于竞争激烈的锁，这会导致虚假共享，应该通过为锁保留整个缓存行而不是其他任何东西来避免（例如，通过在实际锁使用的 4 个字节之后添加 60 个字节的未使用填充，就像在 C++ 中一样 alignas(64) struct { std::atomic<int> lock; };).当然，像这样的自旋锁不应该用于竞争激烈的锁，因此可以合理地假设最小化内存消耗（并且没有任何填充，并且不关心错误共享）是有意义的。
Main purpose for such spin lock for me is to protect very tiny operations inside multiple threads, that run a dozen or two of cycles, hence 30 cycles delay is too much overhead
在那种情况下，我建议尝试用原子、无块算法和无锁算法替换锁。一个简单的例子是跟踪统计信息，您可能想要执行 lock inc dword [number_of_chickens] 而不是获取锁来增加“number_of_chickens”。
除此之外很难说太多 - 对于一个极端情况，程序可能花费大部分时间在不需要锁的情况下完成工作，并且锁定的成本可能对整体性能几乎没有影响（即使 acquire/release 比微小的关键部分更昂贵）；对于另一个极端，程序可能将大部分时间花在获取和释放锁上。换句话说，acquiring/releasing 锁的成本介于“无关紧要”和“主要设计缺陷（使用太多锁并需要重新设计整个程序）”之间。