Home/Learn/Operating Systems/Race Condition & Critical Section

Race Condition & Critical Section

Beginner

Synchronization

A race condition occurs when the outcome of concurrent operations depends on the unpredictable interleaving of thread execution, typically when multiple threads access shared mutable state without synchronization.

Overview

A race condition is a bug where two or more threads access shared data concurrently and at least one thread modifies it, and the final result depends on the relative order of execution — which the programmer cannot control. The critical section is the code segment that accesses the shared resource and must execute atomically. Three requirements for correct critical section solutions: mutual exclusion (only one thread in the critical section at a time), progress (if no thread is in the critical section, a thread that wants to enter should be able to), and bounded waiting (a thread waiting to enter will eventually get in — no starvation). Hardware solutions use atomic instructions: test-and-set and compare-and-swap (CAS), which Java exposes through the java.util.concurrent.atomic package.

The Classic Race Condition: Shared Counter

The increment operator (count++) is not atomic in Java. The JVM compiles it to three bytecode instructions: GETFIELD, IADD, PUTFIELD. A thread can be preempted between any two of these instructions, allowing another thread to read the stale value and produce a lost update. This is the textbook race condition.

Java — race condition on shared counter + fix with synchronized and AtomicInteger

// RACE CONDITION — shared counter with two threads
class RaceCounter {
    private int count = 0;

    // NOT thread-safe — count++ is 3 bytecode ops:
    // 1. GETFIELD  (read count into register)
    // 2. ICONST_1 + IADD  (add 1)
    // 3. PUTFIELD  (write back)
    // Thread A can be preempted between steps 1 and 3!
    public void increment() { count++; }
    public int get() { return count; }
}

RaceCounter counter = new RaceCounter();
int THREADS = 100, INCREMENTS_EACH = 1000;

List<Thread> threads = new ArrayList<>();
for (int i = 0; i < THREADS; i++) {
    threads.add(new Thread(() -> {
        for (int j = 0; j < INCREMENTS_EACH; j++) counter.increment();
    }));
}
threads.forEach(Thread::start);
for (Thread t : threads) t.join();

System.out.println("Expected: " + (THREADS * INCREMENTS_EACH));  // 100,000
System.out.println("Actual:   " + counter.get());  // < 100,000 due to race!

// Fix 1: synchronized method — mutex, most readable
synchronized void incrementSafe() { count++; }

// Fix 2: AtomicInteger — lock-free CAS, fastest for single variable
AtomicInteger atomicCount = new AtomicInteger(0);
atomicCount.incrementAndGet();  // atomic compare-and-swap — no race

Peterson's Solution and Hardware Atomics (CAS)

Peterson's solution is a classic software-only mutual exclusion algorithm for two threads using only shared variables: a flag[] array and a turn variable. It satisfies all three requirements (mutual exclusion, progress, bounded waiting) but assumes atomic memory reads/writes — a requirement modern CPU memory models do not guarantee without memory barriers. Hardware solutions are reliable: compare-and-swap (CAS) reads a value, compares it to an expected value, and writes a new value atomically — all in one uninterruptible machine instruction.

Java — CAS-based lock-free increment + LongAdder for high-contention counters

// Compare-and-Swap (CAS) — hardware atomic instruction, basis of all lock-free algorithms
// CAS(addr, expected, newValue): if *addr == expected → *addr = newValue, return true
//                                 else return false (someone else changed it)

AtomicInteger cas = new AtomicInteger(0);

// CAS-based increment (what AtomicInteger.incrementAndGet() does internally)
int oldVal, newVal;
do {
    oldVal = cas.get();           // read current value
    newVal = oldVal + 1;          // compute new value
} while (!cas.compareAndSet(oldVal, newVal));  // retry if someone changed it first
System.out.println("CAS result: " + cas.get());

// AtomicLong for 64-bit counters (common in metrics/counters)
AtomicLong requestCount = new AtomicLong(0);
requestCount.incrementAndGet();     // atomic, non-blocking
requestCount.addAndGet(5);          // atomic add
System.out.println("Requests: " + requestCount.get());

// LongAdder — better throughput under high contention (striped counters)
LongAdder highContention = new LongAdder();
highContention.increment();         // internally uses multiple cells to reduce CAS contention
System.out.println("LongAdder: " + highContention.sum());

Key Points to Remember

1Race condition: outcome depends on thread interleaving — occurs when shared mutable state is accessed without synchronization.
2Critical section requirements: mutual exclusion, progress, bounded waiting.
3Java count++ is not atomic — three bytecode instructions (read, add, write) can be interleaved.
4synchronized provides mutual exclusion using a monitor lock — simple but may cause contention.
5AtomicInteger uses hardware CAS instruction — lock-free, faster for single-variable updates.
6LongAdder uses striped counters for better throughput than AtomicLong under high contention.

Interview Questions

Why is count++ not thread-safe in Java even though it looks like one operation?

EasyAmazon

What are the three requirements for a correct critical section solution?

MediumGoogle

What is compare-and-swap and how does AtomicInteger use it?

MediumMicrosoft

When would you use LongAdder instead of AtomicLong?

MediumNetflix

Ask Aria about Race Condition & Critical Section

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Contiguous Memory Allocation Strategies

Mutex vs Semaphore