It's called a race because threads are literally racing to access the shared state first. The winner is determined by the OS scheduler—which thread gets the next time slice, when the timer interrupt fires, and the state of the CPU's store buffer. On a single-core CPU, the hardware determines the interleaving; on multi-core, cache coherency traffic adds another dimension of non-determinism. The key insight is that the "winner" is not guaranteed to be the same each run, which is why race conditions are so hard to reproduce.

A data race is a specific technical term: two or more threads accessing the same memory location concurrently, where at least one access is a write, and there is no synchronization establishing a happens-before relationship. Every data race is a race condition, but not all race conditions are data races—some race conditions involve logical inconsistencies that don't involve simultaneous memory access (e.g., timing-dependent business logic). Data races are detectable by tools like ThreadSanitizer; race conditions often require formal verification or extensive testing.

A critical section is a region of code that accesses shared state and must be executed by only one thread at a time. Mutual exclusion ensures that if Thread A is inside the critical section, Thread B must wait at the boundary until A exits. This matters because the read-modify-write sequence that looks atomic in source code is actually three separate operations at the hardware level. Without mutual exclusion, concurrent execution can interleave these operations to produce an incorrect result (like the lost update problem). The critical section is where your correctness guarantees are most fragile.

A memory barrier (or fence) is a hardware instruction that prevents the CPU from reordering memory operations across the barrier. A lock does imply a memory barrier—when you acquire a lock, the CPU ensures all prior loads and stores complete before the critical section begins, and when you release a lock, all stores in the critical section are visible to other threads before the unlock is observed. So locks do provide memory ordering guarantees. However, the reason locks aren't always "sufficient" is that compiler optimizations can reorder code in surprising ways, and on weakly ordered architectures (like ARM or POWER), stores can be buffered and delayed in ways that cause visibility problems even with locks if the lock implementation itself doesn't use proper barriers. Always use the synchronization primitives designed for your language's memory model.

Priority inversion occurs when a low-priority thread holds a lock needed by a high-priority thread, effectively blocking the high-priority thread. Meanwhile, medium-priority threads consume CPU time, preventing the low-priority holder from running and releasing the lock. The result: the high-priority task is indirectly blocked by a low-priority one, which violates the scheduling guarantees you paid for. This was famously involved in the Mars Pathfinder incident where the spacecraft repeatedly reset. The solution is priority inheritance: when a high-priority task waits on a lock held by a low-priority task, the low-priority task temporarily inherits the high priority, allowing it to run and release the lock. Linux implements this as the PI (priority inheritance) futex mechanism.

Mutex implementations leverage hardware atomic instructions. The simplest is a spinlock using a test-and-set (TAS) atomic operation: a single instruction that writes to a memory location and returns its old value. On a uniprocessor, the lock protects critical sections by disabling interrupts during lock acquisition, preventing preemption mid-critical-section. On multiprocessors, TAS creates cache-line contention as all CPUs spin on the same cache line.

More sophisticated mutexes use compare-and-swap (CAS): atomically check if a location equals an expected value and swap it if so. The lock acquisition loop retries with CAS until successful. To avoid the thundering-herd problem on contention, many mutexes use exponential backoff on retry or MCS locks where each waiting thread spins on a unique per-thread node. Futex (fast userspace mutex) in Linux uses a spin-wait in userspace before falling back to kernel-assisted sleeping, combining low overhead for the common uncontended case with efficient handling of high contention.

Deadlock requires all four Coffman conditions simultaneously: Mutual exclusion (at least one resource must be held in a non-shareable mode), Hold and wait (a process holding at least one resource is waiting to acquire additional resources held by other processes), No preemption (resources cannot be forcibly taken from a holding process; they must be explicitly released), and Circular wait (there exists a circular chain of processes where each process holds a resource the next process is waiting for).

Breaking any one condition prevents deadlock. Remove mutual exclusion by using lock-free algorithms. Prevent hold-and-wait by acquiring all resources at once atomically (not always possible). Make resources preemptable by implementing resource reclamation. Prevent circular wait by enforcing a global lock acquisition order across all threads. Most practical deadlock prevention focuses on consistent lock ordering and avoiding hold-and-wait by minimizing critical section duration.

A mutex (mutual exclusion) is a lock with ownership semantics: only the thread that acquires a mutex can release it. Mutexes enforce strict exclusion and typically support priority inheritance to prevent priority inversion. They are designed to protect critical sections and ensure only one thread executes a code region at a time.

A semaphore is a generalized counter that can be acquired and released by any thread. A binary semaphore (count = 1) acts like a mutex but without ownership semantics, allowing any thread to signal even if that thread did not wait. Semaphores are used for signaling between threads (producer-consumer patterns) and resource pooling where N identical resources need controlled access. The absence of ownership means you cannot implement recursive mutex behavior with a semaphore, and priority inheritance is not provided by standard semaphores.

Compare-and-swap (CAS) atomically compares a memory location to an expected value and, if they match, swaps it with a new value, returning whether the swap happened. A CAS loop implements an atomic update: load the current value, compute the new value, attempt CAS with the loaded value as expected. If another thread modified the location in the meantime, the CAS fails and the loop retries.

Lock-free algorithms use CAS to update shared data without locks: a thread can modify shared data as long as no other thread interfered since the thread read it. ABA problem (a thread reads A, another thread changes A to B and back to A, and the first thread's CAS incorrectly succeeds) is a known weakness of CAS. Solutions include double-width CAS (DCAS) or hazard pointers to track whether a value has been modified since being read.

A memory ordering model defines the order in which memory operations become visible to other CPU cores. On x86/64, the hardware provides strong ordering: stores are not reordered with earlier loads, and the memory order is program order. On ARM/PowerPC, the hardware is weakly ordered: loads can be reordered with earlier stores and both can be reordered with respect to other operations, making correct lock-free code significantly harder to write.

C++11 introduced memory ordering annotations (std::memory_order_relaxed, acquire, release, acq_rel, seq_cst) that specify constraints the compiler must enforce when reordering code. seq_cst (sequential consistency) provides the strongest guarantee and simplest mental model at a performance cost. acquire/release is sufficient for most synchronization patterns and is cheaper on weakly ordered hardware.

The Dining Philosophers problem: five philosophers sit at a circular table, each with a fork on their left and right. A philosopher alternates between thinking and eating, but needs both forks to eat. This creates a deadlock if each philosopher picks up their left fork simultaneously and waits indefinitely for the right fork. No philosopher can eat because each waits for a fork held by another who is also waiting.

The problem teaches several lessons: deadlock requires all four Coffman conditions (circular wait is visible here), resource acquisition ordering matters (philosopher picking up lower-numbered fork first prevents circular wait), and timeouts on lock acquisition break the deadlock condition. Solutions include a resource hierarchy (always pick up lower-numbered fork first), a waiter that allows at most four philosophers to sit simultaneously, and asymmetric acquisition where odd philosophers pick up left first while even philosophers pick up right first.

Deadlock: Threads are blocked waiting for each other. Each holds a resource the other needs. Progress halts. The system is stuck. Classic example: Thread A holds Lock 1 and waits for Lock 2; Thread B holds Lock 2 and waits for Lock 1.

Livelock: Threads are actively running (not blocked) but make no progress because they keep reacting to each other. Like two people stepping aside to let each other pass, and both stepping the same direction repeatedly. The threads are not starved of CPU time, but the intended work never completes. Livelock is often detected by CPU usage remaining high while throughput drops to zero.

Starvation: A thread is perpetually denied access to a resource it needs because other threads repeatedly acquire it first. The thread wants to proceed but never gets the opportunity. Example: a low-priority thread never gets CPU time because higher-priority threads keep preempting it. Starvation differs from deadlock in that some threads make progress while others do not.

A condition variable (pthread_cond_wait) allows a thread to atomically release a mutex and suspend execution until another thread signals the condition. The thread is put to sleep inside the critical section, allowing other threads to enter. When signaled, the waiting thread wakes up, reacquires the mutex, and re-evaluates the condition. This pattern implements "wait until X is true" correctly.

A semaphore, by contrast, is a counter-based signaling mechanism without a condition to test. You increment the semaphore to signal; you decrement to wait. Unlike a condition variable, semaphores have no concept of spurious wakeup (signaling a semaphore when no thread is waiting consumes the signal). A semaphore of count 1 can simulate a mutex but without ownership semantics. Condition variables require a mutex because they protect shared state that is tested upon waking.

Lock contention occurs when multiple threads compete for the same lock simultaneously. When Thread A holds a lock, Thread B must wait. On a uniprocessor, this overhead is minimal because the waiting thread is descheduled. On a multiprocessor, the waiting thread may spin (wasting CPU) or sleep (incurring context-switch overhead), and the cacheline holding the lock state ping-pongs between CPU caches, consuming memory bandwidth.

Contention becomes a scalability bottleneck: adding more CPUs increases the chance that threads contend for the same lock, causing diminishing returns or even performance regression. Mitigations include lock striping (splitting one lock into N locks for disjoint data), lock-free data structures that eliminate central coordination, per-CPU data structures where no locking is needed, and RCU (read-copy-update) which allows readers to proceed without locks while writers coordinate updates.

A read-write lock (pthread_rwlock) allows multiple readers to hold the lock simultaneously but requires exclusive access for writers. When a writer holds the lock, no readers or other writers can proceed. When readers hold the lock, new readers can join but writers must wait until all readers release. This maximizes read throughput when reads are much more frequent than writes and the critical section duration is long enough for the additional lock overhead to pay off.

Use a regular mutex when: the critical section is short (lock overhead dominates), writes are frequent (readers starve), or the protected data structure is updated atomically without a critical section. Use a read-write lock when: reads vastly outnumber writes, read sections are long enough to amortize the heavier lock overhead, and writer starvation is acceptable. Beware of writer starvation in read-heavy workloads with many concurrent readers.

The happens-before relationship (defined in the C++ and Java memory models) is a partial ordering that guarantees that if operation A happens-before operation B, then the effects of A are visible to B. Without happens-before, B may observe A's effects, A's effects may not be visible, or any interleaving in between. Synchronization operations (lock acquire/release, thread join, atomic operations with certain memory orders) establish happens-before relationships.

The Java Memory Model and C++11 atomics formalize this: if you establish a happens-before relationship between a writer and a reader, the reader is guaranteed to see the written value. Without it, data races (concurrent read and write of shared state without happens-before) produce undefined behavior. The happens-before relationship composes transitively across synchronization points, so a chain of properly synchronized operations maintains consistency.

The ABA problem occurs with CAS-based lock-free algorithms: Thread A reads a value (A), Thread B changes it from A to B and back to A, and then Thread A's CAS succeeds because it sees A again, missing that the value changed in between. This can cause data structure corruption when the intermediate state (B) represented a structural change (like a removed node) that needs to be accounted for.

Common solutions include: double-width CAS (DCAS) which atomically compares and swaps two adjacent memory words, tagged pointers (adding a version counter that increments on each change, so the CAS sees the old value with old tag and fails), hazard pointers (each thread publishes what pointers it is accessing, and nodes are not freed while any thread holds a reference), and reference counting (with the caveat that reference count manipulation itself requires synchronization).

Context switching saves and restores CPU state (registers, program counter, stack pointer) allowing multiple threads to share a single CPU. A context switch can occur at any point in a thread's execution, potentially mid-instruction, which means a thread can be interrupted between any two operations. This is why preemption can expose race conditions that do not manifest under single-threaded execution.

For concurrent correctness, you must assume context switches can happen at any instruction boundary. A thread may hold a lock, trigger a context switch, and another thread may acquire the same lock before the first thread's critical section completes. Similarly, a thread may read a value, get preempted, and another thread may modify that value before the first thread resumes. Proper synchronization primitives (locks, atomics) ensure that context switches cannot create observable race conditions.

ThreadSanitizer (TSan) is a compile-time instrumentation tool that detects data races at runtime. It works by tagging each memory access with the current thread's identity and a clock vector. On each access, TSan checks if another thread has accessed the same memory without a proper happens-before synchronization. When a data race is detected, TSan reports both threads' stack traces and the conflicting accesses.

TSan detects: races on global variables, races on heap-allocated objects, races on class members, and even races in dynamically loaded code. It does not detect deadlocks, livelocks, or logical race conditions (where concurrent access is intentional but produces incorrect results). It has overhead of 2-20x in CPU and memory, making it suitable for testing but not production. Compile with -fsanitize=thread and run your test suite to surface races before they reach production.

RCU (Read-Copy-Update) is a synchronization mechanism optimized for read-heavy workloads. It allows readers (threads that only observe shared data) to proceed without any locking or atomic operations, by guaranteeing that a writer's changes cannot be observed by readers until all pre-existing readers have completed. Writers make a private copy, modify it, atomically replace the pointer, and then (after a grace period) reclaim the old version.

The grace period is key: Linux kernel RCU blocks reclamation of old data until all CPUs have been observed to context-switch at least once, ensuring no in-flight reader is still referencing the old data. RCU's read-side overhead is near-zero, making it ideal for data structures with 99%+ read operations. It is used heavily in the Linux kernel (rculist, rcu_head) and in userspace libraries like liburcu. The tradeoff is that writers have higher overhead and memory usage due to the copy and deferred reclamation.