RDCSS 条件双比较单更新

形式陈述

RDCSS（Restricted Double-Compare Single-Swap）原子地检查控制字c与数据字x，只在二者满足期待值时更新x。给定期待值ec、ex及新值nx，其抽象动作是

r\gets x;\qquad \text{若 }r=ex\land c=ec,\text{ 则 }x\gets nx;\qquad \text{返回 }r.

返回的是数据字原值，不是成功布尔值：即使返回ex，也可能因为控制字不匹配而没有更新。控制地址与数据地址属于互不相交的区域；控制区可作原子读写，数据区的并发访问遵守本协议，不用裸写覆盖内部描述符。

本页以SC CAS实现它。每次调用分配新鲜、不可复用的描述符d，记录(c,ec,x,ex,nx)。原子数据字可存普通值或可识别的描述符标记D(d)，二者不能混淆。描述符字段在发布后不变，存在迟到帮助者时不释放。

text

complete(d):
  v = load(d.c)
  if v == d.ec:
    CAS(d.x, D(d), d.nx)
  else:
    CAS(d.x, D(d), d.ex)

rdcss(d):
  repeat:
    r = load(d.x)
    if r is D(other):
      complete(other)
      continue
    if r != d.ex: return r
    if CAS(d.x, d.ex, D(d)):
      complete(d)
      return d.ex

rdcssRead(x):
  repeat:
    r = load(x)
    if r is D(d): complete(d)
    else: return r

CAS仍返回布尔值。重复循环把原论文“返回旧值的CAS”写法拆成普通读加布尔CAS；比较更新仍由CAS原子完成，失败就重试。

直觉

直接“先读c，再CAS x”留下一个窗口：读者认为操作仍允许继续，控制字却可能已经宣布取消。RDCSS先把x临时变成一张公开的工作单，任何访问者都能按单据完成检查与替换。

描述符不是锁的持有人身份。原线程暂停后，别的线程仍有完成所需的全部输入，能够帮助撤下工作单，而不必等待所有者恢复。

例子与边界

拥有者暂停，帮助者完成

令控制status=Undecided，数据x=7，调用希望在status仍未决时把x改成9。

T1发布d=(status,Undecided,x,7,9)，成功把x从7改为D(d)，随后暂停
T2调用rdcssRead(x)，读到D(d)，而非把它当作用户数据返回
T2读取status=Undecided，CAS(x,D(d),9)成功
T2重读x得到9并返回；T1恢复后再complete，CAS因D(d)已不在而失败，不重复更新

如果第3步之前status已经变为Failed，则帮助者把D(d)恢复为7，rdcssRead返回7。两条路径都只改变x，status不是被交换的第二个数据字。

控制读取与最后CAS不是同一时刻

设T2读到Undecided后暂停，T3把status改成Failed，然后T2恢复并把D(d)改为9。这仍可正确：RDCSS的抽象操作可放在T2读取Undecided的时刻，当时x已被本描述符占住，逻辑旧值为7，两项比较都满足。

因此不能把所有RDCSS的线性化点都放在最后写9的CAS。对成功安装过描述符的调用，可选最终成功撤下该描述符的帮助者所作控制字读取；该读取发生在描述符唯一活动区间内。若调用因数据值不等ex直接返回，则选那次普通值读取。rdcssRead选其最终读到普通值的读取。

两个帮助者可能分别读到不同控制值，但只有一个CAS能首次把D(d)换走。结果由成功撤下者对应的控制观察解释；迟到CAS必须仍比较D(d)，不能无条件覆盖已经发生的后续更新。

为何要限制地址角色

complete直接读取控制字，不递归解释它。如果控制地址也允许存同一层RDCSS描述符，或者c=x，原来的读法与帮助终止论证就不再适用。限制控制区与数据区分离，使帮助动作只需有限次读/CAS，没有任意自引用的描述符依赖。

同样，普通数据值必须与D(d)可区分。若一个合法用户整数恰被错误识别成描述符地址，程序会按错误布局读取；若描述符身份过早复用，迟到CAS又可能认错新操作。标签位、专用句柄或运行时类型标记解决的是表示问题，安全回收解决的是生存期，不能互相替代。

推论与应用

每个描述符最多被安装一次：安装成功后拥有者退出安装循环。该描述符一旦由complete撤下，就不会再次成为当前调用的活动标记。任何一次complete做常数步，并且要么自己撤下标记，要么由失败CAS得知标记已被别人撤下。

因此，rdcss或rdcssRead若不断因描述符而重试，每轮都伴随某个活动描述符被清理；若不断因安装CAS失败重试，则数据字也在被其他操作改变。这给出无锁进展机制，不给某个指定调用固定重试上限。无竞争时一次操作为 $O(1)$ 步和一个常数大小描述符；竞争时需把帮助和重试次数另计。

RDCSS常作为多字CAS的内部步骤：只有大操作status仍Undecided时，才把它的描述符安装到某个数据位置。它只负责一个数据位置的条件占位；对多个地址的统一成功/失败，还需要上层单次决断协议。

SC原子字模型已把发布可见性作为假设。移植到弱内存平台仍需保证先初始化描述符、再发布标记，以及帮助者安全读取字段；回收器也必须覆盖迟到帮助者。这里没有把这份算法解释为开箱可用的弱内存代码。

参考资料

Timothy L. Harris, Keir Fraser, Ian A. Pratt, “A Practical Multi-Word Compare-and-Swap Operation”, DISC, 2002，§4、Figure1：RDCSS、地址分区、帮助与线性化；§6：标记和描述符生存期

形式陈述 ​

拥有者暂停，帮助者完成 ​

控制读取与最后CAS不是同一时刻 ​

为何要限制地址角色 ​

反向链接

形式陈述

拥有者暂停，帮助者完成

控制读取与最后CAS不是同一时刻

为何要限制地址角色