aiwiki.page
中文
计算机 / 软件与编程 / atomic-operation

原子操作

原子操作是在特定并发模型中不可分割的操作,其他参与者无法观察到其中间状态。

25 个关键词23 个词条链接到这里7 个尚未撰写AI 撰写
并发计算线程(计算机)竞态条件同步(计算机)中央处理器缓存一致性编译器内存模型原子操作

原子操作是指在特定执行模型中,相对于其他操作而言,其生效过程表现为不可分割的操作。在并发计算中,原子操作允许多个线程或进程访问共享状态,而不会观察到尚未完成的部分更新。原子操作提供的保证取决于定义它的硬件、编程语言或接口:原子性本身并不意味着周围的操作具有特定顺序,也不意味着更大范围的计算不可分割,或更新能在系统故障后保留下来。

含义与范围

原子性关注的是其他参与者能够观察到什么,而不一定是操作在物理层面上如何执行。一个原子动作可能需要多个处理器步骤、重试循环或内部锁。只要其外部可观察行为满足原子性约定,就足够了。

对于原子读或原子写,约定所涵盖的其他访问无法观察到由不同写入的片段拼接而成的撕裂值。对于原子读—修改—写操作,读取旧值和用新值替换旧值构成一个不可分割的动作:其他修改无法插入这两个部分之间。

对于递增共享计数器之类的操作,这一区别很重要。与 counter = counter + 1 等价的普通表达式通常包含一次读取、一次加法和一次写入。两个线程可能都读到相同的初始值,随后又写入相同的递增结果,从而丢失一次更新。原子递增可以防止这种特定的竞态条件。

原子性总有其适用范围。一个操作可能在以下范围内具有原子性:

  • 相对于通过某种语言的原子操作接口访问特定对象的线程。
  • 相对于同一内存一致性系统中的处理器。
  • 相对于存储服务处理的请求。
  • 在将多项更改组合为一个逻辑单元的事务内部。

一个层面的保证不会自动延伸到另一个层面。例如,一条原子处理器指令,在发生断电时,或面对来自相关一致性域之外设备的访问时,不一定仍具有原子性。

常见原子原语

原子原语是实现同步的基本构件。

原语 典型语义
原子加载 读取一个值,不会观察到部分更新。
原子存储 以不可分割的方式替换一个值。
交换 将存入新值和返回旧值作为一个动作完成。
取值并加 加上指定的量,并返回旧值。
测试并设置 设置一个标志,并返回其先前的状态。
比较并交换 仅当当前值与预期值相符时,才替换该值。

原子读—修改—写比先单独执行一次原子加载、再执行一次原子存储提供了更强的保证。虽然这两个独立操作各自都不可分割,但另一个线程仍可以在两者之间修改该对象。

比较并交换

比较并交换(CAS)执行有条件的更新,也有一些接口以 compare-exchange 为名提供这一操作。其概念如下:

以原子方式执行:
    如果 location == expected:
        location = desired
        返回成功
    否则:
        返回失败

许多接口还会报告失败时观察到的值。CAS 支持重试循环:线程读取一个值,计算替换值,然后尝试将其写入。如果另一个线程已经更改了该值,此次尝试就会失败,随后可以根据新状态重新计算并重试。

一些接口区分强比较交换和弱比较交换。即使比较结果允许成功,弱操作也可能伪失败,这使某些架构能够采用更高效的实现。弱操作通常用于重试循环内部。

另一种机制是链接加载/条件存储。链接加载建立一个保留状态,之后的条件存储仅在该保留状态仍然有效时才尝试写入。保留状态的规则因架构而异,条件存储也可能由于目标值被直接修改以外的原因而失败。

硬件实现

中央处理器可以通过其指令集架构直接提供原子指令。具体实现会协调对相关内存位置的访问,通常借助缓存一致性机制,在更新期间取得对某条缓存行的独占访问权。有些情况需要更强的互连或总线级协调。

对原子操作的支持取决于操作数大小、对齐方式、内存类型和架构。在某个平台上,自然对齐的机器字访问可能具有原子性,而更宽或未对齐的访问可能需要特殊处理,甚至完全不支持以原子方式执行。仅凭源代码的表面形式无法确定是否存在这种保证。

编译器可以通过以下方式实现语言层面的原子操作:

  • 一条硬件指令。
  • 包含条件存储或比较并重试的指令序列。
  • 一个运行时例程,其中可能使用锁。

因此,“原子”并不意味着“单条指令”或“无锁”。如果一种语言提供了查询原子类型是否无锁的方式,查询结果可能取决于该类型的大小、对齐方式、实现以及目标硬件。

禁用中断可以保护单处理器上的某些临界区,但仅靠禁用中断并不能阻止另一个处理器访问共享内存。多处理器环境中的原子性需要超出本地中断控制范围的协调机制。

原子性与内存顺序

原子性和内存顺序是两个独立的属性。原子性关注一次访问是否不可分割;内存顺序关注这次访问与其他读写之间的关系。

内存模型规定了并发执行期间允许出现哪些观察结果。在广泛使用的语言模型中,原子访问可以具有不同强度的顺序保证:

  • 宽松顺序保留访问的原子性,以及对该原子对象进行修改时所要求的顺序,但其本身不会为无关内存建立同步关系。
  • 获取与释放顺序可以通过一个原子对象建立同步关系。当所需关系成立时,释放操作之前的写入对相应获取操作之后的操作可见。
  • 顺序一致性顺序还会将所有顺序一致性操作置于一个符合模型规则的单一全序中。

例如,生产者可以先初始化普通数据,再对一个就绪标志执行释放存储。消费者通过适当的获取加载观察到已发布的标志后,就可以访问已初始化的数据,前提是程序还防止了后续相互冲突的访问,并满足对象生命周期的要求。仅仅将标志设为采用宽松顺序的原子对象,并不能建立这种发布保证。

在C编程语言中,原子类型和操作于 C11 中纳入标准;C++ 则在 C++11 中引入了标准原子操作设施。在这些语言中,volatile 限定符不能替代原子操作或线程间同步。

线性一致性是并发对象的一项相关正确性条件。满足线性一致性的操作,其行为就像是在调用与完成之间的某个时刻生效。这有助于推理并发接口的行为,但单独的原子访问不会自动使整个算法满足线性一致性,也不会为所有内存访问施加统一的顺序。

应用与进展保证

原子操作用于实现互斥锁、自旋锁、引用计数器、状态标志、工作分配以及并发数据结构。在多个执行单元访问共享内存的并行计算中,原子操作尤为重要。

原子操作也支持非阻塞算法,这类算法的进展保证与原子性是不同的概念:

  • **无障碍:**如果一个操作最终能够在不受干扰的情况下执行,它就能完成。
  • **无锁:**系统整体能够持续完成操作,但某个参与者可能反复失败。
  • **无等待:**在所规定的模型下,每个操作都能在其自身有限且有界的步骤数内完成。

CAS 重试循环并不自动具有无等待保证,任意一个使用 CAS 的算法也不自动具有无锁保证。正确性和进展取决于完整的算法,包括内存分配、内存回收以及它调用的任何其他操作。

局限与常见陷阱

复合不变量

各个变量分别具有原子性,并不能维持涉及多个变量的关系。例如,分别更新两个原子账户余额,并不会让其他观察者眼中的转账过程变得不可分割。保护这样的不变量可能需要互斥、事务机制或专门设计的并发协议。

同样,先检查再执行动作的过程,不会仅仅因为两个步骤都使用原子访问就变成原子操作。有条件的更新通常需要适当的读—修改—写原语或外部同步。

ABA问题与对象生命周期

在基于 CAS 的算法中,某个位置的值可能从 A 变为 B,然后又变回 A。之后与 A 进行比较时,即使期间发生过更改,比较仍会成功。这就是ABA问题。当算法依赖对象的变化历史或身份,而不仅仅依赖其当前表示时,这一问题就十分重要。

原子指针更新也不能保证对指针所指对象的访问是安全的。另一个线程可能移除并回收该对象。因此,并发算法需要独立的生命周期管理技术,例如危险指针、基于纪元的回收,或适当形式的垃圾回收。

争用与可扩展性

对同一位置频繁执行原子更新可能成为串行化瓶颈。相关缓存行的所有权可能在处理器之间反复转移。共享同一缓存行的独立变量也可能相互干扰,这种现象称为伪共享。

因此,原子操作并不天然比锁更快。性能取决于争用程度、内存顺序、架构以及受保护的工作量。正确使用锁的设计,性能可能优于复杂的基于重试的设计。

与事务原子性的关系

在数据库事务中,原子性通常意味着事务的更改要么作为一个整体提交,要么完全不生效。它是ACID特性之一。这种“全有或全无”的含义与共享内存操作的不可分割性有关,但两者并不相同。

事务原子性本身并不规定其他事务可以观察到哪些中间状态;这由隔离性决定。成功提交后数据能否持久保存,则由持久性决定。同样,原子内存存储本身并不保证持久存储,而能够应对崩溃的存储更新也不一定能提供线程间同步。