Critical Sections

01 Introduction

Lesson 6.1 established the problem: when two threads share state and at least one of them writes, the outcome can depend on the interleaving chosen by the scheduler. The lost-update and check-then-act examples showed that correct-looking code can produce incorrect results under concurrency, and that the bug is in the failure to make a sequence of operations atomic, not in the operations themselves.

This lesson introduces the abstraction that fixes the problem. A critical section is a region of code that must be executed by at most one thread at a time. The operations within the critical section are still non-atomic at the machine level — the scheduler can still preempt between them — but the synchronization protocol surrounding the critical section ensures that no other thread can be executing a conflicting critical section at the same time. The effect is to make the entire sequence appear atomic to every other thread.

The critical-section abstraction is the foundation of every synchronization mechanism in the rest of the unit. Locks, semaphores, monitors, and condition variables are all, in different ways, tools for identifying and protecting critical sections. Understanding the requirements — mutual exclusion, progress, and bounded waiting — is therefore prerequisite to understanding why those mechanisms are designed as they are, and why some designs that look correct are not.

This lesson covers the structure of a solution to the critical-section problem, the three properties such a solution must have, Peterson's software solution for two processes, the bakery algorithm for n processes, and the hardware primitives — test-and-set and compare-and-swap — that make practical solutions possible. It closes with a discussion of why purely software solutions, while intellectually satisfying, are not used in practice on modern hardware.

02 Learning objectives

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

03 Required reading

• Operating System Concepts — Chapter 6, Sections 6.1–6.3, Background, The Critical-Section Problem, and Peterson's Solution. The formal definitions and the classic two-process solution.
• OSTEP — Chapter 28, Locks, through the section on test-and-set and compare-and-swap. OSTEP's treatment is the clearest available explanation of how hardware primitives enable locks, and it builds up from the failed software attempts to the working primitives.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3, through the subsections on Mutual Exclusion with Busy Waiting and Sleep and Wakeup. The discussion of Dekker's and Peterson's algorithms.
• Silberschatz et al. — Chapter 6, Section 6.4, Synchronization Hardware, and Section 6.5, Mutex Locks. The hardware support for synchronization and the spinlock.
• Linux man pages: man 7 pthreads, man 3 pthread_mutex_init, man 3 pthread_mutex_lock, man 3 pthread_spin_lock. The POSIX interfaces to the mechanisms discussed here.

04 Core content

4.1 The critical-section abstraction

Consider a program in which several threads access a shared data structure. Some of the accesses are safe: a thread that only reads the structure cannot corrupt it, and multiple readers can proceed concurrently. Other accesses are not safe: a thread that modifies the structure, or that makes a decision based on a value in the structure and then acts on that decision, can produce incorrect results if another thread modifies the structure in between.

The unsafe accesses are grouped into critical sections: regions of code that must be executed by at most one thread at a time. The threads that contain critical sections are structured as follows:

do {
    /* entry section: request permission to enter */
    ...
    /* critical section: access shared state */
    ...
    /* exit section: release permission */
    ...
    /* remainder section: do work that does not touch shared state */
    ...
} while (1);

The entry section contains the protocol by which a thread requests permission to enter the critical section. The exit section contains the protocol by which it releases permission. The remainder section contains the code that does not touch shared state and can therefore run concurrently with any other thread.

The critical section itself is unremarkable: it is ordinary code that reads and writes shared state. What makes it critical is the guarantee provided by the entry and exit sections: no other thread will be executing a critical section on the same shared state at the same time. The operations inside the critical section are still not atomic at the machine level, but the protocol makes them appear atomic to every other thread.

4.2 The three requirements

A correct solution to the critical-section problem must satisfy three properties. They are stated here for the general case of n processes, though many of the classical solutions assume n = 2.

Mutual exclusion is the essential property; a solution that violates it does not solve the problem. Progress and bounded waiting are the properties that distinguish a useful solution from one that is correct only in the sense that it never allows two threads into the critical section at once — but may prevent any of them from ever getting in, or may starve one of them indefinitely.

4.3 Peterson's solution

The classical software solution to the two-process critical-section problem is due to Gary Peterson (1981). It uses two shared variables:

int flag[2] = {0, 0};   /* flag[i] = 1 means Pi wants to enter */
int turn = 0;           /* whose turn it is to enter */

Each process i executes the following protocol, where j = 1 − i is the other process:

do {
    flag[i] = 1;                    /* I want to enter */
    turn = j;                       /* but you can go first */
    while (flag[j] && turn == j)    /* wait while it is your turn */
        ;                           /* and you want to enter */
    /* critical section */
    flag[i] = 0;                    /* I am leaving */
    /* remainder section */
} while (1);

The protocol is remarkably compact. Each process announces its intention by setting its flag, then politely offers the turn to the other process, then waits only if the other process also wants to enter and it is the other process's turn.

4.4 Why Peterson's solution works

The correctness of the protocol can be argued informally for each of the three requirements.

Mutual exclusion. Suppose both processes are in their critical sections at the same time. For P0 to be in its critical section, the condition flag[1] && turn == 1 must have been false when P0 last checked it. That means either flag[1] == 0 or turn == 0. But P1 has set flag[1] = 1 before entering, so flag[1] == 0 is impossible while P1 is in its critical section. Therefore turn == 0 when P0 entered. But P1 set turn = 0 before entering, and turn can only have one value. If turn == 0, then P1's wait condition flag[0] && turn == 1 is true (since flag[0] == 1 while P0 is in its critical section), so P1 is still waiting. Contradiction. Hence both cannot be in their critical sections at once.

Progress. Suppose no process is in its critical section and at least one wants to enter. If only one process wants to enter, its wait condition is false (because the other process's flag is 0), and it enters immediately. If both want to enter, both have set their flags to 1, and the value of turn determines which one waits: the process whose turn it is not enters, and the other waits. In either case, at least one process enters, so the decision cannot be postponed indefinitely.

Bounded waiting. Suppose P0 wants to enter and P1 is in its critical section. P0 sets flag[0] = 1 and turn = 1, then waits. When P1 exits, it sets flag[1] = 0. P0's wait condition becomes false, and P0 enters. If P1 tries to re-enter immediately, it sets flag[1] = 1 and turn = 0. Now turn == 0, so P1 waits, and P0 enters. P0 therefore enters after at most one entry by P1 — the bound is one.

4.5 The bakery algorithm

Peterson's solution generalizes to two processes. The classical solution for n processes is Lamport's bakery algorithm (1974). It is modelled on the way customers take numbered tickets at a bakery: each process that wants to enter takes a number, and the process with the smallest number enters first. Ties are broken by process identifier.

int choosing[N] = {0};
int number[N]   = {0};

/* Process i */
choosing[i] = 1;
number[i] = 1 + max(number[0], ..., number[N-1]);
choosing[i] = 0;

for (int j = 0; j < N; j++) {
    while (choosing[j])
        ;
    while (number[j] != 0 &&
           (number[j] < number[i] ||
            (number[j] == number[i] && j < i)))
        ;
}
/* critical section */
number[i] = 0;
/* remainder section */

The bakery algorithm satisfies all three requirements, and unlike Peterson's solution it does not assume anything about the relative speeds of the processes. Its cost is that each process must read the numbers of all the others, which is O(n) work per entry. The algorithm is historically important because it was the first correct solution for n processes, but it is not used in practice for the same reasons as Peterson's solution: it assumes sequential consistency, which modern hardware does not provide.

4.6 The limits of software-only solutions

Peterson's solution and the bakery algorithm are correct on a machine that provides sequential consistency: a memory model in which all memory operations appear to execute in program order, and all threads see the same order of operations. Early multiprocessors provided this model, and the algorithms were designed for that setting.

Modern hardware does not provide sequential consistency. Two features of modern processors violate it:

• Compiler reordering. The compiler may reorder independent memory accesses for optimisation. In Peterson's protocol, the compiler is permitted to hoist the read of flag[j] out of the loop, since it does not know that another thread may modify it. The resulting code does not implement the protocol.
• Processor reordering. The processor may execute memory accesses out of order, or in a different order than the program specifies, as long as the result appears correct to a single thread. On a multiprocessor, another core may observe the reordered accesses.

The consequence is that Peterson's solution, as written in plain C without memory barriers or atomic operations, does not work on a modern multi-core machine. It must be implemented with atomic variables and memory fences to prevent the compiler and the processor from reordering the accesses. The fundamental problem is that the solution relies on a memory model the hardware does not provide.

4.7 Hardware support: test-and-set

The hardware primitives that make practical synchronization possible are atomic read-modify-write instructions. These instructions perform a read, a modification, and a write as a single indivisible operation, immune to interruption by the scheduler and to reordering by the processor.

The simplest of these is test-and-set. It takes a pointer to a memory location, returns the old value, and sets the location to 1 — all atomically:

int test_and_set(int *target) {
    int old = *target;
    *target = 1;
    return old;
    /* both operations execute atomically */
}

The instruction is provided by the processor; on x86 it is xchg used with a lock prefix, and on ARM it is ldrex/strex. The C standard library exposes it through the atomic operations in <stdatomic.h>.

Test-and-set can be used to implement a spinlock:

int lock = 0;

void acquire(int *l) {
    while (test_and_set(l))
        ;   /* spin until the lock was free */
}

void release(int *l) {
    *l = 0;
}

The acquire function repeatedly calls test_and_set. If the lock was free (value 0), the function returns 0 and the caller enters the critical section; the lock is now 1. If the lock was held (value 1), the function returns 1 and the caller loops. Because test_and_set is atomic, only one thread can observe the lock as free and proceed.

The spinlock satisfies mutual exclusion, and it satisfies progress in the weak sense that if the lock is free, some thread will acquire it. It does not satisfy bounded waiting: a thread that is spinning may lose the race to acquire the lock every time it is released, and may therefore spin indefinitely. In practice, the fairness of a spinlock depends on the hardware's cache-coherence protocol and the scheduler, and it is not guaranteed.

4.8 Hardware support: compare-and-swap

A more general primitive is compare-and-swap (CAS). It takes a pointer to a memory location, an expected value, and a new value. It compares the current value of the location with the expected value; if they match, it stores the new value; and it returns the old value — all atomically:

int compare_and_swap(int *value, int expected, int new) {
    int old = *value;
    if (old == expected)
        *value = new;
    return old;
}

Compare-and-swap is more powerful than test-and-set because it can be used to implement lock-free data structures. A thread can read a value, compute a new value based on it, and then attempt to install the new value with CAS. If another thread modified the value in the meantime, the CAS fails, and the thread retries with the new value. This is the basis of lock-free stacks, queues, and other concurrent data structures.

The C standard library exposes compare-and-swap as atomic_compare_exchange_weak and atomic_compare_exchange_strong in <stdatomic.h>. The weak form may fail spuriously, so it must be used in a loop; the strong form fails only if the comparison fails.

4.9 Disabling interrupts

A different approach to mutual exclusion, available only in the kernel, is to disable interrupts around the critical section. On a uniprocessor, a thread that disables interrupts cannot be preempted, so no other thread can run until it re-enables them. The critical section is therefore atomic by construction.

This approach is simple and effective on a uniprocessor, and it is used in kernel code where the cost of a lock is too high. But it has serious limitations:

• It does not work on a multiprocessor. Disabling interrupts on one core does not prevent threads on other cores from running. The critical section is protected only against preemption on the local core, not against concurrent access from other cores.
• It is dangerous. A thread that disables interrupts and then fails to re-enable them — because of a bug or an exception — can hang the system. The critical section must be short, and the code must be carefully written to restore the interrupt state.
• It is a privileged operation. User-space code cannot disable interrupts; only kernel code can.

For these reasons, interrupt disabling is used only in specific kernel contexts, and it is usually combined with a lock when the kernel must protect against both local preemption and concurrent access from other cores.

4.10 Critical sections and the race conditions of Lesson 6.1

It is worth connecting this lesson back to the race conditions of Lesson 6.1. The critical-section abstraction addresses the third of the three conditions for a race: non-atomic access. By making a sequence of operations appear atomic to other threads, it removes the possibility that the scheduler's interleaving will produce an incorrect result.

For the counter example, the critical section is the increment:

lock(&l);
counter++;
unlock(&l);

For the check-then-act example, the critical section is the check and the act together:

lock(&l);
if (a->balance >= amount) {
    a->balance -= amount;
    result = 1;
} else {
    result = 0;
}
unlock(&l);

In both cases, the operations inside the critical section are the same operations as before. What has changed is that the entry and exit sections now guarantee that no other thread can execute a conflicting critical section concurrently. The critical section abstraction therefore addresses the race condition without requiring the programmer to reason about individual interleavings.

4.11 Common misconceptions

05 Worked example

The following example traces Peterson's solution through an interleaving that exercises the protocol's logic, and implements a spinlock using test-and-set.

#include <stdatomic.h>
#include <pthread.h>
#include <stdio.h>

typedef struct {
    atomic_int locked;
} spinlock_t;

void spin_lock(spinlock_t *s) {
    while (atomic_exchange(&s->locked, 1))
        ;   /* spin until we observe 0 */
}

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

/* Usage */
spinlock_t lock = { 0 };
int counter = 0;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        spin_lock(&lock);
        counter++;
        spin_unlock(&lock);
    }
    return NULL;
}

06 Interactive activity

07 Knowledge check

do {
    flag[i] = 1;                    /* I want to enter */
    turn = j;                       /* but you can go first */
    while (flag[j] && turn == j)
        ;
    /* critical section */
    flag[i] = 0;
    /* remainder section */
} while (1);

int test_and_set(int *target) {
    int old = *target;
    *target = 1;
    return old;
}

void acquire(int *l) {
    while (test_and_set(l))
        ;
}

void release(int *l) {
    *l = 0;
}

08 Unit discussion

09 Practice exercise

10 Summary

• A critical section is a region of code that must be executed by at most one thread at a time. The operations inside it are still non-atomic, but the synchronization protocol makes them appear atomic to other threads.
• The structure of a solution is: entry section (request permission), critical section (access shared state), exit section (release permission), and remainder section (work that does not touch shared state).
• A correct solution must satisfy three requirements: mutual exclusion (at most one thread in the critical section), progress (some thread enters if the critical section is free), and bounded waiting (no thread waits indefinitely).
• Peterson's solution is a software solution for two processes. It uses a flag per process and a turn variable, and it satisfies all three requirements on a sequentially consistent machine.
• Lamport's bakery algorithm generalizes the idea to n processes using a ticket-based scheme. It is correct but requires O(n) work per entry.
• Software-only solutions are not used in practice because modern hardware does not provide sequential consistency. Compiler and processor reordering can break the protocols even when the algorithm is correct in principle.
• Test-and-set and compare-and-swap are hardware atomic read-modify-write instructions. They are the primitives from which all practical synchronization is built.
• A spinlock is implemented with test-and-set. It satisfies mutual exclusion but not bounded waiting, and it wastes CPU time when the lock is held for a long period.
• Disabling interrupts provides mutual exclusion on a uniprocessor but is not sufficient on a multiprocessor, and it is a privileged operation.
• The critical-section abstraction addresses the third condition for a race condition from Lesson 6.1 — non-atomic access — by making a sequence of operations appear atomic to other threads.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Sections 6.1–6.5.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 28. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.3.
• Peterson, G. L. Myths About the Mutual Exclusion Problem. Information Processing Letters, 1981. The original paper on Peterson's solution.
• Lamport, L. A New Solution of Dijkstra's Concurrent Programming Problem. Communications of the ACM, 1974. The bakery algorithm.
• Herlihy, M., & Shavit, N. The Art of Multiprocessor Programming, 2nd ed. The definitive treatment of the hardware primitives and their use in lock-free data structures.
• ISO/IEC 9899:2011, Programming Languages — C, Section 7.17 (atomics).
• Linux man-pages: man 7 pthreads, man 3 pthread_mutex_init, man 3 pthread_mutex_lock, man 3 pthread_spin_lock.