Synchronization (computing)

Coordinating concurrent activities so that required ordering and visibility rules hold. Mutual exclusion is one form of synchronization; waiting for another software thread to finish is another.

Many waiting software threads wake for a state change that can benefit only one or a few of them. Repeated monitor reacquisition, failed predicate checks and context switches add overhead; selective notification can reduce it.

A permit-based synchronization object. A down operation waits until it can consume a permit; an up operation supplies one. Unlike ownership-based mutex use, signalling can pass between different software threads.

A semaphore that satisfies registered down requests in FIFO queue order. Direct handoff reserves a released permit for the oldest waiter rather than exposing it to competing newcomers. The ordering of truly concurrent registrations is determined by the registration mechanism.

A semaphore with at most one available permit. Initially unavailable instances support event signalling; initially available instances can protect one-at-a-time access under a balanced acquisition-and-release discipline.

A semaphore with a nonnegative number of available permits. Its contract must state initial availability and whether unmatched releases beyond an initial or configured bound are allowed.

A construct combining mutual exclusion for operations on shared state with condition-based waiting. A waiting caller releases the monitor while asleep and must recheck its predicate after regaining access.

A wait returning without the application predicate necessarily becoming true. Rechecking that predicate in a loop also handles the separate possibility that another caller consumed the resource before the awakened caller could acquire the monitor.

A concurrent object behaves as if its operations took effect at individual instants between invocation and response, respecting nonoverlapping operations' real-time order. A read overlapping a replacement can return the old version while remaining linearizable.

The instant used to identify an operation's abstract effect in a proof of linearizability. Loading the published pointer can be the linearization point of an immutable snapshot read, with suitable ordering and lifetime guarantees.

A lost wake-up occurs when a notification arrives after a worker checks for work but before it safely starts waiting, so the worker sleeps despite available work. Avoid it by coupling the condition check with the wait protocol, or by using a persistent notification that is checked atomically with entering sleep. A queue test followed by an unrelated sleep instruction is insufficient.

Operating-system processes communicate by sending and receiving messages. A message-passing mutual exclusion server can centralize ownership of a shared resource: clients request permission, wait for a grant, and release the resource when finished. Correctness depends on an explicit delivery and failure model; reliable delivery and compliant clients suffice for the basic ownership protocol.

A message-passing channel carrying protocol instructions, such as cancellation or permission to send, rather than ordinary application payloads. A reverse control channel can communicate consumer closure back to a remote producer.

Sharing one message-passing channel among multiple logical streams by attaching a stream identity to each transferred value. Independent cancellation requires a protocol that conveys which stream is ending; bounded per-stream flow control can prevent head-of-line blocking from a single unready consumer.

A message-passing channel carrying traffic for multiple logical producer-consumer pairs.

A process that receives tagged stream traffic and dispatches its values to the corresponding output ports.

A process that tags values accepted from several input ports with stream identities and forwards them through a shared message-passing channel.

A periodic indication that a peer is still communicating even when it has no application data to send. Absence beyond a deadline can suggest a failure but does not distinguish a crash from excessive delay.

A communication object with an output port used to send values and an input port used to receive them. Its contract specifies ordering, capacity, sharing and closure. In synchronous message passing, a send completes through a matching receive; a buffered message-passing channel can retain accepted values until a receiver is ready.

A process with finite positive capacity whose output sequence is a prefix of its input sequence and whose input-output length discrepancy never exceeds that capacity. While active, it offers input whenever non-full and output whenever nonempty; upstream closure drains retained data, while downstream closure cancels delivery.

Delay to otherwise serviceable work because a preceding operation cannot complete. A timer service using serial synchronous message passing can block on one unready subscriber before delivering notifications to other ready subscribers. Buffered delivery moves the issue to queue capacity and service rate rather than guaranteeing its absence.

A message passing discipline in which a send completes only when a matching receive accepts the message. This rendezvous transfers both data and control dependencies: an unready recipient can block a service and thereby delay its other clients. A reply is a separate send unless the interface supplies synchronous send-and-receive.

A system call that sends a request and commits the caller to receiving the matching reply as one coordinated operation, often named sendrec. It avoids the gap in which a client has completed a send but has not yet entered a receive. It does not make the service nonblocking or eliminate deadlock caused by other circular dependencies.

Mutual exclusion allows at most one participating software thread at a time to execute a protected critical section. A mutex is an object used to enforce that rule; the critical section is the region of the program that needs the rule. Several different critical sections can use the same mutex to protect the same shared data. The benefit is reasoning about a complete update without another cooperating software thread observing or changing its intermediate state.^[ref]

For a small lost update, shared x initially equals $0$. Each of two software threads, T1 and T2, uses its own local r and performs these three steps:Assume sequential consistency: each step is indivisible, each software thread keeps the displayed order, and a read sees the latest preceding write to x. In the thread interleaving T1 read, T2 read, T1 add, T2 add, T1 write, T2 write, both local values become $1$ and both writes store $1$. Final $x=1$ instead of $2$: a lost update despite two correctly executed local additions. Separate indivisible reads and writes are insufficient; the complete read, modify and write must be protected.

The binomial coefficient $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ counts the thread interleavings preserving the two three-step orders: choose T1's three positions, with the remaining positions belonging to T2. Exhaustive enumeration gives final $x=1$ in 18 orders and $x=2$ in the two serial orders. These counts are not probabilities: no random scheduler has been specified. With the same mutex acquired before reading and released after writing, only the two complete increment orders remain, and both give $2$. Alternatively, an atomic read-modify-write increment updates x in one indivisible step. Protecting only the write still allows both software threads to read $0$ beforehand.

Mutual exclusion is a safety property: two participants must never be inside the protected critical section together. Eventual entry for every persistent requester is a liveness property, expressed here as starvation freedom. A protocol that never admits anyone satisfies the first requirement while failing the second. Nor does a mutex alone promise which waiting software thread enters next, or that a producer runs before a consumer. Such application ordering needs an additional synchronization protocol.^[ref]

The sequential consistency assumptions delimit this calculation. In C++, unsynchronized conflicting accesses to an ordinary shared object can be a data race, which makes behavior undefined; the 20 schedules are not a prediction for that program. An atomic operation with relaxed ordering also supplies no acquire-release synchronization for other data. A real mutex must supply both exclusive entry and the required happens-before ordering between its users.^[ref]

Maintain an owner identity, initially empty, and a FIFO queue of accepted client requests. A request appends its sender to the FIFO queue. A release from the owner clears the owner. Whenever there is no owner and the FIFO queue is nonempty, remove its oldest request, record that client as owner, and send a grant. The server processes these state changes sequentially.

Safety proof. At most one grant is outstanding: a new grant requires an empty owner field, and a valid release clears precisely the preceding ownership. Compliant clients access the resource only while holding their grant, so mutual exclusion follows. With reliable eventual message passing, continued server execution and finite resource-use durations, the FIFO queue also gives starvation freedom for accepted requests, since later requests cannot overtake them.

A region whose accesses must obey a shared synchronization protocol. For the lost update in mutual exclusion, the critical section includes the read and the local addition as well as the write. Choosing its boundary means identifying the complete operation whose intermediate state must be protected. Every conflicting access must participate in a compatible protocol; merely declaring a mutex does not protect accesses that bypass it.

An object with acquire and release operations that provides exclusive ownership to a participating software thread. Several source-code regions can acquire the same mutex; two different mutex objects do not exclude each other's users. The caller should enter its critical section only after successful acquisition and release ownership on every exit path. A mutex may make a waiting software thread sleep or use a spinlock; the interface and the waiting mechanism are distinct.^[ref]

A mechanism that waits for ownership by repeatedly trying while consuming CPU execution time. A spinlock built from test-and-set can enforce mutual exclusion without guaranteeing starvation freedom. Progress also requires the owner to run and release: if a waiting software thread monopolizes the only CPU while the owner is suspended, exclusive entry alone cannot help.^[ref]

An atomic read-modify-write that returns a flag's old value while setting it. In a sequential consistency model with the flag initially $0$, exchange(flag, 1) permits entry only when it returns $0$; an owner resets the flag to $0$ on release. Between releases only one exchange can observe $0$. By contrast, separate read(flag) and write(flag, 1) steps allow both contenders to read $0$ before either writes $1$. The indivisibility of the exchange is an assumed primitive, not something proved by writing its steps as ordinary assignments.^[ref]

An ordered execution obtained by mixing steps of several software threads while retaining each one's own step order. In the sequential consistency model of mutual exclusion, an indivisible step finishes before the next begins. Selecting the step boundaries is part of the model: an atomic read-modify-write increment has one boundary, whereas a separate read, local addition and write have three. Enumerating all such orders checks this specified model, not an arbitrary memory model or a real mutex implementation.

A change that is overwritten by another update based on an older value. In mutual exclusion, both software threads read $0$ and later write $1$, so one intended increment is lost. This race condition can occur with individually atomic reads and writes and therefore need not involve a data race. Its repair must cover the complete update, using a critical section or an appropriate atomic read-modify-write.

A requirement whose violation has a finite execution prefix that no continuation can repair. Two software threads simultaneously inside a protected critical section already violate mutual exclusion; later leaving does not erase that violation. This contrasts with a liveness property, for which a long finite wait alone does not establish failure.^[ref]

A requirement of eventual progress, with no finite prefix ruling out its eventual satisfaction. For starvation freedom, a persistent requester must eventually enter its critical section. Establishing such a liveness property requires explicit scheduling and protocol assumptions in addition to mutual exclusion. Exhaustive finite thread interleaving checks alone do not establish eventual service for repeatedly competing software threads.^[ref]

For acquisition of a mutex, the guarantee that every persistent requester eventually succeeds, under specified scheduling assumptions and with owners eventually releasing. Some software threads repeatedly succeeding while another waits forever violates starvation freedom without violating mutual exclusion. A finite bound on the wait, and service in arrival order, are additional requirements.

With a LIFO stack of waiting requests, an old request may remain at the bottom while a new request arrives before each completion and is served next. Every service can finish in finite time while the old request waits forever. A FIFO queue prevents this overtaking within one priority class. Nonpreemptive strict-priority arbitration can separately starve a lower-priority class; using a LIFO stack adds potential starvation even among requests of equal priority.

A group of participants cannot proceed because each waits for a resource whose release depends on another participant in the group. Consider two initially free mutex objects A and B. T1 acquires A then tries B; T2 acquires B then tries A. If each obtains its first mutex, both wait permanently for the other, with release reachable only after the second acquisition. Each mutex still enforces mutual exclusion.^[ref]

Each software thread performs four indivisible operations: acquire its first mutex, acquire its second, release the second, release the first. An unavailable acquisition blocks; neither participant releases early. A state records each participant's completed-operation count and both owners. Exhaustive exploration finds 19 reachable states with opposite orders, including exactly one nonterminal state with no enabled operation: both counts are $1$, T1 owns A, and T2 owns B. Giving both participants the order A then B leaves 16 reachable states and no such blocked state. Unshown grid positions are unreachable. These are tiny sequential consistency models, without timeouts, cancellation, recursive acquisition or other resources.

Absence of a reachable deadlock. In the finite acquisition model under deadlock, reaching a nonterminal state with no enabled operation is a finite witness to failure, so this formulation is a safety property. Sometimes the phrase is used for eventual acquisition by some requester, a liveness property; the intended requirement must be stated. Neither formulation by itself promises starvation freedom for every requester.

A shared order governing acquisition of distinct mutex objects. To prevent circular waiting, choose a strict total order and acquire only a higher-ranked mutex while retaining lower-ranked ones. In the two-object deadlock example, every participant acquires A before B. An outline of the argument is that ranks would strictly increase around any alleged waiting cycle, yet return to the starting rank, a contradiction. The rule must include acquisitions hidden inside called routines. It excludes this kind of deadlock, not arbitrary waiting on other resources or failure to schedule an owner.^[ref]

Rules specifying which shared-data observations and operation orders are allowed. Sequential consistency is the model used in the two diagrams. A language memory model can permit weaker ordering and impose additional conditions on conflicting accesses. Correct use of an indivisible flag must therefore be checked against that memory model, including happens-before relationships for the data guarded by the flag.

A memory operation's execution is conditional on a preceding value. A control dependency alone does not generally order two reads on POWER architecture or the relevant ARM memory models; it must not be substituted for an address dependency in pointer-publication reasoning.

A value loaded by one instruction directly contributes, through register computation, to a later memory access's memory address. Loading a pointer and then reading fields through that saved pointer is a natural example. This differs from a control dependency.

An architectural memory model preserving store-to-store and load-to-load ordering while allowing a later load to a different address to bypass a locally buffered store. This permits the two-zero store-buffering outcome while requiring no extra hardware fence for simple immutable pointer publication.

An operation constraining specified memory-access orderings. The strength and scope of a memory barrier matter; it does not by itself provide mutual exclusion or safe memory reclamation.

Execution behaves as if steps occurred in one total order preserving each participant's program order; reads observe the latest preceding writes in that order. This is the definition given in the 1979 paper How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, printed p. 690. It permits many thread interleavings, including the lost update under mutual exclusion; ordering individual accesses does not combine them into one atomic operation.

For the C++ case used here, conflicting accesses by different software threads, at least one non-atomic, with neither ordered before the other by happens-before. Such a data race has undefined behavior. A race condition is broader: the lost update with separate atomic reads and writes depends on their order while avoiding a data race.^[ref]

An ordering binary relation used by a memory model to constrain observation of shared data. For the mutex example, T1's write precedes its release, that release synchronizes with T2's successful acquisition, and that acquisition precedes T2's read. Together these steps order the write before the read. Wall-clock timing alone does not establish happens-before.^[ref]

A release on an atomic object can synchronize with an acquire that reads the released value, establishing happens-before for surrounding accesses. A test-and-set spinlock needs suitable acquisition and release semantics for its guarded data; relaxed flag operations alone do not supply that relationship. This is a separate question from the flag's indivisibility.^[ref]

An operation that takes effect indivisibly relative to the specified competing accesses. An atomic increment protects the whole read-modify-write; separate atomic loads and stores do not make their combined sequence an atomic operation.

// Target: computer-science.bigb

An atomic operation that reads a shared object's value and changes it as one indivisible action. For an increment from $0$, the two operations under mutual exclusion produce $1$ then $2$ in either software thread order. A test-and-set is another example. The operation's ordering guarantees for other data still depend on the memory model and its selected acquire-release synchronization semantics.

An atomic read-modify-write that replaces a location only if its current value matches an expected value. An update based on an old version can retry after a failed compare-and-swap instead of blindly overwriting a competing writer's change.