Process Synchronization: Race Conditions, Critical Sections, Semaphores & Deadlocks

TAKEAWAYS:

• Race conditions occur when multiple processes access shared data simultaneously, leading to unpredictable results unless synchronized.
• Critical sections are code segments where shared resources are accessed; mutual exclusion ensures only one process executes them at a time.
• Semaphores (binary and counting) and monitors are synchronization primitives that enforce mutual exclusion and condition synchronization.
• Deadlocks arise from circular wait, hold-and-wait, no preemption, and mutual exclusion; prevention, avoidance, and detection methods exist.
• Message passing (blocking/non-blocking) is an alternative to shared memory for synchronization in distributed systems.
• Starvation and priority inversion are fairness issues that must be addressed in scheduling and synchronization policies.

1. Introduction to Process Synchronization

Process synchronization is the mechanism that ensures orderly execution of processes to avoid race conditions (when multiple processes interfere with each other’s execution) and inconsistent data states. Without synchronization, processes may corrupt shared data, produce incorrect results, or crash.

Why Synchronization?

• Shared resources: Multiple processes may need to access the same resource (e.g., a file, printer, or database table).
• Interdependence: Some processes must wait for others to complete a task (e.g., a producer must wait for a consumer to read data).
• Atomicity: Certain operations (e.g., transferring money between bank accounts) must be executed as a single, uninterruptible unit.

Key Problems Without Synchronization

1. Race Condition: When two or more processes access shared data and try to change it simultaneously, leading to unpredictable outcomes.
   • Example: Two bank tellers (processes) update the same account balance at the same time. If not synchronized, the final balance may be incorrect.
2. Starvation: A process is perpetually denied access to a resource.
   • Example: Low-priority processes in a CPU scheduler may never get CPU time.
3. Deadlock: A set of processes are blocked forever, each waiting for a resource held by another.
   • Example: Process A holds Resource 1 and waits for Resource 2, while Process B holds Resource 2 and waits for Resource 1.

2. Critical Section Problem

The critical section is a segment of code where a process accesses shared data. The critical section problem requires three conditions to be satisfied:

1. Mutual Exclusion: Only one process can be in its critical section at a time.
2. Progress: If no process is in its critical section, any process that wants to enter must be allowed to do so.
3. Bounded Waiting: No process should wait indefinitely to enter its critical section.

Solutions to the Critical Section Problem

1. Peterson’s Algorithm (for two processes):

   • Uses two shared variables (flag[2] and turn) to enforce mutual exclusion.
   • Example:

     int flag[2] = {0, 0}; // Indicates if a process wants to enter CS
     int turn = 0;        // Indicates whose turn it is to enter CS
     
     // Process i's entry protocol:
     flag[i] = 1;
     turn = j; // j is the other process
     while (flag[j] == 1 && turn == j);
     // Critical Section
     flag[i] = 0;
     

   • Limitation: Only works for two processes.

2. Test-and-Set Lock:

   • Uses a hardware instruction (test_and_set) to atomically check and set a lock variable.
   • Example:

     int lock = 0; // 0 = unlocked, 1 = locked
     
     // Process's entry protocol:
     while (test_and_set(&lock)); // Spin until lock is free
     // Critical Section
     lock = 0; // Release lock
     

   • Disadvantage: Busy waiting (spinlock) wastes CPU cycles.

3. Synchronization Primitives

3.1 Semaphores

A semaphore is a synchronization tool that controls access to shared resources. It has:

• A value (integer) representing the number of available resources.
• Two operations:
  • wait() (or P()): Decrements the semaphore value. If the value is negative, the process blocks.
  • signal() (or V()): Increments the semaphore value. If there are blocked processes, one is unblocked.

Types of Semaphores

Example: Producer-Consumer Problem

• Problem: Producers generate data and place it in a buffer, while consumers remove data from the buffer. Without synchronization, the buffer may overflow or underflow.
• Solution: Use two semaphores:
  • mutex (binary): Ensures mutual exclusion for buffer access.
  • empty (counting): Tracks empty slots in the buffer.
  • full (counting): Tracks filled slots in the buffer.

sequenceDiagram
    participant Producer
    participant Consumer
    participant Buffer
    Producer->>Buffer: wait(empty) // Check if buffer has space
    Buffer-->>Producer: Decrement empty
    Producer->>Buffer: wait(mutex) // Lock buffer
    Buffer-->>Producer: Enter CS
    Producer->>Buffer: Add item
    Producer->>Buffer: signal(mutex) // Unlock buffer
    Producer->>Buffer: signal(full) // Increment full
    Consumer->>Buffer: wait(full) // Check if buffer has items
    Buffer-->>Consumer: Decrement full
    Consumer->>Buffer: wait(mutex) // Lock buffer
    Buffer-->>Consumer: Enter CS
    Consumer->>Buffer: Remove item
    Consumer->>Buffer: signal(mutex) // Unlock buffer
    Consumer->>Buffer: signal(empty) // Increment empty

Real-World Example: Daraz Order Processing

• Scenario: Multiple users place orders simultaneously (producers), and the order processing system (consumer) must handle them without losing or duplicating orders.
• Synchronization Used:
  • A counting semaphore tracks the number of available order slots in a queue.
  • A binary semaphore ensures only one process accesses the order database at a time.
• Result: No race conditions in order processing, and no starvation for high-priority orders.

3.2 Monitors

A monitor is a high-level synchronization construct that encapsulates shared data and the procedures that operate on it. It ensures:

• Only one process can execute a monitor procedure at a time.
• Processes can wait for conditions inside the monitor.

Example: Bank Account Transfer

monitor BankAccount {
    int balance;
    condition lowBalance;

    procedure deposit(int amount) {
        balance += amount;
        if (balance < 1000) lowBalance.signal();
    }

    procedure withdraw(int amount) {
        while (balance < amount) lowBalance.wait();
        balance -= amount;
    }
}

• Advantage: Simpler than semaphores; reduces risk of deadlocks.

Real-World Example: Ncell Top-Up System

• Scenario: Multiple users request top-ups simultaneously, and the system must ensure no two processes modify the same user’s balance at the same time.
• Synchronization Used:
  • A monitor encapsulates the user’s balance and top-up logic.
  • Processes wait if the balance is insufficient (lowBalance condition).

3.3 Message Passing

Instead of shared memory, processes communicate via messages. Two types:

1. Direct Communication: Sender and receiver names are explicitly specified.
2. Indirect Communication: Messages are sent/received via mailboxes (ports).

Types of Message Passing

Example: Pathao Driver-Passenger Matching

• Scenario: Drivers and passengers exchange messages to confirm rides.
• Synchronization Used:
  • Blocking receive: A passenger waits for a driver’s acceptance message.
  • Non-blocking send: A driver sends a ride confirmation without waiting for an acknowledgment.

4. Deadlocks

A deadlock occurs when four conditions hold simultaneously:

1. Mutual Exclusion: Only one process can use a resource at a time.
2. Hold and Wait: A process holds a resource while waiting for another.
3. No Preemption: Resources cannot be forcibly taken from a process.
4. Circular Wait: A circular chain of processes exists where each waits for a resource held by the next.

Example: NTC Traffic Light Control

• Scenario: Two traffic lights (Process A and B) control intersecting roads. Process A holds the green light for Road 1 and waits for the green light for Road 2, while Process B holds the green light for Road 2 and waits for Road 1.
• Result: Deadlock—both processes wait indefinitely.

Handling Deadlocks

Banker’s Algorithm (Deadlock Avoidance)

• Idea: The OS checks if allocating a resource would leave the system in a safe state (where all processes can complete).
• Example: A bank (OS) ensures that loan requests (resource allocations) do not lead to a situation where some customers (processes) can never repay.

stateDiagram-v2
    [*] --> SafeState: Allocate resources if safe
    SafeState --> [*]: All processes finish
    SafeState --> UnsafeState: Allocate resources if unsafe
    UnsafeState --> Deadlock: Circular wait occurs
    UnsafeState --> SafeState: Rollback or kill process

5. Starvation and Priority Inversion

Starvation

• A process is perpetually denied access to resources.
• Example: Low-priority processes in a CPU scheduler may never get CPU time if high-priority processes keep arriving.

Priority Inversion

• A low-priority process holds a resource needed by a high-priority process, while a medium-priority process preempts the low-priority process.
• Solution: Priority Inheritance Protocol (temporarily boosts the priority of the low-priority process holding the resource).

Example: Ncell Emergency Call Handling

• Scenario: A high-priority emergency call (Process A) waits for a resource held by a low-priority data call (Process B). If a medium-priority voice call (Process C) preempts Process B, Process A may starve.
• Solution: Process B inherits Process A’s priority until it releases the resource.

In the Real World

1. eSewa Payment System

   • Idea Used: Semaphores for mutual exclusion
   • How: When multiple users request transactions simultaneously, eSewa uses semaphores to ensure only one transaction modifies a user’s balance at a time. This prevents race conditions where two payments might incorrectly update the same account.

2. Khalti Wallet Transactions

   • Idea Used: Monitors for atomic operations
   • How: Khalti uses monitors to encapsulate wallet balance updates. When you transfer money, the monitor ensures the deduction from your account and addition to the recipient’s account happen atomically—no partial updates occur.

3. NTC Traffic Management System

   • Idea Used: Deadlock prevention (circular wait avoidance)
   • How: NTC’s traffic light control system uses timeouts to break circular waits. If two traffic lights deadlock (e.g., both waiting for the other to release a road), the system resets one after a timeout to avoid permanent deadlock.

Exam Tip

1. Understand the Critical Section Problem: Be ready to explain Peterson’s algorithm and test-and-set locks. Examiners often ask for pseudocode or scenarios where these are applied.
2. Semaphore vs. Monitor: Know when to use each. Semaphores are low-level (used in kernel code), while monitors are high-level (used in user-space programs like Java).
3. Deadlock Conditions: Memorize the four necessary conditions for deadlock and how each can be broken. The Banker’s algorithm is a common exam question—practice drawing its state transition diagrams.
4. Real-World Scenarios: Relate synchronization to Nepalese systems (e.g., Daraz order queues, Ncell top-ups). Examiners love practical examples.
5. Starvation vs. Deadlock: Distinguish between them. Starvation is about fairness; deadlock is about circular waiting. Both can be tested with short-answer questions.
6. Message Passing: Know the difference between blocking/non-blocking sends and receives. Pathao’s ride-matching system is a great example for this topic.

Key Formulas and Tables

Worked Example: Dining Philosophers Problem

Problem: Five philosophers sit at a table with five forks. Each philosopher alternates between thinking and eating. To eat, a philosopher needs two forks (one on each side). If all pick up their left fork simultaneously, they deadlock.

Solution: Use semaphores to enforce rules:

1. Resource Hierarchy: Philosophers pick up forks in a fixed order (e.g., always left then right).
2. Limit the Number of Philosophers Eating: Use a counting semaphore to allow only 4 to eat at a time.

sequenceDiagram
    participant Philosopher1
    participant Philosopher2
    participant Fork1
    participant Fork2
    Philosopher1->>Fork1: pickUp() // Acquire left fork
    Philosopher1->>Fork2: pickUp() // Acquire right fork
    Philosopher1->>Philosopher1: Eat()
    Philosopher1->>Fork2: putDown() // Release right fork
    Philosopher1->>Fork1: putDown() // Release left fork
    Philosopher2->>Fork1: pickUp() // Now safe to pick up

Real-World Tie-In: This mirrors Nepal’s road traffic system, where drivers (philosophers) need two "forks" (right of way at two intersections) to proceed. If all drivers take the left intersection first, they deadlock. Solutions like traffic lights (resource hierarchy) or limiting concurrent turns (semaphore) prevent deadlocks.