Skip to content

Consolidation 5: Synchronization is ordering plus lifetime plus progress

Use this note after Lecture 10 and Lecture 11. It is a retrieval exercise: predict the answer before opening the explanation. The complete executable reference is the native SPSC queue lab.

1. Name what the atomic protects

A camera thread writes a descriptor, then stores ready=true. The inference thread sees true and reads the descriptor.

Question: is an atomic ready flag enough?

Answer: only with the required ordering and lifetime protocol. In a one-publication example, a release store observed by an acquire load orders prior payload writes before subsequent reads. If the producer rewrites the payload while the consumer still reads it, publication alone is insufficient. A relaxed flag does not publish unrelated ordinary data; volatile is not C++ thread synchronization.

Transfer: add a permission-to-reuse flag or a bounded queue. Mark both ownership directions and explain how the second direction prevents overwrite. The lab uses release/acquire on both read and write indices.

2. Distinguish full from empty

A capacity-three ring uses four storage slots. Begin with read=write=0, push three values, reject the fourth, pop one, then push another.

Answer: write reaches 3; its next value 0 equals read, so the extra push must fail. After read advances to 1, writing slot 3 and wrapping write to 0 is permitted. This implementation does not require a power-of-two capacity. Removing the full check is a real overwrite defect caught by the mutation test.

Transfer: a second producer invalidates the single-writer assumption even if each index remains atomic. Select a reviewed multi-producer algorithm or introduce appropriate synchronization; do not merely change the label to MPSC.

3. Keep progress distinct from timing

Question: can a lock-free queue miss a 10 ms deadline?

Answer: yes. Lock-free is a progress property under algorithmic execution assumptions, not a bound on scheduling delay, cache misses, retries by a particular thread, or downstream device work. A failed push can return quickly while the caller retries indefinitely. Even an atomic type’s implementation may not be lock-free on every target.

Transfer: choose an overload policy: bounded waiting, rejected work, or a separately designed latest-value channel. Define which observation sequences are lost and how a consumer detects stale data.

4. A pointer is not a lifetime guarantee

Question: a thread atomically loads pointer P; another thread replaces P and frees the old object. May the first thread dereference its copy?

Answer: not without a mechanism preserving the object’s lifetime. Atomic pointer access does not keep the pointee alive. A reference count, reviewed hazard-pointer protocol, suitable RCU flavor, or lock may provide the required contract. Device operations retaining a pointer require their own completion/lifetime handling.

Hazard-pointer protection includes publishing and revalidating the pointer. RCU defers reclamation until relevant pre-existing readers finish; implementation/preemption rules vary by flavor. Neither mechanism automatically serializes competing updaters or repairs arbitrary in-place mutation. Read the primary references in Lecture 10 instead of implementing a reclamation algorithm from this short note.

5. Separate deadlock from priority inversion

L holds a mutex needed by H. M preempts L. H cannot proceed.

Answer: this is priority inversion if execution of unrelated M extends H’s wait through the low-priority holder. Priority inheritance can raise L’s effective priority while H blocks. M remains runnable; it is not itself blocked on the mutex. PI does not eliminate L’s remaining critical-section work.

Now let L also wait for a lock held by H. That circular dependency is a deadlock. Priority boosting cannot make either owner release a lock while both are waiting. Establish a consistent lock ordering and include every nested path.

Transfer: a failed trylock followed by retry while retaining another required lock is not a universal deadlock solution. An acquire/release/retry protocol can avoid one condition but still livelock or starve without a suitable policy.

6. Account for bounded blocking

H needs 1.2 ms of CPU work and may wait for 0.6 ms of a lower-priority critical section. Its deadline is 2 ms.

Answer: 1.8 ms is already committed before interrupt, scheduling, higher-priority, and other interference. Priority ceiling can control blocking under its assumptions, but does not mean H never waits. An additional 1 ms of interference makes this instance exceed its deadline.

Completion: retain the three native queue test outcomes, draw both ownership transfers, and explain one example each of data race, lifetime failure, deadlock, and deadline miss. A passing stress test does not replace the memory-order proof; a lockdep-clean run does not establish timing bounds. Continue with memory allocation and DMA ownership.