Instruction and memory ordering

自然情况下，人们会认为程序是按照源代码中语句的顺序执行的。对于单线程代码来说，这是合理的思维模型，但当多个线程通过共享内存交互时，这种想法是不正确的【2, 4】。其中一个原因是编译器会以不同于源代码所暗示的顺序发出加载和存储指令，甚至可能完全省略它们（例如，通过将数据缓存到寄存器中）。另一个原因是，为了提高性能，CPU可能会无序执行指令。例如，CPU 可能会注意到在一系列顺序指令中，指令 A 和 B 之间没有依赖关系。CPU 可能会先执行指令 B，因为其输入在 A 的输入之前已准备好，或者为了使 A 和 B 的执行重叠。

以 push 函数中的代码为例，如果编译器或 CPU 将第 4 行的存储操作移动到第 6 行的释放操作之后的位置，这将是灾难性的。

1 l = malloc(sizeof *l);
2 l->data = data;
3 acquire(&listlock);
4 l->next = list;
5 list = l;
6 release(&listlock);

如果发生了这样的重新排序，将会出现一个窗口，在此期间另一个 CPU 可能会获取锁并观察到已更新的链表，但会看到未初始化的 list->next。

好消息是，编译器和 CPU 通过遵循一组称为内存模型的规则，并提供一些原语来帮助程序员控制重新排序，从而帮助并发程序员。

为了告知硬件和编译器不要重新排序，xv6 在 acquire（kernel/spinlock.c:22）和 release（kernel/spinlock.c:47）中使用了 __sync_synchronize()。  

__sync_synchronize() 是一种内存屏障：它告知编译器和 CPU 不要跨屏障重新排序加载或存储操作。  

xv6 的 acquire 和 release 中的屏障在几乎所有重要情况下强制了顺序，因为 xv6 在访问共享数据时使用了锁。第 9 章讨论了一些例外情况。

附录1： 关于内存序的补充摘要

__sync_synchronize() 和 C++11 中的内存序（acquire/release）在内存模型和控制内存访问顺序方面存在差异：

  1. __sync_synchronize():
    是一个全局的内存屏障，用于告诉编译器和 CPU 不要在调用点前后重新排序任何加载或存储操作。
    强制所有处理器核心在屏障前的所有内存操作在屏障之后的内存操作之前完成。
    会影响整个系统的内存顺序，而不仅限于某个特定变量或操作。
    在性能方面相对较重，因为它是一个全局屏障。

  2. C++11 内存模型中的 acquire/release 语义: C++11 引入了内存序来更细粒度地控制内存访问的顺序。

std::memory_order_acquire: 用于读取操作（如 load()），确保所有读取操作在此加载之前完成，不允许后续操作重新排序到它之前。
读取时获取锁，并确保在获取锁后读取的数据是最新的。

std::memory_order_release: 用于写入操作（如 store()），确保在存储操作之前的所有写入操作都完成，不允许前面的操作重新排序到它之后。 释放锁时，使得在释放锁之前的所有写入操作对其他线程可见。

std::memory_order_acq_rel: 同时具有 acquire 和 release 的属性。适用于既要加载又要存储的操作（如 fetch_add()）。

std::memory_order_seq_cst: 强制操作具有严格的顺序（全序内存模型），类似于 __sync_synchronize() 的效果，但作用范围是由特定的操作控制的，而不是全局的。

主要差异总结: 粒度：__sync_synchronize() 是全局的内存屏障，影响所有线程的所有操作。而 C++11 的 acquire/release 语义是局部的，仅限于特定的变量或操作。 性能：C++11 的内存序列提供了更高的灵活性和更好的性能优化，因为它们只影响与指定变量相关的内存操作，不像 __sync_synchronize() 那样是全局的。 可读性：C++11 提供了更高层的抽象和可控性，使代码更容易理解和维护，特别是在多线程编程中。

使用场景: __sync_synchronize() 适合用于需要简单且强制的全局内存屏障的情况，比如在低级别的锁实现中。 C++11 的 acquire/release 更适合复杂的多线程程序，它提供了更细粒度的控制和更高效的实现，允许开发者在保持内存有序性的同时实现更好的性能。

附录2：内存序由编译器和处理器共同实现，它们在不同层次上控制指令的执行顺序和内存访问顺序：

  1. 编译器的作用: 编译器负责生成机器代码。在编译过程中，编译器可以根据代码优化规则重新排序指令，以提高执行性能。 在没有明确同步或内存序保证的情况下，编译器可能会重新安排加载和存储指令，导致源代码中显式的顺序与生成的机器指令顺序不同。 内存序列如 std::memory_order_acquire 和 std::memory_order_release 是在代码级别对编译器的约束。它们告诉编译器在优化代码时必须遵循这些序的规则。例如，在 acquire 上，编译器保证不会将指令重新排序到加载操作之前；在 release 上，不会将指令重新排序到存储操作之后。

  2. 处理器的作用: 处理器在执行指令时，为了提高性能，可能会进行指令的乱序执行（Out-of-Order Execution）。这种乱序执行并不会影响单个线程内的语义，但在多线程环境中会导致内存可见性的问题。 现代处理器通常实现内存模型（如 x86 的强一致性内存模型和 ARM 的弱一致性模型），这些模型规定了不同处理器如何处理和排序内存操作。 当程序使用了 __sync_synchronize() 或 C++11 的 std::atomic 内存序，如 acquire 和 release，这些操作会在汇编指令级别生成适当的指令（如内存屏障指令 mfence、sfence 等）来告诉处理器保持或强制执行内存访问顺序。

  3. 内存屏障（Memory Barriers）: 内存序的实现常用内存屏障指令来阻止编译器和处理器重新排序特定指令。例如，__sync_synchronize() 会生成一个全局内存屏障，防止指令在该点前后重新排序。 C++11 的内存序，如 memory_order_acquire 和 memory_order_release，会通过生成汇编指令（如 lock 前缀）或内存屏障来确保相应的内存访问顺序。 总结: 编译器和处理器共同实现内存序。编译器在编译时会根据内存序的约束生成汇编代码，确保在优化时不违反这些约束。处理器在执行时会根据指令中的内存屏障和内存模型来维护多线程之间的内存一致性和顺序。