原子总结 - BLOG

数据冲突操作小粒度——指令编译乱序 CPU、内存乱序内存模型大粒度编译乱序 CPU乱序原子操作 linux架构的原子接口关中断自旋锁加锁信号量无锁操作 COW COW优化多对象写日志事务内存总结参考链接

顺序性/原子性：单个标量类型变量、单个复合类型变量、一小段代码的原子性

同步：单个标量类型变量、单个复合类型变量、一小段代码的同步

数据冲突操作

store-load（Write-After-Read）

load-store（Read-After-Write）

store-store（Write-After-Write）

load-load 不会产生数据冲突

ACID（原子性，一致性，隔离性，持久性）事务属性

小粒度——指令

CPU、内存乱序

原始原子操作

处理器具有可用于实现锁定、无锁和无等待算法的指令。暂时抑制中断的能力，确保当前运行的进程不能进行上下文切换，这在单处理器上也足够了。这些指令由编译器和操作系统编写者直接使用，但也被抽象并公开为高级语言中的字节码和库函数：

原子读写；
原子交换（某些Burroughs 大型机 x86 指令中的 RDLK 指令，以及 XCHG）；
test-and-set;
fetch-and-add;
compare-and-swap;
load-link/store-conditional.

大多数[需要引用] 处理器包括相对于内存而言不是原子的存储操作。其中包括多字存储和字符串操作，如果在部分存储完成时发生高优先级中断，则必须在中断级别返回时完成操作。处理中断的例程不得修改正在更改的内存。在编写中断例程时考虑到这一点很重要。

当有多条指令必须不间断地完成时，使用暂时禁止中断的CPU指令。这必须保持在只有几条指令，并且必须重新启用中断，以避免对中断的响应时间不可接受，甚至丢失中断。这种机制在多处理器环境中是不够的，因为无论是否发生中断，每个 CPU 都可能干扰进程。此外，在存在指令管道的情况下，不间断操作会带来安全风险，因为它们可能会被链接在无限循环中以造成拒绝服务攻击，如Cyrix 昏迷 bug中所示。

C标准和SUSv3提供sig_atomic_t简单的原子读写；递增或递减不保证是原子的。C11中提供了更复杂的原子操作，它提供了. 编译器利用硬件特性或更复杂的方法来实现操作；一个例子是 GCC 的 libatomic。stdatomic.h

ARM指令集提供了LDREX可STREX用于通过使用处理器中实现的独占监视器来跟踪特定地址的内存访问来实现原子内存访问的指令。但是，如果在调用和之间发生上下文切换，文档会指出该操作将会失败，指示应重试该操作。LDREX STREX STREX

高级原子操作

实现线性化的最简单方法是在关键部分运行基元操作组。严格来说，可以小心地允许独立操作重叠其关键部分，只要这不违反线性化性。这种方法必须平衡大量锁的成本与增加并行性的好处。

另一种受到研究人员青睐的方法（但尚未在软件行业中广泛使用）是使用硬件提供的本机原子原语来设计线性化对象。这有可能最大化可用并行性并最小化同步成本，但需要数学证明来表明对象行为正确。

这两者的一个有前途的混合是提供事务内存抽象。与临界区一样，用户标记必须与其他线程隔离运行的顺序代码。然后，该实现确保代码以原子方式执行。这种抽象风格在与数据库交互时很常见。例如，当使用Spring框架时，使用@Transactional注释方法将确保所有封闭的数据库交互发生在单个数据库事务中。事务性内存更进一步，确保所有内存交互以原子方式发生。与数据库事务一样，会出现有关事务组成的问题，尤其是数据库事务和内存事务。

设计可线性化对象时的一个常见主题是提供一个全有或全无的接口：操作要么完全成功，要么失败并且不执行任何操作。（ACID数据库将此原则称为原子性。）如果操作失败（通常由于并发操作），用户必须重试，通常执行不同的操作。例如：

仅当某个位置的内容与提供的旧值匹配时，比较和交换才会将新值写入该位置。这通常用于读取-修改-CAS 序列：用户读取位置，计算要写入的新值，然后使用 CAS（比较和交换）写入它；如果该值同时发生变化，CAS 将失败，用户重试。
Load-link/store-conditional更直接地编码此模式：用户使用 load-link 读取位置，计算要写入的新值，然后使用 store-conditional 写入；如果该值同时发生更改，SC（条件存储）将失败，用户重试。
在数据库事务中，如果由于并发操作（例如死锁）导致事务无法完成，事务将被中止，用户必须重试。

单线程

ARM原子指令

LDREXB/LDREXH/LDREX/LDREXD：用于加载（Load）一个字节、半字、单字或双字的值，并将该值存放到寄存器中。LDREX指令会设置一个监视地址，在执行期间如果该地址的值发生变化，则会中止操作。
STREXB/STREXH/STREX/STREXD：用于将一个字节、半字、单字或双字的值存储（Store）到指定的内存地址。STREX指令会尝试将数据写回内存，并在成功时返回0，如果写回失败（由于冲突），则返回1。
SWP/SWPB：用于原子地交换内存中的值。它会将指定的寄存器值存储到内存地址，并将内存地址处的旧值读取到寄存器中。
LDAXR/LDAXRB/LDAXRH/LDAXP/LDAXL：用于加载（Load）一个字节、半字、单字、双字或指针的值，并将该值存放到寄存器中。LDAXR指令也会设置一个监视地址，用于检测内存操作冲突。
STXR/STXRB/STXRH/STXP/STXL：用于将一个字节、半字、单字、双字或指针的值存储（Store）到指定的内存地址。STXR指令会尝试将数据写回内存，并在成功时返回0，如果写回失败（由于冲突），则返回1。

ARM64架构原子指令：

LDAXR/LDAXRB/LDAXRH/LDAXRW：用于加载（Load）一个字节、半字、单字或双字的值，并将该值存放到寄存器中。LDAXR指令也会设置一个监视地址，用于检测内存操作冲突。
STXR/STXRB/STXRH/STXRW：用于将一个字节、半字、单字或双字的值存储（Store）到指定的内存地址。STXR指令会尝试将数据写回内存，并在成功时返回0，如果写回失败（由于冲突），则返回1。
CAS/CASA/CASL/CASAL：Compare and Swap（比较并交换）指令。它用于比较内存地址处的值与寄存器中的值，如果相等，则将寄存器中的新值存储回内存，并返回原来的值；如果不相等，则不执行任何操作。
LDADD/LDADDAB/LDADDAL/LDADDAH/LDADDALH/LDADDL/LDADDAL：Load and Add（加载并相加）指令。它用于加载内存地址处的值到寄存器中，并将一个常数值相加，然后将结果存储回内存，并返回原来的值。
LDCLR/LDCLRA/LDCLRL/LDCLRAB/LDCLRAL/LDCLRLB/LDCLRLAL/LDCLRLALH/LDCLRALH：Load and Clear（加载并清除）指令。它用于加载内存地址处的值到寄存器中，并将内存地址处的值清零，然后将原来的值存储回内存，并返回加载的值。
LDSET/LDSETA/LDSETL/LDSETAB/LDSETAL/LDSETLB/LDSETALH/LDSETAL：Load and Set（加载并设置）指令。它用于加载内存地址处的值到寄存器中，并将一个常数值设置到内存地址处，然后将结果存储回内存，并返回加载的值。
LDAPR/LDAPRB/LDAPRH/LDAPRW：Load Acquire Pair（加载-获取双字）指令。它用于加载一对（64位）内存地址处的值到两个寄存器中。LDAPR指令同样会设置监视地址，用于检测内存操作冲突。
STAPR/STAPRB/STAPRH/STAPRW：Store Release Pair（存储-释放双字）指令。它用于将两个寄存器的值存储（Store）到指定的内存地址。STAPR指令会尝试将数据写回内存，并在成功时返回0，如果写回失败（由于冲突），则返回1。

ARM架构中如下3条内存屏障指令

DMB

数据内存屏障（ Data Memory Barrier，DMB）指令。数据存储器隔离DMB指令保证仅当所有在它前面的存储器访问操作都执行完毕后，才提交(commit)在它后面的存储器访问操作。DMB 指令用于确保所有指令的内存访问（包括加载、存储）在该指令之前发生的所有内存操作都已完成，而在该指令之后的内存操作不会重新排序。

例子：当一个处理器核心执行了数据存储后，使用 DMB 可以确保数据存储操作在接下来的操作前已经完成。（一个核心内）

说明：
DMB 确保指令的顺序性，但并不影响指令之间的操作。具体而言，它将数据访问按照指令的顺序进行强制同步，并确保之前的内存操作（如存储）完成后，后续的内存操作（如加载）可以看到这些变化。

DSB

数据同步屏障（ Data Synchronization Barrier，DSB）指令。数据同步隔离。比DMB严格，仅当所有在它前面的存储器访问操作都执行完毕后，才执行在它后面的指令（亦即任何指令都要等待存储器访问操作）。DSB 指令比 DMB 更强大，它不仅会确保指令执行顺序，还会确保在 DSB 之前的所有内存操作（包括所有存储和加载操作）都被执行并且可见，直到 DSB 执行完成。

例子：如果你在多个核之间共享数据，DSB 可以确保当前核心的内存操作已完成并被其他核心看到。（多个核心之间）

说明：
DSB 强制同步，在执行该指令之前所有的内存访问（包括读写）都必须完成。它通常用于强制执行数据的同步，确保内存操作完成并且所有其他处理器都能看到更新。

ISB

指令同步屏障（Instruction Synchronization Barrier，ISB）指令。指令同步隔离最严格，它会清洗流水线，以保证所有它前面的指令都执行完毕之后，才执行它后面的指令。ISB 指令用于确保所有的指令流在执行之后的指令之前都被正确同步。这意味着，在执行 ISB 指令后，所有之前的指令都将完成执行（包括所有管道中的指令），并且新的指令会从同步点开始执行。

用途：ISB 通常用于影响指令流水线的刷新和同步。它用于强制处理器重新获取新的指令，通常在修改了程序状态（如启用/禁用缓存、切换上下文等）后使用。

例子：在改变控制寄存器的值后，需要使用 ISB 来确保更新立即生效，而不被缓存。

说明：
ISB 确保在它执行之后的指令流不会使用管道中的陈旧指令。它通常用于影响处理器的控制状态，强制从同步点开始执行新的指令。

多线程

Load-link/store-conditional(参考)

加载链接/条件存储( LL/SC )，有时也称为加载保留/条件存储( LR/SC )，是多线程中用于实现同步的一对指令。加载链接返回内存位置的当前值，而仅当自加载链接以来该位置没有发生更新时，同一内存位置的后续条件存储才会存储新值。总之，这实现了无锁、原子、读-修改-写操作。

LL/SC instructions are supported by:

Alpha: ldl_l/stl_c and ldq_l/stq_c
PowerPC/Power ISA: lwarx/stwcx and ldarx/stdcx
MIPS: ll/sc
ARM: ldrex/strex (ARMv6 and v7), and ldxr/stxr (ARM version 8)
RISC-V: lr/sc
ARC: LLOCK/SCOND

通常，CPU 以缓存行或其他粒度跟踪加载链接地址，以便对缓存行任何部分的任何修改（无论是通过另一个核心的存储条件还是仅通过普通存储）都足以导致存储条件失败。

所有这些平台都提供了薄弱的[需要澄清] LL/SC。PowerPC 实现允许 LL/SC 对包装加载甚至存储到其他缓存线（尽管这种方法容易受到错误缓存线共享的影响）。例如，这使得它能够在面对变化的对象图时实现无锁引用计数，并具有任意计数器重用（否则需要双重比较和交换，DCAS）。RISC-V 为有限长度的 LL/SC 序列的最终进展提供了架构保证。

一些 ARM 实现定义了平台相关的块，范围从 8 字节到 2048 字节，如果 LL 和 SC 之间存在同一块内的正常内存访问，则任何给定块中的 LL/SC 尝试都会失败。如果整个地址空间中的任何位置发生修改，其他 ARM 实现都会失败。前者的实现性更强，也最实用。

在设计加载存储架构时，LL/SC 比 CAS 有两个优点：根据设计理念（和管道架构）的要求，读取和写入是单独的指令；并且这两条指令只需使用两个寄存器（地址和值）即可执行，自然适合常见的双操作数 ISA。另一方面，CAS 需要三个寄存器（地址、旧值、新值）以及读取的值和写入的值之间的依赖关系。x86作为CISC架构，没有这个限制；尽管现代芯片很可能在内部将 CAS 指令翻译成单独的 LL/SC微操作。

LL/SC与CAS比较

如果发生任何更新，即使加载链接读取的值已被恢复，条件存储也一定会失败。因此，LL/SC 对比读取后进行比较和交换(CAS) 更强，如果旧值已恢复，CAS 将不会检测更新（请参阅ABA 问题）。

即使没有对相关内存位置进行并发更新，LL/SC 的实际实现也并不总是成功。两个操作之间的任何异常事件，例如上下文切换、另一个加载链接，甚至（在许多平台上）另一个加载或存储操作，都将导致存储条件错误地失败。如果有任何更新通过内存总线广播，旧的实现将会失败。这被研究人员称为弱LL/SC，因为它打破了许多理论上的 LL/SC 算法。弱点是相对的，一些弱的实现可以用于某些算法。

LL/SC 比 CAS 更难模拟。此外，在成对的 LL/SC 指令之间停止运行代码（例如单步执行代码时）可能会阻止前进，从而使调试变得棘手。

尽管如此，LL/SC 与 CAS 是等效的，因为任一原语都可以根据另一个原语以O(1)且无等待的方式实现。

X86

根据intel手册卷三第八章的描述，x86使用三种机制来实现原子操作：

Guaranteed atomic operations。Guaranteed atomic operations是指一些基本的读写内存操作，这些操作都是保证原子性的。一般来说，读写位于一个cache line中的数据是原子性的。
bus lock，使用LOCK#信号和指令的lock前缀。锁总线的方式很简单，进行原子操作的cpu会在bus上assert一个LOCK#信号，此时其他cpu的操作都会被block住。
cache lock，利用cache一致性协议(MESI协议)来实现。如果要访问的内存区域已经在当前cpu的cache中了，就会利用cache一致性协议来实现原子操作，否则会锁总线。

intel早期cpu(如Intel386，Intel486，奔腾处理器)实现原子操作，是通过bus lock来实现的。这种实现的问题，是完全不相关的两个cpu之间，也会相互竞争总线锁，从而导致整体性能下降。在后来的cpu中，intel对这一问题进行了优化。当要进行原子操作的内存已经被拉入cache中时，cpu会使用cache一致性协议来保证原子性，这被称为cache lock。相比于bus lock，cache lock粒度更细，能获得更好的性能。

x86中，有些指令是自带lock语义的，比如XCHG，更新段描述符等等；另外一些指令可以手动加上lock前缀来实现lock语义，比如BTS, BTR,CMPXCHG指令。在这些指令中，最核心的当属CAS(Compare And Swap)指令了，它是实现各种锁语义的核心指令。不同于自带原子语义的XCHG，CAS操作要通过”lock CMPXCHG”这样的形式来实现。一般而言，原子操作的数据长度不会超过8个字节，也不允许同时对两个内存地址进行CAS操作（如果可以的话，免锁双向链表不是梦）。

原子操作中另一个绕不开的话题是ABA问题，水平有限，就不展开讲了。简单提一个例子，在linux内核的slub实现中，用上了一个宏cmpxchg_double，这并不是同时对两个内存地址进行CAS的黑魔法，而正是利用CMPXCHG16B指令解决ABA问题的宏函数，有兴趣的可以深究一把。

在使用上，通常会记录下某块内存中的旧值，通过对旧值进行一系列的操作后得到新值，然后通过CAS操作将新值与旧值进行交换。如果这块内存的值在这期间内没被修改过，则旧值会与内存中的数据相同，这时CAS操作将会成功执行使内存中的数据变为新值。如果内存中的值在这期间内被修改过，则一般来说旧值会与内存中的数据不同，这时CAS操作将会失败，新值将不会被写入内存。

CAS操作基于CPU提供的原子操作指令实现。对于Intel X86处理器，可通过在汇编指令前增加LOCK前缀来锁定系统总线，使系统总线在汇编指令执行时无法访问相应的内存地址。而各个编译器根据这个特点实现了各自的原子操作函数。

在应用中CAS可以用于实现无锁数据结构，常见的有无锁队列（先入先出）[3]以及无锁栈（先入后出）。对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。

CAS：对于内存中的某一个值V，提供一个旧值A和一个新值B。如果提供的旧值V和A相等就把B写入V。这个过程是原子性的。

CAS执行结果要么成功要么失败，对于失败的情形下一班采用不断重试。或者放弃。

ABA：如果另一个线程修改V值假设原来是A，先修改成B，再修改回成A。当前线程的CAS操作无法分辨当前V值是否发生过变化。

CISC

X86架构 UP

关中断

X86架构 SMP

在cache line中，cache lock（https://zhuanlan.zhihu.com/p/115355303）

超过cache line，bus lock

RISC

load-link and store-conditional（LL/SC）

加载链接返回内存位置的当前值，而随后对同一内存位置的存储条件将仅在加载链接后该位置没有发生更新时才存储新值

LL/SC 与 CAS 相比有两个优势

读取和写入是独立的指令，并且这两条指令都可以仅使用两个寄存器（地址和值）来执行

ARM64处理器提供了比较并交换指令--cas指令。cas指令根据不同的内存屏障属性分成4类，如下所示

隐含了加载-获取内存屏障原语。
隐含了存储-释放内存屏障原语。
同时隐含了加载-获取和存储-释放内存屏障原语。
不隐含内存屏障原语。

Linux内核中常见的比较并交换函数是 cmpxchg()。由于 Linux内核最早是基于x86架构来实现的，x86指令集中对应的指令是 CMPXCHG指令，因此 Linux内核保留了该名字作为函数名。对于ARM64架构， cmpxchg()函数定义在arch/arm64/include/asm/cmpxchg.h头文件中.

cmpxchg()函数会调用 __cmpxchg_wrapper()宏，这里第一个参数_mb表示同时需要加载-获取和存储一释放内存屏障原语。

<arch/arm64/include/asm/cmpxchg.h>

#define arch_cmpxchg(...)		__cmpxchg_wrapper( _mb, __VA_ARGS__)

__cmpxchg wrapper()宏经过多次宏转换，它最终会调用 __CMPXCHG_CASE()宏，实现在arch/arm64/include/asm/atomic_lse.h头文件中。下面以64位位宽为例.

__CMPXCHG_CASE()宏包含6个参数。

w：表示位宽，支持8位、16位、32位以及64位。
sfx：cas指令的位宽后缀，8位宽使用b后缀，16位宽使用h后缀。
name表示内存屏障类型，如“acq_"”表示支持加载获取内存屏障原语，“rel_”表示支持存储-释放内存屏障原语，“mb_”表示同时支持加载一获取和存储-释放内存屏障原语。
sz：位宽大小
mb：组成cas指令的内存屏障后缀，“a”表示加载一获取内存屏障原语，“1”表示存储-释放内存屏障原语，“al'”表示同时支持加载一获取和存储一释放内存屏障原语。
cl：内嵌汇编的损坏部

lwn对原子操作的介绍https://lwn.net/Kernel/Index/#Atomic_operations

原子操作函数库https://en.cppreference.com/w/c/atomic

内存模型

order按照的指示，在线程和在同一线程上执行的信号处理程序之间建立非原子访问和宽松原子访问的内存同步顺序。这等效于atomic_thread_fence，除了没有发出用于内存排序的 CPU 指令。只有编译器对指令的重新排序被禁止作为order指令。例如，具有释放语义的栅栏可防止读取或写入移动超过后续写入，而具有获取语义的栅栏可防止读取或写入移动到先前的读取之前。

https://en.cppreference.com/w/cpp/atomic/memory_order

https://www.51cto.com/article/617888.html

https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync

Sequenced-before

同一个线程之内，语句A的执行顺序在语句B前面，那么就成为A sequenced-before B。它不仅仅表示两个操作之间的先后顺序，还表示了操作结果之间的可见性关系。两个操作A和操作B，如果有A sequenced-before B，除了表示操作A的顺序在B之前，还表示了操作A的结果操作B可见。例如：语句A是sequenced-before语句B的。

Carries dependency

同一个线程内，表达式A sequenced-before 表达式B，并且表达式B的值是受表达式A的影响的一种关系，称之为"Carries dependency"。

Modification order

对任何特定原子变量的所有修改都以特定于该原子变量的总顺序发生。

所有原子操作都保证以下四个要求：

1) 写入-写入一致性：如果修改某个原子 M（写入）的评估 A发生在修改 M 的评估 B 之前，则在M的修改顺序中 A 出现在 B 之前

2) 读-读一致性：如果某个原子 M（读）的值计算 A发生在 M 上的值计算 B 之前，并且如果 A 的值来自对 M 的写 X，那么 B 的值要么是X 存储的值，或 M 上的副作用 Y 存储的值，该值在 M 的修改顺序中出现在 X 之后。

3) 读写一致性：如果某个原子 M（读取）的值计算 A发生在 M 上的操作 B（写入）之前，则 A 的值来自较早出现的副作用（写入）X比 B 在M的修改顺序上

4) 写入-读取一致性：如果原子对象 M 上的副作用（写入）X发生在M的值计算（读取）B 之前，则评估 B 应从 X 或副作用 Y 获取其值按照 M 的修改顺序跟随 X

Release sequence

对原子对象 M 执行释放操作A后，M 的修改顺序的最长连续子序列为

1) Writes performed by the same thread that performed A

2) Atomic read-modify-write operations made to M by any threa

Dependency-ordered before

在线程之间，如果以下任何一项为真，则评估 A 在评估 B 之前进行依赖排序

1) A performs a release operation on some atomic M, and, in a different thread, B performs a consume operation on the same atomic M, and B reads a value written by any part of the release sequence headed (until C++20) by A.

2) A is dependency-ordered before X and X carries a dependency into B.

Inter-thread happens-before

在线程之间，如果以下任何一项为真，则评估 A线程间发生在评估 B 之前

1) A synchronizes-with B

2) A is dependency-ordered before B

3) A synchronizes-with some evaluation X, and X is sequenced-before B

4) A is sequenced-before some evaluation X, and X inter-thread happens-before B

5) A inter-thread happens-before some evaluation X, and X inter-thread happens-before B

Happens-before

happens-before关系表示的不同线程之间的操作先后顺序。如果A happens-before B，则A的内存状态将在B操作执行之前就可见。happends-before关系满足传递性、非自反性和非对称性。happens before包含了inter-thread happens before和synchronizes-with两种关系。

1) A is sequenced-before B

2) A inter-thread happens before B

Simply happens-before

无论线程如何，如果以下任何一项为真，则评估 A只会发生在评估 B 之前

1) A is sequenced-before B

2) A synchronizes-with B

3) A simply happens-before X, and X simply happens-before B

Strongly happens-before

无论线程如何，如果以下任何一项为真，则评估 A强烈发生在评估 B 之前：

1) A is sequenced-before B

2) A synchronizes-with B

3) A strongly happens-before X, and X strongly happens-before B

Visible side-effects

如果以下两个都为真，则标量 M（写入）上的副作用 A对于 M（读取）上的值计算 B 是可见的

1) A happens-before B

2) There is no other side effect X to M where A happens-before X and X happens-before B

Consume operation

具有或更强的原子负载memory_order_consume是消耗操作。请注意，std::atomic_thread_fence比消费操作强加了更强的同步要求。

Acquire operation

具有或更强的原子负载memory_order_acquire是获取操作。Mutex上的 lock() 操作也是一个获取操作。请注意，std::atomic_thread_fence比获取操作强加了更强的同步要求。

Release operation

memory_order_release具有或更强的原子存储是一种释放操作。Mutex上的 unlock() 操作也是一个释放操作。请注意，std::atomic_thread_fence比释放操作施加了更强的同步要求。

用于内存模型感知原子操作的内置函数

https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

内置函数：void __atomic_thread_fence (int memorder)

此内置函数根据指定的内存顺序充当线程之间的同步围栏。
所有内存命令均有效。

内置函数：void __atomic_signal_fence (int memorder)

这个内置函数充当线程和基于同一线程的信号处理程序之间的同步围栏。
所有内存命令均有效。

大粒度

编译乱序

顺序性

在单个线程中可能会发生指令重排而导致顺序不一致

解决办法

volatile

volatile 左值的访问（读取和写入）不能重新排序，防止编译器对其进行指令重排

READ_ONCE(x)

WRITE_ONCE(x, y)

asm volatile(”屏障指令”:::”memory”)

保证编译器不会对其进行指令重排的基础上还保证从内存中取对应数据的值，仅保证单个CPU上顺序性，数据大小超过支持的基础类型则使用volatile

a[0]= READ_ONCE(x);
a[1]= READ_ONCE(x);
// READ_ONCE保证了x的值是来自于内存的

WRITE_ONCE(a[0],x);
WRITE_ONCE(a[1],x);
// WRITE_ONCE保证了x的值更新到a[0]所在的内存，但是不保证x的值

a[0] = 1;
WRITE_ONCE(a[0],1);// 1是右值，不能用READ_ONCE

CPU乱序

多核

由于在接下来的学习内容中涉及到对信息、数据的同步，我们在开发操作系统的时候必须考虑到并发、多核情况下的同步问题，要想解决这些问题，实际应用中一般采用锁：原子变量、关中断、信号量、自旋锁。

以对一个全局变量进行操作为例，下述代码是一个中断处理函数和逻辑函数，它们都是对全局变量a进行操作：

int a = 0;
void interrupt_handle()
{
    a++;
}
void thread_func()
{
    a++;
}

对于a++，在编译阶段一般是将其分为三步：

将a存入某寄存器
该寄存器值+1
将寄存器的值刷新回内存

但是，如果在第二步完成之后突然发生中断了该如何？由时刻为标尺对a的值进行观测：

可以看到，由于中断的发生将thread_func的执行过程强行掐断，最终a的值为1，但其实它的值应该为2。

那么如何解决这个问题？

一是，将a++这个操作变成不可分割，即无法再拆解成3步执行，即是原子操作；

二是，在执行a++这个操作时，关闭中断，执行完毕之后再打开中断。

原子操作

所谓原子操作，就是要么不做，要么全做。在很多场景中，都有对原子操作的需求。以下三种情况需要考虑原子：

编译指令重排
CPU乱序执行
内存乱序

编译乱序主要影响单核情况，通过编译器对指令的重排优化程序的运行效率，提高资源的利用率。（编译）（控制流）

CPU指令重排/乱序执行同样影响单核情况，通过CPU执行指令时乱序影响数据正确性。（执行）（控制流）

内存乱序影响多核情况，多个核心访问内存顺序不同影响数据的一致性。以下都是针对这种情况：（数据流）

原子操作

硬件原语（原子操作）	位置	特点
read-modify-write（RMW）	内存	在read和write之间进行lock cache操作以保证原子性
test-and-set	内存
fetch-and-add	内存
fetch-and-and	内存
fetch-and-or	内存
compare-and-swap（CAS）	内存	CAS 需要三个寄存器
DCAS	内存	处理两个不连续的内存位置，可以用来解决ABA问题，一个指针记录数据，另一个指针记录这块内存的引用计数比较容易实现双向链表
DWCAS	内存	处理两个相邻的指针大小的内存位置
STM（事务性内存）	内存	每次读写看作提交一次日志更改，失败则回退

Maurice Herlihy (1991) 按共识数对原子操作进行排序，如下所示：

∞：memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte, load-link/store-conditional (LL/SC)
2 n − 2 : n -寄存器分配（n-register assignment）
2：test-and-set, swap, fetch-and-add, queue, stack
1：atomic read and atomic write

对于需要给定共识数的操作，无论使用多少个共识数较低的操作，都是不可能实现的。在I/O设备上使用时，读-修改-写指令通常会产生意外结果，因为写操作可能不会影响读操作中访问的同一内部寄存器。

该术语还与以原子读取-修改-写入序列的方式执行实际写入操作的RAID级别相关。这样的RAID级别包括RAID 4、RAID 5和RAID 6。

要完成原子操作，单CPU只需要关闭中断，因为中断只发生在指令间且单个CPU同时只能执行一个进程，多CPU需要关闭中断和抢占

原子操作需要底层操作系统支持，X86 CPU支持许多原子指令，C语言正是通过嵌入汇编代码调用这些原子指令来实现原子操作，而Java是在JVM层面对原子操作进行了实现。

另外，内嵌汇编代码编写格式的学习可参考：AT&T格式汇编代码，也可参考文末的补充部分进行理解。

实现原子读和原子写等：

//定义一个原子类型
typedef struct s_ATOMIC{
    volatile s32_t a_count; //禁止编译器优化，使其每次都从内存中加载变量
}atomic_t;

//原子读
static inline s32_t atomic_read(const atomic_t *v)
{        
        //x86平台取地址处是原子
        return (*(volatile u32_t*)&(v)->a_count);
}
//原子写
static inline void atomic_write(atomic_t *v, int i)
{
        //x86平台把一个值写入一个地址处也是原子的 
        v->a_count = i;
}
//原子加上一个整数
static inline void atomic_add(int i, atomic_t *v)
{
        __asm__ __volatile__("lock;" "addl %1,%0"
                     : "+m" (v->a_count)
                     : "ir" (i));
}
//原子减去一个整数
static inline void atomic_sub(int i, atomic_t *v)
{
        __asm__ __volatile__("lock;" "subl %1,%0"
                     : "+m" (v->a_count)
                     : "ir" (i));
}
//原子加1
static inline void atomic_inc(atomic_t *v)
{
        __asm__ __volatile__("lock;" "incl %0"
                       : "+m" (v->a_count));
}
//原子减1
static inline void atomic_dec(atomic_t *v)
{
       __asm__ __volatile__("lock;" "decl %0"
                     : "+m" (v->a_count));
}

注意，“lock”前缀是多核CPU下保证数据同步的指令，该指令会锁住数据总线，防止其他CPU更改对应内存地址的值，单核CPU不需要，更详细内容查看内存屏障、validate。

在使用原子操作的情况下，原本对全局变量的操作就可以改成：

atomic_t a = {0};
void interrupt_handle()
{
    atomic_inc(&a);
}
void thread_func()
{
    atomic_inc(&a);
}

当原子操作的对象大小在16字节或者8字节以内时，一两条指令就能实现原子操作。但是，当对象的大小较大时，实现原子操作的就需要其他方法了，比如加锁和COW。深究这两种方法，可以发现在本质上，它们还是将问题转换成了16字节的原子操作。

linux架构的原子接口

在读取原子变量的值、修改原子变量的值、把新值写入内存的过程中，处理器必须提供原子操作的汇编指令来完成上述操作，如ARM64处理器提供cas指令，x86处理器提供 cmpxchg指令。

Linux内核提供了一组内嵌内存屏障原语的原子操作函数

{}_relaxed：不内嵌内存屏障原语。
{}_acquire: 内置了加载-获取内存屏障原语
{}_release: 内置了存储-释放内存屏障原语

Linux内核中的内存屏障接口函数，如下所示：

barrier(): 编译优化指令，阻止编译器为了性能优化进行指令重排。
mb(): 内存屏障包括读和写，用于SMP和UP
rmb(): 读内存屏障，用于SMP和UP
mmb(): 写内存屏障，用于SMP和UP
smp_mb(): 用于SMP的内存屏障，对于UP不存在内存致性的问题(对汇编指令)，在UP上就是一个优化屏障，确保汇编代码和c代吗的内存一致性
smp_rmb(): 用于SMP的读内存屏障
smp_wmb(): 用于SMP的写内存屏障
smp_read_barrier_depend(): 读依赖屏障
smp_mb_before_atomic/smp_mb_after_atomic用于在原子操作中插入一个通用内存屏障

关中断

上述原子操作虽然可以完成同步操作，但是只能对付一些简单的单体变量，对于复杂的数据结构，如果使用原子操作，可想而知代码的复杂程度有多大。

在这个时候可以考虑通过关闭中断，从而实现相应的代码控制。

x86平台上的CPU关闭中断、开启中断指令是cli、sti，其主要是对CPU的eflags寄存的IF位进行设置，CPU据此来决定是否响应中断信号。

简单的关、开中断代码：

//关闭中断
void hal_cli()
{
    __asm__ __volatile__("cli": : :"memory");
}
//开启中断
void hal_sti()
{
    __asm__ __volatile__("sti": : :"memory");
}
//使用场景
void foo()
{
    hal_cli();
    //操作数据……
    hal_sti();
}
void bar()
{
    hal_cli();
    //操作数据……
    hal_sti();
}

上述方式的问题就在于无法嵌套使用：

void foo()
{
    hal_cli();
    //操作数据第一步……
    hal_sti();
}
void bar()
{
    hal_cli();
    foo();
    //操作数据第二步……
    hal_sti();
}

当从foo()函数返回到bar()时，这时中断已经被打开，但是bar()不知道！如果继续执行操作数据第二步，那么就可能因为其他线程函数的访问造成数据不一致问题。

为了让中断管理可以嵌套，就需要在关闭、开启中断的时候保存之前的状态，如下：

typedef u32_t cpuflg_t;
static inline void hal_save_flags_cli(cpuflg_t* flags)
{
     __asm__ __volatile__(
            "pushfl \t\n" //把eflags寄存器压入当前栈顶
            "cli    \t\n" //关闭中断
            "popl %0 \t\n"//把当前栈顶弹出到flags为地址的内存中        
            : "=m"(*flags)
            :
            : "memory"
          );
}
static inline void hal_restore_flags_sti(cpuflg_t* flags)
{
    __asm__ __volatile__(
              "pushl %0 \t\n"//把flags为地址处的值寄存器压入当前栈顶
              "popfl \t\n"   //把当前栈顶弹出到flags寄存器中
              :
              : "m"(*flags)
              : "memory"
              );
}

简单来说，在关闭中断的时候，把之前的状态存入地址为flag的内存中；在开启中断时，究竟是否开启中断，是由flag地址中存储的值来确定的！（即进行关闭中断操作之前的中断状态）

注：内存中的flag只是用来保存的，CPU是否中断由寄存器中的值而定。

注：注意区分中断与子程序调用的区别。

注：这里没有区分中断的优先级，但是实际的操作系统中，低级中断应该被高级中断所打断。

自旋锁

中断完美解决了原子操作只能针对单体变量的情况，但是——中断只能控制单核CPU，在多核CPU的情况下，又会遇到并发冲突的问题了，这个时候就需要使用“自旋锁”。

自旋锁原理如下：

上述流程有一个必须保证的点：读取锁变量、判断加锁操作必须是原子操作，否则还是会造成并发错误。

好在x86 提供了一个原子交换指令：xchg——让寄存器的值和内存空间的值进行交换。

根据上述流程图，将自旋锁实现如下：

//自旋锁结构
typedef struct
{
    //volatile可以防止编译器优化
    //保证其它代码始终从内存加载lock变量的值 
     volatile u32_t lock;
} spinlock_t;
//锁初始化函数
static inline void x86_spin_lock_init(spinlock_t * lock)
{
     lock->lock = 0;//锁值初始化为0是未加锁状态
}
//加锁函数
static inline void x86_spin_lock(spinlock_t * lock)
{
    __asm__ __volatile__ (
    "1: \n"
    "lock; xchg  %0, %1 \n"//把值为1的寄存器和lock内存中的值进行交换
    "cmpl   $0, %0 \n" //用0和交换回来的值进行比较
    "jnz    2f \n"  //不等于0则跳转后面2标号处运行
    "jmp 3f \n"     //若等于0则跳转后面3标号处返回
    "2:         \n" 
    "cmpl   $0, %1  \n"//用0和lock内存中的值进行比较
    "jne    2b      \n"//若不等于0则跳转到前面2标号处运行继续比较  
    "jmp    1b      \n"//若等于0则跳转到前面1标号处运行，交换并加锁
    "3:  \n"     :
    : "r"(1), "m"(*lock));
}
//解锁函数
static inline void x86_spin_unlock(spinlock_t * lock)
{
    __asm__ __volatile__(
    "movl   $0, %0\n"//解锁把lock内存中的值设为0就行
    :
    : "m"(*lock));
}

其中加锁函数的逻辑部分要好好理解，它通过转移指令形成了一个循环判断的逻辑，直到加锁才会退出。

注意，代码中汇编部分: : "r"(1), "m"(*lock)——系统分配一个寄存器，填入1；取内存地址为lock的值；而后xchg %0，%1即是将两者的值进行交换。

遗憾的是上述代码存在中断嵌套的问题：“如果一个CPU获取自旋锁后发生中断，中断代码里也尝试获取自旋锁，那么自旋锁永远不会被释放，发生死锁。”

关于自旋锁与中断的详细解释可以参考：Linux内核死锁，其中关于自旋锁与中断嵌套导致的一个经典场景叙述如下：

“考虑下面的场景（中断上下文场景）：

运行在CPU0上的进程A在某个系统调用过程中访问了共享资源 R
运行在CPU1上的进程B在某个系统调用过程中也访问了共享资源 R
外设P的中断handler中也会访问共享资源 R

在这样的场景下，使用spin lock可以保护访问共享资源R的临界区吗？

我们假设CPU0上的进程A持有spin lock进入临界区，这时候，外设P发生了中断事件，并且调度到了CPU1上执行，看起来没有什么问题，执行在CPU1上的handler会稍微等待一会CPU0上的进程A，等它离开临界区就会释放spin lock的，但是，如果外设P的中断事件被调度到了同一个CPU0上执行会怎么样？

CPU0上的进程A在持有spin lock的状态下被中断上下文抢占，而抢占它的CPU0上的handler在进入临界区之前仍然会试图获取spin lock，悲剧发生了，CPU0上的P外设的中断handler永远的进入spin状态，这时候，CPU1上的进程B也不可避免在试图持有spin lock的时候失败而导致进入spin状态。

为了解决这样的问题，linux kernel采用了这样的办法：如果涉及到中断上下文的访问，spin lock需要和禁止本 CPU 上的中断联合使用。 ”

关于这一点的解决方式可以参考关中断，详细讲解请看：08 锁。提示一下，获取自旋锁的时候，干脆把中断关闭了就好，这样就不会导致中断嵌套。

经修改后，可以实现关中断下获取自旋锁，以及恢复中断状态释放自旋锁：

static inline void x86_spin_lock_disable_irq(spinlock_t * lock
,cpuflg_t* flags)
{
    __asm__ __volatile__(
    "pushfq                 \n\t"
    "cli                    \n\t"
    "popq %0                \n\t"
    "1:         \n\t"
    "lock; xchg  %1, %2 \n\t"
    "cmpl   $0,%1       \n\t"
    "jnz    2f      \n\t"
    "jmp    3f      \n"  
    "2:         \n\t"
    "cmpl   $0,%2       \n\t" 
    "jne    2b      \n\t"
    "jmp    1b      \n\t"
    "3:     \n"     
     :"=m"(*flags)
    : "r"(1), "m"(*lock));
}
static inline void x86_spin_unlock_enabled_irq(spinlock_t* lock
,cpuflg_t* flags)
{
    __asm__ __volatile__(
    "movl   $0, %0\n\t"
    "pushq %1 \n\t"
    "popfq \n\t"
    :
    : "m"(*lock), "m"(*flags));
}

代码中的cpuflg表示当前的中断状态。

加锁

加锁这个方式很好理解，只要一加锁，整个临界区的操作就可以被看作一个原子操作。内核中提供了各种各样的锁，自旋锁，读写锁，seq锁，mutex，semaphore等等，这些锁对读写者的倾向各有不同，在是否允许睡眠上也有所不同。简单来说，自旋锁和读写锁的核心都是利用原子指令来CAS操纵一个32位/64位的值，它们都不允许睡眠，但是读写锁对于读者做了优化，允许多个读者同时读取数据，而自旋锁则对于读写操作没有什么偏向性。seq基于自旋锁实现，不允许睡眠，但是对写者更为友好。mutex和semaphore也是基于自旋锁实现的，但是它们允许互斥区的操作陷入睡眠。可以看到，加锁这种方式，最核心的还是利用指令实现原子操作。

信号量

以上三种解决同步的方式都不适合长等待，利用自旋锁这种方式去获取需要一定时间准备的资源，并且会造成CPU的时间消耗。

试想，能不能有一种机制，当资源准备好了之后，提醒CPU去获取呢？

还真有，那就是在1965年由荷兰学者Edsger Dijkstra（没错，就是提出那个算法的男人）提出的信号量机制。

互斥锁只能拥有者可以释放，粒度更细，强调互斥性，信号量不是拥有者也可以释放，粒度更粗，强调同步。

互斥锁具有所有权的概念，即锁只能由获取它的那个线程来释放。这有助于避免死锁和数据不一致的问题。
二值信号量没有所有权的概念，任何线程都可以释放信号量，即使它不是获取信号量的线程。

信号量机制由三个环节组成：

等待：程序等待资源准备好
互斥：同时只有一个程序可以访问资源
唤醒：资源准备好之后唤醒固定程序

由于需要等待、互斥等操作，拟定一个数据结构如下：

//等待链数据结构，用于挂载等待代码执行流（线程）的结构
//里面有用于挂载代码执行流的链表和计数器变量,后续会讲
typedef struct s_KWLST
{   
    spinlock_t wl_lock;//等待链表的锁
    uint_t   wl_tdnr;//计数器
    list_h_t wl_list;//等待进程的链表
}kwlst_t;
//信号量数据结构
typedef struct s_SEM
{
    spinlock_t sem_lock;//维护sem_t自身数据的自旋锁
    uint_t sem_flg;//信号量相关的标志
    sint_t sem_count;//信号量计数值
    kwlst_t sem_waitlst;//用于挂载等待代码执行流（线程）结构
}sem_t;

想想信号量一般是怎么使用的呢？

获取信号量

将信号量自身加锁，如果信号值sem_count小于0，则将当前进程放入等待链；否则，对信号量执行“减一”，获取信号量成功，进入代码执行流程；

2. 代码执行

成功获取信号量之后，程序进行自己相应的操作逻辑。

3. 释放信号量

将信号量自身加锁，对信号值sem_count执行“加一”，如果大于0，则从等待链中唤醒一个进程；无论是否大于0，最终即完成信号量的释放

从上述流程可以看出，信号量其实就是一个“多人使用，用完放回”的场景。

根据以上分析一个简单的信号量实现如下：

//获取信号量
void krlsem_down(sem_t* sem)
{
    cpuflg_t cpufg;
start_step: 
    //之前自旋锁的封装   
    krlspinlock_cli(&sem->sem_lock,&cpufg);
    if(sem->sem_count<1)
    {//如果信号量值小于1,则让代码执行流（线程）睡眠
        krlwlst_wait(&sem->sem_waitlst);
        //之前自旋锁的封装
        krlspinunlock_sti(&sem->sem_lock,&cpufg);
        //切换代码执行流，下次恢复执行时依然从下一行开始执行
        //所以要goto开始处重新获取信号量进行判断
        krlschedul();
        goto start_step; 
    }
    sem->sem_count--;//信号量值减1,表示成功获取信号量
    //之前自旋锁的封装
    krlspinunlock_sti(&sem->sem_lock,&cpufg);
    return;
}
//释放信号量
void krlsem_up(sem_t* sem)
{
    cpuflg_t cpufg;
        //之前自旋锁的封装
    krlspinlock_cli(&sem->sem_lock,&cpufg);
    sem->sem_count++;//释放信号量
    if(sem->sem_count<1)
    {//如果小于1,则说数据结构出错了，挂起系统
        krlspinunlock_sti(&sem->sem_lock,&cpufg);
        hal_sysdie("sem up err");
    }
    //唤醒该信号量上所有等待的代码执行流（线程）
    krlwlst_allup(&sem->sem_waitlst);
    krlspinunlock_sti(&sem->sem_lock,&cpufg);
    krlsched_set_schedflgs();
    return;
}

其中krlschedul、krlwlst_wait、krlwlst_allup、krlsched_set_schedflgs是负责进程调度的相关函数，会在之后的进程章节进行讲解，敬请期待！

无锁操作

无锁编程，Memory-barrier，非阻塞算法，wiki

阻塞线程不可取的原因有很多。一个明显的原因是，当线程被阻塞时，它无法完成任何事情：如果被阻塞的线程正在执行高优先级或实时任务，那么停止其进程是非常不可取的。

除少数例外情况，非阻塞算法使用硬件必须提供的原子读-修改-写原语，其中最显著的是比较和交换（CAS）。关键部分几乎总是使用这些基元的标准接口来实现的（在一般情况下，即使使用这些基元，关键部分也是阻塞的）。20 世纪 90 年代，所有非阻塞算法都必须使用底层基元 "原生 "编写，才能达到可接受的性能。然而，新兴的软件事务内存领域为编写高效的非阻塞代码提供了标准抽象。

在提供堆栈、队列、集合和哈希表等基本数据结构方面也做了大量研究。这些数据结构允许程序轻松地在线程间异步交换数据。

此外，一些非阻塞数据结构足够弱，无需特殊的原子原语即可实现。这些例外情况包括：

单读取器单写入器环形缓冲区 FIFO 的安全地实现大小均匀地划分可用无符号整数类型之一的溢出，可以无条件地仅使用内存屏障
单个作者和任意数量的读者进行读取-复制-更新。（读取器是无等待的；写入器通常是无锁的，直到需要回收内存为止）。
多个作者和任意数量的读者的读取-复制-更新。（读取器是无等待的；多个写入器通常使用锁进行序列化，并且不是无阻塞的）。

一些库内部使用了无锁技术，但是很难编写正确的无锁代码。

有几个库在内部使用了无锁技术，但很难编写出正确的无锁代码。

非阻塞算法通常涉及一系列读、读修改写和写指令，其顺序经过精心设计。优化编译器可以积极地重新安排操作。即使不这样做，许多现代 CPU 也经常重新排列此类操作（它们具有 "弱一致性模型"），除非使用内存屏障告诉 CPU 不要重新排序。C++11 程序员可以在 <atomic> 中使用 std::atomic，而 C11 程序员可以使用 <stdatomic.h>，这两种语言都提供了类型和函数，告诉编译器不要重新排列此类指令，并插入适当的内存屏障。

免等待是对进度的最有力的非阻塞保证，它将全系统吞吐量保证与免饥饿结合在一起。如果每个操作在操作完成前的步数都有限制，那么该算法就是无等待算法。这一特性对实时系统至关重要，只要性能代价不是太高，具备这一特性总是很好的。

20 世纪 80 年代的研究表明，所有算法都可以免等待地实现，并且已经证明了许多从串行代码转换而来的算法，这些算法被称为通用构造（universal constructions）。然而，即使是最原始的阻塞设计，其性能一般也无法与之匹敌。后来有几篇论文改进了通用构造的性能，但其性能仍然远远低于阻塞设计。

有几篇论文研究了创建无等待算法的难度。例如，有研究表明，目前广泛使用的原子条件原语 CAS 和 LL/SC 无法在内存成本与线程数呈线性增长的情况下，为许多常见数据结构提供无饥饿实现。

但在实际应用中，这些下限并不会构成真正的障碍，因为对于实际系统而言，每个线程在共享内存中花费一个缓存行或独占保留颗粒（在 ARM 上最多 2KB）的存储空间并不会被认为成本太高（通常逻辑上所需的存储空间是一个字，但物理上同一缓存行上的 CAS 操作会发生碰撞，同一独占保留颗粒中的 LL/SC 操作会发生碰撞，因此物理上所需的存储空间[引文需要]更大）。

在 2011 年之前，无等待算法在研究和实践中都很少见。不过，2011 年，Kogan 和 Petrank 在 CAS 原始码的基础上提出了一种免等待队列，这种队列在普通硬件上普遍可用。他们构建的队列扩展了迈克尔和斯科特的无锁队列，这是一种在实践中经常使用的高效队列。科根和佩特兰克的后续论文提供了一种使免等待算法快速的方法，并利用这种方法使免等待队列的速度实际上与免锁队列一样快。Timnat 和 Petrank 随后发表的论文提供了一种从无锁数据结构生成无等待数据结构的自动机制。因此，现在许多数据结构都可以实现无等待。

COW

针对大对象原子操作的另一种方式是COW（copy on write）。

cow的思想其实非常简单，首先我们有一个指向这个大对象的指针，在需要原子性修改这个大对象的数据时，因为没办法做到inplace修改，所以就把这个对象的数据拷贝一份，在对象副本上修改，最后再原子性地修改指向这个对象的指针。可以看到，这里最核心的地方是利用指令来实现指针的替换。

关于COW，这里举一个AEP的例子。AEP是一种存储介质，这里只需要知道它可以按字节寻址和数据在掉电后不消失即可。普通的磁盘，一般有扇区原子性的保证，也就是在将新数据写入某个扇区的途中突然掉电的话，这个扇区上要么完全没有新数据，要么新数据完全被写下去了，不会出现一半新一半旧的状态。扇区原子性的保证很重要，许多数据库都依赖它，然而，AEP这种存储介质没有这种保证，所以需要用软件的方式来做这种保证，称为BTT。

BTT的思路也很简单，为了方便理解，后文我不引入AEP的术语来进行描述。

首先把整个存储空间划分成若干个block，每个block有自己的物理块号，然后再维护一个表来做逻辑块号到物理块号的转换。给上层逻辑块的数量略小于物理块数量，这样就会有一部分的物理块没有被映射，姑且称为free block。

比如下图，4个逻辑块，5个物理块，其中1号块是free block。

接下来，在往一个逻辑块上写数据时，先找一个free block，把数据写上去，接下来去映射表中，将逻辑块的映射修改该free block。整个流程中，最关键的一步——修改映射关系——是原子性的。只要有这个保证，那么就能够提供block数据原子性更新的能力。COW的思想在很多地方都有，比如qemu的qcow镜像快照，ext4和btrfs在写入数据时的cow，linux内核的rcu机制等等。此外，cow最有名的使用场景莫过于fork的实现了，但是它只是单纯的为了减少拷贝开销，与原子性没有太大关系。

COW优化

cow的方式，有个很麻烦的事情，就是每次都得原子性得去更新指针。那么有没有办法去掉这个指针呢？有的。

这个是在intel关于AEP的文档上学到的另一种取巧的方式（注意，下面描述的例子和上文中的BTT没有任何关系）。起因是这样的：

AEP的驱动使用一个称为index block的结构来管理元数据，这个index block处于整个介质的起始位置，大小至少为256字节。有些操作会去更改它的多个字段的值，所以可能出现更改字段到一半的过程中掉电的情况，因此需要一种机制来保证更改过程是原子性的。

正常的COW方式，需要在起始位置处保留两个index block大小的空间以及一个指针，其中一个index block作为备用。在修改index block的数据时，以cow的方式将全部的数据存储在备用index block中，然后以COW的方式更改指针指向该备用index block中。

intel使用下面的机制来优化掉指针：

依然是两个index block，index block中有一个称为seq的字段。seq是一个两位的数，共有4个状态。除去00状态，还有01、10、11三个状态，将这三个状态视为一个循环，如下:

为了方便叙述，两个index block分别命名为blockA和blockB。

第一次写入数据，写入到blockA中，其上的seq为01；
第二次写入数据，写入到blockB中，其上的seq为10；
第三次写入数据，写入到blockA中，其上的seq为11；
第四次写入数据，写入到blockB中，其上的seq为01；
…

如此往复，在恢复时，只要读取并比较两个index block上的seq中哪个处于循环的前方，就能找到最新的那个index block。这样的优势是显而易见的，一是避免了额外的指针，或者说把指针固化到两个index block中，避免了一个8字节指针对两个index block对齐带来的麻烦；二是少一次写操作，提升了效率。

多对象

前面针对的都是一个个单个的对象，如果涉及到多个对象，要保证原子性就比较复杂了。比如，如果使用加解锁的方式，就需要注意锁的顺序，防止死锁的问题；如果是cow的方式，就需要注意中途失败以后的把已替换的指针回滚回去的问题。从更大的格局来看，针对多个对象的原子操作，本质上就是进行一次事务操作。所以，这个问题的解法，参考事务的实现就好了。

写日志

事务的四大特征ACID，即原子性，一致性，隔离性和持久性，基本上是一个常识了，而原子性只是事务的一个特性。写日志算是实现事务最通用的方式了，日志一般分为redo和undo两种日志，为了加快恢复速度，一般还会引入检查点(checkpoint)的概念。在文件系统和数据库的实现中，基本上都能看到事务的身影。写日志除了能保证原子性和一致性以外，还对磁盘这种外存设备很友好，因为写日志基本上都是顺序的。在这一方面的典型案例，当属日志结构文件系统和leveldb的LSM-tree了。leveldb的原理想必不用再提了，它把对于K-V对的增删改操作都变成一条条的日志，然后持久化为磁盘上的一个个SST，之后再触发合并整理。这样一来，基本上对于磁盘的所有操作都是顺序的了。日志结构文件系统也是类似的思想，它将文件数据的增删改操作直接变成日志写到磁盘里面，文件的实际数据不需要单独再存到某个地方，而是靠日志恢复出来。这种做法对写操作是非常友好的，但是读方面的性能就有点差强人意了。

事务内存

事务通常是用于保证持久性数据一致性的。去掉持久性的要求，将事务的概念引入到对于内存对象的操控中，就有了事务内存的概念。正如上文所说，对于多个对象的操作，加锁和cow的方式，在使用时都比较麻烦。加锁的方式要考虑加解锁顺序防止死锁，中途失败了还要按照特定的顺序解锁回滚；cow也是一样，虽然没有死锁的问题，但是在回滚上也是很麻烦的。另一个问题就是，针对不同的场景，加解锁的顺序要重新考虑，cow的回滚也要重新考虑，不具有通用性。事务内存机制则是为了解决这些问题而提出的，它把针对多个对象的原子操作抽象为一个事务，只要按照它提供的api，以串行化的思路去编程就行了。不用考虑加解锁的顺序，也不必考虑回滚的问题，在遇到了某些fatal error时只要abort掉事务即可。这是一种通用的并发编程方式，简化编码的同时，还能保证并发的性能。事实上，事务内存机制的内部实现，也是依赖于cow机制和加解锁来实现的，更深一步，其实也是依赖于原子操作指令的。

总结

总结一下：16字节或8字节以内的内存数据，使用cpu的原子操作指令；16字节以上的数据，使用加锁、COW的方式，或者优化过的使用seq的COW方式，本质上还是依赖于原子指令；针对多个对象的原子操作，引入事务或者事务内存的概念，实际上的实现要么是写日志，要么是依赖于cow或加锁的方式，最终依赖于原子指令。所以，万变不离其宗，原子操作指令很关键。

参考链接

https://pmem.io/documents/NVDIMM_Namespace_Spec.pdf
https://software.intel.com/content/dam/develop/public/us/en/documents/325462-sdm-vol-1-2abcd-3abcd.pdf
https://zhuanlan.zhihu.com/p/151425608
https://zh.wikipedia.org/wiki/%E8%BD%AF%E4%BB%B6%E4%BA%8B%E5%8A%A1%E5%86%85%E5%AD%98