Process Synchronization

When two threads (or processes sharing memory) read and write the same data at the same time, the result can depend on the exact order in which their instructions happen to run. Synchronization is the set of techniques that make such code correct regardless of timing: locks, semaphores, condition variables, monitors and atomic hardware instructions.

This is one of the most heavily tested OS topics, because bugs here are real, expensive and hard to reproduce. Interviewers commonly ask you to show a race condition step by step, state the three requirements of a critical-section solution, explain Peterson's algorithm and why it breaks on modern CPUs, compare mutexes, spinlocks and semaphores, explain why condition-variable waits sit in a while loop, and describe priority inversion. All C examples here use POSIX threads and C11 atomics and were compiled and run with gcc -pthread.

A race condition, step by step

A race condition occurs when the correctness of a program depends on the relative timing of threads that access shared data, with at least one of them writing.

Here is the smallest useful example: two threads each increment a shared counter one million times.

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

#define ITERS 1000000

static long counter = 0;

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++)
        counter++;              /* not atomic: load, add, store */
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected %d, got %ld\n", 2 * ITERS, counter);
    return 0;
}

Compiled without optimization, two runs printed:

expected 2000000, got 1007799
expected 2000000, got 1001168

Different wrong answers each time. (With -O2 the compiler may turn the loop into a single counter += 1000000, which hides the bug in this toy but not in real code. A data race like this is formally undefined behavior in C and C++, so no result is guaranteed at all.)

Why it happens

counter++ looks like one operation but the CPU executes it as three:

1. Load: read counter from memory into a register.
2. Add: add 1 to the register.
3. Store: write the register back to memory.

Suppose counter is 5 and threads A and B each run counter++ once. Here is one possible interleaving:

Two increments ran, but counter went from 5 to 6. B's store overwrote A's result: a lost update. Any interleaving in which both threads load before either stores loses one increment. Over two million increments, many are lost.

The shared-memory read-modify-write sequence is the root of most races: incrementing counters, appending to a list, checking a balance and then withdrawing, or "check if the file exists, then create it" (a time-of-check to time-of-use, or TOCTOU, bug).

The critical-section problem

A critical section is a piece of code that accesses shared data and must not be executed by more than one thread at a time. Each thread's code is structured like this:

while (true) {
    entry section       <- ask permission to enter
        critical section    <- touch shared data
    exit section        <- announce you have left
        remainder section   <- everything else
}

The critical-section problem is to design the entry and exit sections. A correct solution must satisfy three requirements:

1. Mutual exclusion: if one thread is executing in its critical section, no other thread can be executing in its critical section.
2. Progress: if no thread is in its critical section and some threads want to enter, only the threads that are trying to enter take part in deciding who goes next, and that decision cannot be postponed forever. In other words, a thread in its remainder section cannot block others, and the system cannot get stuck when the section is free.
3. Bounded waiting: after a thread asks to enter, there is a limit on how many times other threads can enter before it does. No thread waits forever (no starvation).

A fourth, implicit assumption: no assumptions about speed or the number of CPUs. The solution must work whatever the relative speeds of the threads.

Why simple attempts fail

Attempt 1: a shared lock variable.

while (locked) ;   /* wait */
locked = 1;        /* enter */
/* critical section */
locked = 0;

Both threads can see locked == 0, both exit the loop, and both set it to 1 and enter. The check and the set are separate steps, which is the same race we are trying to fix. Mutual exclusion fails.

Attempt 2: strict alternation with a turn variable.

/* thread i, where other = 1 - i */
while (turn != i) ;
/* critical section */
turn = other;

Mutual exclusion holds, but the threads must alternate. If thread 0 wants to enter twice in a row while thread 1 is busy in its long remainder section, thread 0 waits for thread 1 even though the section is free. Progress fails.

Attempt 3: each thread raises a flag first.

flag[i] = 1;
while (flag[other]) ;
/* critical section */
flag[i] = 0;

If both set their flags at the same time, each waits for the other forever. Progress fails (a deadlock).

Peterson's solution combines the flags of attempt 3 with the turn of attempt 2.

Peterson's solution

Peterson's algorithm (1981) is a software-only solution for two threads, numbered 0 and 1, using two shared variables:

• flag[2]: flag[i] is true when thread i wants to enter.
• turn: whose turn it is to yield when both want in.

/* Thread i (other = 1 - i) -- pseudocode */
flag[i] = true;              /* I want to enter            */
turn = other;                /* but I'll let you go first  */
while (flag[other] && turn == other)
    ;                        /* wait                        */
    /* critical section */
flag[i] = false;             /* I'm done                   */

The trick is the politeness in turn = other. If both threads arrive at the same time, both set their flags, and then both write turn. Whichever writes turn last has given way; the other one proceeds.

Why it is correct

• Mutual exclusion: suppose both are inside. Then each one passed its while. Thread 0 passed because flag[1] was false or turn == 0; thread 1 passed because flag[0] was false or turn == 1. Both flags are true while both want in, so each must have seen turn equal to its own number. But turn holds a single value, and whichever thread wrote it last wrote the other thread's number. Contradiction.
• Progress: if thread 1 is not interested, flag[1] is false and thread 0 enters immediately. If both are interested, turn breaks the tie.
• Bounded waiting: when thread 0 leaves, it clears flag[0]. If it immediately tries to re-enter, it sets turn = 1, which lets the waiting thread 1 in. So thread 1 waits for at most one entry by thread 0.

Why it fails on modern CPUs without fences

The proof above assumes sequential consistency: every thread's memory operations happen in program order, and all threads see one global order of operations. Modern hardware and compilers do not guarantee this by default.

On x86, each core has a store buffer: when a core writes to memory, the write goes into a small queue first and reaches the cache a little later, while the core keeps executing. A later load from a different address can complete before the earlier store becomes visible to other cores. That is called store-load reordering, and it is allowed even on x86, which otherwise has a fairly strong memory model (total store order, TSO). ARM and POWER allow even more reordering.

Here is how it breaks Peterson's algorithm:

   Core 0                               Core 1
   flag[0] = true   (in store buffer)   flag[1] = true   (in store buffer)
   turn = 1         (in store buffer)   turn = 0         (in store buffer)
   load flag[1] -> false (old value!)   load flag[0] -> false (old value!)
   enters critical section              enters critical section   <-- BOTH

Each core reads the other's flag before the other's store has left its store buffer. Both see false, and both enter. Compilers can cause the same problem by reordering or caching memory accesses for optimization when the variables are ordinary non-atomic ones.

The fix is a memory fence (or barrier): an instruction that forces earlier stores to become visible before later loads proceed, such as mfence on x86 or dmb on ARM. In C11 or C++11 you get the right fences by using sequentially consistent atomics, which is what the default atomic_load and atomic_store provide:

#include <pthread.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>

#define ITERS 1000000

/* seq_cst atomics (the default) stop the CPU from reordering the store to
   flag[] with the later load of flag[other]. volatile stops the compiler
   from merging or removing any of these accesses. */
static volatile atomic_bool flag[2];
static volatile atomic_int turn;
static long counter = 0;

static void lock(int self) {
    int other = 1 - self;
    atomic_store(&flag[self], true);   /* I want to enter */
    atomic_store(&turn, other);        /* but you go first if you want */
    while (atomic_load(&flag[other]) && atomic_load(&turn) == other)
        ;                              /* busy-wait */
}

static void unlock(int self) {
    atomic_store(&flag[self], false);
}

static void *work(void *arg) {
    int self = *(int *)arg;
    for (int i = 0; i < ITERS; i++) {
        lock(self);
        counter++;
        unlock(self);
    }
    return NULL;
}

int main(void) {
    pthread_t t[2];
    int ids[2] = {0, 1};
    for (int i = 0; i < 2; i++)
        pthread_create(&t[i], NULL, work, &ids[i]);
    for (int i = 0; i < 2; i++)
        pthread_join(t[i], NULL);
    printf("expected %d, got %ld\n", 2 * ITERS, counter);
    return 0;
}

This prints expected 2000000, got 2000000. A note from testing it: without volatile, a recent Clang at -O2 hung. The optimizer is allowed to assume that a thread reading turn right after writing it sees its own value, so it removed the turn check and then the store entirely, which breaks the algorithm. Hand-written synchronization is fragile in exactly this way.

Hardware support for synchronization

Instead of clever software, modern CPUs provide atomic instructions: read-modify-write operations that the hardware guarantees happen as one indivisible step, even with many cores. No other core can see the memory location halfway through.

Test-and-set

Test-and-set (TAS) atomically writes true to a memory location and returns the old value. Its meaning, written as pseudocode (the whole function happens atomically in hardware):

bool test_and_set(bool *target) {   // executed atomically
    bool old = *target;
    *target = true;
    return old;
}

A lock follows directly: keep calling it until the old value was false, meaning you were the one who changed it from free to taken.

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

#define ITERS 1000000

static atomic_flag spin = ATOMIC_FLAG_INIT;
static long counter = 0;

static void spin_lock(void) {
    /* test-and-set: atomically set the flag and return its OLD value */
    while (atomic_flag_test_and_set_explicit(&spin, memory_order_acquire))
        ;                                   /* old value was set: someone holds it */
}

static void spin_unlock(void) {
    atomic_flag_clear_explicit(&spin, memory_order_release);
}

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++) {
        spin_lock();
        counter++;
        spin_unlock();
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected %d, got %ld\n", 2 * ITERS, counter);
    return 0;
}

The memory_order_acquire on locking and memory_order_release on unlocking are the fences: everything written inside the critical section becomes visible to the next thread that acquires the lock. This satisfies mutual exclusion and progress, but not bounded waiting: an unlucky thread can keep losing the race. A ticket lock fixes that by giving each arriving thread a number and serving them in order, like a bakery queue.

Compare-and-swap

Compare-and-swap (CAS) atomically compares a memory location with an expected value and, only if they are equal, replaces it with a new value. It reports whether it succeeded.

bool compare_and_swap(int *target, int expected, int new_value) {  // atomic
    if (*target == expected) {
        *target = new_value;
        return true;
    }
    return false;
}

CAS is more powerful than test-and-set because the update can depend on the old value. The standard pattern is a CAS loop: read the current value, compute a new value, try to swap; if another thread changed the value in between, the CAS fails and you retry with the fresh value.

#include <stdatomic.h>
#include <stdio.h>

/* Lock-free "update maximum": retry until our CAS wins. */
static void atomic_max(atomic_int *target, int value) {
    int current = atomic_load(target);
    while (current < value &&
           !atomic_compare_exchange_weak(target, &current, value))
        ;   /* on failure, current is refreshed with the latest value */
}

int main(void) {
    atomic_int best = 10;
    atomic_max(&best, 7);
    atomic_max(&best, 42);
    printf("%d\n", atomic_load(&best));   /* prints 42 */
    return 0;
}

On x86 CAS is the lock cmpxchg instruction. ARM traditionally used a pair called load-linked/store-conditional (ldxr/stxr), where the store fails if anyone touched the location since the load; newer ARM cores also have a direct CAS instruction. Java exposes CAS through AtomicInteger.compareAndSet, and C++ through std::atomic::compare_exchange_weak and compare_exchange_strong. (The weak version may fail spuriously, which is fine inside a loop.)

Atomic variables

For simple shared counters and flags you rarely need a lock. Atomic types provide single operations that are indivisible:

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

#define ITERS 1000000

static atomic_long counter = 0;

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++)
        atomic_fetch_add(&counter, 1);   /* one indivisible read-modify-write */
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected %d, got %ld\n", 2 * ITERS, atomic_load(&counter));
    return 0;
}

This always prints expected 2000000, got 2000000. The equivalents are AtomicLong.incrementAndGet() in Java and std::atomic<long> in C++. Atomics only make one operation indivisible; if you need to update two variables together (move money from one account to another), you still need a lock or a more elaborate design.

Disabling interrupts

On a single-core machine, the kernel can protect a short critical section by disabling interrupts: no timer interrupt means no preemption, so nothing else runs. This does not work on multi-core machines (other cores keep running), it is a privileged operation unavailable to user programs, and leaving interrupts off for long harms responsiveness. Kernels still use it for very short sections combined with spinlocks.

Mutex, spinlock, semaphore and monitor

These are the tools you actually use. They differ in what a thread does while it waits and in what they can express.

Mutex

A mutex (mutual exclusion lock) has two operations: lock (acquire) and unlock (release). Only one thread can hold it at a time. If a thread tries to lock a mutex that is already held, it is put to sleep (blocked) by the OS and woken when the mutex is released, so a waiting thread uses no CPU.

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

#define ITERS 1000000

static long counter = 0;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++) {
        pthread_mutex_lock(&lock);
        counter++;              /* critical section */
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected %d, got %ld\n", 2 * ITERS, counter);
    return 0;
}

Key properties:

• Ownership: the thread that locked the mutex must be the one to unlock it.
• Modern mutexes are cheap when uncontended. On Linux, pthread_mutex_t is built on a futex (fast user-space mutex): locking a free mutex is a single atomic instruction in user space, and the kernel is involved only when a thread actually has to sleep or be woken.
• Many implementations spin briefly before sleeping (an adaptive mutex), because the holder may release it within nanoseconds.

Spinlock

A spinlock is a lock where a waiting thread busy-waits: it loops, repeatedly checking the lock, as in the test-and-set example above.

• Good when critical sections are very short and threads run on different cores: spinning for 50 nanoseconds is cheaper than two context switches.
• Wasteful when the holder may hold the lock for a long time or may be descheduled: the spinner burns its whole time slice.
• On a single core, spinning is pointless: the holder cannot release the lock while the spinner occupies the only CPU.

Kernels use spinlocks heavily, especially in interrupt handlers, which are not allowed to sleep. User-space code should normally use a mutex.

Semaphore

A semaphore, introduced by Edsger Dijkstra, is an integer counter with two atomic operations:

• wait (also called P, down or acquire): decrement the counter; if the result would be negative (no units available), block until one is.
• signal (also called V, up or release): increment the counter and wake one waiting thread, if any.

A blocking implementation, in pseudocode:

struct semaphore { int value; queue waiting; }

wait(S):                         signal(S):
    S.value = S.value - 1            S.value = S.value + 1
    if S.value < 0:                  if S.value <= 0:
        add this thread to               remove a thread T from
          S.waiting                        S.waiting
        block()                          wakeup(T)

Both operations must themselves be atomic, which the OS ensures with a short internal lock. In this version a negative value means "this many threads are waiting".

There are two kinds:

• Binary semaphore: the value is 0 or 1. It can act like a mutex, but with no owner: any thread can signal it.
• Counting semaphore: the value can be any non-negative number. It represents a pool of identical resources. A semaphore initialized to 5 allows up to 5 threads in at once, for example to limit concurrent database connections.

Semaphores are also used for signaling (ordering) between threads, not just exclusion. To make sure statement S2 in thread B runs after S1 in thread A, start a semaphore at 0:

semaphore done = 0;

Thread A:           Thread B:
    S1;                 wait(done);    // blocks until A signals
    signal(done);       S2;

In POSIX C, unnamed semaphores use sem_init, sem_wait and sem_post (on Linux; macOS supports only named semaphores via sem_open). Java has java.util.concurrent.Semaphore. The classic synchronization problems lesson builds the bounded-buffer and readers-writers solutions with them.

Mutex versus binary semaphore

They look similar but differ in intent and rules:

Ownership is what enables priority inheritance and error checking. That is why the common advice is: use a mutex for locking and a semaphore for counting or signaling.

Monitor

Semaphores are powerful but error-prone: swap a wait and a signal, or forget one, and you get deadlocks or broken exclusion that may show up only under load. A monitor is a higher-level construct that packages shared data together with the procedures that operate on it, and guarantees that only one thread at a time can be active inside the monitor. The compiler or runtime inserts the locking for you.

A monitor also provides condition variables so threads can wait inside it for some condition to become true.

Java's synchronized keyword gives every object a built-in monitor:

public class BoundedCounter {
    private int value = 0;
    private final int max;

    public BoundedCounter(int max) { this.max = max; }

    // Only one thread at a time can run any synchronized method on this object.
    public synchronized void increment() throws InterruptedException {
        while (value == max) {
            wait();          // releases the monitor lock while waiting
        }
        value++;
        notifyAll();         // wake threads waiting for a change
    }

    public synchronized void decrement() throws InterruptedException {
        while (value == 0) {
            wait();
        }
        value--;
        notifyAll();
    }
}

C# has lock and Monitor, and in C or C++ you build the same thing from a mutex plus condition variables.

Condition variables

A condition variable lets a thread sleep until some condition about shared data becomes true, such as "the queue is not empty". It is always used together with a mutex that protects that data. It has three operations:

• wait(cv, mutex): atomically release the mutex and go to sleep; when woken, re-acquire the mutex before returning.
• signal(cv) (pthread_cond_signal, Java notify): wake one waiting thread.
• broadcast(cv) (pthread_cond_broadcast, Java notifyAll): wake all waiting threads.

The "atomically release and sleep" part is essential. If the thread released the mutex and then went to sleep as two separate steps, another thread could change the condition and signal in between, and the wakeup would be lost forever.

A condition variable has no memory: if you signal when nobody is waiting, the signal does nothing. The real state lives in your own shared variable, which is why you always check it.

Here several workers wait until a loader thread has finished loading configuration:

#include <pthread.h>
#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t ready_cv = PTHREAD_COND_INITIALIZER;
static bool ready = false;          /* the condition, protected by m */
static int config_value;

static void *loader(void *arg) {
    (void)arg;
    sleep(1);                       /* pretend to load a config file */
    pthread_mutex_lock(&m);
    config_value = 42;
    ready = true;                   /* change the state under the lock */
    pthread_cond_broadcast(&ready_cv);
    pthread_mutex_unlock(&m);
    return NULL;
}

static void *worker(void *arg) {
    long id = (long)arg;
    pthread_mutex_lock(&m);
    while (!ready)                  /* while, not if: recheck after waking */
        pthread_cond_wait(&ready_cv, &m);
    printf("worker %ld sees config %d\n", id, config_value);
    pthread_mutex_unlock(&m);
    return NULL;
}

int main(void) {
    pthread_t l, w[3];
    for (long i = 0; i < 3; i++)
        pthread_create(&w[i], NULL, worker, (void *)i);
    pthread_create(&l, NULL, loader, NULL);
    for (int i = 0; i < 3; i++)
        pthread_join(w[i], NULL);
    pthread_join(l, NULL);
    return 0;
}

Output (the worker order may vary):

worker 0 sees config 42
worker 1 sees config 42
worker 2 sees config 42

Why while and not if

You must recheck the condition in a loop after waking, for three reasons:

1. Spurious wakeups: POSIX and Java explicitly allow wait to return even though nobody signaled. Implementations do this because it makes them simpler and faster on some systems.
2. Stolen wakeups: between the signal and the moment the woken thread re-acquires the mutex, another thread may grab the mutex and consume the item or reset the condition. By the time you run, the condition may be false again.
3. Broadcasts and shared condition variables: broadcast wakes everyone, but perhaps only one can proceed. And if several different conditions share one condition variable, a wakeup may have been meant for a different condition.

The rule: always wait in a while loop that tests the actual condition.

Mesa versus Hoare semantics

With Hoare semantics (the original monitor proposal), a signal immediately hands the monitor to the woken thread, so the condition is guaranteed true when it runs. With Mesa semantics, which almost every real system uses (pthreads, Java, C#), the signaler keeps running and the woken thread only becomes ready, competing for the lock later. Mesa semantics are the reason the while loop is mandatory.

Memory visibility and volatile

Even with no lost updates, there is a second problem: visibility. When thread A writes a variable, when does thread B see the new value? Without synchronization, possibly late, or never.

• The compiler may keep a variable in a register and never reload it. A loop like while (!stop) {} can legally be compiled into an infinite loop that reads stop once.
• The CPU may reorder memory operations, as with the store buffer in the Peterson example, and other cores may observe writes in a different order than they were made.

A memory model is the set of rules a language or CPU promises about which writes a read can see. The key idea is the happens-before relation: if operation X happens-before operation Y, then Y is guaranteed to see X's effects. Synchronization operations create happens-before edges: unlocking a mutex happens-before the next lock of that mutex; a release store happens-before an acquire load that reads its value; starting a thread happens-before anything it does; a thread's actions happen-before another thread's successful join on it.

What volatile means depends on the language

• Java: a volatile field guarantees visibility and ordering. A write to it happens-before every later read of it, and it prevents reordering around it. It does not make compound operations atomic: count++ on a volatile int is still a race. Use it for flags such as volatile boolean running, and in the corrected double-checked locking pattern.
• C and C++: volatile means "every access must really happen, in program order relative to other volatile accesses", which is meant for memory-mapped hardware registers and signal handlers. It is not a threading tool: it provides no atomicity and no ordering with respect to other, non-volatile memory, and it does not prevent CPU reordering. For threads, use _Atomic/<stdatomic.h> in C11 or std::atomic in C++11. (The Peterson example above uses volatile on top of atomics only to stop the optimizer from merging accesses.)

The idea of lock-free programming

A lock-free algorithm guarantees that, at any time, at least one thread makes progress, even if others are stalled or descheduled. It usually works with CAS loops instead of locks, like the atomic_max example. A classic lock-free stack push:

push(stack, node):
    repeat:
        old_top = stack.top           // read current top
        node.next = old_top
    until CAS(&stack.top, old_top, node)   // succeeds only if top unchanged

There is a hierarchy of progress guarantees:

• Blocking (locks): a thread holding a lock that gets descheduled can stall everyone.
• Lock-free: the system as a whole always makes progress, though one thread might retry for a long time.
• Wait-free: every thread finishes in a bounded number of its own steps. Strongest and hardest to achieve.

Advantages: no deadlocks, no priority inversion, good scalability for simple structures. Disadvantages: hard to get right, and subject to subtle problems:

• The ABA problem: a thread reads value A, gets delayed, another thread changes A to B and back to A, and the first thread's CAS succeeds even though the structure changed underneath it. In the stack above, the old top node may have been popped, freed and reused. Fixes include tagging pointers with a version counter and safe memory reclamation schemes (hazard pointers, epoch-based reclamation); garbage-collected languages like Java avoid the reuse half of the problem.
• Heavy contention on one CAS location can make lock-free code slower than a good lock.

In practice, use well-tested library structures such as Java's ConcurrentLinkedQueue and AtomicInteger rather than writing your own.

Priority inversion

Priority inversion occurs when a high-priority task is forced to wait for a lower-priority task, and a medium-priority task makes that wait unbounded.

The setup needs three tasks: High (H), Medium (M) and Low (L), and one lock shared by H and L.

1. L acquires the lock.
2. H becomes ready, preempts L, and tries to take the lock. It blocks, waiting for L.
3. M becomes ready. It does not need the lock, but it has higher priority than L, so it preempts L.
4. As long as M runs, L cannot run, so L cannot release the lock, so H cannot run. Effectively M, a medium-priority task, is blocking H.

priority
  H  .......[blocked on lock]......................[runs]
  M  ..............[ runs, runs, runs, runs ]......
  L  [lock]--[pre]............................[unlock]
      time ------------------------------------------>

The Mars Pathfinder example

The best-known real case is NASA's Mars Pathfinder lander in 1997, which ran the VxWorks real-time OS. Shortly after landing it began resetting itself repeatedly. Engineers traced it to priority inversion: a low-priority meteorological data task held a mutex protecting a shared information bus; a high-priority bus management task blocked on that mutex; and medium-priority communication tasks kept the low-priority task from running. The high-priority task missed its deadline, a watchdog noticed and reset the system. The mutex had been created with priority inheritance turned off. The team reproduced the problem on a ground replica, and fixed it by uploading a change that enabled priority inheritance on that mutex.

Solutions

• Priority inheritance: while a low-priority task holds a lock that a higher-priority task is waiting for, it temporarily inherits the higher priority. In the example, L runs at H's priority, so M cannot preempt it; L finishes its critical section quickly, releases the lock and drops back to low priority, and H runs. POSIX supports this with the PTHREAD_PRIO_INHERIT mutex protocol; Linux real-time mutexes and most RTOSes use it.
• Priority ceiling protocol: each lock has a ceiling equal to the highest priority of any task that may use it, and a task that acquires the lock immediately runs at that ceiling priority. This also prevents certain deadlocks. POSIX offers it as PTHREAD_PRIO_PROTECT.
• Design: keep critical sections that are shared across priority levels short, or avoid sharing locks across very different priorities.

Interview questions

Q1. What is a race condition? Give an example.

A race condition is when a program's result depends on the timing of threads accessing shared data, with at least one writing. The standard example is two threads doing counter++: each loads the value, adds one and stores it, so if both load 5 before either stores, both store 6 and one increment is lost. The fix is to make the read-modify-write atomic, with a lock or an atomic instruction.

Q2. What are the three requirements for a solution to the critical-section problem?

Mutual exclusion: at most one thread is in its critical section at a time. Progress: if the section is free and threads want to enter, the choice cannot be postponed indefinitely, and threads not trying to enter do not take part. Bounded waiting: there is a limit to how many times others can enter after a thread has requested entry, so no thread starves.

Q3. Explain Peterson's solution.

Each of two threads has a flag saying it wants to enter, and there is a shared turn variable. To enter, a thread sets its flag, sets turn to the other thread, and waits while the other's flag is set and it is the other's turn. If both arrive together, whoever wrote turn last waits, which gives mutual exclusion, progress and bounded waiting for two threads.

Q4. Why does Peterson's algorithm fail on modern hardware?

It assumes sequential consistency, but CPUs reorder memory operations; even x86 lets a load complete before an earlier store to a different address leaves the store buffer. Both threads can read the other's flag as false before either flag write is visible, and both enter. Compilers can also reorder or cache ordinary variables. Memory fences, or sequentially consistent atomics in C11 and C++11, restore correctness.

Q5. What are test-and-set and compare-and-swap?

They are atomic hardware instructions. Test-and-set sets a memory location to true and returns its old value in one indivisible step, which directly gives a spinlock. Compare-and-swap writes a new value only if the location still holds an expected value and reports success, enabling lock-free updates with a read-compute-CAS retry loop.

Q6. What is the difference between a mutex and a semaphore?

A mutex is a lock with an owner: only one thread holds it and only that thread can release it, which allows error checking and priority inheritance. A semaphore is a counter with wait and signal, without ownership: any thread can signal. A counting semaphore can admit N threads at once, and semaphores are also used for signaling events between threads, not just exclusion.

Q7. When should you use a spinlock instead of a mutex?

When critical sections are very short, threads run on separate cores and the expected wait is less than the cost of sleeping and waking, or when the code cannot sleep, such as in a kernel interrupt handler. Spinlocks waste CPU if the holder takes long or gets preempted, and they are useless on a single core. In user space, a mutex is the default choice.

Q8. What is a monitor?

A monitor is a high-level synchronization construct that bundles shared data with the operations on it and guarantees only one thread at a time executes inside. It provides condition variables so threads can wait for conditions inside the monitor. Java's synchronized methods with wait and notifyAll implement a monitor per object.

Q9. Why must you call wait on a condition variable inside a while loop?

Because waking up does not guarantee the condition is true. Implementations may produce spurious wakeups, another thread may grab the lock and change the state between the signal and your re-acquisition of the lock, and a broadcast may wake threads that cannot all proceed. Rechecking in a loop handles all three; this is required under the Mesa semantics used by pthreads and Java.

Q10. Why does pthread_cond_wait take a mutex?

The waiting thread must check the condition and go to sleep without another thread changing the condition in between. pthread_cond_wait atomically releases the mutex and puts the thread to sleep, then re-acquires the mutex before returning. Without that atomicity, a signal could arrive after the check but before the sleep and be lost.

Q11. What does volatile do in Java and in C?

In Java, volatile guarantees that writes are visible to other threads and imposes ordering (happens-before) around the access, but compound operations like ++ are still not atomic. In C and C++, volatile only forces the compiler to perform each access, which is meant for hardware registers and signal handlers; it is not a threading tool. Use atomics or locks for thread communication in C and C++.

Q12. What is the ABA problem?

In a CAS-based algorithm, a thread reads value A, is delayed, and meanwhile other threads change the location to B and back to A. The delayed thread's CAS succeeds because the value matches, even though the data structure changed, for example a node was freed and reused. Version-tagged pointers and safe memory reclamation such as hazard pointers are common fixes.

Q13. What is priority inversion and how is it solved?

A high-priority task waits for a lock held by a low-priority task, while a medium-priority task preempts the low-priority one, so the high-priority task is indirectly blocked by the medium one for an unbounded time. Mars Pathfinder suffered from it in 1997. The standard fixes are priority inheritance, where the lock holder temporarily runs at the waiter's priority, and the priority ceiling protocol.

Q14. What is the difference between lock-free and wait-free?

Lock-free guarantees that some thread always makes progress, so the system never stalls, though an individual thread may retry repeatedly. Wait-free guarantees every thread completes its operation in a bounded number of its own steps. Wait-free is stronger and harder to implement; both avoid deadlock because they use no locks.

Q15. Is disabling interrupts a valid way to implement a critical section?

Only in limited cases: inside the kernel, on a single CPU, for very short sections. It does not stop other cores from running, so it fails on multiprocessors, it is privileged so user programs cannot use it, and keeping interrupts off for long delays I/O and timers. Kernels combine it with spinlocks when interrupt handlers share data with other code.

Key takeaways

• A race condition comes from interleaved read-modify-write sequences on shared data; counter++ is three steps.
• A critical-section solution needs mutual exclusion, progress and bounded waiting, without assumptions about speed.
• Peterson's algorithm is a correct two-thread solution only under sequential consistency; real CPUs reorder stores and loads, so it needs fences or sequentially consistent atomics.
• Hardware atomics (test-and-set, compare-and-swap, fetch-and-add) are the foundation of every real lock and of lock-free code.
• Mutexes sleep and have owners; spinlocks busy-wait for very short sections; semaphores count and signal; monitors bundle data with automatic locking and condition variables.
• Condition-variable waits always go in a while loop because of spurious and stolen wakeups.
• Visibility needs synchronization: Java volatile gives visibility but not atomicity; C volatile is not for threads.
• Priority inversion lets a medium task block a high one; priority inheritance fixes it, as Mars Pathfinder famously showed.

Next lesson

Continue with Classic synchronization problems.