OS Notes

Introduction to Process Synchronization

Understanding why process synchronization is needed, race conditions, the critical section problem, and an overview of synchronization mechanisms in operating systems.

Introduction

Imagine two people simultaneously editing the same Google Doc paragraph. Without proper coordination, they might overwrite each other's changes, creating a garbled mess. Now imagine this happening millions of times per second inside your computer — multiple processes or threads accessing shared memory without coordination. The results are unpredictable bugs that appear randomly, making them among the hardest to debug.

Process synchronization is the coordination of concurrent processes to ensure correct and predictable behavior when they access shared resources. It provides mechanisms to prevent race conditions, ensure mutual exclusion, and maintain data consistency.

Why Synchronization is Needed

When multiple processes or threads access shared data concurrently, and at least one of them writes (modifies) the data, the outcome depends on the exact order of execution. This is called a race condition — the result of the computation literally races on which process executes which instruction first.

A Classic Race Condition

Example

// Shared variable int counter = 5; // Thread 1: counter++ register1 = counter; // register1 = 5 register1 = register1 + 1; // register1 = 6 counter = register1; // counter = 6 // Thread 2: counter-- register2 = counter; // register2 = 5 register2 = register2 - 1; // register2 = 4 counter = register2; // counter = 4 // If interleaved: T1 reads (5), T2 reads (5), T1 writes (6), T2 writes (4) // Result: counter = 4 (should be 5 after +1 and -1!)

The problem is that counter++ is not atomic — it involves three machine instructions (load, add, store). If another thread intervenes between these instructions, data is corrupted.

The Critical Section Problem

A critical section is a segment of code where a process accesses shared resources. The critical section problem is about designing a protocol that processes use to cooperate when entering their critical sections.

Process Structure: ┌─────────────────────┐ │ Entry Section │ ← Request permission to enter ├─────────────────────┤ │ CRITICAL SECTION │ ← Access shared resource (only one process here at a time) ├─────────────────────┤ │ Exit Section │ ← Release permission ├─────────────────────┤ │ Remainder Section │ ← Non-critical code └─────────────────────┘

Three Requirements for a Solution

Any correct solution to the critical section problem must satisfy ALL three:

Mutual Exclusion: If process Pi is in its critical section, no other process can be in its critical section simultaneously.

Progress: If no process is in the critical section and some processes wish to enter, only those processes not in their remainder section participate in deciding who enters next — and this decision cannot be postponed indefinitely.

Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections after a process has requested entry. No starvation.

Types of Synchronization Mechanisms

Mechanism	Type	Description
Mutex Locks	Software	Binary lock for mutual exclusion
Semaphores	Software	Generalized counting mechanism
Monitors	Language construct	High-level synchronization object
Hardware instructions	Hardware	Atomic test-and-set, compare-and-swap
Spinlocks	Hardware-assisted	Busy-wait locks using atomic instructions

Peterson's Solution (Software, 2 processes)

A classic software solution for two processes sharing two variables:

Example

int turn; // Whose turn is it? bool flag[2]; // flag[i] = true means Pi wants to enter // Process Pi (i = 0 or 1, j = 1-i) void enter_critical_section(int i) { int j = 1 - i; flag[i] = true; // I want to enter turn = j; // But I give you the chance first while (flag[j] && turn == j) ; // Wait — the other process wants in AND it is their turn } void exit_critical_section(int i) { flag[i] = false; // I am done }

Peterson's solution satisfies all three requirements but only works for two processes and assumes atomic reads/writes (which modern CPUs with out-of-order execution do not guarantee without memory barriers).

Hardware Solutions

Modern CPUs provide atomic instructions that make synchronization simpler:

Test-and-Set

c example

// Hardware atomic instruction — cannot be interrupted
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;  // Returns old value AND sets to true atomically
}

// Using test_and_set for mutual exclusion
bool lock = false;

void enter() {
    while (test_and_set(&lock))
        ;  // Spin until lock was false (and we set it true)
}

void exit() {
    lock = false;
}

Compare-and-Swap (CAS)

c example

// Atomic CAS instruction
int compare_and_swap(int *value, int expected, int new_value) {
    int old = *value;
    if (old == expected)
        *value = new_value;
    return old;
}

Real-World Analogy

Process synchronization is like a bathroom with a single toilet and a lock on the door. The critical section is using the toilet. Mutual exclusion means only one person at a time. The lock mechanism (mutex) ensures this. Progress means if no one is in the bathroom, someone waiting can enter (the lock is not stuck). Bounded waiting means no one waits forever while others keep cutting in line.

Key Takeaways

Race conditions occur when multiple threads access shared data without coordination
The critical section problem requires mutual exclusion, progress, and bounded waiting
Software solutions (Peterson's) exist but are impractical for modern multi-core systems
Hardware atomic instructions (test-and-set, CAS) provide building blocks for synchronization
Multiple mechanisms exist (mutexes, semaphores, monitors) built on these foundations
Synchronization bugs are among the hardest to find because they depend on timing
Proper synchronization is essential for correct concurrent programming

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Introduction to Process Synchronization.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, introduction, introduction to process synchronization

Continue learning this concept

Process SynchronizationCritical Section ProblemDeep dive into the critical section problem — requirements, software solutions (Peterson\Process SynchronizationDining Philosophers ProblemThe classic dining philosophers problem — problem statement, naive solution showing deadlock, correct solutions using semaphores, monitors, and resource hierarchy.Process SynchronizationMonitorsUnderstanding monitors as a high-level synchronization construct — encapsulation, condition variables, wait and signal operations, and comparison with semaphores.Process SynchronizationMutex LocksUnderstanding mutex locks for mutual exclusion — acquire and release operations, spinlocks vs blocking mutexes, recursive mutexes, and practical mutex usage patterns.Process SynchronizationProducer-Consumer ProblemThe classic producer-consumer (bounded buffer) synchronization problem — solutions using semaphores, mutex locks, and monitors with complete code examples.Process SynchronizationReaders-Writers ProblemThe readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.

PreviousSemaphores NextBanker\

OS Notes

Introduction to Process Synchronization

Understanding why process synchronization is needed, race conditions, the critical section problem, and an overview of synchronization mechanisms in operating systems.

Introduction

Why Synchronization is Needed

A Classic Race Condition

Example

The problem is that counter++ is not atomic — it involves three machine instructions (load, add, store). If another thread intervenes between these instructions, data is corrupted.

The Critical Section Problem

Three Requirements for a Solution

Any correct solution to the critical section problem must satisfy ALL three:

Mutual Exclusion: If process Pi is in its critical section, no other process can be in its critical section simultaneously.

Progress: If no process is in the critical section and some processes wish to enter, only those processes not in their remainder section participate in deciding who enters next — and this decision cannot be postponed indefinitely.

Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections after a process has requested entry. No starvation.

Types of Synchronization Mechanisms

Mechanism	Type	Description
Mutex Locks	Software	Binary lock for mutual exclusion
Semaphores	Software	Generalized counting mechanism
Monitors	Language construct	High-level synchronization object
Hardware instructions	Hardware	Atomic test-and-set, compare-and-swap
Spinlocks	Hardware-assisted	Busy-wait locks using atomic instructions

Peterson's Solution (Software, 2 processes)

A classic software solution for two processes sharing two variables:

Example

Hardware Solutions

Modern CPUs provide atomic instructions that make synchronization simpler:

Test-and-Set

c example

// Hardware atomic instruction — cannot be interrupted
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;  // Returns old value AND sets to true atomically
}

// Using test_and_set for mutual exclusion
bool lock = false;

void enter() {
    while (test_and_set(&lock))
        ;  // Spin until lock was false (and we set it true)
}

void exit() {
    lock = false;
}

Compare-and-Swap (CAS)

c example

// Atomic CAS instruction
int compare_and_swap(int *value, int expected, int new_value) {
    int old = *value;
    if (old == expected)
        *value = new_value;
    return old;
}

Real-World Analogy

Key Takeaways

Race conditions occur when multiple threads access shared data without coordination
The critical section problem requires mutual exclusion, progress, and bounded waiting
Software solutions (Peterson's) exist but are impractical for modern multi-core systems
Hardware atomic instructions (test-and-set, CAS) provide building blocks for synchronization
Multiple mechanisms exist (mutexes, semaphores, monitors) built on these foundations
Synchronization bugs are among the hardest to find because they depend on timing
Proper synchronization is essential for correct concurrent programming

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Introduction to Process Synchronization.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, introduction, introduction to process synchronization

Continue learning this concept

PreviousSemaphores NextBanker\