= 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.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Locks>[pp. 1–2: lock ownership and critical sections]{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:
``
r = read(x)
r = r + 1
write(x, r)
``
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.
\Image[/mutual-exclusion-lost-update-timelines.png]
{title=A <lost update> and its repair by <mutual exclusion> around the complete increment}
The <binomial coefficient> $\binom{6}{3}=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.<Defining Liveness by Bowen Alpern and others>[pp. 181–182: mutual exclusion, finite witnesses to safety violations, and eventual service]{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.<Working Draft, Standard for Programming Language C++ (N4861)>{ref}
Back to article page
