Mutual exclusion

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.