16. Nondeterministic Parallel Programming

What this lecture covers

Up to this point the course treated parallel programming as deterministic: Cilk's guarantees mean a race-free program always produces the same result. This lecture crosses into the messier territory of nondeterministic parallel programming, where shared, mutable state is updated by concurrent threads without a guarantee of consistent ordering.

It opens with the "golden rule" (never write nondeterministic parallel code) and the "silver rule" (if you must, have a strategy for managing it), then builds up mutual exclusion with mutexes, the sharp distinction between data races and determinacy races, how mutexes are implemented at the assembly level, deadlock and its three necessary conditions, the classic dining philosophers problem and its lock-ordering fix, and closes with an introduction to lock-based transactional memory as an alternative to hand-placed locks.

Key ideas

• Golden and silver rules: avoid nondeterministic parallel programs when possible; when not possible, always have a strategy (turning off the source of nondeterminism, fixed random seeds, record-replay, encapsulation) for managing and debugging it.
• Atomicity via mutexes: a mutex's lock/unlock calls make a critical section appear, to the rest of the system, as either fully executed or not executed at all, preventing races like a lost-update bug in a hash table insertion.
• Data race vs. determinacy race: a data race is two parallel instructions accessing the same location with no lock held in common and at least one write; a determinacy race is the same access pattern regardless of locking. Programs with locks are typically free of data races but still have determinacy races, and are therefore intentionally nondeterministic.
• No data races does not mean no bugs: a program can lock and unlock around a read and separately around a write, eliminating the data race but destroying atomicity, producing a subtly wrong result.
• Mutex properties: spinning (busy-wait) versus yielding (returns control to the OS); reentrant versus non-reentrant; fair versus unfair. A spinning mutex's implementation checks the lock value before attempting an atomic exchange, because that avoids generating cache-invalidation traffic while waiting.
• Competitive (spin-then-yield) mutex: spin for roughly one context-switch interval, then yield; this guarantees acquiring the lock within about twice the optimal wait time, an instance of the "ski rental problem."
• Deadlock's three conditions: mutual exclusion, non-preemption, and circular waiting; removing any one prevents deadlock. Acquiring locks in a fixed linear order (as in the dining philosophers fix) eliminates circular waiting and thus deadlock.
• Transactional memory: instead of manually placed locks, a critical region is marked as a transaction; the system detects conflicts and aborts/restarts conflicting transactions, useful for algorithms like concurrent graph Gaussian elimination where lock placement is awkward.

Walkthrough

Determinism, and why nondeterminism is dangerous (1:02)

The lecture defines a deterministic program as one where every memory location sees the same sequence of updates on every run, states the golden rule against writing nondeterministic parallel programs (mainly because it breaks debuggability), and the silver rule to always have a test strategy, such as disabling address randomization, fixing random seeds, record-replay, or encapsulating the nondeterminism (as Cilk's randomized scheduler already does).

Mutual exclusion and atomicity (13:15)

Using a hash table with chaining as the running example, the lecture shows how two concurrent insertions without synchronization can corrupt the list (a classic lost-update race), then introduces mutex locks to make the insertion's pointer updates atomic, restoring the invariant that all elements remain reachable in the list.

Data races versus determinacy races (20:23)

The lecture carefully distinguishes a data race (concurrent access to the same location with no common lock, at least one a write) from a determinacy race (same access pattern regardless of locking). Code that uses locks is typically free of data races but still has determinacy races, so it is deliberately nondeterministic; a race detector can still be useful for finding genuine, unintended data races. An example shows that eliminating a data race by locking a read and a write separately does not restore atomicity.

Implementing mutexes (34:42)

Working through x86 assembly for a spinning mutex, the lecture explains why the code first checks the lock's value before attempting the atomic exchange: checking only requires shared cache state, while the exchange requires exclusive/modified state, so checking first avoids generating unnecessary cache-invalidation traffic while spinning. It then contrasts yielding mutexes and introduces the competitive (spin-then-yield) mutex, connecting it to the ski-rental problem and noting a randomized variant achieving a competitive ratio of e/(e-1).

Deadlock and dining philosophers (59:02)

The lecture defines deadlock's three necessary conditions (mutual exclusion, non-preemption, circular waiting), illustrates it with two threads acquiring two locks in opposite orders, and tells the dining philosophers story (with chopsticks), showing that acquiring resources in a fixed linear order prevents the circular wait and proves deadlock cannot occur. It also warns that holding a mutex across a Cilk sync can deadlock a Cilk program even with just one lock, and recommends holding mutexes only within a single strand and for as short a time as possible.

Transactional memory (1:11:10)

Using concurrent graph Gaussian elimination as a motivating example where manual lock placement is awkward, the lecture introduces transactional memory: mark a critical region as a transaction, and let the system detect conflicts and abort/restart as needed. It defines conflict, contention resolution, forward progress, and throughput, then sketches a lock-based transactional-memory algorithm using a finite ownership array (hashing memory locations to a fixed set of fair locks) and a "release, sort, reacquire" protocol that avoids ever needing a single global lock.

Before you watch

• Be comfortable with Cilk's deterministic execution model and the guarantees Cilk provides when programs are free of determinacy races.
• Review the MSI/MESI cache coherence protocol from an earlier lecture, since it explains why spinning mutexes check before exchanging.
• Recall work and span analysis, since the lecture briefly contrasts "easy" deterministic parallel reasoning with the harder nondeterministic case.

Check your understanding

1. What is the difference between a data race and a determinacy race, and why can a program have no data races yet still have a bug?
2. Why does a well-implemented spinning mutex check the lock's value before attempting an atomic exchange, rather than just attempting the exchange directly?
3. What are the three necessary conditions for deadlock, and how does acquiring locks in a fixed linear order prevent it?
4. Why can holding a mutex across a Cilk sync statement deadlock a program even with a single lock?
5. In the transactional-memory algorithm described, what problem does the "release, sort, reacquire" protocol solve, and why does it avoid needing a global lock?