基于 Epoch 的内存回收

形式陈述

基于Epoch的回收用线程进入/退出访问区间的公告，批量判断退休节点是否还可能被旧操作引用。它不为每个读取节点单独登记，而是保护一个操作期间取得的所有指针。

固定p个已注册线程的共享内存，所有公告、全局epoch和结构指针访问均为SC 原子操作。全局E是单调递增、不回绕的整数；公告ann[i]为inactive或一个epoch值。节点从共享结构永久摘除、且不再产生新的共享引用后，才可retire；所有旧私有引用必须只在pin区间内使用，unpin后不得携带这些指针继续解引用。

以下是一套明确的教学协议，展示经典EBR的两次世代推进条件，不冒称所有库实现都逐行相同。

text

pin(i):
  repeat:
    e = load(E)
    ann[i] = e
    if load(E) == e: return
    ann[i] = inactive

unpin(i):
  ann[i] = inactive

tryAdvance():
  e = load(E)
  for each registered thread j:
    a = load(ann[j])
    if a != inactive and a != e: return false
  return CAS(E, e, e+1)

pin成功以后才能取得待保护结构中的指针；一个活动区间内不能擅自把ann改成更新epoch。摘除节点后把它与当时读取的E一起放进本线程私有退休列表，记为(n,r)。收集时读取当前E=s，只释放本列表中 $r\le s-2$ 的节点。该版本先使用整数代号说明规则；实际三桶循环实现还须处理桶重用及计数回绕。

直觉

Epoch像分批进入展厅的批次号。某件展品从入口名单移除后，新进入的人不再能拿到它，但早已进场的人可能还握着指向它的指针。回收者等旧批次的访问者离场，才能拆掉展品。

公告的作用不是给读者授予锁。多个线程可以同时pin并修改底层无锁结构；某线程暂停，其他线程仍可能完成很多操作，只是旧节点的安全回收会停下来。

旧epoch中的活动线程阻止第二次推进；它退出后，退休于e的节点到e加二才可释放

例子与边界

两次推进逐步看

初始E=10。T1已pin并公告10，取得节点a后暂停。T2从结构摘除a，将它以退休代号10入表。

阶段	E	ann[T1]	关键动作与结果
1	10	10	其他公告为10或inactive，可推进到11
2	11	10	T3扫描发现旧公告10，不能推进到12
3	11	inactive	T1恢复、结束最后访问并unpin
4	11	inactive	若所有其他活动线程公告11，可推进到12
5	12	inactive	a的代号10满足10≤12−2，可释放

第一次10→11并不说明T1已经退出：它原本就公告10，满足推进检查。若只等一次变化就释放a，T1恢复后仍可能读取已释放内存。第二次推进要求活动线程都已公告11；T1若还在原区间，就只能保持10，因而阻止该推进。

在E=11期间退休的b需等到E≥13。退休批次与线程进入时的批次不一定相同，所以不能笼统地把“不是当前桶”的节点全释放。

pin的复查关闭公告窗口

设T1读E=10后暂停，还未发布ann。T2的扫描看到T1为inactive，准备推进。

若T2先把E改为11，T1再公告10，复查发现E不同，必须清公告并重试，不能开始读取结构
若T1先公告10并复查成功，T2随后推进到11，这一次推进允许发生；但T1连续保留的10会阻止11→12

因此扫描不必与所有线程的进入动作形成一个大锁。复查和“两次推进”共同保证，新读者要么按新批次重新登记，要么被当作还未离开的旧批次。

安全性的核心次序

设节点n退休时记录r。任何仍可能持有n的读者都必须在n摘除之前进入pin区间，其公告不大于r，而且在最后使用前不能变成inactive或自行更新。

要从r+1推进到r+2，推进者必须读取每个公告，接受的只有inactive或r+1。一个仍持有n的旧读者不满足这个条件。若扫描看见它inactive，则该线程已经在程序顺序上结束此前全部使用；以后再次pin也不能从共享结构重新取得已退休的n。因此达到r+2后可安全释放。这个SC证明建立了“旧访问结束在释放之前”的必要先行次序，实际弱内存实现还要提供相应发布与排序。

推论与应用

无竞争pin尝试和unpin为 $O(1)$ ；一次推进扫描为 $O(p)$ ，另加一个CAS。竞争可能使pin或推进重试。若一次收集检查本线程r个退休项，简单列表过滤为 $O(r)$ ；按退休代号分桶可以直接处理已经满足条件的桶，但释放本身仍与节点数有关。

一次pin可保护很多连续指针访问，读侧成本往往低于逐节点hazard发布；代价是保护粒度粗。T1只握着一个旧节点却永久不unpin，可能把整个系统后续退休的许多批次都拖住，未回收内存可持续增长。有限线程数并不推出有限垃圾量。

底层对象的lock-free进展也要与回收分开。如果假设有足够新内存，T2、T3仍能完成结构操作；若真实内存耗尽而分配只能等待回收，整体服务最终也可能停顿。不能只证明CAS循环无锁，就宣称包含分配与EBR的完整操作在任意暂停下都持续前进。

线程注销、嵌套pin、可中断区间和epoch回绕都需明确协议。最简单的本页模型不允许一个线程仍保留指针时注销公告，也不把异步取消视为自动unpin。RCU同样利用旧读区间结束来判断回收，但它规定发布与宽限期的接口责任，本页则给出具体epoch公告、两次推进与退休阈值。RCU的不同实现不必采用这些计数规则，不能把两个名称当成同一套代码。

参考资料

Keir Fraser, Practical Lock-Freedom, Cambridge Technical Report 579, 2004，§5.2.3：退休limbo列表、两代间隔与暂停线程导致的回收阻塞；§5.3：SC与实际内存排序的区别

形式陈述 ​

两次推进逐步看 ​

pin的复查关闭公告窗口 ​

安全性的核心次序 ​

反向链接

形式陈述

两次推进逐步看

pin的复查关闭公告窗口

安全性的核心次序