Locks

01 Introduction

Lesson 6.2 introduced the critical-section abstraction and the hardware primitives — test-and-set and compare-and-swap — that make it implementable. This lesson presents the lock: the standard library abstraction that packages those primitives into a convenient interface for the programmer. A lock has just two operations: lock(), which blocks the caller until it acquires the lock, and unlock(), which releases it. Between them the caller is guaranteed to be the only thread executing code protected by that lock.

The interface is simple. The implementation is not. A lock that simply spins on a test-and-set instruction — the naive approach from Lesson 6.2 — satisfies mutual exclusion but wastes CPU cycles while it waits, and it offers no fairness guarantee. A lock that blocks the caller on a wait queue avoids the wasted cycles but adds the cost of a context switch to every contended acquisition. Neither approach is right for every workload, and the design of a production lock must balance the two.

This lesson examines the lock abstraction from both sides. It presents the interface and its semantics, the two fundamental implementation strategies (spinning and blocking), and the refinements that make each strategy practical: ticket locks for fairness, queue-based locks for cache efficiency, and futexes for a hybrid that is fast in the common case and efficient in the contended case. It closes with the design considerations that determine how a lock performs — granularity, contention, and the choice between coarse-grained and fine-grained locking.

Locks are the tool you will use in every concurrent program in the rest of the course. Understanding what they guarantee, what they cost, and how they are implemented is essential to using them well.

02 Learning objectives

This lesson contributes to U6.3 and U6.5, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• OSTEP — Chapter 28, Locks. The complete chapter. OSTEP builds up the lock from the naive spinlock through ticket locks and queue-based locks, and finishes with the futex. This is the single most important reading for this lesson.
• Operating System Concepts — Chapter 6, Section 6.5, Mutex Locks. The standard treatment of the mutex and the spinlock.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3.3, Mutual Exclusion with Busy Waiting and Sleep and Wakeup. The historical development of spinlocks and blocking locks.
• Silberschatz et al. — Chapter 6, Sections 6.5–6.7, Mutex Locks, Semaphores, and Monitors. Read section 6.5 for the lock itself; the later sections preview the next lessons.
• Linux man pages: man 7 pthreads, man 3 pthread_mutex_init, man 3 pthread_mutex_lock, man 3 pthread_mutex_unlock, man 3 pthread_mutexattr_settype, man 3 pthread_spin_lock, man 2 futex.

04 Core content

4.1 The lock abstraction

A lock (also called a mutex, for mutual exclusion) is an object with two operations:

lock_acquire(L)

Block the caller until it holds the lock L. When the function returns, the caller is the sole holder. If another thread already holds the lock, the caller waits until it is released.

lock_release(L)

Release the lock L. The caller must currently hold the lock. If another thread is waiting, it may acquire the lock as a result of the release.

The programmer uses the lock to protect a critical section:

lock_acquire(&mutex);
/* critical section: access shared state */
counter++;
lock_release(&mutex);

The lock guarantees mutual exclusion: at most one thread holds the lock at any time, so at most one thread is executing the code between the acquire and the release. The programmer is responsible for making sure that every access to the shared state is protected by the same lock — a lock protects a region of code, not a set of variables.

A lock that satisfies only mutual exclusion is correct in the minimal sense, but a usable lock should also satisfy two additional properties:

• Progress. If the lock is free and some thread wants to acquire it, some thread acquires it. A lock that can be "stuck" — no holder, but no acquirer — is deadlocked.
• Bounded waiting. There is a bound on how many times a thread can be overtaken by other threads after it has requested the lock. Without this, a thread can starve while others repeatedly acquire and release.

These are the same three requirements introduced in Lesson 6.2 for the critical-section problem. A lock is simply the packaging of a critical-section solution into a reusable object.

4.2 Spinlocks

The simplest lock implementation is the spinlock: a thread that wants to acquire a held lock repeatedly tests the lock until it becomes free. The implementation uses the test-and-set primitive from Lesson 6.2:

typedef struct {
    atomic_int flag;   /* 0 = free, 1 = held */
} spinlock_t;

void spin_lock(spinlock_t *s) {
    while (atomic_exchange(&s->flag, 1))
        ;   /* spin until the old value was 0 */
}

void spin_unlock(spinlock_t *s) {
    atomic_store(&s->flag, 0);
}

The acquire operation loops until atomic_exchange returns 0, which means the lock was free and the caller has now set it to 1. The release operation stores 0 into the flag. The lock satisfies mutual exclusion because the exchange is atomic: only one thread can observe the flag as 0.

The spinlock is fast when the lock is uncontended: the acquire operation is a single atomic instruction plus a branch, taking tens of nanoseconds. It is also appropriate when the critical section is short, because the waiting thread does not pay the cost of a context switch. But it has two serious problems when the lock is heavily contended:

• It wastes CPU cycles. A spinning thread is using a processor core to do nothing useful. On a system with more threads than cores, this steals time from threads that could be doing real work.
• It causes cache-line bouncing. The atomic exchange invalidates the cache line holding the lock in every other core, forcing them to re-fetch it on the next iteration. The cache-coherence traffic can dominate the cost of the critical section itself.

A second problem is that the simple spinlock does not satisfy bounded waiting. A thread that is spinning can lose the race to acquire the lock every time it is released, and may starve. In practice the scheduler's preemption of the spinning thread is enough to break the tie on most systems, but there is no formal guarantee.

4.3 Ticket locks

The ticket lock is a small modification that adds bounded waiting. It uses two counters: a next ticket that a thread increments when it arrives, and a now serving counter that the lock advances on each release.

typedef struct {
    atomic_int next_ticket;
    atomic_int now_serving;
} ticket_lock_t;

void ticket_lock(ticket_lock_t *t) {
    int my_ticket = atomic_fetch_add(&t->next_ticket, 1);
    while (atomic_load(&t->now_serving) != my_ticket)
        ;   /* spin until it is my turn */
}

void ticket_unlock(ticket_lock_t *t) {
    atomic_fetch_add(&t->now_serving, 1);
}

When a thread arrives, it takes a ticket by atomically incrementing next_ticket. It then spins until now_serving equals its ticket. On release, the lock increments now_serving, which allows the thread holding the next ticket to proceed.

The ticket lock satisfies bounded waiting: a thread that takes ticket k will acquire the lock after exactly k − now_serving releases, regardless of how many other threads arrive in the meantime. It is fair in the strictest sense — first-come, first-served among waiting threads.

Its disadvantage is that it does not solve the cache-line bouncing problem. Every thread spins on now_serving, and every release invalidates the cache line holding it. On a heavily contended lock, the cache-coherence traffic is still a bottleneck.

4.4 Queue-based locks

A queue-based lock solves the cache-bouncing problem by giving each waiting thread its own memory location to spin on. The waiting threads are kept in a linked list (a queue), and each thread spins on a flag that is specific to its position in the queue. When the holder releases the lock, it sets the flag of the next thread in the queue, and only that thread's cache line is invalidated.

The best-known example is the MCS lock, named after its inventors Mellor-Crummey and Scott. Each thread has its own qnode structure containing a locked flag and a next pointer. The lock itself holds a pointer to the tail of the queue.

The MCS lock satisfies mutual exclusion, progress, and bounded waiting (the queue order is FIFO), and it scales far better than a simple spinlock under contention. Its disadvantage is complexity: each thread must allocate a qnode and pass it to the acquire and release operations, which is awkward for an interface that wants to look like lock(L) and unlock(L). Production locks therefore often use a hybrid: a fast path that spins a few times on a simple flag, falling back to a queue-based path under heavy contention.

4.5 Blocking locks

A blocking lock (or sleeping lock) avoids the wasted cycles of spinning by putting the waiting thread to sleep. When a thread cannot acquire the lock, the operating system moves it from the ready queue to a wait queue associated with the lock, and the scheduler runs some other thread. When the lock is released, the releasing thread wakes up one of the waiters.

The advantage of a blocking lock is that the waiting thread consumes no CPU while it waits. On a system with more threads than cores, this is decisive: a spinning thread is actively preventing other threads from making progress. On a system with fewer threads than cores, spinning may be cheaper, because the context-switch cost is avoided.

The disadvantage is the cost of the context switch. Moving a thread from the ready queue to a wait queue, and later waking it up, involves kernel work: saving and restoring state, managing the wait queue, and invoking the scheduler. On a modern machine this costs on the order of a few microseconds — one to two orders of magnitude more than a single spinlock iteration. For a very short critical section, the context-switch cost dominates, and spinning is faster even under contention.

A well-designed blocking lock uses a two-phase strategy. On acquire, it spins for a short time in user space (a few hundred iterations, say). If the lock is released during this period, the thread acquires it without entering the kernel. If not, the thread blocks, paying the context-switch cost once. This is the design of the Linux futex, described in the next section.

4.6 Futexes

A futex (fast userspace mutex) is a Linux kernel primitive that supports fast user-space locking. The essential idea is that the fast path — acquiring an uncontended lock, or acquiring a lightly contended lock after a short spin — is handled entirely in user space, without any system call. Only when the lock is heavily contended does the thread enter the kernel, and only then does it pay the cost of a context switch.

A futex is a 32-bit integer in user-space memory that the kernel treats specially. The user-space lock implementation looks like this:

typedef struct {
    atomic_int state;   /* 0 = free, 1 = held, 2 = contended */
} futex_lock_t;

void futex_lock(futex_lock_t *f) {
    int c;
    if ((c = atomic_exchange(&f->state, 1)) == 0)
        return;                          /* fast path: got the lock */

    /* slow path: spin a little, then sleep */
    while (atomic_exchange(&f->state, 2) != 0) {
        syscall(SYS_futex, &f->state, FUTEX_WAIT, 2, NULL, NULL, 0);
    }
}

void futex_unlock(futex_lock_t *f) {
    if (atomic_exchange(&f->state, 0) == 2)
        syscall(SYS_futex, &f->state, FUTEX_WAKE, 1, NULL, NULL, 0);
}

The acquire operation first attempts an atomic exchange. If the lock was free (old value 0), the fast path succeeds and the function returns. If the lock was held, the function enters the slow path: it loops, setting the state to 2 (contended) and calling the futex system call to sleep on the futex. The kernel wakes the thread when the futex's value changes.

The release operation uses an atomic exchange to clear the state. If the old state was 2 (contended), it calls the futex system call to wake one of the waiting threads. If the old state was 1 (uncontended), no system call is needed — the lock was released without any contention.

The futex design is a hybrid that combines the best of both worlds. An uncontended lock is acquired and released entirely in user space, with the cost of a couple of atomic instructions. A contended lock falls back to a kernel wait queue, so the waiting thread does not waste CPU cycles. The transition between the two modes is triggered by the value of the futex itself, which is why the kernel can be involved only when needed.

4.7 Lock granularity and contention

The performance of a lock depends not only on its implementation but on how it is used. Two design decisions determine this.

Granularity

The size of the data structure or region of code that a single lock protects. A coarse-grained lock protects a large region — for example, one lock for an entire hash table. A fine-grained lock protects a small region — for example, one lock per bucket in the hash table. Coarse-grained locks are simpler and less error-prone but serialize more of the program; fine-grained locks allow more concurrency but multiply the number of locks to manage and the opportunities for deadlock.

Contention

The rate at which threads attempt to acquire the lock while it is held. A lock with no contention is nearly free — the fast path is a couple of atomic instructions. A lock with high contention becomes a serialization point, and the throughput of the program is bounded by the rate at which the lock can be acquired and released.

The trade-off between coarse-grained and fine-grained locking is one of the central design decisions in concurrent programming. A coarse-grained lock is simple to reason about: everything under the lock is mutually exclusive, and there is no risk of a lock-ordering deadlock as long as there is only one lock. A fine-grained lock allows more threads to make progress in parallel, but it introduces the risk of deadlock (two threads each holding one lock and waiting for the other) and of races that were not present when a single lock protected the whole structure.

The right choice depends on the workload. A data structure that is rarely accessed can use a single coarse-grained lock without any performance cost. A data structure that is accessed by many threads simultaneously benefits from fine-grained locking, provided the contention on the individual locks is low enough to justify the complexity.

Contention is not a fixed property of a lock: it depends on the access pattern of the workload. A hash table with a million buckets and ten threads is unlikely to see any two threads contend for the same bucket, so per-bucket locks are effectively uncontended. A hash table with ten buckets and a million threads will see contention on every bucket. The design of the lock must match the access pattern.

4.8 Read-write locks

A read-write lock (or shared-exclusive lock) is a refinement of the basic lock that distinguishes between readers and writers. Multiple readers can hold the lock simultaneously, because reading does not modify the shared state; a writer must have exclusive access, so no other reader or writer can hold the lock at the same time.

pthread_rwlock_t rw = PTHREAD_RWLOCK_INITIALIZER;

/* Reader */
pthread_rwlock_rdlock(&rw);
/* read shared state */
pthread_rwlock_unlock(&rw);

/* Writer */
pthread_rwlock_wrlock(&rw);
/* modify shared state */
pthread_rwlock_unlock(&rw);

Read-write locks are useful when the access pattern is dominated by reads. A cache, a configuration table, or a routing table is read far more often than it is written, and a regular lock would serialize all the readers unnecessarily. With a read-write lock, the readers proceed in parallel and only the occasional writer blocks them.

They are not a universal improvement. When the access pattern is mixed or write-heavy, the bookkeeping overhead of a read-write lock exceeds the benefit, and a regular mutex is faster. A well-known study by David Butenhof found that read-write locks were slower than plain mutexes in most workloads on the hardware of the time, and the result has been replicated since. The lesson is that the abstraction is not free: it must match the workload to be worthwhile.

4.9 Deadlock and lock ordering

The preceding discussion has assumed that a thread acquires and releases a single lock. In a program with multiple locks, the possibility of deadlock arises. Two threads, T1 and T2, each acquire two locks, L1 and L2, in a different order:

T1: lock(L1); lock(L2); ... unlock(L2); unlock(L1);
T2: lock(L2); lock(L1); ... unlock(L1); unlock(L2);

If T1 acquires L1 and T2 acquires L2 before either attempts to acquire the second lock, both will block forever: T1 is waiting for L2, which T2 holds; T2 is waiting for L1, which T1 holds. Neither can proceed.

The standard prevention technique is a global lock order: all threads acquire locks in the same order, so a cycle can never form. If both T1 and T2 always acquire L1 before L2, the deadlock above cannot occur. This is a simple rule, but it must be applied consistently throughout a program, and violations are easy to introduce accidentally — particularly when locks are acquired in different functions or at different layers of a system.

Deadlock is a large enough topic to have its own unit. Unit 7 covers the four necessary conditions for deadlock, the resource-allocation graph, prevention and avoidance techniques, the Banker's algorithm, and detection and recovery. For this lesson, the relevant point is that locks introduce the possibility of deadlock, and the programmer must manage the risk.

4.10 Common pitfalls

Locks are simple in principle but easy to misuse. The following mistakes appear frequently in practice.

05 Worked example

The following example traces a ticket lock through a contended acquisition, compares its performance to a simple spinlock and a POSIX mutex on the same workload, and shows how the choice of lock affects the throughput of a concurrent counter.

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A lock (or mutex) is an object with two operations: acquire blocks the caller until it holds the lock, and release releases it. A lock protects a critical section by guaranteeing mutual exclusion.
• A usable lock should satisfy three properties: mutual exclusion, progress, and bounded waiting. These are the same requirements as for the critical-section problem in Lesson 6.2.
• A spinlock repeatedly tests the lock until it is free. It is fast when uncontended and appropriate for short critical sections, but it wastes CPU cycles and causes cache-line bouncing under contention.
• A ticket lock adds bounded waiting by issuing tickets to arriving threads and serving them in FIFO order. It is fair but still suffers from cache-line bouncing because all waiters spin on the same counter.
• A queue-based lock (such as MCS) gives each waiting thread its own memory location to spin on. A release invalidates only the next thread's cache line, so the lock scales far better under contention.
• A blocking lock puts waiting threads to sleep, avoiding wasted CPU cycles at the cost of a context switch. It is preferable when the critical section is long or when there are more threads than cores.
• A futex (fast userspace mutex) is a hybrid: the uncontended fast path is handled entirely in user space, and only contended acquisitions enter the kernel. POSIX mutexes are implemented on top of futexes in glibc.
• Lock granularity determines how much of the program is serialized. Coarse-grained locks are simpler and deadlock-free (with a single lock); fine-grained locks allow more concurrency but introduce the risk of deadlock and subtle races.
• A read-write lock allows multiple concurrent readers but only one writer. It is useful for read-dominated workloads but is slower than a plain mutex when the workload is mixed or write-heavy.
• Locks introduce the possibility of deadlock when multiple locks are acquired in different orders. The standard prevention is a global lock order, applied consistently. Unit 7 covers deadlock in detail.
• The fastest lock is the one you do not need. Partitioning the state so that threads do not share it — per-thread counters, replicated data, message passing — often eliminates the need for synchronization entirely and is faster than any lock.

11 References

• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 28. Available online at ostep.org.
• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Sections 6.5–6.7.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.3.3.
• Mellor-Crummey, J. M., & Scott, M. L. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, 1991. The original MCS lock paper.
• Drepper, U. Futexes Are Tricky. Red Hat, 2004. The authoritative discussion of the futex interface and its pitfalls.
• Franke, H., Russell, R., & Kirkwood, M. Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux. Proceedings of the Ottawa Linux Symposium, 2002. The design rationale for futexes.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods. The kernel's own locks — spinlocks, mutexes, reader-writer locks, and RCU.
• Linux man-pages: man 7 pthreads, man 3 pthread_mutex_init, man 3 pthread_mutex_lock, man 3 pthread_mutexattr_settype, man 3 pthread_spin_lock, man 3 pthread_rwlock_init, man 2 futex.
• Butenhof, D. R. Programming with POSIX Threads, Chapter 7. The discussion of mutex and read-write lock performance.