# 无锁栈：Treiber 栈、ABA、指数退避与消除退避

DevFeed: [无锁栈：Treiber 栈、ABA、指数退避与消除退避](<https://devfeed.tech/articles/treiber-aba-60378.md>)

Original publisher: [Read original article](<https://quant67.com/post/algorithms/73-lockfree-stack/lockfree-stack.html>)

Author: Liao Tonglang

Published: 2025-07-15T00:00:00Z

Content type: article

Language: zh

Sources: [土法炼钢 - 系统与基础设施](<https://devfeed.tech/sources/source-4.md>)

Topics: [Concurrency](<https://devfeed.tech/topics/concurrency.md>), [synchronization](<https://devfeed.tech/topics/synchronization.md>), [systems](<https://devfeed.tech/topics/systems.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [Parallelism](<https://devfeed.tech/topics/parallelism.md>), [Cache](<https://devfeed.tech/topics/cache.md>), [Linux](<https://devfeed.tech/topics/linux.md>), [Windows](<https://devfeed.tech/topics/windows.md>), [Boost C++ Libraries](<https://devfeed.tech/topics/boost.md>), [x86](<https://devfeed.tech/topics/x86.md>), [x86-64](<https://devfeed.tech/topics/x86-64.md>)

Tags: [aba](<https://devfeed.tech/tags/aba.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [boost](<https://devfeed.tech/tags/boost.md>), [boost-lockfree](<https://devfeed.tech/tags/boost-lockfree.md>), [cache](<https://devfeed.tech/tags/cache.md>), [cas](<https://devfeed.tech/tags/cas.md>), [cmpxchg16b](<https://devfeed.tech/tags/cmpxchg16b.md>), [elimination-backoff](<https://devfeed.tech/tags/elimination-backoff.md>), [exponential-backoff](<https://devfeed.tech/tags/exponential-backoff.md>), [linux](<https://devfeed.tech/tags/linux.md>), [llist](<https://devfeed.tech/tags/llist.md>), [lock-free](<https://devfeed.tech/tags/lock-free.md>), [parallelism](<https://devfeed.tech/tags/parallelism.md>), [synchronization](<https://devfeed.tech/tags/synchronization.md>), [treiber-stack](<https://devfeed.tech/tags/treiber-stack.md>), [windows](<https://devfeed.tech/tags/windows.md>), [x86](<https://devfeed.tech/tags/x86.md>), [x86-64](<https://devfeed.tech/tags/x86-64.md>)

## AI overview

This article explains Treiber lock-free stacks and distinguishes ABA, memory reclamation, and contention. It compares Linux llist, Windows SList, and Boost.Lockfree, covering linearization, progress guarantees, memory ordering, deterministic ABA testing, sanitizer checks, and performance experiments using exponential backoff and elimination arrays.

## Source excerpt

Treiber 栈只靠一次 CAS，却要分别处理 ABA、内存回收和争用三件事。本文用确定性复现、守恒测试和 sanitizer 区分前两者，在 4 个逻辑 CPU 上实测指数退避与消除数组，并对照 Linux llist、Windows SList、Boost.Lockfree 的取舍。