Concurrency and Synchronization

Race conditions: why counter++ is not safe

counter++ looks like one operation but the CPU executes three: load the value into a register, add 1, store it back. If two threads A and B each increment a shared counter (initially 0) once, one possible interleaving is:

Two increments, final value 1: a lost update. Of the 20 possible interleavings of these 6 steps, only 2 (A completely before B, or B before A) give the correct 2 — 18 give 1. A race condition is any situation where the result depends on the order of such interleavings.

With k increments per thread, the final value can be anywhere from 2 up to 2k when k ≥ 2 (for k = 1 it is 1 or 2). Surprisingly the minimum is not k: with carefully bad timing, almost all updates of both threads can be lost.

The critical-section problem

A critical section is code that accesses shared data. A correct solution must guarantee:

1. Mutual exclusion — at most one thread in the critical section at a time.
2. Progress — if no thread is in the critical section, a thread that wants to enter will eventually be allowed; threads not interested cannot block it.
3. Bounded waiting — after a thread asks to enter, there is a bound on how many times others can enter before it (no starvation).

Peterson's solution (1981) for two threads, using flag[2] ("I want to enter") and turn ("whose turn to yield"):

// thread i (the other is j = 1 - i)
flag[i] = true;
turn = j;                          // politely give the turn to the other
while (flag[j] && turn == j) { }   // busy-wait while the other wants in and it is its turn
// critical section
flag[i] = false;

If both want to enter at once, the one that wrote turn last waits — mutual exclusion; a thread that is not interested has flag = false — progress; after one entry of the other thread, it is my turn — bounded waiting. (On modern CPUs, which reorder memory operations, Peterson's algorithm needs memory barriers; it is a teaching model, not production code.)

Hardware help: atomic instructions

Modern CPUs provide instructions that read and modify memory atomically (indivisibly):

• Test-and-set: atomically set a flag to true and return its old value.
• Compare-and-swap (CAS): atomically "if the value equals expected, replace it with new; return whether it succeeded".

A spinlock built on CAS:

while (!lock.compareAndSet(false, true)) { /* spin */ }
// critical section
lock.set(false);

Spinning vs. blocking. A spinlock wastes CPU while waiting, but avoids a context switch — good for very short critical sections on multicore machines. A mutex that blocks (puts the waiting thread to sleep) is better when waits may be long. Real kernels spin briefly, then block.

Lock-free programming uses CAS directly: e.g., AtomicInteger.incrementAndGet() retries a CAS until it succeeds — no lock at all.

Semaphores

A semaphore S is an integer with two atomic operations (Dijkstra, 1965):

• wait(S) (also P, acquire): decrement S; if the result is negative, the caller blocks in S's queue.
• signal(S) (also V, release): increment S; if processes are waiting, wake one of them.

With this definition, a negative value −n means n processes are waiting.

• A binary semaphore (initial value 1) works as a lock.
• A counting semaphore (initial value N) controls access to N identical resources — e.g., 4 GPU slots.
• A semaphore with initial value 0 is a signal between threads ("wait until the other thread has done X").

Trace — mutex initialized to 1:

Classic problems

Bounded buffer (producer–consumer). Producers put items into a buffer of size N; consumers take them. Three semaphores:

mutex = 1   // protects the buffer
empty = N   // free slots
full  = 0   // filled slots

producer:  wait(empty); wait(mutex); put(item); signal(mutex); signal(full);
consumer:  wait(full);  wait(mutex); item = take(); signal(mutex); signal(empty);

⚠ Order matters: if a producer did wait(mutex) before wait(empty) and the buffer is full, it would sleep holding the mutex — and no consumer could ever get in: deadlock (Chapter 8).

Readers–writers. Many readers may read shared data at the same time, but a writer needs exclusive access. The simple "readers first" solution can starve writers if readers keep arriving; "writers first" solutions can starve readers. Real systems (database locks, ReentrantReadWriteLock) choose a fairness policy.

Dining philosophers. Five philosophers around a table, one chopstick between each pair; each needs both neighbours' chopsticks to eat. If every philosopher picks up the left chopstick first, all five may hold one and wait forever — deadlock. Solutions: pick up the lower-numbered chopstick first (resource ordering), allow at most four at the table, or pick up both chopsticks atomically. The problem models any system where tasks need several shared resources at once.

Monitors and condition variables

A monitor is a language construct that bundles shared data with the procedures that access it, and guarantees that only one thread is active inside at a time. Condition variables let a thread wait inside the monitor until some condition holds.

In Java, every object is a monitor:

class BoundedBuffer {
    private final Queue<Integer> q = new LinkedList<>();
    private final int capacity = 10;

    public synchronized void put(int x) throws InterruptedException {
        while (q.size() == capacity) wait();      // releases the lock while waiting
        q.add(x);
        notifyAll();
    }

    public synchronized int take() throws InterruptedException {
        while (q.isEmpty()) wait();
        int x = q.remove();
        notifyAll();
        return x;
    }
}

Always wait in a while loop, not an if: after waking up, the condition must be re-checked (another thread may have taken the item first, and spurious wake-ups are allowed).

Java toolbox: synchronized methods/blocks; ReentrantLock (with tryLock and timeouts); AtomicInteger/AtomicLong (lock-free counters); ConcurrentHashMap; ArrayBlockingQueue/LinkedBlockingQueue (ready-made producer–consumer buffers); Semaphore; CountDownLatch. The volatile keyword guarantees that writes by one thread become visible to others (it does not make counter++ atomic).

Message passing

Instead of sharing memory, processes can send messages (pipes, sockets, message queues, actors). There is no shared data to protect, and it works across machines — but copying messages costs time. Both models are used: threads share memory inside a process; microservices and edge–cloud components exchange messages.

Key takeaways

• counter++ = load, add, store; interleavings cause lost updates; with k increments per thread the result lies between 2 and 2k (k ≥ 2).
• Critical-section solutions need mutual exclusion, progress, bounded waiting; Peterson's algorithm achieves them for two threads.
• Atomic test-and-set / CAS build spinlocks and lock-free counters; spin for short waits, block for long ones.
• Semaphores: wait decrements (block if negative), signal increments (wake one); binary = lock, counting = N resources, 0 = signalling.
• Bounded buffer: empty, full, mutex — and the order of waits matters. Readers–writers → starvation choices; dining philosophers → deadlock unless resources are ordered.
• Monitors / condition variables: wait in a while loop. Java: synchronized, locks, atomics, BlockingQueue, volatile (visibility only).
• Shared memory vs. message passing; the same problems exist in distributed systems (transactions, distributed locks, message queues).