Threads, Race Conditions, and Locks

A thread is one sequence of execution inside a process. Several threads can work on the same program data, but each needs its own place in the code and its own unfinished function calls.

What is shared and what belongs to a thread

Threads in one process share code, global and static variables, heap objects, open file descriptors, and the process ID. Each thread has its own program counter, registers, stack, and thread ID. A global int total denotes one shared object. An ordinary local int i in the worker function denotes a different object in each call.

A three-thread process has three stacks at different addresses in the same address space. A stack is not a protected compartment: another thread can reach a local variable if it receives its address. That sharing is valid only while the variable exists. A pointer into a function's finished stack frame cannot keep the variable alive. Large local arrays and deep recursion can also exhaust a thread's stack.

Switching between threads

The operating system saves each thread's execution state in a thread control block, or TCB. When it switches from T1 to T2, it saves T1's registers and restores T2's registers. T1's unfinished calculation stays in its saved registers until it runs again.

For threads in the same process, the address space stays the same during the switch. The page tables need not change, which usually makes this switch cheaper than switching between processes. Shared memory also means shared failures: an invalid pointer write can damage another thread's data, and a fault that terminates the process ends every thread.

Why use several threads?

Parallelism means executing at the same instant on different CPU cores. Four independent parts of a computation can approach a fourfold speedup on four cores, if shared work and coordination do not become bottlenecks. Threads also let a program overlap waiting with work: while one waits for a disk read or network reply, another can use the CPU.

Concurrency means that executions make progress over overlapping periods. On one core, the scheduler switches between threads, so they are concurrent without running in parallel. A single core still allows concurrency bugs: a switch can interrupt a shared update between its machine instructions.

Who schedules the threads?

Linux and Windows use a one-to-one model: each ordinary application thread corresponds to a kernel-scheduled thread. Different threads can run on different cores, and a blocking call blocks its calling thread. A many-to-one library schedules several user threads on one kernel thread. Its switches can be cheap, but it cannot run those threads on several cores, and a blocking system call can stop the whole group.

Creating A before B does not promise that A runs first. If A prints "A" and B prints "B", either "AB" or "BA" can appear. Creation order establishes when a thread becomes available to run; the scheduler chooses its execution time.

The POSIX threads interface, or pthreads, starts a C function in another thread. Include <pthread.h> and build with a command such as gcc -pthread -o sum sum.c. The -pthread option supplies the compiler and linker settings for threaded code.

Create a thread with stable arguments

The call pthread_create(&t, NULL, worker, arg) stores a thread ID in t and starts worker(arg). The NULL attribute pointer requests defaults. A worker has the signature void *worker(void *arg): the argument and return value are pointers. A struct lets that one pointer carry several fields.

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

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

The creator prepares two structs, {1, 50, 0} and {51, 100, 0}, and passes a different address to each worker. Keep both structs alive until the workers finish. Each worker accumulates in its own local sum and writes only its own result field.

pthread_create returns 0 on success and an error number on failure. Check that returned number directly; it does not set errno to report the failure. Only a successful creation gives a thread to join.

Join before reading results

After successfully creating both workers, main calls pthread_join(t[0], NULL) and pthread_join(t[1], NULL). A join blocks until its target ends. Successful joining also makes that worker's writes visible to the joining thread. Main can then read 1,275 and 3,775 and add them to obtain 5,050 without a mutex: the workers wrote separate objects, and main waited before reading them.

Starting both threads before joining allows their work to overlap. Creating one worker and immediately joining it before creating the next makes the workers run one after the other.

Here is the driver. It exits on a pthread error, so it never uses an ID from a failed creation:

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

To collect a returned pointer, pass its receiving address: void *answer; pthread_join(t, &answer);. The pointer must refer to storage that outlives the worker, such as allocated heap memory or a creator-owned struct. Returning &local_result from the worker is invalid because its local variable ends when the function returns.

Avoid sharing a changing loop variable

Passing &i to every worker in a creation loop passes one address repeatedly. Workers may read it after the loop has changed it, so several can receive the same apparent ID. Use an array instead: assign ids[i] = i, pass &ids[i], and keep the array alive and unchanged until all joins complete.

End threads and processes deliberately

Returning from main, or calling exit() in any thread, ends the whole process and can cut workers off. Main normally joins workers before returning. Calling pthread_exit() ends only its calling thread; other threads can continue.

A detached thread releases its thread resources automatically when it ends and cannot be joined. Arrange for each joinable thread to be joined once or detached. Joining waits for completion; it does not protect two workers that update the same object while both are running.

The statement counter++ looks small, but an ordinary shared integer increment is not an indivisible operation. It usually loads a value, adds in a register, and stores the result. Another thread can run between those steps.

A trace that loses one increment

Start with counter equal to 50. Treat load, add, and store as separate machine steps:

Two increments should have produced 52. T1 instead overwrites T2's result with a value computed from the older 50. This is a lost update.

A context switch preserves T1's registers in its TCB. When T1 resumes, its register still holds 51; it does not reload the shared counter simply because T2 ran. The error lies in the unprotected sequence, not in the scheduler restoring a wrong register.

Compare with a serial execution

If T1 completes all three steps before T2 loads, T1 stores 51 and T2 then stores 52. Reversing the whole-thread order also gives 52. The interleaved result 51 cannot arise from either serial order. To find this kind of failure, mark a read, place another thread's write after it, and resume the first thread's stale computation.

This trace is a machine-level model of the bug. In actual C, unsynchronized conflicting accesses to an ordinary shared integer form a data race, which gives undefined behavior. C does not limit that program to the results of a simple instruction-interleaving model.

Why passing tests is weak evidence

Two threads performing 10,000,000 increments each should produce 20,000,000. Unprotected experimental runs can print different smaller totals, such as 19,345,221 and 19,221,041 in published examples. A good-looking run only means its observed outcome happened to be acceptable.

The vulnerable window may be only a few instructions wide. Different core counts, compiler choices, or system load can expose a schedule that thousands of earlier runs missed. For two threads performing one modeled increment each from zero, the trace model permits 1 or 2. With at least two increments per thread, rare schedules can leave a total as low as 2 even as the number of intended increments grows.

Fix the operation, not its appearance

Declaring the integer volatile does not make its load, addition, and store indivisible and does not synchronize threads. Writing all the work on one line changes nothing. Even an x86 instruction that adds directly to memory needs the appropriate atomic form to coordinate across cores.

Protect the complete read-modify-write with a shared mutex, or use a C11 atomic read-modify-write such as atomic_fetch_add. The same need exists on one core: a timer-driven switch can separate the load from the store even without parallel execution.

A concurrency error can involve one memory access or a whole business rule. Identify both the shared objects and the operation that must appear indivisible to other threads.

Race condition or data race?

A race condition occurs when correctness depends on relative timing. A data race occurs when different threads access the same memory location without synchronization, at least one writes it, and at least one access is non-atomic. C11 and C++11 assign undefined behavior to a data race.

Atomic accesses can avoid a data race while a larger operation still has a race condition. For example, individually protected reads and writes do not keep a decision valid between them. Two threads can each read a sufficient balance, release the lock, and later withdraw using that outdated decision.

Work through a withdrawal

A balance starts at 100. Two threads each request 80. The rule is to accept a withdrawal only when the balance covers it.

1. T1 checks 100 and decides its withdrawal can succeed.
2. T2 also checks 100 and makes the same decision.
3. T1 subtracts 80, leaving 20.
4. T2 acts on its earlier decision and subtracts 80 from 20, leaving −60.

Protecting only the subtraction does not fix that sequence. Protect the check and the subtraction with the same lock, held continuously. Then one thread leaves 20, and the next checks 20 and refuses. A different unprotected schedule can lose a subtraction and leave 20 after both withdrawals were paid, which is also wrong.

Find the critical section

A critical section is the shared-data region that must exclude competing access. A read-modify-write sequence first reads data, computes a new value, and writes it back. A check-then-act sequence decides whether an action is allowed and then performs it. List operations, lazy initialization, and file creation can contain these patterns too.

A lock gives mutual exclusion: at most one participating thread is inside the protected region at a time. An atomic operation appears to other participating threads as one complete operation; they cannot observe a half-finished state. A mutex provides that view only for code that follows the same locking agreement.

Not every object needs a lock. Data accessed by one thread stays private unless its address is shared. Data fully initialized before workers start and only read thereafter can be shared without locking. Judge who can reach an object and whether writes overlap its use, not just where it was declared.

What a correct solution promises

• Mutual exclusion: competing threads cannot enter together.
• Progress: when the section is free and threads want it, choosing an entrant cannot be postponed indefinitely by threads that are not trying to enter.
• Bounded waiting: after a request, a limit exists on how many competing entries can precede it.

C11 atomic_fetch_add(&count, 1) performs one atomic update on an atomic_int. Atomicity is guaranteed even on a platform that implements the operation with an internal library lock. Making two account fields individually atomic still does not turn a transfer between them into one atomic transaction; the relationship between the fields needs protection too.

A mutex is a lock that lets one thread at a time own a protected region. A thread acquires it before touching guarded data and releases it afterward. If another thread holds it, a blocking lock call waits.

Initialize the shared mutex

Use pthread_mutex_t from <pthread.h>. A static mutex can start with pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;. A dynamically created object can initialize its field with pthread_mutex_init(&obj->lock, NULL). Initialization must finish before any thread uses the mutex.

Here is a counter operation using a statically initialized shared mutex. The helper checks pthread return values, which are error numbers directly:

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

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

static void check(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Every concurrent read or update of counter must follow this same rule. A separate function using a different mutex would not coordinate with increment.

What happens while the mutex is held?

T1 locks m, loads the counter, computes, and stores. If T2 calls pthread_mutex_lock(&m) during that interval, it cannot pass the call until it acquires ownership after T1 releases. T1 can still be preempted: a mutex prevents competing entry, not context switches.

For the balance rule, hold the mutex before evaluating balance >= amount. Subtract only if it passes, record success or failure, and then unlock. A balance of 100 with two requests for 80 allows exactly one success and leaves 20.

Choose how to wait

pthread_mutex_trylock(&m) returns immediately: 0 means the caller acquired the mutex; EBUSY means it did not because the mutex was held. The busy path can do other work and must not access the guarded data. pthread_mutex_timedlock waits until an absolute deadline. These interfaces still require checking return codes and releasing a lock only after a successful acquisition.

Respect ownership and lifetime

The owning thread releases a mutex. A normal nonrecursive mutex blocks if its owner tries to lock it again. An error-checking mutex reports mistakes such as relocking with EDEADLK or a non-owner unlock with EPERM. A recursive mutex counts repeated acquisitions by its owner and requires the same number of releases. Do not depend on a default mutex to diagnose misuse: its behavior depends on the implementation's mapped type and the operation.

When all threads have stopped using the mutex and it is unlocked, call pthread_mutex_destroy. Destroying or freeing an object while another thread can still lock it breaks the mutex's lifetime. Passing the mutex by pointer preserves its identity; copying it does not create another valid handle to the same lock.

Lock granularity is the amount of shared state covered by one lock. It determines which operations must wait for one another, even when they run on different cores.

One large lock or several smaller locks?

A coarse-grained design puts one mutex around a whole structure or subsystem. It has a simple protection rule, but unrelated operations serialize. A fine-grained design assigns separate mutexes to separate accounts, buckets, or regions. Threads can then work in different regions at once, at the cost of more lock operations and more complicated rules.

Put the guard beside the state it protects:

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

An operation on one account takes its mutex. A transfer between two distinct accounts needs both because it changes their relationship. Choose a fixed order, such as increasing account ID, and use it on every path. Otherwise one thread can hold A and wait for B while another holds B and waits for A.

A lock puts a ceiling on throughput

Suppose every operation holds a single global lock for 2 µs. The protected work can complete at most one operation per 2 µs:

Adding cores cannot make two operations hold that same mutex simultaneously. Lock overhead and other work can lower the achieved rate further. The protected duration is therefore a useful limit to calculate before expecting speedup.

Shorten the section without breaking the operation

Prepare private work before acquiring the mutex. For a list insertion, allocate the new node and fill its key first. Acquire the list mutex only when reading the current head and linking the node. Allocation failure then occurs without a held lock.

Slow I/O, printing, or an unknown callback can keep every waiter stalled. Move such work outside when the data can remain valid there. Keep a decision and its dependent update together: shortening a withdrawal by unlocking between its balance check and subtraction destroys correctness.

Evaluate three different properties

Mutual exclusion asks whether the design really prevents conflicting entry. Fairness asks whether a waiting thread eventually gets a turn or can starve. Performance asks what the lock costs with one thread, several threads on one CPU, and threads on several CPUs. A lock can be correct and still unfair or slow.

Contention occurs when threads compete for an already-held lock. Under heavy contention, they also move shared lock and data cache lines between cores. One published counter experiment took about 0.03 s for one thread's million updates but over 5 s for two threads doing a million each; those are measurements of that setup, not universal timings.

For a scaling experiment, keep each thread's work fixed. Ideal scaling lets N threads on N cores do N times the work in the original time. Start with a simple correct structure, measure waiting and total time, and split a lock only where the additional concurrency pays for its added overhead.

A mutex can be implemented perfectly while a program still uses it incorrectly. Review the whole path through a function, including reads, errors, callbacks, and object destruction.

Make every exit release ownership

This function leaks the lock on its failure path:

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

The returning thread may finish, but the mutex stays held. A later caller then waits for a release that will never happen. Use one cleanup path or place an unlock before every return. With checked pthread calls, the structure can be:

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Reviewing one release point is easier than reviewing many scattered ones. The important property is that every successfully acquired lock is released on every ordinary exit.

Follow the protection rule on reads too

A status function that "only reads" can race with an updater. It can also observe related fields at different stages of one update. If a list operation publishes a node before completing its fields, an unprotected reader may follow a pointer into unfinished data. Acquire the documented guard for each access whose correctness depends on it.

Using different mutexes for the same object does not help. If T1 takes lockA and T2 takes lockB, both acquisitions can succeed. A mutex declared as a fresh local inside every worker makes this error easy to miss: each thread locks its own object, so no shared exclusion exists.

Preserve both identity and operation boundaries

A pthread_mutex_t cannot be copied by assignment or by copying its containing struct and then used as a second mutex handle. Using the copy is undefined behavior. Pass a pointer to the original shared mutex.

Also check where releases occur. A function that locks to check a balance, unlocks, and later relocks to subtract has protected individual accesses but left the decision stale. Keep the complete check-then-act sequence under continuous ownership.

Avoid waiting on yourself

Calling unknown code while holding a mutex can unexpectedly reenter the same protected object. With a normal mutex, a second lock call by the owner blocks that owner. An error-checking mutex reports this mistake, while a recursive mutex allows nested ownership and needs matching unlocks. Select a type deliberately; do not use recursion to hide an unclear protection design.

Keep slow I/O and sleeps out of a shared critical section when possible. Before destroying the mutex or freeing its containing object, ensure no thread owns it or may access it again. Initialization, use, and destruction must have a clear order.

Use runtime tools to expose observed failures

ThreadSanitizer, enabled with -fsanitize=thread, and Valgrind's Helgrind can report data races and lock misuse in executions they observe. Combine their reports with a review of shared accesses and possible interleavings. A clean run establishes that the tool found no problem in those executions; an untested path still needs reasoning.

A lock needs a reliable way to choose one owner. An ordinary read followed by an ordinary write leaves a gap in that decision, even if the protected work itself is very short.

Interrupt control has a narrow role

On one CPU, a kernel can briefly disable interrupts around a nonblocking critical section to prevent interrupt-driven preemption there. This relies on staying on the CPU without voluntarily blocking or switching. The kernel uses the technique for short internal operations.

It is not a general application mutex. Interrupt-control instructions are privileged; giving an application unrestricted use would let it monopolize the CPU. Disabling interrupts on one core does not stop other cores from accessing the same data. Long disabled intervals also delay interrupt handling and can lose events on some devices.

Trace the broken flag lock

Consider this C-like pseudocode:

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Start with flag at 0. T1 tests it and leaves the loop, then pauses before the assignment. T2 tests the same 0, sets it to 1, and enters. T1 resumes, sets it to 1, and enters too. Both passed the test before either claimed ownership.

Making the read and write individually atomic would remove a data race on the flag, but it would still leave two separate operations in this protocol. The ownership claim needs an atomic read-modify-write or a more complete synchronization algorithm.

The empty loop is spin-waiting: repeated checking while consuming CPU time. On one CPU, a waiter that spins after preempting the owner cannot make the owner release sooner. It must eventually let the owner run.

Peterson's two-thread solution

Peterson's algorithm coordinates two threads with an interest flag per thread and a shared turn. Thread i performs:

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

It announces interest, gives the other thread priority in a tie, and waits only while the other is interested and has priority. Under sequential consistency, every thread's operations retain program order and all threads observe one common order. In that model, Peterson's algorithm supplies mutual exclusion, progress, and bounded waiting for two threads.

The memory order matters too

Modern processors and compilers may let memory operations become visible in an order different from the source. A store can remain buffered while a later load reads memory. Both threads can then see the other's interest flag as 0 and both enter. Plain shared C integers also introduce C data races.

A valid implementation needs suitable atomic operations and ordering, such as sequentially consistent C11 atomics for the flags and turn. volatile does not provide that synchronization. Practical locks combine an indivisible ownership operation with memory-order guarantees so protected accesses stay on the correct side of acquisition and release.

An atomic read-modify-write combines reading a location and updating it into one indivisible action. It closes the gap that lets two threads pass an ordinary flag test together.

Exchange the flag and inspect its old value

Test-and-set, or atomic exchange, writes a new value and returns the old one. With a flag initially 0, T1 exchanges in 1 and receives 0, so it enters. T2 exchanges in 1 and receives 1, so it waits. Until release writes 0, no other exchange can return 0.

Here is a C11 spin lock using the default sequentially consistent atomic operations:

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

The ordering matters as well as the flag. Acquisition must keep subsequent critical-section accesses after the successful acquire; release must keep earlier critical-section accesses before the release. Clearing the flag must also be atomic; mixing ordinary stores with atomic accesses does not implement this handoff.

Compare before replacing

Compare-and-swap, or CAS, changes a value only when it equals an expected value. Suppose two threads read a counter at 7 and each wants to add 1. T2 successfully changes 7 to 8. T1's attempt to change 7 to 8 now fails, so T1 retries from 8 and changes it to 9. Retrying preserves both increments.

C11 atomic_compare_exchange_strong returns success or failure and updates the expected argument on failure. Some hardware-style pseudocode instead returns the old stored value. Check which convention a trace uses. On x86, memory xchg implements exchange, while lock cmpxchg supplies atomic compare-and-exchange.

Other hardware building blocks

Load-linked/store-conditional, or LL/SC, reads while establishing a reservation and then attempts a write. The conditional write fails if another write invalidated the reservation; it can also fail for other reasons, so it belongs in a retry loop. ARM's LDXR/STXR and RISC-V's lr/sc support this pattern.

Fetch-and-add adds atomically and returns the old value. C11 exposes it as atomic_fetch_add; x86 provides lock xadd. Returning the old value makes it useful for handing out unique ticket numbers.

C guarantees the atomic behavior of its atomic library operations. It does not require every atomic type to be lock-free; some operations use an internal library lock. atomic_flag has the lock-free guarantee, and atomic_is_lock_free checks other objects.

Correct does not mean fair or fast

A test-and-set lock gives mutual exclusion, but no arrival order: a thread can repeatedly lose the race after release and starve. On one CPU, four threads with 10 ms round-robin time slices can waste 30 ms spinning in three waiters before the preempted owner runs again. On several cores with a running owner and short sections, a short spin can avoid sleep-and-wake overhead.

A test-and-set lock remembers whether it is held but not who has been waiting. A ticket lock adds an arrival order using an atomic ticket dispenser and a serving counter.

Take a number, then wait for it

Both counters start at 0. Each caller atomically increments ticket and keeps its old value as mine. It enters only when turn equals mine. The owner releases by increasing turn once.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

These default C11 atomic operations supply both atomicity and sequentially consistent ordering. Each caller keeps mine in its own local variable. The shared ticket counter dispenses unique outstanding numbers.

Follow three arrivals

A takes ticket 0 and enters because turn is 0. B takes ticket 1 and waits. C takes ticket 2 and waits. The next unused ticket is now 3, while the current turn is still 0.

When A releases, turn becomes 1, so B enters. C still waits for 2. B's release advances turn to 2 and C enters. A newly arriving thread gets ticket 3 and cannot cut ahead of C.

This distinction matters when tracing: ticket records the next number to hand out; turn records the number being served. Taking a ticket changes only the dispenser. Release advances service.

What fairness guarantees

A caller waits behind the threads with earlier tickets. If every holder eventually releases and the threads ahead can run, later arrivals cannot overtake it. The number of competing critical sections ahead is bounded by the earlier outstanding tickets. This supplies bounded waiting and prevents starvation under those progress conditions.

The guarantee concerns entry order, not elapsed time. A holder that stalls for a long time can make every later caller wait a long time too. A ticket number cannot force the scheduler to run its owner.

Costs that ticket order leaves behind

Every waiter still spins. If the thread whose turn comes next is descheduled, later runnable threads wait even though no thread currently occupies the critical section. This is a scheduling cost of strict order.

Waiters also read one shared turn location. Each release changes the cache line they all watch, producing traffic across cores. Queue-based spin locks reduce that traffic by letting each waiter watch a separate local location; Linux moved from ticket spin locks to queued designs.

Real ticket counters use unsigned arithmetic. Equality checks can work across wrap-around when the number of outstanding tickets stays smaller than the counter's value range. Reusing a number while an earlier equal ticket is still outstanding would destroy uniqueness and exclusion.

A correct lock can waste most of a CPU on waiting. The right waiting strategy depends on whether the owner can run and how long it will hold the lock.

Yielding gives up a turn

A waiter can call yield() after a failed ownership attempt. Yielding moves it from running to ready so the scheduler can select another thread. It is still runnable, so it may soon be selected and fail again. With 100 threads on one CPU, up to 99 waiters can each run and yield before a preempted owner gets another turn. Yielding reduces spinning but supplies no fair entry order.

Blocking removes the waiter from runnable work

A sleeping lock puts an unsuccessful caller on a wait queue. It consumes no CPU while blocked. Unlock wakes a waiter so it can run again. A small internal spin guard can protect the flag and queue; that guard is held only for brief bookkeeping.

Separating "decide to sleep" from "actually sleep" creates a lost wakeup risk:

1. A waiter queues itself and releases the guard.
2. It is paused before calling park().
3. The owner releases and calls unpark() for it.
4. If that wakeup is discarded, the waiter later parks with nobody left to wake it.

Solaris's setpark() announces the intent to sleep. An intervening unpark then makes the later park return immediately. The protocol connects the decision to the actual blocking.

Linux uses an atomic compare-and-block

A futex combines a word in user memory with kernel support for waiting. futex_wait(addr, expected) blocks only if the word still equals the expected value; the check and blocking decision are atomic with respect to operations on that futex word. If an unlock already changed it, the caller does not go to sleep on the stale expectation.

futex_wake(addr, n) wakes up to n waiters. An uncontended lock can acquire and release with user-space atomic instructions, avoiding a system call. Linux's glibc pthread mutexes use futexes for contended waits. A wakeup makes a thread runnable; its locking protocol must still establish ownership before accessing the protected data.

Spin briefly, then sleep

A two-phase lock first spins briefly and then blocks if waiting continues. Spinning can be worthwhile when the owner is running on another core and the expected wait is shorter than sleeping and waking. Blocking is preferable for long waits or when runnable threads outnumber cores. On one CPU, a spinner cannot help a descheduled owner finish.

Scheduling priority can stop progress

In priority inversion, a high-priority thread waits for a mutex held by a low-priority thread while medium-priority work keeps the owner off the CPU. Sleeping the high-priority waiter avoids a spin, but does not remove that scheduling delay.

Priority inheritance temporarily raises the owner's priority to that of its highest-priority waiter, allowing it to finish and release. NASA's Mars Pathfinder experienced resets from priority inversion in 1997; enabling mutex priority inheritance corrected the problem. A high-priority spinner on a strictly priority-scheduled single CPU can be worse: it can prevent the low-priority owner from running at all.

A shared counter is easy to protect with one mutex. Its increment, decrement, and get operations each acquire the same lock, act, and release. It is exact, but all updates pass through one shared place.

Why the exact counter becomes a bottleneck

On several cores, a mutex serializes the counter operations. The cores also transfer ownership of the lock and counter cache lines. Adding workers can increase waiting faster than it increases useful work. Replacing the mutex with atomic_fetch_add removes explicit lock overhead on common processors, but every update still writes the same shared location.

An approximate counter, also called a sloppy counter, spreads updates over local counters and transfers them to a global counter in batches. Its reported global value deliberately omits recent local increments.

Build the local-to-global update

Keep one counter and mutex per core, a global counter with its own mutex, and a threshold S. For each increment:

1. Choose the local slot for this update and acquire its mutex.
2. Add 1 to the local count.
3. If it reaches S, acquire the global mutex while still holding the local one.
4. Add that local count to the global count, reset the local count to 0, and release the global mutex.
5. Release the local mutex.

Keep the chosen slot stable throughout the update. Threads using different slots usually touch different locks, and acquire the global mutex only at a transfer. Reading the global count also follows its locking rule.

Follow a batch transfer

With four cores and S equal to 5, suppose their update totals are 7, 3, 4, and 0. Core 1 transfers 5 on its fifth increment and leaves 2 local increments afterward. The final local counts are 2, 3, 4, and 0. The global count is 5, and the true total is 14: nine increments remain local.

After completed unit-increment updates, each local count lies from 0 through S − 1. With P cores, the global total can lag by at most:

For four cores and S equal to 5, the bound is 16. This bound concerns completed updates and their remaining local counts; do not apply it halfway through a transfer.

Choose the threshold for the job

A smaller threshold improves freshness but requires more global acquisitions. With S equal to 1, every increment transfers globally, adding local-lock overhead without avoiding the global bottleneck. A larger threshold improves update scaling but increases possible lag. In one published experiment, S equal to 1024 let four threads perform four million updates in nearly the time one thread needed for one million.

An exact snapshot must hold all local mutexes in a fixed order and then the global mutex before adding the counts. That ordering agrees with updates taking a local lock before the global lock. The snapshot stops concurrent transfers while it reads; reading each field separately could double-count or miss a transfer.

Approximate counters suit statistics that tolerate delayed visibility. A reference count that determines when memory can be freed needs an exact method: an underestimated count could free an object that is still in use.

A shared linked list needs to preserve both its links and its nodes' lifetimes. One mutex around each operation is a useful first design because every shared traversal and modification follows a single rule.

How two insertions lose a node

Suppose the list begins at A. T1 prepares node X and T2 prepares node Y. Without a shared lock, both can read head == A, assign their new node's next to A, and then store their own node into head. The later head assignment hides the first inserted node. That node becomes unreachable, losing an insertion and leaking its memory.

The protected sequence must include reading the current head, setting the new link, and publishing the new head. A lock only around the final assignment would allow both threads to build links from the same stale head.

Prepare private data before acquiring the lock

A new node remains private until it is linked into the shared list. Allocation and key initialization can happen before acquisition. Using the checked pthread helper from earlier, insertion can be written:

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Allocation failure returns before any mutex is held. The shared section stays small while the check of head and the link update stay together. Thread-safe allocation does not make the list itself thread-safe; its links still need their own protection.

Readers participate in the same rule

A lookup takes the list mutex before reading head and retains it during traversal. This coordinates with insertion and removal. Set a result variable before the loop, update it on a match, and break to one unlock point before returning. A successful early return inside the locked loop would otherwise need its own release.

Under this design, removal holds the same mutex while unlinking a node. Other traversals cannot be in that node because they also need the mutex. Free it only when no other operation can still reach it. If an API lets a caller keep a node pointer after unlocking, that extra use needs its own lifetime agreement; the list lock alone no longer covers it.

Decide whether per-node locks pay off

Hand-over-hand locking, or lock coupling, acquires the next node's lock before releasing the current node's lock. That overlap preserves a protected path as traversal advances. Multiple operations can then occupy different regions of the list.

The extra concurrency has a price: every visited node adds lock and unlock operations, even when no other thread is nearby. A traversal-heavy workload can become slower than the single-mutex version. Locking groups of nodes is a middle ground. Compare the more complicated design with the simple one under the actual workload, including failed lookups and removal paths.

One mutex per structure is a sound starting point, but it can serialize operations that touch different regions. Two useful refinements are a lock per queue end and a lock per hash bucket.

Keep a dummy at the queue head

A two-lock queue starts with one dummy node D and head == tail == D. D holds no current queue item. The first real item, if one exists, is at head->next. A head mutex serializes dequeues; a tail mutex serializes enqueues. One enqueue and one dequeue can therefore proceed together.

Enqueue prepares a new node's value and null next link privately. Under the tail mutex, it publishes that node through the old tail's next field and moves tail to the new node. Dequeue uses the head mutex to read the old dummy's next link. If it is null, it unlocks and reports empty. Otherwise it copies the first real value, moves head to that node, unlocks, and frees the old dummy.

The node that contained the returned value becomes the next dummy. Freeing that node immediately would leave head dangling.

Trace the moving dummy

Start with D. Enqueue 5 creates N5 and links D -> N5, with tail == N5. Enqueue 8 adds N8, producing D -> N5 -> N8. A dequeue returns 5, moves head to N5, and frees D. N5 is now the dummy; only 8 remains a queued value. After another dequeue, N8 becomes the dummy and the queue is empty.

The two ends still share a link

When the queue is empty, enqueue can write the current dummy's next while dequeue reads it under a different mutex. The two mutexes alone do not synchronize those accesses. In C11, declare next as an atomic pointer and publish/load it with appropriate ordering; default sequentially consistent atomic stores and loads suffice. Publishing must make the prepared node value visible before dequeue reads it.

Waiting for an item requires a signaling mechanism in addition to locking.

Hash by key, then lock the bucket

A fixed-size hash table can use a thread-safe list in each bucket, each with its own mutex. With 101 buckets and bucket = key % 101, keys 7 and 50 use different locks. Keys 7 and 108 both map to bucket 7 and must serialize there. Collisions affect contention as well as lookup length.

All accesses to a bucket's list follow that bucket's locking rule, including reads. Resizing changes the bucket mapping and moves entries, so this simple design needs exclusive access across the table during resizing. A bucket mutex alone cannot protect a change that affects every bucket.

Refine only after finding the bottleneck

Begin with a shared-state map: which fields are shared, which mutex or atomic operation protects each, and when nodes become reachable or can be freed. Check every return and allocation-failure path. Reason through interleavings, test under load with a race detector, and measure contention before adding finer locks.