Process Synchronization in Operating Systems

Process synchronization coordinates access to shared resources. Without it, concurrent programs corrupt data and crash. Understanding synchronization is essential for writing correct multi-threaded and multi-process software, from embedded systems to distributed databases.

The Race Condition Problem

Two processes access shared memory simultaneously:

Process A: count = count + 1
Process B: count = count - 1

If both run concurrently:
  A reads count (5)
  B reads count (5)
  A writes 6
  B writes 4  ← WRONG! Should be 5

A race condition occurs when the outcome depends on the order of execution. These bugs are notoriously hard to reproduce because they depend on precise timing. A program that runs correctly thousands of times in testing may fail only under specific scheduling conditions in production.

Critical Section

A region of code that accesses shared resources. Only one process should execute it at a time.

Requirements

Peterson’s Algorithm (Two Processes)

int flag[2] = {0, 0};
int turn = 0;

// Process 0
void process_0() {
    while (1) {
        flag[0] = 1;
        turn = 1;
        while (flag[1] && turn == 1);
        // Critical section
        flag[0] = 0;
    }
---

// Process 1
void process_1() {
    while (1) {
        flag[1] = 1;
        turn = 0;
        while (flag[0] && turn == 0);
        // Critical section
        flag[1] = 0;
    }
---

Semaphores

An integer variable with atomic operations: wait() and signal().

Binary Semaphore (Mutex)

Values: 0 or 1. Used for mutual exclusion.

semaphore mutex = 1;

void process() {
    wait(&mutex);
    // Critical section
    signal(&mutex);
---

Counting Semaphore

Values: 0 to N. Used for resource management.

semaphore resources = 5;

void process() {
    wait(&resources);
    // Use resource
    signal(&resources);
---

Implementation

typedef struct {
    int value;
    struct process *list;
--- semaphore;

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        block();
    }
---

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        wakeup();
    }
---

Mutex vs. Semaphore

Rule: Use mutex for protecting shared data. Use semaphore for resource pools.

Monitors

A high-level synchronization construct that encapsulates shared variables and operations.

public class BoundedBuffer {
    private int[] buffer = new int[100];
    private int count = 0, in = 0, out = 0;

    public synchronized void insert(int item) {
        while (count == 100) {
            wait();
        }
        buffer[in] = item;
        in = (in + 1) % 100;
        count++;
        notifyAll();
    }

    public synchronized int remove() {
        while (count == 0) {
            wait();
        }
        int item = buffer[out];
        out = (out + 1) % 100;
        count--;
        notifyAll();
        return item;
    }
---

Classical Synchronization Problems

Producer-Consumer (Bounded Buffer)

Producer → Buffer (N slots) → Consumer

Problem: Producer must wait if buffer is full. Consumer must wait if buffer is empty.

semaphore empty = N;
semaphore full = 0;
semaphore mutex = 1;

void producer() {
    while (1) {
        produce_item();
        wait(&empty);
        wait(&mutex);
        signal(&mutex);
        signal(&full);
    }
---

void consumer() {
    while (1) {
        wait(&full);
        wait(&mutex);
        signal(&mutex);
        signal(&empty);
        consume_item();
    }
---

Readers-Writers

Multiple readers can read simultaneously, but writers need exclusive access.

First readers-writers problem: No reader is kept waiting (readers preferred).

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

void reader() {
    wait(&mutex);
    read_count++;
    if (read_count == 1) wait(&rw_mutex);
    signal(&mutex);
    // Read
    wait(&mutex);
    read_count--;
    if (read_count == 0) signal(&rw_mutex);
    signal(&mutex);
---

void writer() {
    wait(&rw_mutex);
    // Write
    signal(&rw_mutex);
---

Dining Philosophers

5 philosophers sit at a round table. Each needs two chopsticks to eat.

semaphore chopsticks[5] = {1, 1, 1, 1, 1};

void philosopher(int i) {
    while (1) {
        think();
        wait(&chopsticks[i]);
        wait(&chopsticks[(i+1)%5]);
        eat();
        signal(&chopsticks[i]);
        signal(&chopsticks[(i+1)%5]);
    }
---

Deadlock fix: Pick up both chopsticks atomically, or have odd/even philosophers pick up in different order.

Deadlock

Four Necessary Conditions

Deadlock Prevention

Break one of the four conditions:

• Mutual exclusion: Use shareable resources when possible
• Hold and wait: Require all resources at once
• No preemption: Allow preemption
• Circular wait: Order resources and acquire in order

Banker’s Algorithm (Deadlock Avoidance)

Process declares maximum resources needed. System grants requests only if a safe sequence exists.

Available: [3, 3, 2]

Process  Allocation  Max  Need
P0       [0, 1, 0]  [7, 5, 3]  [7, 4, 3]
P1       [2, 0, 0]  [3, 2, 2]  [1, 2, 2]
P2       [3, 0, 2]  [9, 0, 2]  [6, 0, 0]
P3       [2, 1, 1]  [2, 2, 2]  [0, 1, 1]
P4       [0, 0, 2]  [4, 3, 3]  [4, 3, 1]

Safe sequence: P1 → P3 → P0 → P2 → P4

Hardware Support

Modern CPUs provide atomic instructions:

int test_and_set(int *lock) {
    int old = *lock;
    *lock = 1;
    return old;
---

void acquire(int *lock) {
    while (test_and_set(lock));
---

void release(int *lock) {
    *lock = 0;
---

Spinlocks vs. Blocking Locks

Spinlocks continuously check a condition in a tight loop, wasting CPU cycles but avoiding context switch overhead. Use spinlocks when the critical section is very short and contention is low. Blocking locks yield the CPU, allowing other threads to run, but incur the cost of two context switches per acquire-release cycle. On single-CPU systems, spinlocks are always worse — they waste CPU and the lock can’t be released until the holding thread is rescheduled.

Deadlock Detection and Recovery

Some systems allow deadlocks to occur and recover from them. The OS periodically checks for circular waits using a wait-for graph. When a deadlock is detected, it can recover by terminating one or more processes (killing the lowest-priority or youngest process) or preempting resources. Deadlock detection is used in database systems where deadlocks are expected and recovery is automated.

Concurrent Data Structures

Building thread-safe data structures requires careful synchronization. A lock-free stack using CAS must handle the ABA problem where a pointer changes from A to B and back to A between the CAS read and write. Hazard pointers and epoch-based reclamation solve the memory reclamation problem in lock-free data structures, ensuring that no thread frees memory while another thread holds a reference to it.

Synchronization is the foundation of reliable concurrent software. Get it right or debug forever.

Architecture Decision Records

Architecture Decision Records (ADRs) document significant architectural decisions and their rationale. Each ADR captures: the context (why the decision was needed), the decision (what was chosen), the alternatives considered (what was rejected and why), and the consequences (tradeoffs and implications). ADRs are stored in version control alongside the code, creating a historical record of design evolution. Benefits include: onboarding new team members faster, preventing repeated debates about past decisions, and providing rationale for future architects questioning why things are the way they are. Start an ADR repository with a lightweight template. Write ADRs for significant decisions that affect system architecture, technology choices, or design patterns. Review ADRs as a team before implementation.

Conway’s Law in Practice

Conway’s Law states that organizations design systems that mirror their communication structures. Teams that communicate frequently will produce tightly coupled components. Teams that communicate infrequently will produce loosely coupled components that communicate through well-defined interfaces. Use this law deliberately: align team boundaries with service boundaries (inverse Conway maneuver). If you want microservices, structure your teams around services. If you want a monolith, have one team. The organization chart and the architecture diagram should be congruent.

FAQ

What is a race condition? A race condition occurs when the behavior of a program depends on the relative timing of concurrent operations, and the result is incorrect under certain orderings. Race conditions are the most common concurrency bug and the hardest to reproduce.

What is the difference between a mutex and a semaphore? A mutex provides mutual exclusion with ownership (only the thread that locked it can unlock it). A semaphore is a signaling mechanism for resource management. Mutexes are binary; semaphores can count to any value.

Can deadlocks be prevented entirely? No. Deadlock prevention algorithms eliminate one of the four necessary conditions, but this reduces resource utilization and may not be possible for all systems. Deadlock avoidance (like the Banker’s algorithm) requires advance knowledge of resource needs. Many practical systems use deadlock detection and recovery instead.

What is priority inversion and how do you fix it? Priority inversion occurs when a high-priority task is blocked by a lower-priority task holding a shared resource. Priority inheritance temporarily elevates the lower-priority task’s priority to resolve the inversion.

Deadlocks Guide — Process Scheduling Guide — Memory Management Guide