原子操作

把高级操作当成一步，意味着客户端不能利用它的内部交错获得顺序规格禁止的结果。实现可以先分配节点、再修改指针；需要证明的是这些内部动作产生的所有调用—返回历史，都能解释为合法原子步骤。线性化点有时取成功的 CAS，有时依赖另一线程的帮助动作，未必是调用者固定的一条指令。

原子性必须标明对象边界。一个队列的 enqueue 可以原子，却不能推出“向两个队列各入队一次”也是原子操作；两个独立对象之间仍存在其他调用可插入的间隔。它也不保证等待时间：把整个方法置于锁内可以满足原子规格，但持锁者停止时其他调用可能永远等待。

正例：线性一致的原子寄存器不仅禁止撕裂，还要求读值能放入保留实时先后的合法顺序。初值为 0，write(1) 已返回后才开始的读，在没有其他写时必须返回 1；仅承诺“读到某次完整写的值”仍可能允许返回过时的 0，所以无撕裂只是必要的一部分。反面对照能看清它防住了什么：在只支持 32 位原子访问的机器上用两条指令写一个 64 位数，并发读者可能读到"前一半旧值、后一半新值"拼成的从未被写入过的数——原子性排除的正是这种中间状态泄露。

边界情形之一是复合操作：先原子地读 $x$、再在 $x$ 满足条件时原子地写，这两步各自原子，但整体不原子——另一线程可在两步之间修改 $x$，造成 check-then-act 竞态。消除它需要把"读—判—写"合并为单个原子的读改写理路读改写原语Read-modify-write operation · RMW将读取旧状态、依据旧状态决定更新及返回结果合为一个原子状态转移的同步原语；其内存序和进度保证需另行规定。操作，例如比较并交换理路比较并交换Compare-and-swap · CAS原子地比较内存值并在相等时写入新值、同时返回比较结果的读改写原语。。之二是术语歧义：数据库事务的"原子性"指故障时全做或全不做（失败原子性），与这里的并发不可分割性相关但不相同。之三是排序：硬件原子指令的语义还涉及内存排序、访问宽度与对齐，原子性本身不提供跨位置的顺序保证，弱内存模型下仍需 acquire/release 等排序约束才能建立线程间的可见性推理。

例如库存为 1，A、B 先后原子读取都得到 1，随后各自写入 0 并发货，库存字段始终完整却发出了两件商品。用 compare_exchange(1,0) 把检查与扣减合为一次 RMW 后，只有一个调用能成功，另一个必须按失败结果处理。若还需同时写订单记录，单个库存 CAS 并未覆盖该跨对象不变量，仍要另定事务或同步边界。

原子操作是同步对象的实现基础：互斥锁理路互斥锁Mutex · Mutex lock · 互斥量以获取、释放与所有权封装临界区互斥的同步对象。可用原子测试与更新转移所有权，信号量理路信号量Semaphore · Counting semaphore · 信号灯以非负计数保存可用许可，并用原子等待与释放操作协调容量或事件的同步原语。实现则需原子维护许可计数及等待队列状态，引用计数依赖原子增减，无锁数据结构以比较并交换为骨架并追求lock-free 进展理路无锁进展Lock-free progress · Lock-freedom系统整体保证在有限步内有某个操作完成，而不保证指定线程。。这些对象各自还规定所有权、阻塞或唤醒语义，不能从“底层更新是原子的”直接推出完整接口正确性。

在正确性理论中，为每个操作指定线性化点是证明线性一致性理路线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。的标准手法，原子操作因此连接实现与顺序规格。不同原子原语的表达力并不相同；它们能为多少参与者实现何种对象，由共识数层级理路共识数与 Wait-free 层级Consensus number · Consensus hierarchy · Wait-free hierarchy以共识数分类同步原语，并完整证明二进程原子读写共识的双价、临界配置和覆盖写入下界。统一刻画。