消除回退栈 | Codeboy's Blog

形式陈述

消除回退栈在一个线性一致的中央栈旁增加交换槽。并发的push(v)与pop可以直接配对：push成功，pop取得v，中央栈不变。操作先尝试中央栈；因竞争失败后，才在有界消除窗口寻找互补操作，失败则回到中央栈。

本页采用SC原子读写与单字CAS。中央栈使用已有的无锁栈操作；节点及以下请求描述符在可能被访问时不释放、不复用。消除部分用请求描述符说明状态协议，布局不同于原论文的location/collision数组，但保留互补配对、单次认领和有界回退机制。

每个槽S为null或一个新鲜描述符指针d。d保存不可变的kind（PUSH或POP）、push值，以及原子state：WAIT、CANCEL或MATCH(r)。MATCH(r)可以编码为指向不可变结果记录的带标签指针，不要求对任意大值做多字CAS。

一个尝试只选择一个槽，执行以下协议：

text

tryEliminate(op, budget):
  d = load(S)
  if d != null:
    if d.state is CANCEL or MATCH:
      CAS(S, d, null)
      return RETRY
    if d.kind == op.kind: return RETRY
    r = immutableMatchRecord(value from the PUSH)
    if CAS(d.state, WAIT, MATCH(r)):
      CAS(S, d, null)
      return MATCHED(r)
    return RETRY

  mine = freshDescriptor(op, state=WAIT)
  if not CAS(S, null, mine): return RETRY
  repeat at most budget local polling steps:
    if mine.state is MATCH(r):
      CAS(S, mine, null)
      return MATCHED(r)
  if CAS(mine.state, WAIT, CANCEL):
    CAS(S, mine, null)
    return RETRY
  else:
    r = match record in mine.state
    CAS(S, mine, null)
    return MATCHED(r)

拥有者一旦发布mine，就不能同时回到中央栈；必须先确认取消成功，或接受已经确定的匹配结果。发布者与匹配者都可清理终态槽，但没人直接清掉WAIT槽来假装另一请求已经撤回。

直觉

如果栈当前为[a]，push(b)后紧接着pop，pop得到b，栈仍为[a]。这对互补操作对持久栈状态的净影响是零，所以可以在旁边直接交货，不必两次争抢中央Top。

交换槽解决的不是LIFO规则，而是如何在并发中可靠地确认“这一个push恰好交给这一个pop”。CAS把配对与超时取消放在同一个决定点上，防止一个值既被别人取走，又由原push重新放回中央栈。

push b与pop在交换槽配对并返回b，中央栈中的a保持不变，另一个pop仍可取得a

例子与边界

一对消除与一个中央出栈

设中央栈为[a]，P的push(b)和Q的pop已因此前竞争进入消除窗口。

P把PUSH(b)、WAIT描述符d放进槽
Q读到相反操作，成功把d.state改为MATCH(b)
Q返回b，P观察到MATCH后完成push，中央栈仍为[a]
R在中央栈成功pop，得到a，中央栈变为空

可把第2步附近的抽象历史排列成 push(b); pop→b，然后是R的 pop→a。一对消除操作必须相邻且push在前，不能把pop排在push之前再声称从空中取得了b。

若两个请求都是push，它们不互补，协议返回RETRY。误把两个push都报成完成却不改中央栈，会丢掉两个应该仍在栈里的值；两次pop也不能凭空为彼此提供元素。

超时与匹配只允许一个获胜

P的描述符仍为WAIT，P已用完预算，Q同时准备匹配。

若P的CAS(WAIT,CANCEL)先成功，Q的CAS(WAIT,MATCH)必失败，P可回到中央栈。Q不能仅因先前读到WAIT就拿走b
若Q的匹配CAS先成功，P的取消CAS失败。P必须读取MATCH并作为已经完成的push返回，不能再把b入中央栈

状态不回到WAIT，所以取消失败后唯一可能的终态是MATCH。若允许复用同一个描述符并把state重置WAIT，迟到线程可能误操作新一轮请求；基础模型用新鲜身份排除这种ABA，真实回收需另证。

暂停不会占住全部出路

P发布WAIT后永久暂停，这个槽可能长时间不可被同类请求使用。但其他线程只做有界槽尝试，随后仍回到中央栈；不能围着该槽等待P主动退出。

若一个互补请求Q出现，它还可认领P的请求并完成自己；P是一个允许补全到历史中的待返回操作。若Q在匹配成功后暂停，其他线程看到终态可清理槽，P也能从自身描述符读取结果。结果记录不能随着槽清空立即释放，因为原拥有者尚可能未读到它。

推论与应用

线性化分两类：中央栈操作沿用其关键CAS或空读点；消除对以成功匹配CAS为共同事件，push紧邻地排在pop之前。该事件在两次调用的时间区间内；一对操作对中央栈净影响为零，所以可插入中央栈的线性历史而不改变其他操作的返回值。

进展依赖中央栈仍满足lock-free，并且每次消除尝试预算有界。一次中央尝试若失败，表明其他线程已成功改变Top；消除若成功，则两个操作取得进展；消除失败不阻止下一次中央尝试。因此不能用无限等待碰撞的策略替换有界回退，否则可能破坏系统进展。

设轮询预算为B，单次消除尝试做 $O(B+1)$ 次本地/共享步骤、常数次CAS；同一操作可能经历无界轮数，所以不是wait-free。m个交换槽占 $O(m)$ 共享入口空间，另加未安全回收的请求与结果记录。随机选槽、调整窗口和消除范围影响吞吐，不能从正确性证明推出所有负载下都更快。

互补比例接近时，许多push/pop可以绕开中央瓶颈；几乎全是push或全是pop时，可消除的对数受到较少一侧数量限制。保留低竞争时的直接中央路径，正是“消除作为回退”而非“所有操作先去交换”的原因。

参考资料

Danny Hendler, Nir Shavit, Lena Yerushalmi, “A Scalable Lock-Free Stack Algorithm”, SPAA, 2004, 206–215，§2及Figures3–4：互补碰撞、撤回竞争；§5：配对线性化和lock-free证明

形式陈述 ​

一对消除与一个中央出栈 ​

超时与匹配只允许一个获胜 ​

暂停不会占住全部出路 ​

反向链接

形式陈述

一对消除与一个中央出栈

超时与匹配只允许一个获胜

暂停不会占住全部出路