安全,常规和原子寄存器之间有什么区别？

Question

有人能提供详尽的解释吗？我正在尝试并发编程并在尝试理解共识时遇到这些寄存器.

从Lamport的"进程间通信":...如果两个连续读取重叠相同的写入不能获得新的旧值,则常规寄存器是原子的.

假设,第一次来thread0.write(0)- 没有重叠.基本上,可以说使用Lamports定义,如果两个读取都是结果并且与之重叠,则thread1可以先读取1然后再读取0thread0.write(1).但那怎么可能呢？

Answer 1

对共享内存位置的读取和写入需要一段有限的时间,因此它们可能重叠或完全不同.

例如

Thread 1:      wwwww     wwwww
Thread 2:   rrrrr              rrrrr
Thread 3:   rrrrr rrrrr

线程2的第一次读取与线程1的第一次写入重叠,而第二次读取和第二次写入不重叠.在线程3中,两个读取都与第一次写入重叠.

一个安全寄存器是唯一安全的,只要读不重叠写入.如果读取不与任何写入重叠,则它必须读取最近写入所写的值.否则,它可能返回寄存器可能持有的任何值.因此,在线程2中,第二次读取必须返回第二次写入所写的值,但第一次读取可以返回任何有效值.

一个普通寄存器增加了额外的保证,如果读取与写入重叠那么它要么读取旧值还是新的,但多次读取重叠写不必同意其和值可能会出现"闪烁"来回晃动.这意味着来自同一线程的两次读取(例如上面的线程3中)与写入重叠可能会出现"乱序":较早的读取返回新值,后者返回旧值.

一个原子寄存器保证了读取和写入出现在单个时间点发生.在该点之前起作用的读者将全部读取旧值,并且在该点之后起作用的读者将全部读取新值.特别是,如果来自同一线程的两个读取与写入重叠,那么如果先前的读取返回新值,则后一个读取不能返回旧值.原子寄存器是可线性化的.

Maurice Herlihy和Nir Shavit 的多处理器编程艺术给出了一个很好的描述,以及示例和用例.