Concurrency Bugs

Concurrency Bugs

by | Nov 12, 2025

This lecture explains concurrency bugs in multithreaded programming including deadlocks (where threads wait indefinitely), atomicity bugs caused by race conditions, and order-violation bugs where expected execution order flips. It discusses detection, prevention using locks, condition variables, semaphores, and strategies for avoiding deadlocks such as lock ordering.

Writing correct single-threaded code is hard enough. Add a second thread and a whole category of faults appears that the compiler cannot see, the debugger rarely reproduces, and testing frequently misses. These are concurrency bugs: defects that exist not in what a thread does, but in how two or more threads interleave. This note covers the three families you are expected to know for an operating systems paper, deadlock, atomicity violation and order violation, along with how each is detected and prevented.

Why concurrency bugs are hard to catch

A sequential program has one execution order. A program with n threads has an enormous number of possible interleavings, and the scheduler picks one at runtime based on timing, load and which core happens to be free. Your test run picks a safe interleaving. Production picks the unsafe one.

Three properties follow from this, and they are the reason concurrency bugs earn a chapter of their own:

  • Non-determinism. The same input can produce different results on different runs. A bug that appears once in ten thousand executions still appears daily at scale.
  • Poor reproducibility. Attaching a debugger changes timing, which changes the interleaving, which often makes the bug disappear. This is the classic Heisenbug.
  • Locality is misleading. The code that crashes is often not the code that is wrong. A thread writes a field without a lock; a different thread, in a different file, reads a torn value and fails there.

Deadlock

Deadlock is the state in which a set of threads are each blocked waiting for a resource that another thread in the same set holds. None can proceed, and none will ever be woken, because the event each is waiting for can only be produced by another member of the set.

The textbook shape is two threads acquiring two locks in opposite orders:

Thread 1              Thread 2
lock(A);              lock(B);
lock(B);              lock(A);
// work                // work
unlock(B);            unlock(A);
unlock(A);            unlock(B);

If Thread 1 acquires A and Thread 2 acquires B before either reaches its second acquire, both block permanently. Nothing here is a logic error in the usual sense; each thread on its own is perfectly reasonable.

The four Coffman conditions

Deadlock requires all four of these to hold simultaneously. Break any one and deadlock becomes impossible.

  1. Mutual exclusion. At least one resource is held in a non-shareable mode.
  2. Hold and wait. A thread holding at least one resource is waiting to acquire another.
  3. No preemption. A resource cannot be forcibly taken from the thread holding it; it must be released voluntarily.
  4. Circular wait. A cycle exists in the wait-for graph: T1 waits on a resource held by T2, T2 on one held by T3, and so on back to T1.

Examiners frequently ask you to map a prevention strategy onto the condition it removes, so learn them as pairs rather than as a list.

Atomicity violation

An atomicity violation occurs when a sequence of operations that the programmer assumed would execute as an indivisible unit is interrupted by another thread. No lock ordering is wrong; the problem is that a lock is missing, or that the critical section was drawn too small.

// Thread 1
if (thd->proc_info != NULL) {
    fputs(thd->proc_info, log);   // (A)
}
// Thread 2
thd->proc_info = NULL;            // (B)

Thread 1 checks the pointer, and the check succeeds. Before it dereferences the pointer, Thread 2 runs and sets it to NULL. Thread 1 then dereferences NULL and crashes. The check and the use were meant to be atomic together; nothing enforced that. This pattern, testing a condition and then acting on it without holding a lock across both steps, is often called a check-then-act race, and it is the single most common shape of concurrency bug in real code.

The fix is to widen the critical section so that the check and the use sit inside the same lock acquisition, not to add a second lock.

Order violation

An order violation occurs when the correctness of the program depends on operation A happening before operation B, but nothing in the code enforces that order. Both operations may be individually protected by locks and the bug still occurs, because locks provide mutual exclusion, not sequencing.

// Thread 1
void init() {
    mThread = CreateThread(worker, NULL);
}
// Thread 2 (worker)
void worker() {
    state = mThread->state;   // assumes mThread is already assigned
}

If the worker thread is scheduled before the assignment to mThread completes, it dereferences an uninitialised pointer. The correct tool here is a condition variable or a semaphore, used to make the worker wait until initialisation has genuinely finished. A mutex alone cannot fix an ordering bug.

What the empirical evidence shows

The most cited study on this topic is Lu, Park, Seo and Zhou, Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics (ASPLOS 2008). The authors examined 105 real concurrency bugs drawn from four large open-source applications: MySQL, Apache, Mozilla and OpenOffice.

Two findings are worth remembering:

  • Of the 105 bugs, 74 were non-deadlock bugs and 31 were deadlock bugs. Non-deadlock bugs are more than twice as common, yet deadlock receives most of the teaching time.
  • Within the non-deadlock group, the study classified 51 as atomicity violations and 24 as order violations, with a small number falling into both categories. Between them, these two patterns account for the overwhelming majority of non-deadlock concurrency bugs.

The paper also reports that 97% of the deadlock bugs examined involved at most two resources, which is why the simple two-lock example above is representative rather than a toy case.

Detecting concurrency bugs

Because ordinary testing samples only a handful of interleavings, detection relies on tools that reason about interleavings directly.

  • Dynamic race detectors instrument memory accesses at runtime and flag pairs of unsynchronised accesses to the same location where at least one is a write. The lockset algorithm and happens-before analysis are the two classical approaches; ThreadSanitizer and Helgrind are practical implementations.
  • Static analysis inspects source code for lock-discipline violations without running the program. It scales well and needs no test input, but produces false positives.
  • Deadlock detection at runtime constructs the wait-for graph and searches for a cycle. On detecting one, the system recovers by aborting a thread and rolling back, which is essentially what a database transaction manager does.
  • Stress and fuzz testing with deliberately randomised scheduling increases the chance of hitting a rare interleaving, but never proves absence.

Prevention

Each strategy below works by eliminating one Coffman condition.

  • Lock ordering removes circular wait. Define a total order over all locks in the system, for example by memory address or by a fixed numeric rank, and require every thread to acquire them in that order. This is the most widely used technique in practice because it costs nothing at runtime and can be checked statically.
  • Acquire all locks at once removes hold and wait. A thread takes every lock it will need in a single atomic step, or none. It is correct but reduces concurrency and requires knowing the full lock set in advance.
  • Trylock with backoff removes no preemption. A thread attempts a non-blocking acquire; on failure it releases everything it holds and retries. Watch for livelock, where threads repeatedly release and retry in lockstep, and add randomised backoff to break the symmetry.
  • Lock-free data structures remove mutual exclusion entirely by using atomic primitives such as compare-and-swap. Correct implementations are difficult to write but eliminate the problem at its root.

Deadlock avoidance, as opposed to prevention, uses advance knowledge of maximum resource needs to keep the system in a safe state. Banker’s algorithm is the standard example. It is important for examinations but rarely used in real operating systems, because the required advance knowledge seldom exists.

Quick revision summary

  • Deadlock – threads wait on each other in a cycle. Needs all four Coffman conditions. Prevent by lock ordering.
  • Atomicity violation – a sequence assumed indivisible is interrupted. Fix by widening the critical section.
  • Order violation – a required happens-before relationship is not enforced. Fix with condition variables or semaphores, not mutexes.
  • Non-deadlock bugs outnumber deadlock bugs roughly two to one in real software.
  • Locks give mutual exclusion. Condition variables and semaphores give ordering. Confusing the two is the root of most order violations.