ConcurrentStack<T>：无锁链式栈的 CAS 协议
专栏：C# 与常用数据结构源码剖析
本文基线：.NET 8.0.0发布标签中System.Collections.Concurrent.ConcurrentStack<T>的公开契约与私有实现
阅读原则：公开 API 是跨版本契约；字段、节点类型和退避策略只是该标签下的源码事实，不应当成未来版本的 ABI。
ConcurrentStack<T>常被概括成“单链表加一次 CAS”。这句话抓住了主干，却容易遮住真正值得学习的部分：为什么节点可以只发布一次？哪个指令是线性化点？无锁是不是等于每个线程都会很快？枚举和Count看到的又是什么时刻？
本文从不变式、内存顺序和进度保证出发，再回到游戏开发中的任务回收、对象复用和 Unity 平台选型。
1. 先定义契约：它是并发 LIFO，不是调度器
栈的抽象规则是后进先出：单线程依次推入A、B、C，随后弹出应得到C、B、A。并发情况下，不同线程的调用可以时间重叠，因而不能用墙上时钟强行排出唯一顺序。正确的要求是可线性化：每个已完成操作都可以视为在调用与返回之间的某一瞬间生效，所有瞬间组成一个合法的顺序栈历史。
ConcurrentStack<T>适合表达“取最近放入的一项”，但不自带以下语义：
- 没有公平性，先等待的线程不一定先获得元素；
- 没有容量上限和生产者背压；
- 没有异步等待数据、完成通知或取消协议；
- 没有“取出后只处理一次”的业务事务保证；
- 不会因为容器是线程安全的，就使元素内部的可变状态也自动线程安全。
如果需要有界异步管道，Channel<T>通常更贴近问题；如果需要阻塞式生产者/消费者协议，可考察BlockingCollection<T>。不应把“无锁”当成绕过业务协议设计的理由。
2. 固定版本下的存储模型
在.NET 8.0.0源码基线中，核心是一个头引用与不对外暴露的节点类。下面是为突出结构而改名和省略特性的结构化节选，不是可替换 BCL 的完整源码：
private volatile Node? _head; private sealed class Node { internal readonly T _value; internal Node? _next; }若按顺序推入A、B、C，可达节点图为：
_head -> [C] -> [B] -> [A] -> null结构只要保持四条不变式：
_head为null当且仅当栈为空；- 从
_head沿_next可达的节点，按照由新到旧构成单链； - 已成功发布的节点的值不再改变，它们的
_next在正常公开操作中也不被重写； - 修改整个可达图入口的动作，通过对
_head的原子操作完成。
第 3 条非常关键。新节点在尚未共享时可以设置_next；一旦 CAS 把它发布为新头，其后继链就可被当成不变快照。这让读取者无需为遍历链表加锁。
节点是引用类型，每次单元素Push通常都要分配一个节点对象。具体对象字节数依赖位数、对齐、对象头和T的实例化，不能用一个固定数字概括。与连续数组相比，链式节点也可能带来更差的缓存局部性和更高的 GC 扫描成本。
3.Push：先私有构造，再一次发布
单元素入栈可以用下列教学伪代码理解：
Node node = new(item); while (true) { Node? observed = Volatile.Read(ref head); node.Next = observed; Node? actual = Interlocked.CompareExchange( ref head, node, observed); if (ReferenceEquals(actual, observed)) return; // 其他线程改过 head，用新的观测值重连并重试。 }CompareExchange(ref location, value, comparand)是不可分割的“比较后交换”：仅当location仍等于comparand时写入value，并无论成功与否都返回操作前的值。因此不能把它写成“先if再赋值”：那会在比较和写入之间留下竞态窗口。
成功 CAS 就是Push的线性化点。在它之前，新节点只属于当前线程；在它之后，所有按正确同步方式读头指针的线程，都能看到节点的值和已设置的后继。Interlocked不只是防止指针被写坏，它还参与建立发布所需的内存顺序。不应用“x64 大概不会乱序”代替 C#/.NET 内存模型下的同步原语。
两个线程同时观测到旧头A时，两者都可以先私有地构造“新节点 -> A”。最多一个 CAS 能把自己的节点设为头；失败者读取新头、更新尚未发布节点的_next，然后重试。所以“Push只需一次 CAS”只对无竞争快速路径成立，不是每次调用的上界。
4.TryPop：只有赢得 CAS 的线程能取走头节点
出栈的教学伪代码如下：
while (true) { Node? observed = Volatile.Read(ref head); if (observed is null) { result = default!; return false; } Node? next = observed.Next; Node? actual = Interlocked.CompareExchange( ref head, next, observed); if (ReferenceEquals(actual, observed)) { result = observed.Value; return true; } }非空出栈的线性化点是成功把_head从observed替换为observed.Next的 CAS。另一线程若同时看中该头节点，它的 CAS 会失败，因而不会把同一个元素成功弹出两次。空栈返回的线性化点可视为读到空头的瞬间；返回之前另一线程又推入元素不构成错误，因为两个调用存在重叠。
固定标签中的实现还区分无竞争快路径和竞争慢路径，慢路径使用自旋/退避来降低多线程反复碰撞。具体在第几次尝试让出 CPU、是否随版本调参，都是实现细节。不应把SpinWait解释成固定的“第 8 次 Yield、第 16 次 Sleep”契约；这些决策还会受平台、处理器数量和运行时实现影响。
TryPeek不删除元素。它读到某个头后，该节点即使紧接着被另一线程弹出，仍然可由当前线程的局部引用安全读值。但返回值只是调用期间的一个观测，不是对后续TryPop结果的预留。
5. 进度保证：无锁不等于无等待
这类 CAS 循环通常被称为lock-free：在持续竞争中，某个线程的 CAS 之所以失败，通常意味着别的线程已成功改变头指针，因而系统整体在前进。它不是wait-free：某个倒霉的线程可以连续失败，公开 API 也没有承诺有限步内完成。
无锁也不意味着：
- 不会被操作系统调度器挂起；
- 不会因竞争消耗 CPU 或发生缓存行来回转移；
- 吞吐一定高于
lock (Stack<T>)； - 尾延迟一定更小；
- 一组业务操作可以自动组成原子事务。
头指针是所有写操作的单一热点。核数增加后，CAS 重试与缓存一致性流量可能主导成本。如果临界区很小、竞争不高，锁版本可能更简洁，也可能一样快。结论必须在目标硬件、运行时、元素类型和真实竞争度下测量。
6. ABA：这个实现为何不仅靠“GC 会保护地址”
ABA 描述 CAS 的比较值从A变成B，后来又变回“同一个A”，使只比较标识的线程无法察觉中间变化。在手工内存管理的可复用节点栈中，它可导致严重错误。
对这里的托管实现，不能只说“GC 不重用地址，所以没有 ABA”。更完整的理由是：
- CAS 比较的是托管对象引用语义，而不是用户手中可自由复用的原始地址；
- 线程观测到节点后，局部引用使该对象在使用期间保持可达；
- 最重要的是，公开
Push(T)会为值构造新的私有节点，而TryPop不会把被弹出的Node交给调用者；因而用户无法把同一个节点对象重新插回头部； - 已发布节点的链接不被外部代码篡改。
这些条件一起排除了经典“弹出 A、修改 A、再把同一节点 A 推回”的路径。如果自行实现无锁结构，并引入节点池、非托管指针或可重新入链的节点，上述证明便不再成立，需要版本标记指针、hazard pointer、epoch reclamation 等其他方案。
7. 批量操作：单个线性化点，不是随意多次调用
PushRange先在当前线程中构造一整段节点链，然后把该链的尾节点指向观测到的旧头，最后用一个成功 CAS 发布新头。若 CAS 失败，只需让尾部重连最新头并重试，不应每次都重新遍历整段链表找尾。
它的顺序等价于对指定区间从低索引到高索引逐个调用Push，因此该范围的最后一项位于新栈顶。下面示例返回3, 2, 1：
var stack = new ConcurrentStack<int>(); stack.PushRange(new[] { 1, 2, 3 }); stack.TryPop(out int first); // 3 stack.TryPop(out int second); // 2 stack.TryPop(out int third); // 1TryPopRange先从某个头快照沿链表计算本次最多要取的区间，然后尝试用一次 CAS 跳过整段。成功后才把值按弹出顺序写入目标数组；返回值是实际取得的数量，可以小于请求数。参数区间、空数组等异常是公开 API 契约的一部分，不应为了手写“更快版”而漏掉验证。
批量操作的价值不是一个无条件的性能倍数，而是把多个节点的发布或移除合并到一个头指针交换，并且对外暴露一个整段变化。元素分配、数组写入和竞争重试仍有成本。
8.Count、IsEmpty、枚举与快照的真实边界
8.1 单次观测不能预测下一次操作
IsEmpty是对头部的并发安全观测，但返回后栈立刻就可能变化。下列代码有典型的检查后执行竞态：
if (!stack.IsEmpty) { // 此时另一线程可能已经弹出最后一项。 stack.TryPop(out var item); }正确做法是直接以TryPop的布尔结果决定是否获得元素。Count需沿节点链计数，因而不是可以在热路径随意读取的 O(1) 计数器；它适合监控或诊断性观测，不适合作为随后多步业务逻辑的同步条件。
8.2 不变后继链使枚举快照成立
枚举器可以捕获某一头节点，然后沿不再修改的后继链向下遍历。之后的新入栈位于快照头之前，不会进入这次遍历；之后的出栈只改变全局头引用，不会破坏已捕获链。因此枚举不会像Stack<T>那样因并发修改而依赖版本号立即抛出异常。
但“快照”不等于元素对象的深拷贝。如果T是可变引用类型，枚举者和其他线程仍持有同一对象，它的字段可能在遍历中被改变。如果需要内容级快照，应使用不可变元素，或在业务层复制数据。
枚举器、ToArray或长时间持有的局部头引用还会延长已出栈节点和其值的生命期。这不是泄漏，而是快照正确性的代价；如果元素持有大块资源，应避免把枚举器跨帧或跨任务长期保存。
9.Clear和引用生命周期
Clear可通过原子地把全局头设为null切断容器入口。它不遍历每个节点执行手工释放；当没有并发操作、枚举器或其他局部引用再持有旧链时，GC 才可以回收相关节点与元素。
并发Clear不是“世界停顿式清空”。一个Push可能在Clear前读取旧头，但它必须经过 CAS 竞争；各操作仍可按它们的线性化点排出合法历史。如果业务需要“清空后禁止所有旧生产者再写入”，就需要额外的停止协议、代际标识或替换整个容器引用，单独调用Clear不足以表达该业务边界。
不建议通过反射抓取私有Node来做对象池：这同时破坏实现封装、节点不变性和前面的 ABA 推理。若分配成本确实不可接受，应先确认需求是否可以用数组批处理、线程本地缓冲、有界Channel<T>或经过专门验证的池化数据结构表达。
10. 复合操作与错误用法
10.1 线程安全的方法不会自动组成原子序列
假设需求是“只在栈顶是某任务时才替换它”。TryPeek后接TryPop存在间隙，另一线程可以在其间修改栈。ConcurrentStack<T>没有公开的条件式 CAS API，不能从外部访问其私有头指针补上原子性。此时应重设业务状态机，或用一把锁保护整个复合不变式。
10.2 LIFO 可能造成饥饿
若生产速度长期高于消费速度，旧任务会被新任务不断压在下面。对象复用中“最近归还对象有更好缓存热度”可能是优点，但对必须有界时间内处理的任务却是错误语义。后者应考虑 FIFO 队列、优先队列或带公平性约束的调度器。
10.3 不可用Count当作容量控制
if (stack.Count < limit) stack.Push(item);多个生产者可同时通过检查，最终超出limit。即使额外维护原子计数，也要严密处理预留、发布失败和异常回滚。需要容量上限时，优先使用契约本身支持有界容量的协调原语。
10.4 容器原子性不保护元素
把List<T>、UnityGameObject或其他可变对象放入并发栈，只保证引用的入栈和出栈不破坏容器。对象在线程间的所有权转移、何时允许修改以及何时归还资源，仍需要明确协议。
11. Unity 中的边界：托管并发不等于可以跨线程操作引擎
Unity 项目的 API 可用性取决于编辑器版本、API Compatibility Level 和目标平台提供的参考程序集。即使都能编译ConcurrentStack<T>，Unity Mono 后端、IL2CPP AOT 和上游 CoreCLR 也不是同一个执行引擎；代码生成、GC、原子指令降低和调度环境都可不同。不应把 CoreCLR 某台机器上的基准数字直接复制为所有 Unity 平台结论。
更重要的是，大多数UnityEngine.Object及场景 API 要求在主线程访问。后台线程可以把纯托管、所有权清晰的结果放入容器，主线程再取出并应用；但一个无界 LIFO 通常不是跨线程消息流的最佳默认值。消息是否可丢弃、是否要保序、每帧最多消费多少、停机时如何排空，都应先定义。
一个可辩护的场景是多线程归还完全托管的临时工作项，下一个申请者优先复用最近归还的项。即便如此，也要比较局部缓存加全局溢出栈、ConcurrentBag<T>或专用池。若元素的创建/销毁必须回到主线程，还要把这一约束编入池的生命周期。
IL2CPP 下必须在真实目标设备验证，特别是主机、移动端和 Web 类平台的线程限制不同。“编辑器中正常”只能证明编辑器当前后端与硬件的行为，不能代替玩家设备测试。
12. 如何做可复现的正确性和性能实验
12.1 先测不丢、不重，再谈吞吐
让P个生产者分别推入不重复的编号区间，C个消费者循环弹出，停止生产后排空栈。最后检查：
- 弹出总数等于推入总数；
- 所有编号的出现次数恰好为 1；
- 消费者报告的成功数之和与最终集合一致；
- 在无并发的小规模用例中，严格验证 LIFO 顺序和批量区间顺序。
并发压力测试不能单凭一次通过证明无竞态。应使用多个随机种子、不同生产/消费者比例、空栈竞争和长链排空场景，并为每轮设置超时。对自研结构，还可记录小历史并用线性化检查器搜索是否存在合法顺序化。
12.2 基准必须隔离调度器噪声与测试器开销
可对比ConcurrentStack<T>、一把锁保护的Stack<T>，以及语义允许时的线程本地栈加批量合并。每一组都要报告：
- .NET SDK/runtime 完整版本、GC 模式、操作系统和 CPU；
- 线程数、是否绑核、单线程与过度订阅两个边界；
- 元素是小值类型还是引用，是单个操作还是批量操作；
- 生产者/消费者比例、预填充量与每次操作间的业务工作量；
- 吞吐、中位数与高分位延迟、分配量和 GC 计数，而不是只报一个毫秒数。
不要把Parallel.For的启动、线程池爬坡和容器操作混在一个未预热的单次计时中。也不要在一组基准中让无锁栈与锁栈执行不同的业务语义。在 Unity 中，另外导出对应后端的 Development 和非 Development 构建，在真机记录 Profiler/GC 数据；编辑器测量只能作为迭代线索。
13. 选型决策表
| 需求 | 更合适的起点 | 原因 |
|---|---|---|
| 单线程严格 LIFO | Stack<T> | 数组存储，语义简单，不支付并发协议成本 |
| 多线程共享且需要 LIFO | ConcurrentStack<T> | 单头 CAS，公开操作可并发调用 |
| 多线程 FIFO | ConcurrentQueue<T> | 顺序契约不同，避免旧项长期被压住 |
| 异步、有界、需背压/完成 | Channel<T> | 它表达的是通信协议，不只是存储容器 |
| 阻塞消费与取消 | BlockingCollection<T> | 在IProducerConsumerCollection<T>上增加阻塞/容量/完成协议 |
| 工作者偏好本地复用 | ConcurrentBag<T>或专用池 | 设计目标不是一条全局严格 LIFO 链 |
| 多步状态转换要共同原子 | 锁加专用状态对象 | 多个线程安全方法不能自动合成事务 |
选型时先问顺序与流控语义，再问竞争和分配成本。如果根本不需要全局 LIFO，即使ConcurrentStack<T>的某个微基准更快，它也不是正确的抽象。
14. 源码阅读与评审清单
阅读新版本源码时，建议固定标签后按以下路线复核：
- 确认
_head与Node的实际字段和可变性； - 标出
Push、TryPop、批量操作与Clear的线性化点； - 检查快路径与慢路径何时分流，退避是否变化；
- 跟踪
Count、ToArray和枚举从哪个头快照开始； - 对照官方 API 文档检查异常、顺序和线程安全契约；
- 用目标框架和部署平台实测，不从一个标签外推所有运行时。
在项目代码评审中，则检查：
- LIFO 是真实业务语义，而不是只因为名字里有
Concurrent； - 消费速率不足时有容量、丢弃、背压或告警策略；
- 业务没有依赖
IsEmpty/Count与后续操作之间的假原子性； - 元素所有权和元素内部同步另有明确规则；
- 没有长期保存枚举器快照而意外留存大对象图；
- Unity 主线程限制、退出流程和真机后端已经验证；
- 所有性能结论都附带可复现环境，而不是无条件的“CAS 比锁快”。
15. 总结
ConcurrentStack<T>的简洁来自一组相互支撑的设计：单一头引用是共享发布点，新节点在线程内构造，发布后的后继链保持不变，CAS 既决定唯一胜者又建立必要的可见性。由此，入栈、出栈和批量变化都能找到清晰的线性化点，枚举也可以沿已捕获的不变链安全进行。
但它不是“并发就选它”的通用容器。单一热点会竞争，每元素节点会分配，LIFO 可使旧任务饥饿，且容器不提供背压、完成或元素内部同步。真正的掌握标志不是能默写 CAS 循环，而是能证明它为何正确、说清它不承诺什么，并在目标运行时与真实负载下做出选择。
