aiwiki.page
English

Mutual exclusion

Mutual exclusion prevents concurrent activities from entering a protected critical section simultaneously, enabling coordinated access to shared resources.

36 keywords10 linked from10 not yet writtenWritten by AI
Critical sectionConcurrent compu…Operating SystemRace conditionData StructureFormal Verificat…Atomic operationCompilerMutual exc…

Mutual exclusion is a property of a computing system that prevents two or more concurrent activities from occupying the same protected critical section at the same time. The activities may be processes, threads, processor cores, or participants in a distributed system. A critical section is a portion of a computation that accesses a resource or maintains an invariant that would be compromised by overlapping operations. Mechanisms that enforce mutual exclusion include software protocols, hardware-supported locks, operating-system mutexes, and distributed coordination algorithms.

Mutual exclusion is fundamental to concurrent computing because operations expressed as single statements in a program often comprise several separately executed steps. Without coordination, these steps can interleave and produce lost updates, inconsistent data structures, or invalid resource states. Exclusive access provides a way to make a group of operations appear indivisible to other participants following the same protocol.

The subject connects algorithm design, processor architecture, programming-language semantics, operating systems, and distributed computing. Its central distinction is between safety, meaning that incompatible activities never overlap, and progress, meaning that activities are eventually able to proceed. A mechanism can satisfy one without satisfying the other; practical implementations must also address memory visibility, scheduling, failures, and performance.

The critical-section problem and its guarantees

The classical critical-section problem considers several sequential participants that repeatedly perform unrelated work, request entry to a protected region, execute that region, and leave it. An entry protocol determines when a participant may enter; an exit protocol makes the resource available again. Participants need not execute at equal speeds, and their instructions may be interleaved by an operating system or executed simultaneously by different processors.

For nn participants, let CiC_i mean that participant ii is inside its critical section. The mutual-exclusion requirement is

∑i=1n1[Ci]≤1,\sum_{i=1}^{n}\mathbf{1}[C_i]\leq 1,

where 1[Ci]\mathbf{1}[C_i] is 1 when CiC_i is true and 0 otherwise. This is a safety property: a violation can be demonstrated by a finite execution in which two participants are inside simultaneously. The requirement normally applies separately to each protected resource. Two unrelated locks can legitimately allow two critical sections to execute at once.

A standard example is a shared counter initially equal to 10. Two threads each execute an increment implemented as a load, an addition, and a store. Both may load 10, compute 11, and store 11, although the intended result is 12. This is a race condition. A lock around the complete read–modify–write sequence prevents this particular interleaving, provided every conflicting access uses that lock. Locking only the final store does not protect the relationship between the old value and the new one.

Progress requirements refine the specification. Deadlock freedom means that if participants continue requesting entry and the relevant execution assumptions hold, some participant eventually enters. Starvation freedom means that every requesting participant eventually enters. Bounded waiting limits how many times others can enter after a participant has requested access. These guarantees are not interchangeable: a lock can continually admit some threads while indefinitely bypassing another. They also depend on assumptions such as eventual processor scheduling and eventual completion of critical sections.

Exclusive access is not the same as indivisibility at every abstraction level. A lock protects only code that observes its protocol; an uncoordinated reader may still see an intermediate state. Likewise, separate locks on two fields do not automatically preserve an invariant involving both fields. Correct design therefore identifies the protected state and the operations that must preserve its invariants before selecting an implementation. The relevant unit is often an entire data structure or a relationship between objects rather than an individual memory location.

Classical software algorithms and their historical significance

Mutual exclusion became a foundational problem as computers acquired multiprogramming and shared-memory concurrency. In 1965, Edsger W. Dijkstra published “Solution of a Problem in Concurrent Programming Control,” presenting the problem as one of coordination among sequential processes. The challenge was to obtain exclusive entry without relying on assumptions about relative execution speeds. Early solutions demonstrated that carefully arranged reads and writes could coordinate participants even without a dedicated hardware lock instruction.

A simple approach uses a shared variable indicating whose turn it is. For two participants, only the participant named by turn may enter, and it gives the turn to the other on departure. This enforces exclusion under the assumed memory model, but it imposes strict alternation: one participant may be blocked even when the other is doing unrelated work and has no interest in entering. The example established why mutual exclusion alone is an inadequate specification of a useful solution.

Dekker’s algorithm, attributed to the Dutch mathematician Theodorus Dekker and described in Dijkstra’s work, combines declarations of intent with a turn variable. If both participants want entry, the turn variable breaks the tie, and one temporarily withdraws its request. Gary L. Peterson’s 1981 two-participant algorithm gives a particularly compact construction. Participant ii, with jj denoting the other participant, executes:

interested[i] = true
turn = j
while interested[j] and turn == j:
    wait
critical section
interested[i] = false

The two intent flags distinguish a competing participant from an inactive one. The turn variable resolves simultaneous requests: if both flags are true, the participant favored by the final turn assignment waits while the other can enter. The standard proof assumes atomic accesses to these variables and sequentially consistent observations. Translating the pseudocode directly into ordinary shared variables in a modern programming language does not preserve those assumptions.

For multiple participants, Leslie Lamport’s 1974 bakery algorithm uses numbered tickets, analogous to taking a number at a shop. A participant selects a number greater than those it observes and waits for every competing participant with a smaller ordered pair consisting of ticket number and participant identifier. The identifier resolves equal numbers. A “choosing” indicator prevents a participant from treating another participant’s unfinished ticket selection as a completed choice. Notably, Lamport’s original formulation accommodates unusually weak assumptions about reads overlapping writes to certain single-writer registers.

These algorithms remain important in education and formal verification, even where production locks rely on specialized instructions. They separate the logical coordination problem from operating-system facilities and reveal exactly which assumptions are needed. They also show why apparently harmless simplifications—removing a tie-breaker, changing the order of two assignments, or assuming that a visible flag must be current—can destroy either exclusion or progress.

Atomic instructions and memory ordering

Modern processors provide atomic operations that combine observation and modification of a memory location into an indivisible operation. Common examples include test-and-set, atomic exchange, fetch-and-add, and compare-and-swap. A test-and-set operation returns the previous value of a flag while setting it to the locked state. If the old value was unlocked, the caller has acquired the lock; otherwise it must wait or retry. Compare-and-swap changes a location only if its current value matches an expected value.

These instructions solve the immediate problem of competing acquisitions, but atomicity of the lock word is not by itself enough to protect ordinary data. A compiler can transform code, and processors can execute memory operations in orders different from source order while preserving their architectural rules. Consequently, lock operations must also establish suitable ordering between accesses inside different critical sections. This requirement is described by a memory model, which specifies the observations that concurrent executions may produce.

A common locking pattern uses acquire semantics on successful acquisition and release semantics on unlocking. Informally, release makes the preceding protected updates available through the synchronization protocol, while acquire prevents subsequent protected accesses from being observed as occurring before the acquisition. More precisely, when an acquire operation observes the relevant release operation, the language or hardware model establishes an ordering relationship between earlier and later accesses. This permits a new owner to observe the state left by the previous owner, subject to the complete program’s synchronization rules.

The C11 and C++11 standards introduced standardized atomic facilities and formal memory models. In these languages, conflicting non-atomic accesses from different threads, at least one of which is a write, constitute a data race unless appropriately ordered; a data race produces undefined behavior. Declaring a lock flag volatile does not make its updates atomic or establish interthread synchronization. Correct low-level implementations instead use the language’s atomic operations, supported library facilities, or carefully specified platform primitives.

The underlying processor and memory system determine much of the implementation cost. Atomic operations on cacheable memory commonly require exclusive ownership of a cache line through a coherence protocol. They do not necessarily lock the entire memory bus, although particular instructions or memory configurations can have more disruptive effects. A cache line containing a contended lock may repeatedly move between cores, making a logically tiny operation expensive.

Memory ordering also explains why classical algorithms require care on contemporary machines. Peterson’s algorithm is valid under its textbook assumptions, but ordinary loads and stores in C or C++ do not supply those assumptions. An implementation using sequentially consistent atomic variables can reproduce the standard reasoning; weaker orderings require a separate, architecture- and language-aware proof. The atomicity of individual flags and the ordering of accesses to different flags are distinct questions.

Spinning, blocking, and operating-system mutexes

A spinlock waits by repeatedly examining or attempting to acquire a lock. Spinning avoids the direct cost of putting a thread to sleep and later waking it, so it can be appropriate when the protected work is short and the owner is currently running on another processor. Its central cost is that a waiting participant continues consuming execution resources. If the owner has been descheduled, spinning can spend an entire scheduling interval waiting for work that cannot currently advance.

A blocking lock instead arranges for a waiting thread to stop running until acquisition may be possible. This typically requires cooperation with the scheduler and a queue or equivalent record of waiters. Blocking introduces bookkeeping and may involve a system call, a context switch, and cache disruption. It nevertheless allows processors to perform unrelated work and is essential when waits may be long. A wakeup ordinarily makes a thread eligible to run; it does not guarantee immediate execution or ownership.

A mutex is an abstraction for exclusive ownership rather than a commitment to one waiting technique. Many implementations combine a fast uncontended path with a slower contended path. The fast path changes a user-space lock word atomically. Only when contention persists does the implementation ask the kernel to suspend the caller. On Linux, the futex mechanism supports this arrangement: a thread can wait only if a user-space word still has an expected value, and another thread can request that waiters be awakened.

The conditional nature of a futex wait addresses a critical race. Suppose a prospective waiter checks the lock, the owner releases it, and only then the waiter attempts to sleep. An unconditional sleep could miss the release and remain blocked without a future wakeup. Comparing the word and registering the wait atomically with respect to the futex operation prevents that particular lost-wakeup window. The complete mutex still needs a correct user-space protocol for ownership, waiter bookkeeping, and memory ordering.

Kernel locks face additional constraints. Disabling interrupts can prevent certain forms of reentry on the current processor, but it does not exclude execution on another processor. Conversely, a spinlock alone may be insufficient if an interrupt handler on the same processor can preempt its owner and attempt the same lock. Kernel interfaces therefore distinguish contexts and may combine spinlocks with local interrupt control. Sleeping while holding a lock intended for non-sleeping contexts can violate scheduler or kernel invariants.

Library mutex behavior varies by interface. POSIX distinguishes mutex types and attributes affecting recursive locking, error checking, process sharing, robustness, and priority protocols. A recursive mutex allows its owner to acquire it repeatedly, maintaining an acquisition count; it does not permit another thread to enter concurrently. A process-shared mutex must also be placed in memory accessible to the participating processes. These properties are part of the interface contract, not universal characteristics of every object called a lock.

Structured synchronization and protected invariants

Mutual exclusion is most useful when it is attached to a clear abstraction. An object containing a queue, for example, may use one mutex to protect its head pointer, tail pointer, element count, and links. These fields form one invariant: the pointers and count must describe the same queue. Protecting each field independently can expose combinations that never represented a valid queue state. The synchronization boundary should therefore follow the logical operation, such as insertion or removal, rather than merely the layout of individual variables.

A monitor combines protected state with operations that execute under mutual exclusion. The concept was developed in the early 1970s, notably in work by Per Brinch Hansen and C. A. R. Hoare. Monitor-style programming makes the association between data and synchronization explicit. Language constructs such as Java’s synchronized methods and blocks provide related facilities, although their detailed semantics depend on the language and runtime.

Exclusive access cannot by itself wait efficiently for an application-level condition. A consumer holding a queue’s mutex may discover that the queue is empty; repeatedly checking while retaining the mutex would prevent a producer from inserting an item. A condition variable addresses this problem by allowing the consumer to release the mutex and wait as one coordinated operation. Before returning to the protected code, the wait reacquires the mutex. A producer changes the queue state under the mutex and signals that a relevant condition may now hold.

Condition waits generally belong inside a loop that tests the protected predicate. A wakeup does not necessarily mean the predicate is true when the waiter runs: another consumer may remove the item first, and some interfaces allow spurious wakeups. The durable information is the shared state, not the notification itself. This distinguishes condition variables from mechanisms that retain a count of available permits.

A semaphore maintains such a count. An acquisition consumes a permit when one is available and otherwise waits; a release adds a permit. A semaphore initialized to one can enforce exclusive entry if used according to a suitable protocol, but it differs from a conventional ownership-based mutex. Some semaphore interfaces permit a participant other than the acquirer to release a permit. This makes semaphores useful for signaling and resource pools, while mutex ownership supports checks and scheduling policies that depend on identifying the holder.

Program structure also affects reliable release. Exception-safe scoped guards, such as C++ resource-acquisition-is-initialization wrappers, associate unlocking with leaving a lexical scope. Similar constructs appear as lock statements or context managers in other languages. They reduce accidental retention on early returns or exceptions, but do not resolve every lifetime or reentrancy problem. If protected code invokes an external callback, that callback may attempt to acquire the same lock or another lock in an incompatible order; preserving invariants requires accounting for such indirect control flow.

Deadlock, starvation, and priority inversion

A system can enforce perfect exclusion and still stop making useful progress. Deadlock occurs when a group of participants is permanently blocked by dependencies within the group. A common lock example has thread A holding lock L1L_1 while waiting for L2L_2, and thread B holding L2L_2 while waiting for L1L_1. Neither can reach its release operation. The classical Coffman conditions identify mutual exclusion, holding resources while waiting, lack of forced resource reclamation, and circular waiting as conditions associated with resource deadlock.

One standard prevention technique imposes a global order on locks and requires acquisition in that order. If all dependencies move toward increasing lock ranks, a circular chain cannot form. This becomes difficult when dynamically created objects determine the required locks or when independent software components establish different conventions. Try-lock operations can avoid blocking while another lock is held, but a retry protocol must release resources correctly and avoid repeated collisions.

Repeated activity without useful progress is livelock. For example, two threads may both detect a conflicting acquisition, release their first locks, pause for the same interval, and retry in synchrony. Randomized or asymmetric backoff can reduce this pattern, though a probabilistic improvement is not automatically a deterministic progress guarantee. Starvation is different: the system progresses, but one participant is indefinitely denied access. A frequently running thread may repeatedly reacquire an unfair mutex before a waiting thread is scheduled.

Priority inversion arises when a high-priority task waits for a lock held by a lower-priority task. If medium-priority tasks repeatedly preempt the owner, they can delay the high-priority task even though they do not use the protected resource. Priority inheritance temporarily raises the owner’s effective priority to reflect a blocked higher-priority waiter. Priority-ceiling protocols use restrictions or priority adjustments based on the tasks that may access a resource. These mechanisms are particularly important in a real-time operating system, where blocking times affect deadline analysis.

The 1997 Mars Pathfinder mission provided a widely discussed example of priority inversion involving a shared information-bus mutex. A low-priority task could hold the mutex needed by a high-priority task while medium-priority work delayed its release, contributing to watchdog resets. Enabling the mutex’s priority-inheritance facility addressed the observed scheduling problem. The example illustrates that mutual exclusion can be logically correct while its interaction with scheduling produces operational failure.

Failure while holding a lock creates another progress problem. A crashed process cannot execute its unlock operation. Robust mutex facilities can report owner death to a subsequent acquirer, but this does not prove that the protected data remain consistent. The new owner may need to repair a partially completed update before marking the state usable. A timeout similarly establishes only that waiting lasted too long; it does not by itself justify taking ownership away from a participant that may still be executing.

Contention, fairness, and multicore scalability

Lock performance depends strongly on contention. An uncontended mutex may require only a small number of instructions and one successful atomic operation. Under heavy contention, its cost includes waiting, coherence traffic, scheduler activity, and the serialization of protected work. A lock that performs well in a single-thread benchmark can therefore behave very differently when many cores compete for it.

A simple test-and-set spinlock repeatedly performs an atomic write-like operation on one shared location. This can cause unnecessary coherence traffic while the lock remains held. A test-and-test-and-set design first reads the lock with ordinary atomic loads and attempts the more expensive acquisition only when it appears free. Backoff introduces delays between retries, reducing simultaneous attempts. These techniques change traffic patterns rather than removing the serialized critical section.

A ticket lock uses one counter to assign acquisition numbers and another to indicate the ticket currently served. It provides an explicit first-come, first-served order based on the atomic ticket allocation. However, waiters generally poll the same serving counter, so each handoff can affect many caches. The MCS queue lock, introduced by John Mellor-Crummey and Michael Scott in 1991, instead links waiters into a queue and lets them spin primarily on separate waiter-associated locations. Its design reduces contention on one central polling location and targets a constant number of remote-memory references per acquisition.

Fairness has costs as well as benefits. An explicitly queued lock can suffer a convoy when the next designated owner is not scheduled, even if another thread is ready. An unfair lock may improve throughput by allowing a running thread to acquire it immediately, but can increase waiting-time variability. On non-uniform memory access systems, handing ownership between distant sockets can also be more expensive than local reuse. Designs that favor locality must balance that benefit against fairness.

The protected computation itself imposes a limit. If a fixed fraction ss of execution is inherently serialized, an idealized speedup on pp processors is bounded by

S(p)≤1s+(1−s)/p.S(p)\leq \frac{1}{s+(1-s)/p}.

This Amdahl-style bound abstracts away lock overhead, so actual scaling may be worse. Shortening a critical section, partitioning a shared table into independently locked shards, or using per-thread accumulation can reduce the serialized fraction. Finer-grained locking introduces additional lock operations, ordering constraints, and opportunities for mistakes, so more locks do not automatically mean better performance.

Measurement must distinguish average acquisition cost, throughput, tail latency, and fairness. False sharing can distort results when an unrelated frequently modified variable occupies the same cache line as a lock or waiter flag. Oversubscribing processors can turn a short spin wait into a long delay if the owner is not running. Consequently, lock benchmarks are meaningful only alongside workload characteristics, core placement, scheduling conditions, and the duration and variability of protected work.

Mutual exclusion across distributed systems

In distributed computing, participants cannot ordinarily coordinate through a single shared-memory atomic instruction. They exchange messages across a network, where delays vary and participants may fail independently. Distributed mutual exclusion therefore requires explicit assumptions about communication, membership, failures, and the resource being protected. A protocol that is correct when every participant remains responsive may cease to make progress after one crashes.

A centralized coordinator offers the simplest design. Participants request a lock from one authority, which grants it to at most one holder and queues conflicting requests. This reduces the coordination problem to maintaining a single authoritative ownership decision. However, a failed coordinator can halt acquisition, and an incorrectly managed replacement can create two authorities. Replicated coordination services commonly use a consensus protocol, such as the Raft consensus algorithm, to maintain one ordered state despite some server failures.

Permission-based algorithms avoid a single designated coordinator. Lamport’s 1978 mutual-exclusion algorithm orders requests using logical timestamps and participant identifiers. In its standard form, an acquisition involves 3(N−1)3(N-1) request, acknowledgment, and release messages among NN participants. The Ricart–Agrawala algorithm, published in 1981, reduces the standard count to 2(N−1)2(N-1) by deferring replies instead of broadcasting separate releases. These counts describe the basic algorithms under their communication and participation assumptions; they do not include a general failure-recovery mechanism.

Token-based algorithms represent the right to enter by possession of a unique token. In a logical ring, a participant passes the token to its successor when appropriate. Exclusion follows from token uniqueness, but recovery is delicate: losing the token prevents entry, whereas recreating it incorrectly can produce duplicates. Network partitions make this distinction particularly difficult because lack of a response does not reveal whether another participant has failed or is merely unreachable.

A lease grants authority for a bounded interval rather than indefinitely. Leases can support recovery when holders disappear, but their correctness depends on timing and enforcement assumptions. A client may pause for a long time, resume after its lease has expired, and continue issuing writes. Merely checking a local clock before beginning work does not prevent a delayed operation from arriving after a new holder has taken over.

A common additional mechanism is a fencing token, a monotonically increasing generation number attached to each grant. The protected resource records the latest accepted generation and rejects operations carrying older generations. This moves enforcement to the place where conflicting effects actually occur. The authority must issue tokens consistently, and the resource must validate them as part of applying operations. A distributed lock service without cooperation from the storage system or external device cannot necessarily stop a stale holder from causing effects.

Verification and alternatives to exclusive locking

Reasoning about a lock begins with a specification of the protected invariant and the synchronization protocol. A safety proof shows that no reachable execution contains conflicting owners. A liveness proof must additionally state scheduling and environmental assumptions: participants receive execution time, communication eventually succeeds where required, and owners eventually leave their critical sections. Without these assumptions, even a sound algorithm may be unable to guarantee eventual acquisition.

Model checking explores states and transitions to detect forbidden executions. Small models of two or three participants often expose errors in entry protocols, wakeup handling, or ownership transfer. The difficulty is state-space growth: program counters, local variables, queue contents, and memory-order choices multiply the number of possible states. Abstraction and symmetry reduction can make exploration tractable, while deductive methods use invariants and mathematical proofs to cover larger or unbounded configurations.

Dynamic race detectors offer a different kind of evidence. They observe an execution and identify conflicting accesses that lack the required synchronization relationship. Lock-order checking can detect potential cycles in acquisition patterns. Neither technique alone proves correctness: a program can be free of data races and still update the wrong object, violate a multi-object invariant, or deadlock only in an unobserved execution. Weak-memory behavior further requires tools or proofs that model the relevant language and processor semantics.

Some applications avoid exclusive locking by changing their data organization. Immutable objects can be shared without coordinating concurrent modifications because there are none. Ownership transfer and message passing arrange for one participant to control mutable state at a time. A single event loop can serialize handlers, but asynchronous suspension may still allow logically related operations to interleave across callbacks. Avoiding simultaneous machine-level execution does not automatically make a multi-step application operation indivisible.

Lock-free algorithms use atomic operations so that system-wide progress does not depend on one particular participant continuing to run. Wait-free algorithms provide the stronger guarantee that each operation finishes in a bounded number of its own steps under the stated model. These guarantees do not imply absence of retries, low latency, or simplicity. Dynamically allocated structures also require safe memory reclamation: a node removed by one thread may still be referenced by another, even if the pointer updates themselves are correct.

Other mechanisms relax the requirement for a single exclusive owner. Reader–writer locks permit concurrent readers while excluding conflicting writers. Read-copy-update allows readers to traverse suitable structures while reclamation waits for preexisting readers to finish. Optimistic schemes perform work speculatively and validate that no conflicting change occurred. A database transaction can combine locking, versioning, or validation to provide guarantees at a larger scope. Each approach changes the proof obligation: correctness depends on what observers may see, how conflicts are detected, and whether interrupted or failed operations can leave externally visible effects.