同步与数据竞争自由

同步机制协调并发线程，以安全地访问共享数据，而数据竞争自由是使并发程序可预测的特性。

Definition

同步是对并发活动的协调，以在共享资源上强制执行排序或互斥，而数据竞争自由是指在没有干预同步的情况下，没有两个线程并发访问同一内存位置且至少有一个线程进行写入的特性。

Scope

本主题涵盖了使共享状态的并发访问正确的机制和属性：互斥、锁、信号量和管程、条件变量、无锁和无等待算法、事务内存、先行发生关系以及数据竞争的检测。它解决了死锁、原子性以及保持程序数据竞争自由所需的规范。

Core questions

• 如何实现互斥及其危害（死锁、饥饿）？
• 基于锁的同步与无锁同步有何区别？
• 先行发生关系如何定义数据竞争？
• 如何自动检测数据竞争？

Key theories

互斥

Dijkstra 对并发控制问题的解决方案确立了互斥作为基础同步要求，保证了临界区不会同时执行。

事务内存

Herlihy 和 Moss 提出了事务内存，其中内存操作组以原子方式执行，为构建并发数据结构提供了细粒度锁定的可组合替代方案。

先行发生和动态竞争检测

基于 Lamport 的先行发生关系，Eraser 检测器展示了如何通过检查锁定规范来动态查找数据竞争，这体现了自动化竞争检测。

Clinical relevance

正确的同步对于可靠的并发和并行软件至关重要；数据竞争在实践中会导致一些最难以捉摸的错误。竞争检测器、事务内存和规范的同步模式是构建可靠多线程系统的核心工具。

History

Dijkstra 于 1965 年提出的互斥解决方案及其随后的信号量奠定了同步的基础，随后是 Hoare 和 Brinch Hansen 的管程。Lamport 于 1978 年提出的先行发生关系是现代竞争定义的基础；Herlihy 和 Moss 于 1993 年引入了事务内存，而 Eraser (1997) 等动态竞争检测器以及后来的先行发生工具成为调试并发的标准。

Debates

锁与无锁和事务方法

设计人员争论传统的基于锁的同步，它简单但容易死锁且组合性差，与无锁算法和事务内存相比，后者以复杂性或开销为代价提高了组合性和进度保证。

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

什么是数据竞争？

当两个线程并发访问同一内存位置，其中至少一个访问是写入，并且这些访问没有通过同步进行排序时，就会发生数据竞争，这在大多数内存模型中会导致未定义或不可预测的行为。

基于锁的同步和无锁同步有什么区别？

基于锁的同步使用互斥，因此一次只有一个线程进入临界区，而无锁同步使用原子操作来保证某些线程总能在不持有锁的情况下取得进展，从而避免死锁。