ECE344 Fall 2026 (Sec 1) Lec 17 - Building Locks

Overview

The lecture builds from an unsafe check-then-set lock to atomic compare-and-swap spin locks, then shows why efficient sleeping mutexes need coordinated queueing to prevent lost wakeups and unfair lock acquisition. It explains how Linux futexes provide a fast user-space path with kernel-assisted waiting, and how read-write locks allow concurrent readers while introducing writer-starvation risks.

Key takeaways

A correct lock must make checking and acquiring one atomic operation; compare-and-swap prevents two threads from both claiming a lock after reading the same unlocked value.
Spin locks are safe but waste CPU when waits are long, so they are most appropriate for short critical sections or brief internal bookkeeping.
A sleeping mutex needs coordinated queue management: otherwise a new thread can steal the lock, or an unlock can miss a waiter and cause a lost wakeup.
Linux futexes keep uncontended mutex operations in user space and use kernel-assisted atomic waiting only when threads contend.
Read-write locks can run multiple readers concurrently, but a policy that admits new readers ahead of a waiting writer can cause writer starvation.

Chapters

0:00 From a Broken Check-Then-Set Lock to Atomic Operations

Two threads can both read an unlocked value of 0, set it to 1, and enter the critical section, so the original lock does not provide mutual exclusion.
Disabling interrupts can help on one CPU but does not solve the problem across multiple CPUs.
Peterson's algorithm and Lamport's bakery algorithm can work under strong assumptions, but depend on ordered execution and do not suit modern out-of-order processors.
Compiler and CPU reordering make a single atomic operation necessary for safely testing and acquiring a lock.

11:00 Compare-and-Swap Makes Lock Acquisition Atomic

Compare-and-swap takes a pointer, an expected old value, and a replacement value, returning the original value at the pointer.
For a lock initialized to 0, compare-and-swap from 0 to 1 succeeds for only one competing thread.
A thread can loop until compare-and-swap returns 0, ensuring that checking and claiming the lock happen in one atomic operation.
The lock's unlock operation sets its value back to 0, assuming callers follow the lock, critical section, unlock protocol.

16:50 Hardware Instructions and the Basic Spin Lock

x86 provides compare-and-swap through the CMPXCHG instruction, while RISC-V can implement the operation using load-reserved and store-conditional.
GCC exposes atomic operations through intrinsics such as __sync_val_compare_and_swap and selects instructions for the target architecture.
The resulting spin lock repeatedly retries compare-and-swap while another thread holds the lock, which is safe but consumes CPU time.
A sample protected increment consistently reaches 8 million, demonstrating that the atomic lock prevents lost updates.

21:10 When Spinning Helps, and xv6's Spin-Lock Tradeoff

Spinning can be faster when a critical section is very short, because another CPU may release the lock before a sleep-and-wake operation would finish.
xv6 uses spin locks and disables interrupts while acquiring them to avoid interference from interrupt handlers on the same CPU.
A spin lock is especially wasteful on a single CPU if the lock holder cannot run while another thread spins.
For longer waits, yielding or sleeping lets the scheduler run the lock holder or another useful thread.

24:10 A Queue-and-Sleep Design for Contended Locks

The proposed blocking lock places a thread in a FIFO wait queue when compare-and-swap fails, then puts that thread to sleep.
On unlock, the current holder sets the lock to 0 and wakes a waiting thread from the queue.
Queue insertion and checking are initially treated as atomic to focus attention on the lock protocol rather than list implementation.
The design aims to replace prolonged busy-waiting with sleeping, but its separate queue and lock operations create race conditions.

28:10 Naive Queueing Causes Lock Stealing and Lost Wakeups

A new thread can acquire a lock immediately after it is set to 0, stealing it from a thread that has already waited in the queue.
A lost wakeup occurs if an unlock checks an empty queue just before another thread joins the queue and goes to sleep.
The queued thread can then sleep indefinitely because the unlocking thread has already skipped its wakeup check.
Waking every queued thread would also cause a thundering herd: many threads wake, but only one can acquire the lock.

36:30 Use an Internal Spin-Lock Guard to Protect the Protocol

A separate guard spin lock protects the mutex's internal state and queue while lock and unlock operations inspect or modify them.
The guard serializes queue insertion with the unlock operation's queue check, preventing a waiter from being missed.
The guard is held only around short internal operations, rather than throughout the user's potentially long critical section.
Simply adding a guard is insufficient if a thread sleeps while still holding it, because other threads would be unable to make progress.

40:00 Transfer Mutex Ownership Directly to a Queued Thread

When the wait queue is empty, unlock sets the mutex state to 0; when a waiter exists, unlock wakes the queue's front thread instead.
In the queued case, the mutex remains marked as held, so a newly arriving thread cannot steal it before the awakened waiter resumes.
The waiter is added to the queue while holding the internal guard, then the guard is released before the thread sleeps.
This design uses a brief spin lock for queue coordination while allowing the main mutex to sleep through longer waits.

44:10 Handle the Race Between Releasing the Guard and Sleeping

A thread can be queued and release the guard, then be context-switched before it has actually gone to sleep.
An unlock operation may try to wake that thread during this interval, so the wake operation must handle a thread that is not asleep yet.
One remedy is to retry the wake until the thread is sleeping; another is a kernel operation that checks the condition and blocks atomically.
The internal spin lock remains useful because it protects only a small amount of queue bookkeeping, not the full critical section.

52:00 Linux Futexes Combine User-Space Fast Paths with Kernel Waiting

A futex, short for fast user-space mutex, pairs an integer in memory with a system call for atomic wait and wake operations.
The futex wait operation sleeps only if the integer still has the expected value, preventing a wakeup from being lost between checking and sleeping.
The wake operation can wake a specified number of waiting threads, leaving queue management and atomic coordination to the kernel.
A standard mutex first tries compare-and-swap in user space and enters the kernel only when contention requires queueing and sleep.

56:00 Futex Mutex States and the Cost of Contention

The described mutex uses states 0 for unlocked, 1 for locked without known waiters, and 2 for locked with a waiter.
When a mutex alternates between 0 and 1 without contention, threads can acquire and release it without entering kernel mode.
Contended acquisition takes the slower futex path, where the kernel queues sleepers and wakes them when the lock becomes available.
Many futex calls during a workload such as 8 million lock operations indicate substantial contention and may signal a performance problem.

58:18 Read-Write Locks Allow Concurrent Readers

A mutex excludes all other threads, whereas a read-write lock permits multiple readers while limiting access to one writer.
A writer must wait until existing readers have released their read locks before entering its critical section.
The pthread interface uses separate read-lock and write-lock operations, with a shared unlock operation.
Read-write locks can improve performance when reads are common, but they add coordination beyond the basic mutex.

1:01:00 Build a Read-Write Lock and Identify Writer Starvation

The example combines a mutex, a short-lived spin-lock guard, and a reader count to coordinate shared read access.
The first reader acquires the mutex, later readers increment the count, and the last reader releases the mutex.
A steady stream of new readers can keep extending the shared-reader group ahead of a waiting writer, starving the writer.
For ECE344's data-race prevention work, a mutex is generally sufficient; read-write locks are an advanced performance tool with fairness tradeoffs.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jon Eyolfson.