垃圾回收算法全景
从引用计数到并发三色标记，从分代假说到 ZGC 的亚毫秒暂停。垃圾回收是编程语言运行时中最复杂也最精妙的子系统。
concurrent 标签归档
共 8 篇文章 · 返回首页
无锁队列：Michael-Scott 算法与 ABA 问题
当多线程争抢一把 mutex 保护的队列时，吞吐量随线程数增长反而下降——锁成了瓶颈。无锁队列用 CAS 循环取代互斥，换来真正的无阻塞并发，但也引入了 ABA 问题和内存回收的工程深渊。
无锁栈：Treiber 栈与指数退避
Treiber 栈可能是最简单的无锁数据结构——只需要一个 CAS 操作就能完成 push 和 pop。但'最简单'不意味着'没有坑'。从 ABA 问题到伪共享，从指数退避到 elimination backoff，这个看似朴素的数据结构蕴含了并发编程最核心的设计权衡。
并发跳表：ConcurrentSkipListMap 的设计
Java 的 `java.util.concurrent` 提供了 ConcurrentHashMap，却没有 ConcurrentTreeMap——取而代之的是一个基于跳表的 ConcurrentSkipListMap。为什么 Doug Lea 选择了跳表而不是红黑树？因为平衡树的旋转操作会同时修改多个节点的指针，在并发场景下几乎不可能做到无锁；而跳表天然的分层链表结构使得每次修改只涉及局部指针，为 CAS 操作提供了完美的施展空间。
RCU：Linux 内核的读侧零开销并发
Linux 内核如何在并发数据结构中实现读侧零开销？RCU 用一种违反直觉的方式回答了这个问题：让读者永远不等待，让写者承担一切代价。
MPMC Channel：Go channel 与 crossbeam-channel 的实现对比
同一个并发原语，Go 和 Rust 却走出了截然不同的道路：一个用全局互斥锁守护环形缓冲区，另一个用逐槽位 CAS 实现无锁推进。本文深入拆解 Go channel、crossbeam-channel、LMAX Disruptor 和 DPDK rte_ring 的内部结构，并给出一份完整的 C 语言有界 MPMC 队列实现。
Treap 与跳表：随机化的力量
当我们放弃对确定性平衡的执念，转而拥抱随机化，会发现一些最优雅的数据结构——Treap 用一个随机优先级就消除了旋转的痛苦，跳表用抛硬币就实现了对数级查找。这不是妥协，而是对概率论最精彩的工程应用。
Hazard Pointers：安全内存回收的优雅方案
在无锁数据结构中，你不能简单地 free() 一块内存——因为另一个线程可能正在读取它。Hazard Pointers 是解决这个问题的经典方案。