Operating Systems · Cluster
Synchronization
Locks, futexes, and memory ordering.
- 01 Atomic Read-Modify-Write and the Mutual Exclusion Problem Why a flag plus a check cannot keep two threads out of the same critical section, and what a single indivisible read-modify-write instruction changes about the problem.
- 02 Acquire and Release Ordering: What a Lock Actually Guarantees About Memory How store buffers and compiler reordering let a consumer observe a published value before the data it points to, and how release and acquire operations restore the ordering without a full fence.
- 03 Condition Variables and the Lost Wakeup Problem Why checking a predicate and then sleeping is not atomic, how a condition variable closes the window with the mutex it is paired with, and why the wait must be a loop.
- 04 Futex Wait and Wake: How a Lock Sleeps Without a Syscall on the Fast Path How a 32-bit word in user memory plus a hashed kernel wait queue gives uncontended locks no kernel entry at all, and what requeue and priority inheritance add for the contended cases.
- 05 Spinlock Contention: Ticket Ordering and MCS Queues Why a test-and-set spinlock makes every waiter hammer one cache line, how a ticket lock restores first-come order, and why a queue of per-thread flags beats both.
- 06 Reader-Writer Locks and the Starvation They Invite How a shared-exclusive lock counts readers in one word, why an unbroken stream of readers can postpone a writer indefinitely, and which fairness schemes actually bound the wait.
- 07 Seqlocks: Optimistic Reading Without Blocking the Writer How a version counter lets readers copy shared data without registering, why the writer never waits, and which data types make the retry loop impossible to get right.
- 08 Read-Copy-Update: Publishing New Versions and Waiting Out Old Readers How RCU lets readers run without any synchronization instruction at all, what a grace period must prove before memory can be freed, and where the approach stops working.
- 09 Lock-Free Reclamation: ABA, Tagged Pointers, and Hazard Pointers Why a compare-and-swap pop can succeed against a pointer that was freed and reused, and what tagging, hazard pointers, and epoch schemes each cost to close that hole.
- 10 Priority Inversion and the Protocols That Bound It How a low-priority lock holder can block a high-priority thread indefinitely, what inheritance and ceiling protocols each guarantee, and why both need the scheduler inside the lock.