无锁进展

lock-free 是执行级而非单线程级保证：在任何持续有步骤发生的无限执行中，系统必须不断完成操作。某线程的 CAS 失败通常证明共享状态已被别人成功改变，这可作为“失败也见证全局进展”的摊还论证。它避免持锁者暂停导致全体冻结，但不控制哪一个请求获益，也不提供固定步数或延迟上界。

CAS 循环中，一个线程可能每次比较交换前都被其他线程抢先修改而无限重试；只要那些修改对应操作不断完成，算法仍可 lock-free。它因此不能推出个体无饥饿，也不能给指定调用提供步骤上界。

Treiber栈的push读取栈顶、构造新节点并CAS；若CAS失败，说明某次并发修改已在线性化点成功，线程可重读重试。一个恶意调度可让同一线程每次都在CAS前被抢先，永不完成而系统仍lock-free。消除回退栈理路消除回退栈Elimination-backoff stack · Elimination array stack让并发push与pop在有界交换窗口直接配对，并以单次认领/取消协议保持栈语义和无锁回退。还可让重叠push/pop配对而不修改中央栈顶，但配对与超时撤回应竞争同一个单次状态决断，不能失败后再重复执行中央操作。

内存回收的进展也必须计入。Hazard Pointer理路Hazard Pointer 安全回收Hazard pointer · Hazard pointers · 危险指针回收先发布并验证节点保护，再按hazard扫描释放退休节点，关闭裸指针获取与回收之间的竞态。通过固定槽持续保护具体地址；epoch回收理路基于 Epoch 的内存回收Epoch-based reclamation · EBR用进入区间的epoch公告与两次安全推进批量回收退休节点，并明确暂停线程对回收进展的影响。则等待旧活跃区间结束，一个暂停的旧epoch读者可能阻止后续批次释放。核心CAS循环无锁，并不足以推出内存耗尽后仍能分配和完成方法。

lock-free 是安全性与活性理路安全性与活性Safety and liveness · Correctness properties把系统正确性分为坏事永不发生与好事最终发生两类性质。中的系统级活性保证：无限执行中总有某个操作完成，但不保证指定线程完成；线性化点等安全证明仍需另行给出。

共享内存理路共享内存系统Shared-memory system进程通过读写共享对象交互的并发模型。中的原子读改写理路读改写原语Read-modify-write operation · RMW将读取旧状态、依据旧状态决定更新及返回结果合为一个原子状态转移的同步原语；其内存序和进度保证需另行规定。常实现 lock-free 对象，正确性还需与线性一致性理路线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。分开证明。标准非阻塞层级为 wait-free理路Wait-free 进展Wait-free progress · Wait-freedom · 无等待进展每个正确参与者的每次操作都在有限个自身步骤内完成的个体级非阻塞保证。 强于 lock-free，lock-free 强于obstruction-free理路Obstruction-free 进展Obstruction-free progress · Obstruction-freedom · 无障碍进展一个操作只要最终获得足够长的独占执行区间，就会在有限步骤内完成的非阻塞保证。；相邻页面分别给出个体有限步骤与 solo-termination 的量词，本页只刻画系统级持续完成。

无锁队列、栈和哈希表需要把算法重试、调度公平与内存回收组合成端到端进展论证。核心 CAS 循环满足 lock-free，不代表分配器或回收协议阻塞时公开方法仍满足该性质。