在这种情况下，任何合理的 CPU 实现都可以给出 foo = 2 吗？
Can any reasonable CPU implementation give foo = 2 in this case?
阅读 Dan Luu 撰写的一篇非常有趣的 blog post 关于过去几十年 x86 架构进步的文章，他说：
If we set _foo to 0 and have two threads that both execute incl (_foo) 10000 times each, incrementing the same location with a single instruction 20000 times, is guaranteed not to exceed 20000, but it could (theoretically) be as low as 2. If it’s not obvious why the theoretical minimum is 2 and not 10000, figuring that out is a good exercise.
其中 _foo 是一些内存地址。
显然这是因为（正如他所说的） incl 被实现为一个加载，然后是一个添加，然后是一个存储。所以如果你 "desugar" 它变成：
mov reg, _foo ;; #1
inc reg ;; #2
mov _foo, reg ;; #3
然后 u-ops 的以下排序结果为 _foo = 2:
Thread A executes #1, #2
Thread B executes #1, #2
Thread A executes #3
Thread B executes #3
Thread A executes #1, #2.... etc
（我可能在这里混淆了汇编程序的细节，但据我所知，这是对 _foo = 2 情况的相当准确的描述。）
我想知道的是他的下一个 "exercise:"
[M]y bonus exercise for you is, can any reasonable CPU implementation get that result, or is that some silly thing the spec allows that will never happen? There isn’t enough information in this post to answer the bonus question...
可以吗？我的直觉是否定的，因为我相信当 A 执行 #3 时，则：
A 和 B 在同一个 CPU 上。在 A 的时间片结束之前，B 不会到达 运行，而且执行一条指令不可能花费整个时间片，所以最终有人会写出一个值 > 2，或者
A 和 B 在不同的 CPU 上。 A 的写入导致 B 的缓存失效，A 继续执行，写出一个 > 2 的值。
但我不确定是否每家商店都导致所有其他缓存失效，或者 A 是否能够在那段时间继续 运行ning，我不确定是否 OS 级别的时间片之类的东西应该适用于关于 CPUs.
的推理
A executes #1, #2
B executes #1, #2, #3 9999 times (_foo == 9999)
A executes #3 (_foo == 1)
B executes #1, #2 (part of iteration 10000, and reg == 2)
A executes #1, #2, #3 9999 times (completing its total of 10000 iterations)
B executes #3 (writing 2 to _foo)
tl;dr 总结：在 one-instruction inc [foo] 的单核上不可能。也许每个线程都在它自己的核心上，但我认为只有超线程才能通过在 load/inc 和商店之间引起缓存驱逐来在商店上造成额外的延迟。
我认为甚至 multi-socket 缓存一致性都不能慢到 B 的最终存储在 B 的最终加载后延迟 50k 周期，但超线程可能能够在之前排队多个 cache/TLB 未命中它。
在 single-core 情况下：您假设 B 在 A 的时间片到达 之前不会到达 运行 不一定成立。中断（例如定时器中断或 NIC）可以随时进入，在任何指令边界暂停执行 user-space 线程。也许在中断之后，一个 higher-priority 进程醒来并被调度到 CPU 一段时间，所以调度程序没有理由更喜欢已经 运行 一小部分的线程一个时间片。
然而，如果我们只讨论 single-core 情况，并且并发只能通过上下文切换发生，inc [mem] 与 mov reg, [mem] / inc reg / mov [mem], reg。无论 CPU 内部如何处理 inc [mem]， 上下文切换仅 saves/restores 架构 状态 。如果 load 和 inc 部分已经在内部完成，但存储没有完成，那么整个指令就不会退出。上下文切换不会 save/restore 取得进展：当线程再次开始执行并且 CPU 再次看到 inc [mem] 指令时，load 和 inc 必须是 re-run .
如果测试使用单独的 load/inc/store 指令，即使是 single-core 机器在理论上也可以通过 Michael Burr 指出的序列获得 2：
A loads 0 from _foo
B loops 9999 times (finally storing _foo = 9999)
A stores _foo = 1 (end of first iteration)
B's final iteration loads 1 from _foo
A loops 9999 times (eventually storing _foo = 10000)
B's final iteration stores _foo = 2
这是可能的，但需要在非常特定的时间到达的中断触发多次上下文切换。从导致调度程序抢占线程的中断到来自新线程的第一条指令实际 运行s 的点需要很多周期。可能有足够的时间让另一个中断到达。我们只是对它的可能性感兴趣，即使经过几天的试验也不太可能被观察到！
同样，对于 inc [mem]，这在单个内核上是 不可能的，因为上下文切换只能在整个指令之后发生。 CPU 的体系结构状态是否执行了 inc。
在多核情况下，两个线程同时运行，情况就完全不同了。缓存一致性操作可以发生在单个指令被解码成的微指令之间。所以 inc [mem] 不是这个上下文中的单个操作。
我不确定，但我认为即使 single-instruction inc [foo] 循环也可能产生最终结果 2。中断/上下文切换无法解释但是，对于加载和存储之间的延迟，我们需要想出其他可能的原因。
- A 从
foo 加载 0
- B循环9999次（最终存储foo = 9999）。缓存行现在在 B 的 CPU 核心
上处于 E 状态
- A 存储 _foo = 1（第一次迭代结束）。可以想象，这可能会在超线程 CPU 上延迟这么长时间，原因是另一个逻辑线程使存储端口饱和，大量积压的存储在缓存 and/or TLB 中丢失，并且存储被缓冲了一段时间.可能这会在没有多个 cache-miss 商店等待完成的超线程的情况下发生。请记住，在 x86 的强内存模型中，存储在程序顺序中变得全局可见，因此稍后存储到热缓存行仍然需要等待。正好在 B 的最后一次迭代之前完成它只是时间上的巧合，这很好。
- B 的最终迭代从 foo 加载 1。 （中断或其他东西可能会延迟 B 执行最后一次迭代。这不需要在 load/inc/store 指令之间发生任何事情，所以我不需要弄清楚是否接收到一致性使缓存行无效的消息（来自 A）将阻止 store-forwarding 将 9999 值从前一次迭代的存储转发到本次迭代的加载。我不确定，但我认为可以。）
- A循环9999次（最终存储
_foo = 10000）
B 的最终迭代存储 _foo = 2。 解释这个存储如何延迟到 A 的循环完成之后似乎是最大的延伸。超线程可以做到这一点：另一个逻辑核心可以逐出 _foo 的 TLB 条目，也可能逐出包含该值的 L1 D$ 行。这种逐出可能发生在最终 inc 指令的加载和存储微指令之间。我不确定一致性协议需要多长时间才能获得对当前由另一个核心拥有的高速缓存行的写访问权。我敢肯定这通常要少得多一个 50k 周期，实际上少于 CPUs 上的主内存访问，其中包含 last-level 缓存作为一致性流量的后盾（例如英特尔的 Nehalem 和后来的设计）。 Very-many-core 具有多个套接字的系统可能很慢，但我认为它们仍然使用环形总线来实现一致性流量。
我不确定 B 的最终存储在没有超线程的情况下延迟 50k 周期是否合理来堆积一些 store-port 争用并导致缓存逐出。负载（必须看到 A 的存储 1，但不能看到 A 的任何其他存储）在 OOO 调度程序中不能超前于存储太远，因为它仍然必须在倒数第二次迭代的存储之后。 （核心必须在单个执行上下文中维护 in-order 语义。）
由于只有一个内存位置在两个线程中读取然后写入，因此不会对存储和加载进行任何重新排序。加载将始终看到来自同一线程的先前存储，因此只有在存储到同一位置之后它才能变得全局可见。
在 x86 上，只有 StoreLoad reordering 是可能的，但在这种情况下，唯一重要的是 out-of-order 机器可以延迟存储很长时间，即使没有相对于重新排序任何负载。
您所指的原始博客 post 总体上看起来不错，但我确实注意到至少一个错误。里面有很多好的link。
it turns out that on modern x86 CPUs, using locking to implement
concurrency primitives is often cheaper than using memory
barriers
那 link 只是表明使用 lock add [mem], 0 作为屏障 在 Nehalem 上更便宜，尤其是。它与其他指令更好地交错。它与使用依赖于屏障的锁定算法和无锁算法没有什么可说的。如果您想以原子方式增加内存位置，那么到目前为止最简单的选择是 locked 指令。如果可能的话，仅使用 MFENCE 将需要在没有原子 RMW 操作的情况下实现某种单独的锁。
分明是想介绍lock inc [mem] vs. inc [mem]的话题，只是措辞不慎而已。在大多数情况下，他的概括效果更好。
示例代码也很奇怪，一如既往地用-O0 makes quite nasty code编译。我修复了内联 asm 以向编译器询问内存操作数，而不是手动编写 incl (reg)，因此在启用优化的情况下，它会生成 incl counter(%rip) 而不是将指针加载到寄存器中。更重要的是，-O3 还避免了将循环计数器保留在内存中，即使是原始源也是如此。 -O3 原始源似乎仍然生成正确的代码，即使它没有告诉编译器它写入内存。
无论如何，尽管实验存在缺陷，但我认为该实验仍然有效，并且使用 -O0 编译的巨大循环开销不太可能人为限制最终计数器可能结束的范围与.
Dan Luu 的示例 asm 语法是 Intel 和 AT&T 语法的奇怪组合：mov [_foo], %eax 是一个负担。它应该写成mov eax, [_foo]，或者mov _foo, %eax，或者如果你想清楚地表明它是一个负载而不是mov-immediate，那么它应该写成mov (_foo), %eax。无论如何，我认为如果我不知道他的意思并试图证明它会令人困惑。
阅读 Dan Luu 撰写的一篇非常有趣的 blog post 关于过去几十年 x86 架构进步的文章，他说：
If we set
_footo 0 and have two threads that both executeincl (_foo)10000 times each, incrementing the same location with a single instruction 20000 times, is guaranteed not to exceed 20000, but it could (theoretically) be as low as 2. If it’s not obvious why the theoretical minimum is 2 and not 10000, figuring that out is a good exercise.
其中 _foo 是一些内存地址。
显然这是因为（正如他所说的） incl 被实现为一个加载，然后是一个添加，然后是一个存储。所以如果你 "desugar" 它变成：
mov reg, _foo ;; #1
inc reg ;; #2
mov _foo, reg ;; #3
然后 u-ops 的以下排序结果为 _foo = 2:
Thread A executes #1, #2
Thread B executes #1, #2
Thread A executes #3
Thread B executes #3
Thread A executes #1, #2.... etc
（我可能在这里混淆了汇编程序的细节，但据我所知，这是对 _foo = 2 情况的相当准确的描述。）
我想知道的是他的下一个 "exercise:"
[M]y bonus exercise for you is, can any reasonable CPU implementation get that result, or is that some silly thing the spec allows that will never happen? There isn’t enough information in this post to answer the bonus question...
可以吗？我的直觉是否定的，因为我相信当 A 执行 #3 时，则：
A 和 B 在同一个 CPU 上。在 A 的时间片结束之前，B 不会到达 运行，而且执行一条指令不可能花费整个时间片，所以最终有人会写出一个值 > 2，或者
A 和 B 在不同的 CPU 上。 A 的写入导致 B 的缓存失效，A 继续执行，写出一个 > 2 的值。
但我不确定是否每家商店都导致所有其他缓存失效，或者 A 是否能够在那段时间继续 运行ning，我不确定是否 OS 级别的时间片之类的东西应该适用于关于 CPUs.
的推理A executes #1, #2
B executes #1, #2, #3 9999 times (_foo == 9999)
A executes #3 (_foo == 1)
B executes #1, #2 (part of iteration 10000, and reg == 2)
A executes #1, #2, #3 9999 times (completing its total of 10000 iterations)
B executes #3 (writing 2 to _foo)
tl;dr 总结：在 one-instruction inc [foo] 的单核上不可能。也许每个线程都在它自己的核心上，但我认为只有超线程才能通过在 load/inc 和商店之间引起缓存驱逐来在商店上造成额外的延迟。
我认为甚至 multi-socket 缓存一致性都不能慢到 B 的最终存储在 B 的最终加载后延迟 50k 周期，但超线程可能能够在之前排队多个 cache/TLB 未命中它。
在 single-core 情况下：您假设 B 在 A 的时间片到达 之前不会到达 运行 不一定成立。中断（例如定时器中断或 NIC）可以随时进入，在任何指令边界暂停执行 user-space 线程。也许在中断之后，一个 higher-priority 进程醒来并被调度到 CPU 一段时间，所以调度程序没有理由更喜欢已经 运行 一小部分的线程一个时间片。
然而，如果我们只讨论 single-core 情况，并且并发只能通过上下文切换发生，inc [mem] 与 mov reg, [mem] / inc reg / mov [mem], reg。无论 CPU 内部如何处理 inc [mem]， 上下文切换仅 saves/restores 架构 状态 。如果 load 和 inc 部分已经在内部完成，但存储没有完成，那么整个指令就不会退出。上下文切换不会 save/restore 取得进展：当线程再次开始执行并且 CPU 再次看到 inc [mem] 指令时，load 和 inc 必须是 re-run .
如果测试使用单独的 load/inc/store 指令，即使是 single-core 机器在理论上也可以通过 Michael Burr 指出的序列获得 2：
A loads 0 from _foo
B loops 9999 times (finally storing _foo = 9999)
A stores _foo = 1 (end of first iteration)
B's final iteration loads 1 from _foo
A loops 9999 times (eventually storing _foo = 10000)
B's final iteration stores _foo = 2
这是可能的，但需要在非常特定的时间到达的中断触发多次上下文切换。从导致调度程序抢占线程的中断到来自新线程的第一条指令实际 运行s 的点需要很多周期。可能有足够的时间让另一个中断到达。我们只是对它的可能性感兴趣，即使经过几天的试验也不太可能被观察到！
同样，对于 inc [mem]，这在单个内核上是 不可能的，因为上下文切换只能在整个指令之后发生。 CPU 的体系结构状态是否执行了 inc。
在多核情况下，两个线程同时运行，情况就完全不同了。缓存一致性操作可以发生在单个指令被解码成的微指令之间。所以 inc [mem] 不是这个上下文中的单个操作。
我不确定，但我认为即使 single-instruction inc [foo] 循环也可能产生最终结果 2。中断/上下文切换无法解释但是，对于加载和存储之间的延迟，我们需要想出其他可能的原因。
- A 从
foo 加载 0
- B循环9999次（最终存储foo = 9999）。缓存行现在在 B 的 CPU 核心 上处于
- A 存储 _foo = 1（第一次迭代结束）。可以想象，这可能会在超线程 CPU 上延迟这么长时间，原因是另一个逻辑线程使存储端口饱和，大量积压的存储在缓存 and/or TLB 中丢失，并且存储被缓冲了一段时间.可能这会在没有多个 cache-miss 商店等待完成的超线程的情况下发生。请记住，在 x86 的强内存模型中，存储在程序顺序中变得全局可见，因此稍后存储到热缓存行仍然需要等待。正好在 B 的最后一次迭代之前完成它只是时间上的巧合，这很好。
- B 的最终迭代从 foo 加载 1。 （中断或其他东西可能会延迟 B 执行最后一次迭代。这不需要在 load/inc/store 指令之间发生任何事情，所以我不需要弄清楚是否接收到一致性使缓存行无效的消息（来自 A）将阻止 store-forwarding 将 9999 值从前一次迭代的存储转发到本次迭代的加载。我不确定，但我认为可以。）
- A循环9999次（最终存储
_foo = 10000） B 的最终迭代存储
_foo = 2。 解释这个存储如何延迟到 A 的循环完成之后似乎是最大的延伸。超线程可以做到这一点：另一个逻辑核心可以逐出_foo的 TLB 条目，也可能逐出包含该值的 L1 D$ 行。这种逐出可能发生在最终inc指令的加载和存储微指令之间。我不确定一致性协议需要多长时间才能获得对当前由另一个核心拥有的高速缓存行的写访问权。我敢肯定这通常要少得多一个 50k 周期，实际上少于 CPUs 上的主内存访问，其中包含 last-level 缓存作为一致性流量的后盾（例如英特尔的 Nehalem 和后来的设计）。 Very-many-core 具有多个套接字的系统可能很慢，但我认为它们仍然使用环形总线来实现一致性流量。我不确定 B 的最终存储在没有超线程的情况下延迟 50k 周期是否合理来堆积一些 store-port 争用并导致缓存逐出。负载（必须看到 A 的存储 1，但不能看到 A 的任何其他存储）在 OOO 调度程序中不能超前于存储太远，因为它仍然必须在倒数第二次迭代的存储之后。 （核心必须在单个执行上下文中维护 in-order 语义。）
E 状态
由于只有一个内存位置在两个线程中读取然后写入，因此不会对存储和加载进行任何重新排序。加载将始终看到来自同一线程的先前存储，因此只有在存储到同一位置之后它才能变得全局可见。
在 x86 上，只有 StoreLoad reordering 是可能的，但在这种情况下，唯一重要的是 out-of-order 机器可以延迟存储很长时间，即使没有相对于重新排序任何负载。
您所指的原始博客 post 总体上看起来不错，但我确实注意到至少一个错误。里面有很多好的link。
it turns out that on modern x86 CPUs, using locking to implement concurrency primitives is often cheaper than using memory barriers
那 link 只是表明使用 lock add [mem], 0 作为屏障 在 Nehalem 上更便宜，尤其是。它与其他指令更好地交错。它与使用依赖于屏障的锁定算法和无锁算法没有什么可说的。如果您想以原子方式增加内存位置，那么到目前为止最简单的选择是 locked 指令。如果可能的话，仅使用 MFENCE 将需要在没有原子 RMW 操作的情况下实现某种单独的锁。
分明是想介绍lock inc [mem] vs. inc [mem]的话题，只是措辞不慎而已。在大多数情况下，他的概括效果更好。
示例代码也很奇怪，一如既往地用-O0 makes quite nasty code编译。我修复了内联 asm 以向编译器询问内存操作数，而不是手动编写 incl (reg)，因此在启用优化的情况下，它会生成 incl counter(%rip) 而不是将指针加载到寄存器中。更重要的是，-O3 还避免了将循环计数器保留在内存中，即使是原始源也是如此。 -O3 原始源似乎仍然生成正确的代码，即使它没有告诉编译器它写入内存。
无论如何，尽管实验存在缺陷，但我认为该实验仍然有效，并且使用 -O0 编译的巨大循环开销不太可能人为限制最终计数器可能结束的范围与.
Dan Luu 的示例 asm 语法是 Intel 和 AT&T 语法的奇怪组合：mov [_foo], %eax 是一个负担。它应该写成mov eax, [_foo]，或者mov _foo, %eax，或者如果你想清楚地表明它是一个负载而不是mov-immediate，那么它应该写成mov (_foo), %eax。无论如何，我认为如果我不知道他的意思并试图证明它会令人困惑。