ConcurrentStackT无锁链式栈的 CAS 协议专栏C# 与常用数据结构源码剖析本文基线.NET 8.0.0发布标签中System.Collections.Concurrent.ConcurrentStackT的公开契约与私有实现阅读原则公开 API 是跨版本契约字段、节点类型和退避策略只是该标签下的源码事实不应当成未来版本的 ABI。ConcurrentStackT常被概括成“单链表加一次 CAS”。这句话抓住了主干却容易遮住真正值得学习的部分为什么节点可以只发布一次哪个指令是线性化点无锁是不是等于每个线程都会很快枚举和Count看到的又是什么时刻本文从不变式、内存顺序和进度保证出发再回到游戏开发中的任务回收、对象复用和 Unity 平台选型。1. 先定义契约它是并发 LIFO不是调度器栈的抽象规则是后进先出单线程依次推入A、B、C随后弹出应得到C、B、A。并发情况下不同线程的调用可以时间重叠因而不能用墙上时钟强行排出唯一顺序。正确的要求是可线性化每个已完成操作都可以视为在调用与返回之间的某一瞬间生效所有瞬间组成一个合法的顺序栈历史。ConcurrentStackT适合表达“取最近放入的一项”但不自带以下语义没有公平性先等待的线程不一定先获得元素没有容量上限和生产者背压没有异步等待数据、完成通知或取消协议没有“取出后只处理一次”的业务事务保证不会因为容器是线程安全的就使元素内部的可变状态也自动线程安全。如果需要有界异步管道ChannelT通常更贴近问题如果需要阻塞式生产者/消费者协议可考察BlockingCollectionT。不应把“无锁”当成绕过业务协议设计的理由。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 (StackT)尾延迟一定更小一组业务操作可以自动组成原子事务。头指针是所有写操作的单一热点。核数增加后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, 1var stack new ConcurrentStackint(); 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 不变后继链使枚举快照成立枚举器可以捕获某一头节点然后沿不再修改的后继链向下遍历。之后的新入栈位于快照头之前不会进入这次遍历之后的出栈只改变全局头引用不会破坏已捕获链。因此枚举不会像StackT那样因并发修改而依赖版本号立即抛出异常。但“快照”不等于元素对象的深拷贝。如果T是可变引用类型枚举者和其他线程仍持有同一对象它的字段可能在遍历中被改变。如果需要内容级快照应使用不可变元素或在业务层复制数据。枚举器、ToArray或长时间持有的局部头引用还会延长已出栈节点和其值的生命期。这不是泄漏而是快照正确性的代价如果元素持有大块资源应避免把枚举器跨帧或跨任务长期保存。9.Clear和引用生命周期Clear可通过原子地把全局头设为null切断容器入口。它不遍历每个节点执行手工释放当没有并发操作、枚举器或其他局部引用再持有旧链时GC 才可以回收相关节点与元素。并发Clear不是“世界停顿式清空”。一个Push可能在Clear前读取旧头但它必须经过 CAS 竞争各操作仍可按它们的线性化点排出合法历史。如果业务需要“清空后禁止所有旧生产者再写入”就需要额外的停止协议、代际标识或替换整个容器引用单独调用Clear不足以表达该业务边界。不建议通过反射抓取私有Node来做对象池这同时破坏实现封装、节点不变性和前面的 ABA 推理。若分配成本确实不可接受应先确认需求是否可以用数组批处理、线程本地缓冲、有界ChannelT或经过专门验证的池化数据结构表达。10. 复合操作与错误用法10.1 线程安全的方法不会自动组成原子序列假设需求是“只在栈顶是某任务时才替换它”。TryPeek后接TryPop存在间隙另一线程可以在其间修改栈。ConcurrentStackT没有公开的条件式 CAS API不能从外部访问其私有头指针补上原子性。此时应重设业务状态机或用一把锁保护整个复合不变式。10.2 LIFO 可能造成饥饿若生产速度长期高于消费速度旧任务会被新任务不断压在下面。对象复用中“最近归还对象有更好缓存热度”可能是优点但对必须有界时间内处理的任务却是错误语义。后者应考虑 FIFO 队列、优先队列或带公平性约束的调度器。10.3 不可用Count当作容量控制if (stack.Count limit) stack.Push(item);多个生产者可同时通过检查最终超出limit。即使额外维护原子计数也要严密处理预留、发布失败和异常回滚。需要容量上限时优先使用契约本身支持有界容量的协调原语。10.4 容器原子性不保护元素把ListT、UnityGameObject或其他可变对象放入并发栈只保证引用的入栈和出栈不破坏容器。对象在线程间的所有权转移、何时允许修改以及何时归还资源仍需要明确协议。11. Unity 中的边界托管并发不等于可以跨线程操作引擎Unity 项目的 API 可用性取决于编辑器版本、API Compatibility Level 和目标平台提供的参考程序集。即使都能编译ConcurrentStackTUnity Mono 后端、IL2CPP AOT 和上游 CoreCLR 也不是同一个执行引擎代码生成、GC、原子指令降低和调度环境都可不同。不应把 CoreCLR 某台机器上的基准数字直接复制为所有 Unity 平台结论。更重要的是大多数UnityEngine.Object及场景 API 要求在主线程访问。后台线程可以把纯托管、所有权清晰的结果放入容器主线程再取出并应用但一个无界 LIFO 通常不是跨线程消息流的最佳默认值。消息是否可丢弃、是否要保序、每帧最多消费多少、停机时如何排空都应先定义。一个可辩护的场景是多线程归还完全托管的临时工作项下一个申请者优先复用最近归还的项。即便如此也要比较局部缓存加全局溢出栈、ConcurrentBagT或专用池。若元素的创建/销毁必须回到主线程还要把这一约束编入池的生命周期。IL2CPP 下必须在真实目标设备验证特别是主机、移动端和 Web 类平台的线程限制不同。“编辑器中正常”只能证明编辑器当前后端与硬件的行为不能代替玩家设备测试。12. 如何做可复现的正确性和性能实验12.1 先测不丢、不重再谈吞吐让P个生产者分别推入不重复的编号区间C个消费者循环弹出停止生产后排空栈。最后检查弹出总数等于推入总数所有编号的出现次数恰好为 1消费者报告的成功数之和与最终集合一致在无并发的小规模用例中严格验证 LIFO 顺序和批量区间顺序。并发压力测试不能单凭一次通过证明无竞态。应使用多个随机种子、不同生产/消费者比例、空栈竞争和长链排空场景并为每轮设置超时。对自研结构还可记录小历史并用线性化检查器搜索是否存在合法顺序化。12.2 基准必须隔离调度器噪声与测试器开销可对比ConcurrentStackT、一把锁保护的StackT以及语义允许时的线程本地栈加批量合并。每一组都要报告.NET SDK/runtime 完整版本、GC 模式、操作系统和 CPU线程数、是否绑核、单线程与过度订阅两个边界元素是小值类型还是引用是单个操作还是批量操作生产者/消费者比例、预填充量与每次操作间的业务工作量吞吐、中位数与高分位延迟、分配量和 GC 计数而不是只报一个毫秒数。不要把Parallel.For的启动、线程池爬坡和容器操作混在一个未预热的单次计时中。也不要在一组基准中让无锁栈与锁栈执行不同的业务语义。在 Unity 中另外导出对应后端的 Development 和非 Development 构建在真机记录 Profiler/GC 数据编辑器测量只能作为迭代线索。13. 选型决策表需求更合适的起点原因单线程严格 LIFOStackT数组存储语义简单不支付并发协议成本多线程共享且需要 LIFOConcurrentStackT单头 CAS公开操作可并发调用多线程 FIFOConcurrentQueueT顺序契约不同避免旧项长期被压住异步、有界、需背压/完成ChannelT它表达的是通信协议不只是存储容器阻塞消费与取消BlockingCollectionT在IProducerConsumerCollectionT上增加阻塞/容量/完成协议工作者偏好本地复用ConcurrentBagT或专用池设计目标不是一条全局严格 LIFO 链多步状态转换要共同原子锁加专用状态对象多个线程安全方法不能自动合成事务选型时先问顺序与流控语义再问竞争和分配成本。如果根本不需要全局 LIFO即使ConcurrentStackT的某个微基准更快它也不是正确的抽象。14. 源码阅读与评审清单阅读新版本源码时建议固定标签后按以下路线复核确认_head与Node的实际字段和可变性标出Push、TryPop、批量操作与Clear的线性化点检查快路径与慢路径何时分流退避是否变化跟踪Count、ToArray和枚举从哪个头快照开始对照官方 API 文档检查异常、顺序和线程安全契约用目标框架和部署平台实测不从一个标签外推所有运行时。在项目代码评审中则检查LIFO 是真实业务语义而不是只因为名字里有Concurrent消费速率不足时有容量、丢弃、背压或告警策略业务没有依赖IsEmpty/Count与后续操作之间的假原子性元素所有权和元素内部同步另有明确规则没有长期保存枚举器快照而意外留存大对象图Unity 主线程限制、退出流程和真机后端已经验证所有性能结论都附带可复现环境而不是无条件的“CAS 比锁快”。15. 总结ConcurrentStackT的简洁来自一组相互支撑的设计单一头引用是共享发布点新节点在线程内构造发布后的后继链保持不变CAS 既决定唯一胜者又建立必要的可见性。由此入栈、出栈和批量变化都能找到清晰的线性化点枚举也可以沿已捕获的不变链安全进行。但它不是“并发就选它”的通用容器。单一热点会竞争每元素节点会分配LIFO 可使旧任务饥饿且容器不提供背压、完成或元素内部同步。真正的掌握标志不是能默写 CAS 循环而是能证明它为何正确、说清它不承诺什么并在目标运行时与真实负载下做出选择。