Synchronization & Concurrency in Operating Systems

Concurrency is the foundation of modern computing. Multicore processors, multithreaded servers, asynchronous I/O, and parallel data processing all depend on multiple execution contexts making progress simultaneously. Synchronization ensures that when these concurrent contexts access shared data, the system behaves correctly regardless of the arbitrary interleaving of operations. This is one of the most intellectually demanding areas of OS design — as Edsger Dijkstra noted in his 1965 paper on semaphores, the problem of coordinating concurrent processes is “inherently difficult” and error-prone.

The Race Condition Problem

A race condition occurs when the program’s correctness depends on the relative timing of operations in different threads. The classic example is a shared counter:

/* Two threads execute concurrently: counter++ */
/* Equivalent to:
   LOAD counter into register
   INCREMENT register
   STORE register to counter */

If both threads load the same initial value (say, 5), both increment to 6, and both store 6, the counter ends at 6 instead of 7. One increment is lost. The operations race — the outcome depends on the exact interleaving of load and store instructions.

Race conditions can produce corrupted data structures, incorrect accounting, security vulnerabilities (TOCTOU — Time of Check to Time of Use), and unreproducible crashes. They are notoriously difficult to debug because they depend on timing and may only manifest under specific load conditions.

Critical Sections and Mutual Exclusion

The code that accesses shared resources must be protected. This protected region is called a critical section. The solution requires satisfying three conditions, formalized by Dijkstra:

1. Mutual exclusion: At most one thread can execute in the critical section at any time.
2. Progress: If no thread is in the critical section, and a thread wants to enter, only threads that are not in their remainder sections can participate in deciding which thread enters next.
3. Bounded waiting: A bound exists on the number of times other threads are allowed to enter their critical sections after a thread has made a request to enter.

The hardware provides the foundation: atomic instructions like test-and-set, compare-and-swap (CAS), and fetch-and-add. These instructions execute indivisibly — on x86, the LOCK prefix asserts the bus lock or cache lock to prevent other CPUs from accessing the memory location concurrently.

Synchronization Primitives

Mutex (Mutual Exclusion Lock)

A mutex is the simplest synchronization primitive. A thread locks the mutex before entering the critical section and unlocks it after leaving. If a thread attempts to lock an already-locked mutex, it blocks (sleeps) until the mutex is unlocked.

POSIX threads (pthreads) provide pthread_mutex_lock() and pthread_mutex_unlock(). The implementation distinguishes between fast (non-recursive), recursive, and error-checking mutexes. A thread must not unlock a mutex it does not hold — doing so is undefined behavior. Mutexes should be held for the shortest possible duration to minimize contention.

The kernel implementation of a mutex uses a two-phase approach: first spin briefly (optimistic spinning), and if the lock is not acquired quickly, fall back to sleeping. This hybrid avoids the overhead of immediate context switching when the lock is held briefly while preventing CPU waste when the lock is contended.

Semaphore

Dijkstra’s semaphore is a non-negative integer with two atomic operations: P (proberen, “to test” in Dutch) decrements the value; V (verhogen, “to increment”) increments it. If P would make the value negative, the calling thread blocks. V always succeeds and wakes a blocked thread if any are waiting.

Binary semaphores (values 0 and 1) are functionally equivalent to mutexes, with one critical distinction: a semaphore can be signaled from any thread, while a mutex must be unlocked by the same thread that locked it. Counting semaphores (values 0 to N) manage multiple identical resources — for example, a pool of database connections.

Monitor

Monitors, formalized by C. A. R. Hoare and Per Brinch Hansen in the 1970s, bundle shared data, operations, and synchronization into a language-level construct. Only one thread can execute inside the monitor at a time. Condition variables within the monitor support waiting (wait) and signaling (signal, notify).

Java’s synchronized keyword implements monitor semantics: each object has an associated lock and condition variable. C#’s lock statement provides comparable functionality. The advantage of monitors is that the synchronization structure is declared in the code rather than embedded at each access point.

Spinlock

A spinlock is a lock that busy-waits — the thread repeatedly tests the lock in a tight loop until it becomes available. Spinlocks are appropriate only for very short critical sections (tens of instructions) where the overhead of context switching (microseconds) would exceed the spinning time (nanoseconds). The Linux kernel uses spinlocks extensively for protecting per-CPU data structures, interrupt handlers, and data accessed in atomic context (where sleeping is forbidden).

Spinlocks interact poorly with preemption. While holding a spinlock, the thread must not be preempted — otherwise, the preempting thread may spin on the same lock, wasting CPU. Linux disables kernel preemption while a spinlock is held. On x86, spinlocks use the xchg instruction with the LOCK prefix to atomically test and set the lock word.

Read-Copy-Update (RCU)

RCU is a synchronization mechanism optimized for read-mostly data. Readers access shared data without acquiring locks — they follow pointers without any memory barrier overhead beyond that required by the CPU’s cache coherence protocol. Writers create a new version of the data structure, update pointers atomically, and wait for all pre-existing readers to complete before freeing the old version.

RCU is used extensively in the Linux kernel for routing tables, file system directory caches, and security structures. Its advantage is that readers never block, spin, or contend for memory bus access. The cost is complexity for writers and grace period tracking (waiting for readers to finish). Paul McKenney, RCU’s creator and primary maintainer, documented the algorithm in “Is Parallel Programming Hard, And, If So, What Can You Do About It?”

Classical Synchronization Problems

Producer-Consumer (Bounded Buffer)

A producer thread adds items to a fixed-size buffer; a consumer thread removes items. Two counting semaphores track empty and full slots. A mutex protects the buffer structure itself. The producer waits on empty, acquires the mutex, inserts the item, releases the mutex, and signals full. The consumer does the reverse. This pattern underlies work queues, pipeline stages, and the kernel’s pipe implementation.

Readers-Writers

Multiple readers can safely read a shared data structure simultaneously. Writers need exclusive access. The priority variant matters: readers-preference can starve writers; writers-preference provides bounded waiting for writers but reduces read concurrency. The Linux kernel’s rwlock_t provides this mechanism with slight writer preference.

Dining Philosophers

Five philosophers sit at a table with five forks. Each philosopher alternately thinks and eats. Eating requires two forks. The naive solution — each philosopher picks up the left fork first — leads to deadlock. Correct solutions include limiting diners to four (so one fork remains free), requiring asymmetric fork pickup (even-numbered philosophers pick up left first, odd-numbered pick up right first), or using a mutex-protected waiter.

Locking Strategies and Best Practices

Lock ordering: Establish a global lock hierarchy and always acquire locks in the same order. This prevents circular wait, the most common deadlock cause. Document the ordering so developers understand it.

Lock granularity: Coarse-grained locking (a single lock for a large data structure) is simple but limits concurrency. Fine-grained locking (separate locks for each hash bucket or list node) increases concurrency but raises locking complexity, memory overhead, and deadlock risk. Start coarse, profile, and refine.

Lock-free programming: For simple data structures (stacks, queues, hash tables), lock-free algorithms using CAS can eliminate contention entirely. The cost is algorithmic complexity and correctness proofs. The Linux kernel’s kfifo and the liblfds library provide validated lock-free data structures.

Instrumentation: Thread sanitizers (ThreadSanitizer, Helgrind) detect data races automatically during testing. Kernel lockdep (CONFIG_PROVE_LOCKING) validates lock ordering and detects potential deadlocks dynamically.

Transactional Memory

Hardware Transactional Memory (HTM), implemented in Intel’s Transactional Synchronization Extensions (TSX) and IBM Power PC, allows groups of memory operations to execute speculatively as transactions. If a conflict is detected (another thread accesses the same location), the transaction aborts and retries. HTM simplifies concurrency for moderate contention but has practical limits on transaction size and duration. The Linux kernel briefly attempted to use TSX for lock elision but disabled it due to erratum issues in early Haswell/Broadwell processors. Language-level transactional memory (Clojure’s STM, Haskell’s TVar) provides software-only approaches that compose well.

FAQ

What is the difference between a mutex and a semaphore?

A mutex is a lock that enforces ownership — only the thread that locked it can unlock it. A semaphore is a signaling mechanism — any thread can signal (V) any semaphore, regardless of which thread performed the wait (P). Mutexes are used for mutual exclusion on shared data; semaphores are used for signaling between threads (e.g., producer notifying consumer that data is available).

How do I detect and debug race conditions?

Use thread sanitizer tools: Clang/GCC’s ThreadSanitizer (TSan, compiled with -fsanitize=thread) instruments every memory access and detects races during testing. Valgrind’s Helgrind provides similar functionality. For kernel code, enable lockdep (CONFIG_DEBUG_LOCKDEP) and KCSAN (Kernel Concurrency Sanitizer, CONFIG_KCSAN). Reproduce under heavy load with controlled thread interleaving.

What is the performance cost of locking?

Lock contention is the primary cost — threads spinning or sleeping while waiting for a lock held by another thread. An uncontended mutex lock/unlock costs approximately 25–50 ns on modern x86. A contended lock can cost microseconds or milliseconds. Cache line bouncing — where the cache line containing the lock is transferred between CPU cores — adds measurable memory bus traffic.

Can I avoid locking entirely?

For some data access patterns, yes. Read-only data needs no protection. Per-CPU data (each CPU accesses its own copy) avoids locking entirely. RCU eliminates locking for readers. Lock-free data structures using CAS avoid blocking. Atomic operations (fetch-and-add, compare-and-swap) handle simple counters and flags without locks. For the general case of shared writable data accessed by multiple cores, some form of synchronization is unavoidable.

What happens when a thread holding a lock crashes?

If a thread crashes while holding a mutex, the mutex remains locked. Other threads waiting for that mutex will block indefinitely — a deadlock. Robust mutexes (pthread_mutexattr_setrobust) address this: if the owning thread terminates, the next thread to acquire the mutex receives an EOWNERDEAD error and can mark the protected data as potentially inconsistent. Windows provides similar semantics with InitializeCriticalSectionAndSpinCount and structured exception handling.

The Deadlocks Guide provides detailed analysis of deadlock prevention, avoidance, and recovery strategies. The Interprocess Communication Guide covers shared memory and the synchronization that must accompany it. The seminal reference for synchronization theory is E. W. Dijkstra’s 1965 paper “Cooperating Sequential Processes.” For practical POSIX threading, see Butenhof’s Programming with POSIX Threads. Kernel synchronization is documented in the Linux kernel source at Documentation/locking/.