Classic Synchronization Problems
To understand the correct use of synchronization tools, let us examine three classic problems traditionally studied in the operating systems field.
1. Bounded-Buffer Problem
The producer creates data and places it in the buffer, while the consumer takes data from the buffer and uses it. Since the buffer size is finite, the producer must wait when the buffer is full, and the consumer must wait when it is empty.
[Bounded Buffer Structure]
Producer --> [ | | | | ] --> Consumer
0 1 2 3 4
^ ^
out in
Semaphores:
mutex = 1 (mutual exclusion for buffer access)
empty = N (number of empty slots, initial = buffer size)
full = 0 (number of filled slots, initial = 0)
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define BUFFER_SIZE 5
int buffer[BUFFER_SIZE];
int in = 0, out = 0;
sem_t empty; // Number of empty slots
sem_t full; // Number of filled slots
pthread_mutex_t mutex;
void *producer(void *arg) {
int id = *(int *)arg;
for (int i = 0; i < 10; i++) {
int item = rand() % 100;
sem_wait(&empty); // Wait until empty slot available
pthread_mutex_lock(&mutex); // Lock buffer access
// Critical section: add item to buffer
buffer[in] = item;
printf("Producer %d: buffer[%d] = %d produced\n", id, in, item);
in = (in + 1) % BUFFER_SIZE;
pthread_mutex_unlock(&mutex);
sem_post(&full); // Increase filled slot count
usleep(rand() % 500000);
}
return NULL;
}
void *consumer(void *arg) {
int id = *(int *)arg;
for (int i = 0; i < 10; i++) {
sem_wait(&full); // Wait until filled slot available
pthread_mutex_lock(&mutex); // Lock buffer access
// Critical section: remove item from buffer
int item = buffer[out];
printf("Consumer %d: buffer[%d] = %d consumed\n", id, out, item);
out = (out + 1) % BUFFER_SIZE;
pthread_mutex_unlock(&mutex);
sem_post(&empty); // Increase empty slot count
usleep(rand() % 800000);
}
return NULL;
}
int main() {
pthread_mutex_init(&mutex, NULL);
sem_init(&empty, 0, BUFFER_SIZE);
sem_init(&full, 0, 0);
pthread_t prod[2], cons[2];
int ids[] = {0, 1};
for (int i = 0; i < 2; i++) {
pthread_create(&prod[i], NULL, producer, &ids[i]);
pthread_create(&cons[i], NULL, consumer, &ids[i]);
}
for (int i = 0; i < 2; i++) {
pthread_join(prod[i], NULL);
pthread_join(cons[i], NULL);
}
pthread_mutex_destroy(&mutex);
sem_destroy(&empty);
sem_destroy(&full);
return 0;
}
The Semaphore Order Is Not Arbitrary
In the producer code above, sem_wait(&empty) comes before pthread_mutex_lock(&mutex). Swap those two lines and the program still compiles, runs fine for a few seconds, and then quietly stops. Staring at the code will not tell you why. You have to walk the two threads through time, one step at a time.
Here is what the swapped version looks like.
// Wrong order: take the lock first, then wait for an empty slot
void *producer_broken(void *arg) {
for (int i = 0; i < 10; i++) {
int item = rand() % 100;
pthread_mutex_lock(&mutex); // (1) lock first
sem_wait(&empty); // (2) then wait for a slot <-- danger
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
pthread_mutex_unlock(&mutex);
sem_post(&full);
}
return NULL;
}
The buffer holds 5 items, so once the producer fills it, empty reaches 0. From that state, the following happens.
[The interleaving that leads to deadlock]
Time Producer P Consumer C
---- -------------------------------- --------------------------------
t0 (buffer full, empty=0, full=5) (not running yet)
t1 pthread_mutex_lock(&mutex) OK
-> P now holds mutex
t2 sem_wait(&empty) called
empty is 0, so it blocks
-> P sleeps WHILE HOLDING mutex
t3 sem_wait(&full) OK (full=5)
t4 pthread_mutex_lock(&mutex)
P holds it, so it blocks
t5 P waits for C to call C waits for P to release
sem_post(&empty) mutex
---- -------------------------------- --------------------------------
Result: neither thread ever wakes up = deadlock
The critical moment is t2. The producer fell asleep still holding the lock. The consumer is the only thread that can drain the buffer, but draining requires the lock, and the lock is held by the producer who is waiting for the consumer to drain. Each thread's progress is now conditional on the other's, which is exactly a circular wait.
The original order breaks the cycle for a simple reason. With sem_wait(&empty) first, the producer goes to sleep before it takes the lock. While it sleeps, nobody owns the lock, so the consumer can walk in at any time, drain the buffer, and wake the producer with sem_post(&empty). As a rule: any wait that can block for a long time goes outside the lock, and you never wait indefinitely while holding a lock.
The trailing pthread_mutex_unlock(&mutex) and sem_post(&full), by contrast, can be swapped without causing deadlock, because neither operation blocks. Doing sem_post first only means the woken consumer immediately bounces off the lock, costing one extra context switch. That is a performance issue, not a correctness one.
2. Readers-Writers Problem
When multiple processes share a database, processes that only read (readers) can access concurrently without issues, but writing processes (writers) need exclusive access.
[Readers-Writers Rules]
Reader + Reader = Allowed (concurrent reads OK)
Reader + Writer = Not Allowed (conflict)
Writer + Writer = Not Allowed (conflict)
First Variation: Reader Priority
Writers wait while readers are present. If readers keep arriving, writers may starve.
#include <pthread.h>
#include <stdio.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t rw_mutex = PTHREAD_MUTEX_INITIALIZER;
int read_count = 0;
int shared_data = 0;
void *reader(void *arg) {
int id = *(int *)arg;
pthread_mutex_lock(&mutex);
read_count++;
if (read_count == 1) {
// First reader blocks writers
pthread_mutex_lock(&rw_mutex);
}
pthread_mutex_unlock(&mutex);
// Critical section: read
printf("Reader %d: data read = %d (current readers: %d)\n",
id, shared_data, read_count);
pthread_mutex_lock(&mutex);
read_count--;
if (read_count == 0) {
// Last reader unblocks writers
pthread_mutex_unlock(&rw_mutex);
}
pthread_mutex_unlock(&mutex);
return NULL;
}
void *writer(void *arg) {
int id = *(int *)arg;
pthread_mutex_lock(&rw_mutex); // Exclusive access
// Critical section: write
shared_data++;
printf("Writer %d: data updated = %d\n", id, shared_data);
pthread_mutex_unlock(&rw_mutex);
return NULL;
}
Tracing Writer Starvation Concretely
It is often said that the first variation starves writers, but the exact condition under which it starves is rarely spelled out. Following how read_count moves makes the condition obvious.
[The flow in which the writer waits forever]
Step Event read_count rw_mutex holder
---- -------------------------------- ---------- ---------------
1 R1 enters: read_count 0 -> 1 1 R1 locked it
2 W arrives: requests rw_mutex 1 R1 (W blocks)
3 R2 arrives: read_count 1 -> 2 2 R1
not the first, so it never touches rw_mutex and walks straight in
4 R3 arrives: read_count 2 -> 3 3 R1
5 R1 leaves: read_count 3 -> 2 2 R1
not zero, so no unlock happens
6 R2 leaves: read_count 2 -> 1 1 R1
7 R4 arrives: read_count 1 -> 2 2 R1
---- -------------------------------- ---------- ---------------
If read_count never touches 0, W waits forever
Stated in one sentence: if new readers keep arriving before the last reader leaves, that is, if the reader arrival interval stays shorter than a reader's time in the critical section, then read_count never hits 0 and the writer waits indefinitely. On a system with many readers or slow reads, this is not a freak coincidence; it happens under normal load.
Note that this is not a deadlock. The system as a whole keeps moving forward and every reader finishes normally. Exactly one participant has stopped: the writer. A deadlock stops everyone involved, whereas starvation stops only some, so if your monitoring only watches throughput you will never see it. It shows up only when you separately measure the maximum or upper-percentile latency on the writer path.
Second Variation: Writer Priority
When a writer is ready, new readers cannot enter. After all existing readers leave, the writer executes.
This variation attacks the condition above head-on. From the moment a writer joins the queue, an extra gate blocks new readers from entering. Then only the readers already inside need to drain, and read_count is guaranteed to reach 0 in finite time. The side effect is symmetric, though: now a steady stream of writers starves the readers. Neither choice is free, and which variation you pick comes down to whether read latency or write latency is more damaging to your service.
Blocking both kinds of starvation requires a third design that preserves arrival order: put all waiters in one queue and wake them in the order they arrived. Some read-write lock libraries let you choose this fairness behavior. Turning fairness on costs throughput, since order must be maintained. Check the default in the documentation for the version you are using.
3. Dining Philosophers Problem
Five philosophers sit at a round table. There is one chopstick between each pair of philosophers, and eating requires two chopsticks.
[Dining Philosophers]
P0
C4 C0
P4 P1
C3 C1
P3
C2
P2
P: Philosopher
C: Chopstick
Philosopher i uses chopstick i and chopstick (i+1)%5
Simple Solution Using Semaphores (Deadlock Risk)
// Warning: This solution can cause deadlock!
sem_t chopstick[5];
void *philosopher(void *arg) {
int id = *(int *)arg;
while (1) {
printf("Philosopher %d: thinking\n", id);
usleep(rand() % 1000000);
// Pick up both chopsticks
sem_wait(&chopstick[id]); // Left
sem_wait(&chopstick[(id + 1) % 5]); // Right
printf("Philosopher %d: eating\n", id);
usleep(rand() % 1000000);
// Put down chopsticks
sem_post(&chopstick[id]);
sem_post(&chopstick[(id + 1) % 5]);
}
}
// Deadlock: If all 5 pick up their left chopstick simultaneously
// no one can get their right chopstick!
Deadlock Prevention Solutions
// Solution 1: Asymmetric - Even philosophers pick left first, odd pick right first
void *philosopher_asymmetric(void *arg) {
int id = *(int *)arg;
while (1) {
printf("Philosopher %d: thinking\n", id);
if (id % 2 == 0) {
sem_wait(&chopstick[id]);
sem_wait(&chopstick[(id + 1) % 5]);
} else {
sem_wait(&chopstick[(id + 1) % 5]);
sem_wait(&chopstick[id]);
}
printf("Philosopher %d: eating\n", id);
usleep(rand() % 1000000);
sem_post(&chopstick[id]);
sem_post(&chopstick[(id + 1) % 5]);
}
}
Monitor-Based Solution
// Monitor-based solution (using Pthreads condition variables)
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
pthread_mutex_t monitor_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t self[N];
// Left and right neighbor indices
#define LEFT(i) ((i + N - 1) % N)
#define RIGHT(i) ((i + 1) % N)
void test(int i) {
// If I'm hungry and neither neighbor is eating, I can eat
if (state[i] == HUNGRY &&
state[LEFT(i)] != EATING &&
state[RIGHT(i)] != EATING) {
state[i] = EATING;
pthread_cond_signal(&self[i]);
}
}
void pickup(int i) {
pthread_mutex_lock(&monitor_mutex);
state[i] = HUNGRY;
printf("Philosopher %d: hungry\n", i);
test(i); // Check if can eat immediately
while (state[i] != EATING) {
pthread_cond_wait(&self[i], &monitor_mutex);
}
printf("Philosopher %d: starts eating\n", i);
pthread_mutex_unlock(&monitor_mutex);
}
void putdown(int i) {
pthread_mutex_lock(&monitor_mutex);
state[i] = THINKING;
printf("Philosopher %d: done eating, starts thinking\n", i);
// Check if neighbors can eat
test(LEFT(i));
test(RIGHT(i));
pthread_mutex_unlock(&monitor_mutex);
}
void *philosopher(void *arg) {
int id = *(int *)arg;
while (1) {
usleep(rand() % 1000000); // Think
pickup(id); // Pick up chopsticks
usleep(rand() % 1000000); // Eat
putdown(id); // Put down chopsticks
}
}
Why the Monitor Solution Cannot Deadlock
The semaphore solution and the monitor solution are roughly the same length, yet only one of them deadlocks. The difference lies in how many chopsticks a philosopher picks up at a time.
In the semaphore version, a philosopher takes the left chopstick with sem_wait(&chopstick[id]) and then calls sem_wait again for the right one. There is a gap between those two calls, and inside that gap the philosopher holds one resource while waiting for another. If all five enter that state simultaneously, the circular wait is complete.
The monitor version has no such gap. pickup takes monitor_mutex, marks state[i] as HUNGRY, and calls test(i). test flips the state to EATING only when neither neighbor is eating. In other words, the philosopher acquires both chopsticks at once or none at all, and that decision is made atomically under the monitor lock. The intermediate state of holding exactly one chopstick simply does not exist.
Of the four conditions for deadlock, hold-and-wait therefore never holds, which makes deadlock structurally impossible. A waiting philosopher holds zero chopsticks, and since pthread_cond_wait also releases monitor_mutex, it does not block a neighbor from entering putdown either.
[What the state array guarantees]
state[] = [THINKING, EATING, HUNGRY, THINKING, HUNGRY]
P0 P1 P2 P3 P4
P2 is waiting because its left neighbor P1 is EATING
-> holds 0 chopsticks. Blocks nobody.
P1 calls putdown():
state[1] = THINKING
test(LEFT(1)=P0) -> P0 is THINKING, condition fails
test(RIGHT(1)=P2) -> P2 is HUNGRY, neither P1 nor P3 is EATING
-> set state[2] = EATING and signal P2
By the time P2 wakes up, "you may eat" is already decided
This solution does not, however, prevent starvation, because test considers no ordering at all. Even if P2 has been waiting a long time, P1 and P3 taking turns eating forever can keep P2's condition false indefinitely. "No deadlock" and "everyone eventually eats" are different guarantees. If you want the latter, you have to record when each philosopher became hungry and put logic favoring the longest waiter directly into test.
POSIX Synchronization
POSIX Mutex
#include <pthread.h>
pthread_mutex_t lock;
// Static initialization
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
// Dynamic initialization
pthread_mutex_init(&lock, NULL);
// Usage
pthread_mutex_lock(&lock);
// Critical section
pthread_mutex_unlock(&lock);
// Non-blocking attempt
if (pthread_mutex_trylock(&lock) == 0) {
// Lock acquired successfully
pthread_mutex_unlock(&lock);
} else {
// Another thread holds the lock
}
// Cleanup
pthread_mutex_destroy(&lock);
POSIX Semaphores
POSIX provides named and unnamed semaphores.
#include <semaphore.h>
// Unnamed semaphore (between threads)
sem_t sem;
sem_init(&sem, 0, 1); // 0: between threads, initial value 1
sem_wait(&sem);
sem_post(&sem);
sem_destroy(&sem);
// Named semaphore (between processes)
sem_t *sem = sem_open("/my_sem", O_CREAT, 0644, 1);
sem_wait(sem);
sem_post(sem);
sem_close(sem);
sem_unlink("/my_sem");
POSIX Condition Variables
#include <pthread.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int data_ready = 0;
// Producer
void *producer(void *arg) {
pthread_mutex_lock(&mutex);
// Generate data
data_ready = 1;
printf("Producer: data ready\n");
pthread_cond_signal(&cond); // Wake up waiting consumer
pthread_mutex_unlock(&mutex);
return NULL;
}
// Consumer
void *consumer(void *arg) {
pthread_mutex_lock(&mutex);
while (!data_ready) {
// Wait until condition is met
// Mutex is automatically released during wait
pthread_cond_wait(&cond, &mutex);
}
printf("Consumer: data consumed\n");
data_ready = 0;
pthread_mutex_unlock(&mutex);
return NULL;
}
Why the Loop Must Be while, Never if
In the consumer code above, pthread_cond_wait sits inside a while, not an if. This is not a matter of style but of correctness, and it is the single most common source of bugs in condition-variable code.
The POSIX standard states two things. First, spurious wakeups can occur: "Spurious wakeups from the pthread_cond_timedwait() or pthread_cond_wait() functions may occur." Second, the return itself tells you nothing about the condition: "the return from pthread_cond_timedwait() or pthread_cond_wait() does not imply anything about the value of this predicate." A return is a hint that someone may have signaled, not a guarantee that the condition you were waiting for is true.
Spurious wakeups are not the only reason. Even when the signal was real, the condition may already be gone by the time you wake.
[Woken up, but the condition is gone]
Waiters A and B are both waiting on data_ready.
1 A: enters pthread_cond_wait, releases mutex, waits
2 B: enters pthread_cond_wait, releases mutex, waits
3 P: acquires mutex, data_ready = 1, cond_broadcast, releases mutex
4 A: wakes up, reacquires mutex
5 A: consumes, sets data_ready = 0, releases mutex
6 B: wakes up, reacquires mutex
7 B: with if, it just falls through -> consumes with data_ready == 0
with while, it rechecks -> false, so it waits again
There is necessarily a gap between steps 4 and 6. pthread_cond_wait must reacquire the mutex before it returns ("Upon successful return, the mutex shall have been locked and shall be owned by the calling thread"), and only one thread can hold a mutex at a time. During that gap the world can change, and if never checks the changed world.
There is also a failure in the opposite direction: the lost wakeup. If you call pthread_cond_signal before making the condition true, and outside the lock, the signal can fire while no waiter has entered the wait yet. Condition variables have no memory, so a signal sent when nobody is waiting simply vanishes. In that case even while does not save you: the first check fails, the thread goes to sleep, and the signal that would have woken it is already gone.
// Dangerous: signaling before setting the condition, and outside the lock
pthread_cond_signal(&cond); // if no one is waiting, this signal is lost
pthread_mutex_lock(&mutex);
data_ready = 1;
pthread_mutex_unlock(&mutex);
// Safe: set the condition under the lock, then signal
pthread_mutex_lock(&mutex);
data_ready = 1; // make the predicate true first
pthread_cond_signal(&cond); // then signal
pthread_mutex_unlock(&mutex);
// The waiting side always uses while
pthread_mutex_lock(&mutex);
while (!data_ready) { // change this to if and all protection above collapses
pthread_cond_wait(&cond, &mutex);
}
data_ready = 0;
pthread_mutex_unlock(&mutex);
What makes this bug nasty is that the symptom is a hang, not a crash. No stack trace, no core dump. The process is alive, CPU usage sits near zero, and the log simply stops. It will not reproduce in tests because the timing never lines up, and then it fires once every few hours in production. It is worth remembering that with condition variables, while is not negotiable.
Java Synchronization
synchronized Keyword
public class Counter {
private int count = 0;
// Method-level synchronization
public synchronized void increment() {
count++;
}
public synchronized int getCount() {
return count;
}
// Block-level synchronization
public void incrementBlock() {
synchronized (this) {
count++;
}
}
}
ReentrantLock
A more flexible locking mechanism than synchronized.
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;
public class BoundedBufferLock {
private final Object[] buffer;
private int count = 0, in = 0, out = 0;
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public BoundedBufferLock(int size) {
buffer = new Object[size];
}
public void produce(Object item) throws InterruptedException {
lock.lock();
try {
while (count == buffer.length) {
notFull.await(); // Wait until buffer has space
}
buffer[in] = item;
in = (in + 1) % buffer.length;
count++;
notEmpty.signal(); // Wake up consumer
} finally {
lock.unlock();
}
}
public Object consume() throws InterruptedException {
lock.lock();
try {
while (count == 0) {
notEmpty.await(); // Wait until data available
}
Object item = buffer[out];
out = (out + 1) % buffer.length;
count--;
notFull.signal(); // Wake up producer
return item;
} finally {
lock.unlock();
}
}
}
Alternative Approaches
Transactional Memory
Applies the database transaction concept to memory access.
// Conceptual code (actual syntax varies by implementation)
atomic {
// All memory operations in this block execute atomically
// Automatically retries on conflict
account1.balance -= amount;
account2.balance += amount;
}
Functional Programming
Using immutable data structures means shared state is never modified, making synchronization unnecessary. Functional languages like Erlang, Scala, and Haskell utilize this approach.
Failure Cases and Pitfalls
Synchronization bugs show up in exactly three shapes. Classify the symptom first and the tool to reach for is decided for you.
Symptom 1: Hung, With CPU Usage Near Zero
Every thread is blocked. Either a deadlock, a lost wakeup, or a wait on a semaphore nobody will ever post. Diagnose in this order.
- Confirm with
toporpsthat the process really is near zero CPU. If it is pinned at 100 percent, go to symptom 2. - Attach a debugger to the running process and dump the call stacks of every thread.
- Find the lock-wait frames in the stacks and pair up which thread is waiting on which lock.
According to the GDB documentation, the syntax for applying a command to all threads is thread apply [thread-id-list | all [-ascending]] [flag]… command, and the thread list comes from info threads.
# find the PID of the hung process and attach
pgrep -a myprogram
gdb -p 12345
Example output.
(gdb) info threads
Id Target Id Frame
* 1 Thread 0x7f2a1c0 (LWP 12345) __lll_lock_wait () at ...
2 Thread 0x7f2a1c1 (LWP 12346) futex_wait (...) at ...
3 Thread 0x7f2a1c2 (LWP 12347) futex_wait (...) at ...
(gdb) thread apply all backtrace
Thread 3 (Thread 0x7f2a1c2):
#0 futex_wait (...)
#1 __new_sem_wait_slow (...)
#2 producer (arg=0x0) at bb.c:22 <-- stuck in sem_wait(&empty)
#3 start_thread (...)
Thread 2 (Thread 0x7f2a1c1):
#0 __lll_lock_wait (...)
#1 pthread_mutex_lock (...)
#2 consumer (arg=0x0) at bb.c:41 <-- waiting on mutex
#3 start_thread (...)
Reading it is simple. __lll_lock_wait or pthread_mutex_lock near the top means the thread is waiting on a mutex; futex_wait sitting under a semaphore or condition-variable function means it is waiting for a signal. The file and line of your own code, usually around frame 2, is the actual culprit. The example above is exactly the deadlock from earlier: the producer waits on empty and the consumer waits on mutex.
Symptom 2: Looks Hung, but CPU Usage Is 100 Percent
This is spinning, not blocking. Either a spinlock is churning, or threads are yielding to each other forever without ever satisfying the condition, which is livelock. Unlike a deadlock, a livelock keeps changing state, so a single stack dump tells you nothing. Dump the stacks several times a few seconds apart and look for threads bouncing around the same span of functions. The cause is usually a retry loop with no cap and no backoff.
Symptom 3: Results Are Occasionally Wrong
Nothing hangs, nothing crashes, but the counter is off once in a while. That means some shared variable is being touched without a lock, and hunting for it by eye is a waste of time. Use a race detector.
The GCC documentation describes -fsanitize=thread as "ThreadSanitizer, a fast data race detector." It instruments memory access instructions to catch data races. The same document notes that the option cannot be combined with -fsanitize=address or -fsanitize=leak, and recommends passing -g as well for more meaningful output. Runtime behavior is controlled through the TSAN_OPTIONS environment variable.
gcc -fsanitize=thread -g -O1 counter.c -o counter -lpthread
./counter
Example output.
WARNING: ThreadSanitizer: data race (pid=4711)
Write of size 4 at 0x55a1c8 by thread T2:
#0 increment counter.c:14 (counter+0x1234)
Previous write of size 4 at 0x55a1c8 by thread T1:
#0 increment counter.c:14 (counter+0x1234)
Location is global 'shared_counter' of size 4 at 0x55a1c8
SUMMARY: ThreadSanitizer: data race counter.c:14 in increment
Read it from the bottom up. The SUMMARY line gives you the file and line, and the two blocks above it are the two accesses that collided. If the same line appears twice, the same code ran concurrently in two threads; if the lines differ, one side is often a read and the other a write.
When recompiling is impractical, use Valgrind's Helgrind. The manual says you select it with --tool=helgrind, and that it catches three classes of error: misuses of the POSIX pthreads API, inconsistent lock orderings, and data races. Lock order checking is governed by --track-lockorders, whose default is yes. How much history of past accesses to collect is set by --history-level, whose default is full.
valgrind --tool=helgrind --track-lockorders=yes ./counter
Example output.
==5123== Possible data race during write of size 4 at 0x60105C by thread #3
==5123== Locks held: none
==5123== at 0x4006B1: increment (counter.c:14)
==5123==
==5123== This conflicts with a previous write of size 4 by thread #2
==5123== Locks held: none
==5123== at 0x4006B1: increment (counter.c:14)
The decisive clue is the "Locks held" line. If it says none, no lock was held at the moment of access, so wrapping that line in a lock is the fix. If the two accesses held different locks, a lock existed but the wrong one was used.
Be aware in advance that all three tools slow the program down substantially. In practice it is far faster to shrink the reproduction scenario to the bare minimum before running them.
When Not to Use This
The three problems in this chapter are teaching material for reasoning about synchronization, not templates to copy. In production code, the cases where you must hand-assemble semaphores are rarer than you would think.
First, there are cases where message passing beats shared memory. If your threads really only hand data off and never need to mutate the same structure concurrently, transferring ownership through a channel or a queue is the better shape. Then the critical section does not exist at all, and both deadlock and data races disappear at design time. The bounded buffer problem above is really an exercise in implementing that queue yourself, and if a proven queue already ships in your standard library there is no reason to write one.
For application code, a concurrent collection from the standard library is usually the right answer. Java's java.util.concurrent package, or the thread-safe queue in whatever language you use, is the already-solved form of this chapter's problems, hardened over years in production. The odds that your hand-rolled bounded buffer beats it are low.
Lock-free data structures are the last resort. Reach for them only after measurement confirms that lock contention is the actual bottleneck. Lock-free code requires an exact understanding of the memory model and memory ordering, and when it is wrong the symptom appears only on certain CPUs under certain loads. Starting down that road because "locks are slow," with no measurement, turns working code into undebuggable code.
It is also always worth asking whether synchronization can be removed entirely. Give each thread its own slice of data and merge once at the end; use immutable structures; run a single-threaded event loop. The fastest critical section is the one that does not exist.
Conversely, there are places where this chapter genuinely applies. Whenever you hand out a fixed number of resources, such as a thread pool, a connection pool, or a rate limiter, a counting semaphore is exactly the right tool. And if you are building an operating system kernel or a language runtime, you have no choice in the matter to begin with.
References
- GCC, Program Instrumentation Options: https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html — verified 2026-08-16
- Valgrind, Helgrind: a thread error detector: https://valgrind.org/docs/manual/hg-manual.html — verified 2026-08-16
- POSIX pthread_cond_wait(3p): https://man7.org/linux/man-pages/man3/pthread_cond_wait.3p.html — verified 2026-08-16
- GDB, Debugging Programs with Multiple Threads: https://sourceware.org/gdb/current/onlinedocs/gdb.html/Threads.html — verified 2026-08-16
Summary
The bounded buffer, readers-writers, and dining philosophers problems are classic examples that illustrate the core challenges of synchronization. POSIX and Java provide various synchronization tools including mutexes, semaphores, and condition variables. Alternative approaches like transactional memory and functional programming are also gaining attention as methods for solving concurrency problems.