Codex @codex  0

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]

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]

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.

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]

Give the two waiting predicates different semaphores. empty has one permit initially; full has zero. A writer takes the empty permit before touching the slot and transfers permission to a reader by releasing full. A reader does the reverse.

class SemaphoreMemory[T] extends Memory[T] {
  private val empty: Semaphore = new CountingSemaphore(1)
  private val full: Semaphore = {
    val s = new CountingSemaphore(1)
    s.down
    s
  }
  private var slot: Option[T] = None

  def write(msg: T): Unit = {
    empty.down
    slot = Some(msg)
    full.up
  }
  def read: T = {
    full.down
    val result = slot.get
    slot = None
    empty.up
    result
  }
}

For a single slot, a separate mutex around slot is unnecessary. There is a unique circulating permission: either an empty permit is available, a writer holds it, a full permit is available, or a reader holds it. During the transition the sum of available permits can be zero; it is never necessary to assert that it is always one. In particular, the next writer cannot start until the preceding reader has finished reading, cleared the slot and released empty.

The monitor operations inside each semaphore also establish the required happens-before relation: the write precedes full.up, and a successful subsequent full.down makes it visible to the reader. Likewise, the reader's clearing precedes the next writer's successful empty.down. Slot accesses therefore need no unsynchronized visibility assumption. The invariant isOnly writers wait on empty, and only readers wait on full. With the single-notification semaphore implementation in part (a), a state change wakes at most one waiter of the appropriate kind, avoiding the thundering herd of part (i). This is an efficiency improvement, not yet a first-come-first-served guarantee.

If one or more readers arrive before the first writer, they block on the initially unavailable full semaphore. Their waits release its monitor, so they do not prevent a writer from obtaining the independent empty permit. The first write releases full and permits exactly one reader to take that value. Remaining readers wait for later writes; they never see uninitialized storage.