A data race occurs when two threads access the same memory location concurrently, at least one access is a write, and the accesses are not ordered by synchronization, leading to undefined or unpredictable behavior in most memory models.

What is the difference between lock-based and lock-free synchronization?

Lock-based synchronization uses mutual exclusion so only one thread enters a critical section at a time, while lock-free synchronization uses atomic operations to guarantee that some thread always makes progress without holding locks, avoiding deadlock.

Synchronization and Data-Race Freedom

Synchronization mechanisms coordinate concurrent threads so that shared data is accessed safely, and data-race freedom is the property that makes concurrent programs predictable.

Definition

Synchronization is the coordination of concurrent activities to enforce ordering or mutual exclusion on shared resources, and data-race freedom is the property that no two threads access the same memory location concurrently with at least one writing without intervening synchronization.

Scope

This topic covers the mechanisms and properties that make concurrent access to shared state correct: mutual exclusion, locks, semaphores and monitors, condition variables, lock-free and wait-free algorithms, transactional memory, the happens-before relation, and the detection of data races. It addresses deadlock, atomicity, and the discipline needed to keep programs data-race free.

Core questions

How is mutual exclusion achieved and what are its hazards (deadlock, starvation)?
What distinguishes lock-based from lock-free synchronization?
How does the happens-before relation define data races?
How can data races be detected automatically?

Key theories

Mutual exclusion: Dijkstra's solution to the concurrent-control problem established mutual exclusion as the foundational synchronization requirement, guaranteeing that critical sections are not executed simultaneously.
Transactional memory: Herlihy and Moss proposed transactional memory, in which groups of memory operations execute atomically, offering a composable alternative to fine-grained locking for building concurrent data structures.
Happens-before and dynamic race detection: Building on Lamport's happens-before relation, the Eraser detector showed how to find data races dynamically by checking a locking discipline, exemplifying automated race detection.

Clinical relevance

Correct synchronization is essential to reliable concurrent and parallel software; data races cause some of the most elusive bugs in practice. Race detectors, transactional memory, and disciplined synchronization patterns are central tools for building dependable multithreaded systems.

History

Dijkstra's 1965 mutual-exclusion solution and his subsequent semaphores founded synchronization, followed by Hoare and Brinch Hansen's monitors. Lamport's 1978 happens-before relation underlies modern race definitions; Herlihy and Moss introduced transactional memory in 1993, and dynamic race detectors such as Eraser (1997) and later happens-before tools became standard for debugging concurrency.

Debates

Locks versus lock-free and transactional approaches: Designers debate traditional lock-based synchronization, which is simple but prone to deadlock and poor composition, against lock-free algorithms and transactional memory, which improve composability and progress guarantees at the cost of complexity or overhead.

Key figures

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

Seminal works

dijkstra1965
herlihy1993
savage1997
lamport1978

Frequently asked questions

What is a data race?: A data race occurs when two threads access the same memory location concurrently, at least one access is a write, and the accesses are not ordered by synchronization, leading to undefined or unpredictable behavior in most memory models.
What is the difference between lock-based and lock-free synchronization?: Lock-based synchronization uses mutual exclusion so only one thread enters a critical section at a time, while lock-free synchronization uses atomic operations to guarantee that some thread always makes progress without holding locks, avoiding deadlock.