编程与软件工程preshing.com
无锁编程入门（2012）
An Introduction to Lock-Free Programming (2012)
2012 — 2020，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是一篇介绍无锁编程（lock-free programming）的经典入门文章。它澄清了“无锁”里的 lock 并不直接指互斥锁，而是指避免整个应用因死锁、活锁或极端线程调度而无法推进，并讨论原子操作、内存模型等基础概念。
为什么经久不衰：它用清晰的概念区分和常见误区，帮助读者建立对无锁并发的正确直觉，今天在多核与低延迟系统里仍然值得读。
HN 评论精选
实践中无锁队列未必划算，降低耦合和批处理更有效，且可移植性与内存模型常被低估。
我通过消除系统中的无锁队列来让系统更高效可靠。更准确地说，我喜欢用单写者环形缓冲区；严格说它也算一种无锁队列，但环里出错的地方很少。主要是降低耦合，让偶尔用 mutex 也不明显拖累；显式 mutex 比无锁技术更不容易出现难以捉摸的 heisenbug。我拆掉的是那些把“无锁”耦合当成免费的队列：它不免费，每次交互至少 50 个周期，如今 50 周期能完成很多工作。每次“无锁”操作引发的总线级交互更像 mutex 而不是不像，所以并不能带来你期望的收益。降低耦合可以增加批处理：每次交互处理 10 或 50 个事件而不是一个。你找到的大多数“无锁”实现无法移植出 x86；x86 内存模型比 ARM 宽松得多。你以为自己很小心，但系统比你更擅长发现错误。
ncmncm查看英文原文
I make systems performant and reliable by eliminating their lock-free queues. To be more precise... I like to use single-writer ring buffers. (Technically you could say they are a sort of lock-free queue. But there is little to go wrong in a ring buffer.) Mainly, I reduce coupling enough that taking the occasional mutex is not a noticeable drain. Explicit mutex locking is less prone to obscure heisenbugs than lock-free techniques. What I rip out are queues treated as if "lock-free" coupling were free. It's not free; it is at least 50 cycles, each interaction. Nowadays you can get a hell of a lot of work done in 50 cycles. Each "lock-free" operation engages bus-level interactions more like a mutex than not, so it doesn't buy what you hope. To reduce coupling, you increase batching. Instead of one event per interaction, do ten, or fifty. Most "lock-free" implementations you find are not portable off of x86 systems, which have a much more forgiving memory model than, say, ARM. You think you were careful, but the system is better at finding your mistakes than you are.
无锁代码极易隐藏罕见错误，入门应先警告，并了解 lock-free、wait-free、obstruction-free 等不同层级。
好文章，但任何无锁编程入门都应包含“别在家里做重要项目”的警告。没有经验几乎一定会犯错，而这些错误可能只在极罕见情况下以崩溃出现。我 2004 年根据 Maged Michael 的论文写了第一段无锁代码，用 PowerPC 汇编写无锁 FIFO，确信安全健壮。邮件给 Maged 后他指出，如果线程在某个特定指令被挂起，且某块特定内存在它再次运行前被取消映射，程序可能崩溃。我很惊讶：我认真想过算法却完全漏掉这种可能。文章还提到，文献中其实定义了几个层级：lock-freedom、wait-freedom、obstruction-freedom；PowerPC/ARM 的 LL/SC 也有其优点。
haberman查看英文原文
Nice article, though I think that any intro-level material on lock-free programming should always include a "don't try this at home for anything important" warning. Until you have some experience with this stuff you will almost certainly make mistakes, but these mistakes might only manifest themselves as crashes in extremely rare circumstances. I wrote my first lock-free code in 2004 based on reading some papers by Maged Michael from IBM. I wrote a lock-free FIFO in PowerPC assembly, and was convinced it was safe and robust. When I emailed Maged about it, he pointed out that if a thread was suspended on one specific instruction and some specific memory was unmapped before it could run again, the program could crash. I was amazed; I had thought hard about this algorithm, but had completely missed that possibility. Some other specific notes about the article: > Basically, if some part of your program satisfies the following conditions, then that part can rightfully be considered lock-free. The are actually several levels of lock-freedom defined in the literature: lock-freedom, wait-freedom, and obstruction-freedom. For more info see: http://en.wikipedia.org/wiki/Non-blocking_algorithm > Processors such as PowerPC and ARM expose load-link/store-conditional instructions, which effectively allow you to implement your own RMW primitive at a low level, though this is not often done. One benefit of load-linked/store-conditional (often abbreviated LL/SC) is that it avoids the ABA problem (http://en.wikipedia.org/wiki/ABA_problem). In practice this doesn't matter that much since x86 doesn't support LL/SC, but I just think it's an interesting factoid to know. > For instance, PowerPC and ARM processors can change the order of memory stores relative to the instructions themselves, but the x86/64 family of processors from Intel and AMD cannot. (I've edited my reply here since my original assertion was incorrect). It's true that x86/64 won't reorder stores (see http://en.wikipedia.org/wiki/Memory_ordering for details) but it will reorder loads, so memory barriers are still required in some situations. However I believe that the atomic instructions ("lock cmpxchg", and "lock xadd") imply full barriers on x86.
用分布式系统思维理解无锁并发。
大约 10 年前让我豁然开朗的想法是：分布式系统表达并发进程，但不能合理使用锁；把你的线程/进程等建模为分布式系统中的节点，用分布式系统技术确保事情收敛。
tptacek查看英文原文
The idea that made this click for me 10 years or so ago was that distributed systems express concurrent processes but can't reasonably use locks; model your threads/processes/whatever as if they were nodes in a distributed system, and use distributed system techniques to ensure things converge.
线程持锁死亡和分布式故障恢复是无锁算法通常不处理的更深层问题。
> 共享互斥锁被轻易排除，因为一旦一个线程获得互斥锁，你最坏的敌人可能再也不调度那个线程。另一种可能是线程持锁（或独占资源）时死亡。在共享内存系统中看似牵强，在分布式系统中则不然。恢复资源不容易，尤其恢复线程也可能死亡，或者被认定死亡的线程突然复活。在我看来，让并行系统对这种故障健壮，远超业界认为可接受的无锁算法范畴。我在 Robusta 项目里思考过该场景；我怀疑它没有实际用途，但至少对通用计算模型有效。
omazurov查看英文原文
> Shared mutexes are ruled out trivially, because as soon as one thread obtains the mutex, your worst enemy could simply never schedule that thread again. Another possibility is that the thread dies while holding a mutex (or exclusively possessing a resource). It may seem like a stretch for shared memory systems, but not so much for distributed systems. Recovering the resource is not an easy task, especially considering the fact that recovering threads may also die or that the thread assumed dead all of a sudden returns to life. In my opinion, making a parallel system robust to that kind of malfunction goes far beyond what the industry considers acceptable as lock-free algorithms. I gave some thought to that scenario in my project Robusta [1]. I doubt it could be useful for any practical purpose but at least it works for a universal computational model. [1] https://github.com/OlegMazurov/Robusta
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选