Safe、Regular 与 Atomic 寄存器

Safe 只保护没有写者干扰的读。Regular 进一步要求干扰期间读到的也是“这次变化附近”真正写入的值，却没有协调两个读者对变化发生位置的判断。Atomic 则要求大家对同一次写何时生效能达成一致解释。

这里的 atomic 描述外部历史，不要求一条机器指令完成操作。反过来，把值存进某种机器字也不足以省去语言内存模型与访问协议的前提。三种寄存器规格回答的是可观察读值问题，均不自带终止或公平保证。

同一次写中的新旧倒退 ​

取 $V=\{0,1,2\}$，初值 $0$。写者启动长操作 $W=\mathrm{write}(1)$；在它返回前，读者先完成 $R_1$，再调用并完成 $R_2$。两次读都与 $W$ 重叠，但 $R_1$ 与 $R_2$ 不重叠。

若结果为 $(R_1,R_2)=(1,0)$，每个读都满足 regular：$1$ 来自重叠写，$0$ 是先前值。但 $R_1=1$ 迫使 $W<R_1$，实时顺序迫使 $R_1<R_2$，而 $R_2=0$ 又迫使 $R_2<W$。三条约束成环，所以不存在 atomic 解释。这个现象称新旧倒退；即使两个读来自不同读者，实时先后约束仍然有效。

若改成某个重叠读返回 $2$，它仍符合 safe，因为 $2\in V$；却不 regular，因为最近旧值与唯一重叠写值只有 $0,1$。若两读返回 $(0,1)$，则可排列为 $R_1<W<R_2$；$(0,0)$ 可把写放在两读之后，$(1,1)$ 可把写放在两读之前。这些都是合法 atomic 历史。

二值域也不能抹掉区别 ​

值域只有 $\{0,1\}$ 时，从 $0$ 写到 $1$ 的一次重叠读必然返回旧值或新值。然而，这不能证明所有 safe 二值寄存器都是 regular：初值为 $0$，写者再次执行 write(0)，重叠读仍可按 safe 返回 $1$。Regular 在此只允许 $0$。Lamport 的二值构造让写者在私有状态中记住上次值，只在值改变时实际访问底层 safe 寄存器，正是为了排除这个重复写边界。

这些定义不能未经说明地扩展到多写者：写操作自身也会重叠，“最近的写”不再由单写者次序直接给出。讨论多写者 regular 变体时，需要重新规定历史和写的排序规则。多写多读的 atomic 则可以直接使用同一个顺序寄存器规格：在保留实时先后的合法排列中，每次写替换当前值，每次读返回最近前驱写的值；并发写在排列中仍逐个出现。因而扩展的是可调用写的进程集合，并非读返回值的类型，也不是让一个读返回所有并发写值。ABD 的 MWMR 扩展公理库ABD 寄存器ABD register · Attiya–Bar-Noy–Dolev register用单调版本、多数确认与读后写回实现原子寄存器，并以写前查询和二元标签扩展到多写者。用写前查询生成二元标签，再构造这种全历史顺序；本页的 safe、regular 分类仍采用前述单写模型。

设计共享内存系统公理库共享内存系统Shared-memory system进程通过读写共享对象交互的并发模型。时，应先写明基础寄存器处于哪一级，再证明上层算法。以原子读为依据的版本验证，不能直接在 safe 读上运行并沿用原证明；重叠读可能凭空产生一个版本号。

即使每个槽都是 atomic，也不能把逐槽读取自动当作原子快照公理库原子快照Atomic snapshot · Wait-free snapshot · 原子共享内存快照利用带序号的原子寄存器、重复收集与已发布视图，在有限自身步骤内读取共享数组的线性一致快照。。单槽历史各自合法，与整个数组能在一个瞬间被读取，是两项不同承诺。进展则另由wait-free公理库Wait-free 进展Wait-free progress · Wait-freedom · 无等待进展每个正确参与者的每次操作都在有限个自身步骤内完成的个体级非阻塞保证。等条件描述：安全规格再强，也不排除某个操作永不返回。

ABD 寄存器公理库ABD 寄存器ABD register · Attiya–Bar-Noy–Dolev register用单调版本、多数确认与读后写回实现原子寄存器，并以写前查询和二元标签扩展到多写者。在异步消息传递中实现这里的单写多读 atomic 规格：多数写确认保护写后读，读者返回前的多数写回进一步排除上述新旧倒退。它说明 atomic 是可由多轮消息实现的外部承诺，不要求共享的原子机器字。

自测：保留上例时间区间，列出二元结果 $\{0,1{\}}^2$ 中哪些可线性化，并说明若把 $R_2$ 移至 $W$ 返回之后，哪些结果还合法。检查标准：原来仅 $(1,0)$ 不 atomic；移动后第二读必须为 $1$，只剩 $(0,1)$ 与 $(1,1)$，这个限制连 safe 也必须遵守。