D04：审核带回收的并发工作队列
固定模型与题面
所有步骤处于SC原子读写/CAS模型；线程可在任意两步之间暂停。已发布节点的value不变，next只从null变为后继；地址只有在回收协议允许之后才能复用，不重新插入同一个已退休节点。分配暂视为能在有限步完成，以便单独比较对象算法与回收的进展。
采用Michael–Scott队列。d是哨兵，u.value=α，v.value=β。每个hazard槽为固定实际内存位置；在一次危险使用期间不能把保护迁移到另一槽。退休节点只入列表，扫描以后才可能释放。
第一组执行从空队列开始：Head=Tail=d，d.next=null，A准备入队u，B准备入队v。
I1 A把u链接到d.next，然后暂停，尚未改Tail
I2 B帮助Tail从d前进到u
I3 B把v链接到u.next
I4 B把Tail推进到v并返回
I5 C把Head从d移到u，返回α，退休d
I6 A恢复，尝试CAS(Tail,d,u)，随后结束第二组执行单独重置为Head=d、Tail=v、物理链d→u→v。读者R尝试出队，使用固定槽R₀保护旧Head、R₁保护后继；其他线程C、D可以分别成功出队α、β，返回后清空自己的hazard。R的正确读取前缀为：
P1 h = Head
P2 R₀ = h
P3 若Head != h则重试
P4 n = h.next
P5 R₁ = n
P6 若Head != h则重试
P7 若非空且h != Tail，读取n.value并尝试CAS(Head,h,n)遇到Head==Tail但next非空时先帮助Tail，再重试。失败尝试不再使用其局部节点指针以后才清槽。
给定两条交错：
LATE: R执行P1至P4后暂停；C、D依次出队；扫描；R继续P5至P6
EARLY: R执行P1至P6且两次验证成功后暂停；C、D依次出队；扫描；R继续P7第三组讨论另一种回收方式。E=11，T1仍在先前pin区间并公告10，T2为inactive，T3公告11。已退休d的代号为10、u的代号为11。按本单元EBR协议，只接受inactive或当前E的公告才能推进，节点须等待至退休代号加二。
选修操作也给定如下，不要求自行寻找反例：
- 有序集合a(1)→b(3)→d(7)，删除b与插入c(5)竞争b.next
- 中央栈为[a]，push(b)与pop在同一个消除槽争夺WAIT→MATCH；拥有者可能同时尝试WAIT→CANCEL
- CASN d要求把(x,y)从(1,2)改为(2,1)，地址顺序x<y；另有失败执行先在y读到8，稍后y被改回2，再将d.status置F
任务
- 为I1至I6列出物理指针与抽象队列；指出每次入队/出队的线性化点、尾帮助的作用以及I6失败是否使A入队失败
- 为LATE与EARLY列出C、D结束后的Head、退休列表及R₀/R₁。扫描分别可以释放谁？R恢复后是否可以读取u.value、是否可以再次返回α？
- 若只发布R₀而不发布R₁，指出一次真实悬空读取；说明入队读取t.next是否也要保护
- 反驳“保护从槽1移到槽2时保持重叠，就足以让单遍扫描安全”：初始槽1=u、槽2=null，给出四步漏检轨迹
- 计算第三组EBR中两次后续推进及d/u最早释放条件；再与MCS保护的普通队列比较R永久暂停时的进展和垃圾量
- 对三个选修操作分别说明：标记先于摘链如何保留c；取消/匹配哪个CAS胜出后拥有者才能回中央栈；CASN成功和失败为何不能统一选择最后一次清理为线性化点
- 比较MCS与CLH：A、B、C按此顺序排队，CLH初始哨兵为S、各请求节点为a、b、c，B与C分别轮询谁？A释放后立即再次获取，为何应把mine改为pred？另按RCU的不可变配置模型重放：R1先进入并取得old，更新者发布new后开始宽限期，R2随后进入并取得new；R1退出而R2尚未退出时能否释放old？若R1永久暂停，具体阻止什么，与队列锁持有者暂停有何不同？
答案一：结构与抽象状态
| 步骤后 | Head | Tail | 物理链 | 抽象队列 |
|---|---|---|---|---|
| 初始 | d | d | d | [] |
| I1 | d | d | d→u | [α] |
| I2 | d | u | d→u | [α] |
| I3 | d | u | d→u→v | [α,β] |
| I4 | d | v | d→u→v | [α,β] |
| I5 | u | v | u→v | [β] |
| I6 | u | v | u→v | [β] |
A在I1链接u时入队生效，B在I3链接v时生效，C在I5的Head CAS处出队生效。I2和I4是路标推进，不再增加一次队列元素。I6期望Tail=d，实际为v，所以CAS失败；A仍已成功入队，必须正常结束，不能重入一次α。
开启hazard回收时，A对t=d的保护还须持续覆盖I6这个迟到CAS。因此I5的retire(d)不等于立即free(d)。本题下一组独立重置，避免把A的残留保护混入R的双槽问题。
答案二：晚发布与早发布
C先出队α，将Head从d改为u并退休d；D再出队β，将Head从u改为v并退休u。二者结束后Head=Tail=v，v.next=null，抽象队列为空，退休列表为{d,u}。
LATE中，R停在P4之后，已经有R₀=d，但R₁仍为null。扫描必须保留d，却可以释放u。R恢复后只是把地址值u发布到R₁，再在P6看到Head=v≠d，因此不能执行P7，不能读取u.value。失败验证使它在潜在悬空读之前退出本次尝试。
EARLY中，R停在P6之后，R₀=d、R₁=u，两次验证当时都成功。C、D结束后的扫描必须同时保留d和u。R恢复可以安全读取u.value=α，因为固定实际槽R₁仍保护u；但CAS(Head,d,u)会因Head=v失败。R不能返回刚读到的α，否则会把同一个值重复出队。它应丢弃这次尝试的局部结果，结束对d/u的危险使用后清槽，再从当前队列重试，最终可返回EMPTY。
两条轨迹分别说明：晚发布靠验证失败防止悬空读；早发布保证旧节点可读，却不保证结构更新仍能成功。内存安全与线性化验证不能互相替代。
答案三：只保护旧Head不够
若R只发布R₀=d，读取n=u以后暂停，C、D照样可以连续推进Head并退休d、u。d受保护，u没有保护；扫描释放u后，R若直接读u.value便是use-after-free。旧哨兵d还活着，并不让d.next曾经指向的u自动保持活着。
入队也要保护其局部t。正确次序是读取Tail，发布固定槽=t，复查Tail=t，然后才读t.next；保护还须覆盖所有随后使用t作为地址或CAS期待身份的步骤。队列刚开始只有一个哨兵时，入队者持有的旧Tail也可能随着别人的入队、出队成为退休节点。
答案四：重叠迁移仍会漏检
初始槽1=u、槽2=null，回收者逐槽扫描，不持有全体槽的原子快照。
- 回收者读取槽2，得到null
- 读者写槽2=u，暂时两个槽都有u
- 读者清槽1，仍由槽2保护u
- 回收者读取槽1，得到null
扫描结果没有u，虽然每个真实时刻至少一槽含u。故单遍扫描所需的是危险使用从合法获取时刻到结束，同一个实际槽持续保护。仅交换私有的“当前/前驱”槽角色名称不改变实际内存，可保持该条件；实际搬移地址需要额外协议。
答案五：进展与空间
E=11时，T1公告10，所以第一次尝试11→12失败，d和u都不能按阈值释放。T1完成最后访问并unpin后，若其他活动线程都公告11，就可推进到12；d的10满足10≤12−2，u的11不满足。
要推进12→13，仍在公告11的T3必须结束该区间，或者退出后重新pin并公告12；不能在仍持有旧指针时直接改公告。达到13后，u的11满足11≤13−2，才可释放。
若R使用MCS保护普通队列并在临界区永久暂停，其他所有队列操作会在锁前等待；只要全部节点访问和释放都遵守同一把锁，就不会有并发出队者越过R释放它正在读的节点，但服务被阻塞。
若使用MS队列加固定hazard槽，暂停R可以留下两个受保护节点，其他线程仍可沿新Head操作并回收不受保护的退休节点；还有各线程的退休批次缓存成本。若改成EBR并让R永久停在旧pin区间，epoch推进会被挡住，其他线程退休的许多新节点也不能及时释放，垃圾量可不断增长。有限内存最终耗尽时，不能继续声称包含分配的整体服务无条件进展。
选修答案：三个不同的决定点
若插入c先把b.next从d改为c，删除器按旧d作标记CAS会失败；它必须重读c，标记指向c的next，再让a跳过b连到c。若删除标记先成功，插入器期望未标记的d便失败，重新搜索后可在a与d之间插c。标记封住的是b继续作为插入前驱的资格。
消除槽中，WAIT→CANCEL成功才允许拥有者回中央栈。若WAIT→MATCH先成功，取消必失败，拥有者接受该次匹配，不能再执行一次中央push。匹配对可在线性历史中相邻排列为push(b)、pop→b，中央栈仍为[a]。
CASN成功在status U→S时让全部逻辑值从(1,2)变为(2,1)，后续清理只是表示变化。失败执行则在线性化于观察到y=8的那个不匹配读取；y后来改回2不撤销此前有效的失败见证。最后一次清理既不能说明成功何时可见，也不保证失败条件当时仍成立。
答案七：轮询对象与旧读者
MCS中B轮询b.wait、C轮询c.wait，由各自前驱清除其标志；CLH中B轮询a.wait、C轮询b.wait。CLH的A释放时先写a.wait=false，再令mine=pred=S；下一轮发布S并排在当前尾节点之后。若A立即把a.wait重新设为true，尚未看到false的B会继续等a，A的新请求却已排在C之后，便可能形成A等C、C等B、B等A的环。接管前驱节点让刚完成的通知留在a上，直到B不再需要它；节点也必须在仍被引用时保持有效。
RCU的顺序是发布new、开始宽限期、等待相关旧区间结束、再释放old。R1在宽限期开始前已进入且持有old，必须等它退出。R2在宽限期开始后进入并从P取得new，本次宽限期不必等它；所以R1退出后，即使R2仍在读new，也可以在宽限期满足条件并返回后释放old。这里“可以”只表示生命周期条件已经满足，不是实时完成保证。
R1永久暂停会阻止本次宽限期返回及old回收；使用同步synchronize的串行更新者也会卡在该调用，但后来读者仍可读取已发布的new。异步回调可以推迟释放而不让该次发布等待，不过待回收对象会积累。队列锁持有者若停在临界区，则后继不能取得锁并执行受保护操作；阻塞的是所有权交接，不只是旧版本回收。
验收标准
- 抽象队列在链接CAS而非Tail修复时增长，I6失败不撤销入队
- LATE只保留d且不解引用u；EARLY保留d/u但Head CAS失败，不能重复返回α
- hazard保护按固定实际槽持续计，四步迁移反例必须得到全空扫描结果
- EBR在12可释放代号10、在13可释放代号11，旧活动公告阻止相应推进
- 锁进展、无锁结构进展、回收进展和有限内存可用性分别说明
- 所有结论都在题面SC/生命周期假设内，没有直接声称弱内存C++实现已获证明