Synchronization & Deadlocks: Race Conditions, Critical Sections, Deadlocks & Solutions

TAKEAWAYS:

• Race conditions occur when multiple processes access shared data without synchronization, leading to unpredictable results.
• Critical sections must be protected using mutual exclusion, progress, and bounded waiting to ensure correctness.
• Deadlocks arise from circular wait, hold-and-wait, no preemption, and mutual exclusion; Banker’s algorithm prevents them by checking resource allocation safety.
• Solutions to deadlocks include prevention, avoidance, detection, and recovery—each with trade-offs in performance and complexity.
• Semaphores and monitors are synchronization tools: semaphores use wait()/signal() while monitors encapsulate shared data and operations.
• Real-world examples: eSewa’s transaction locks, Kathmandu traffic signals, and WhatsApp message queues all rely on synchronization to avoid corruption or deadlocks.

1. Why Synchronization? The Problem of Race Conditions

When multiple processes access shared data or resources concurrently, their interleaved execution can lead to inconsistent states. This is called a race condition.

Example: Bank Account Balance

Suppose two processes (P1 and P2) try to withdraw money from the same account simultaneously:

sequenceDiagram
    participant P1 as Process 1 (Withdraw 100)
    participant P2 as Process 2 (Withdraw 200)
    participant Account as Shared Bank Account (Balance = 500)
    P1->>Account: Read balance (500)
    P2->>Account: Read balance (500)
    P1->>Account: Write balance (500 - 100 = 400)
    P2->>Account: Write balance (500 - 200 = 300)  <!-- Overwritten! -->

Result: The final balance is 300 instead of 200 (correct). This happens because the processes interleave without synchronization.

Real-World Analogy: Kathmandu Traffic Lights

• Unsynchronized signals: If two traffic lights at an intersection don’t coordinate, cars from perpendicular roads might collide.
• Solution: Traffic lights use timed synchronization (like semaphores) to ensure safe passage.

2. Critical Sections and Synchronization Requirements

A critical section is a segment of code where a process accesses shared resources. To protect it, we need:

1. Mutual Exclusion: Only one process can be in its critical section at a time.
2. Progress: No process should be blocked indefinitely from entering its critical section.
3. Bounded Waiting: No process should wait forever to enter its critical section.

Peterson’s Solution (Software-Based)

For two processes, Peterson’s algorithm ensures mutual exclusion without hardware support:

boolean flag[2] = {false, false};  // Indicates intent to enter CS
int turn = 0;                       // Whose turn it is

```figure
{"type":"fields","width":32,"rows":[[{"label":"turn","bits":2},{"label":"flag[0]","bits":1},{"label":"flag[1]","bits":1},{"label":"reserved","bits":28}]],"caption":"Shared variables in Peterson’s solution for mutual exclusion."}

// Process Pi enters CS: flag[i] = true; turn = j; // j is the other process while (flag[j] && turn == j); // Wait if j is in CS or has priority // Critical Section flag[i] = false; Limitation: Only works for two processes. For N processes, we need semaphores or monitors.

3. Semaphores: The Traffic Cop of Processes

A semaphore is a synchronization tool with:

• An integer value (initially ≥ 0).
• Two operations:
  • wait() (or P()): Decrements the semaphore. If < 0, the process blocks.
  • signal() (or V()): Increments the semaphore. If any process is blocked, it unblocks one.

Types of Semaphores

Example: Producer-Consumer Problem

sequenceDiagram
  participant P as Producer
  participant C as Consumer
  participant Buffer as Shared Buffer (size = 5)
  participant mutex as Semaphore (1)
  participant empty as Semaphore (5)
  participant full as Semaphore (0)

  P->>empty: wait()
  P->>mutex: wait()
  P->>Buffer: Add item
  P->>mutex: signal()
  P->>full: signal()

  C->>full: wait()
  C->>mutex: wait()
  C->>Buffer: Remove item
  C->>mutex: signal()
  C->>empty: signal()

Real-World Use:

• eSewa transactions: Semaphores ensure only one user can modify an account balance at a time.
• WhatsApp message queue: Semaphores prevent multiple processes from reading/writing the same message simultaneously.

4. Monitors: A Higher-Level Abstraction

Monitors encapsulate shared data and operations, ensuring only one process can execute them at a time. Example: A Monitor for a Shared Printer

monitor Printer {
    boolean busy = false;
    procedure print(job) {
        while (busy) wait();  // Block if printer is busy
        busy = true;
        // Print job
        busy = false;
        signal();  // Wake up any waiting processes
    }
}

Advantages:

• Simpler than semaphores (no risk of deadlock from misused wait()/signal()).
• Ensures mutual exclusion automatically.

Real-World Use:

• Khalti payment processing: Monitors ensure transactions are atomic (all-or-nothing).

5. Deadlocks: When Processes Get Stuck

A deadlock occurs when four conditions hold simultaneously:

1. Mutual Exclusion: At least one resource is non-sharable.
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, each waiting for the next.

Example: The Dining Philosophers Problem

Five philosophers sit at a table with chopsticks (resources). Each needs two chopsticks to eat:

stateDiagram-v2
  [*] --> Thinking
  Thinking --> PickUpLeft: Pick up left chopstick
  PickUpLeft --> PickUpRight: Pick up right chopstick
  PickUpRight --> Eating
  Eating --> PutDownRight: Put down right chopstick
  PutDownRight --> PutDownLeft: Put down left chopstick
  PutDownLeft --> [*]

  state PickUpLeft {
    [*] --> WaitLeft: If left chopstick is free
    WaitLeft --> PickUpLeft: Take it
  }
  state PickUpRight {
    [*] --> WaitRight: If right chopstick is free
    WaitRight --> PickUpRight: Take it
  }

  state Eating {
    [*] --> WaitBoth: Both chopsticks held
    WaitBoth --> Eating: Eat
  }

Deadlock Scenario: All philosophers pick up their left chopstick simultaneously and wait for the right one, creating a circular wait.

Solutions:

1. Prevention: Break one of the four conditions (e.g., limit resources).
2. Avoidance: Use algorithms like Banker’s Algorithm to check safety.
3. Detection and Recovery: Periodically check for deadlocks and abort processes.

6. Banker’s Algorithm: Avoiding Deadlocks Proactively

The Banker’s Algorithm ensures the system never enters an unsafe state by:

1. Tracking available resources.
2. Checking if a process can complete without causing a deadlock.

Worked Example: Ncell’s Server Resource Allocation

Suppose Ncell’s server has:

• 3 CPU units, 2 RAM units, and 1 Disk unit.
• Processes P0, P1, P2 request resources as follows:

Available Resources: (1, 1, 0)

Step-by-Step Check:

1. P0’s request: Can it finish?
   • Need: (2, 2, 1) - (1, 0, 0) = (1, 2, 1)
   • Available: (1, 1, 0) < (1, 2, 1) → Cannot proceed.
   • Reject P0’s request to avoid deadlock.

Real-World Tie-In:

• Daraz’s order processing: The Banker’s Algorithm ensures the system doesn’t run out of inventory or server resources during Black Friday sales.

7. Deadlock Handling Strategies

Wait-for Graph Example

graph TD
    P0["P0"] -->|"waits for"| R1["Resource 1"]
    P1["P1"] -->|"waits for"| R2["Resource 2"]
    P2["P2"] -->|"waits for"| R3["Resource 3"]
    R1 -->|"held by"| P1
    R2 -->|"held by"| P2
    R3 -->|"held by"| P0

Cycle: P0 → R1 → P1 → R2 → P2 → R3 → P0 → Deadlock detected!

Recovery:

• Process termination: Kill P0, P1, or P2.
• Resource preemption: Take R1 from P1 and give it to P0.

8. Real-World Applications of Synchronization

Exam Tip

1. Define clearly:

   • "A deadlock is a state where two or more processes are blocked forever, each waiting for a resource held by another."
   • "A semaphore is a variable used to control access to a shared resource with wait() and signal() operations."

2. Draw diagrams:

   • Peterson’s algorithm (for mutual exclusion).
   • Wait-for graphs (to detect deadlocks).
   • Producer-Consumer (semaphore usage).

3. Worked examples:

   • Always show step-by-step Banker’s Algorithm calculations.
   • For deadlock prevention, explain how breaking one condition (e.g., no circular wait) solves the problem.

4. Compare:

   • Semaphores vs. Monitors: Monitors are safer but less flexible.
   • Prevention vs. Avoidance: Prevention is simpler; avoidance is more robust.

5. Real-world links:

   • Relate eSewa transactions to critical sections.
   • Link Ncell’s server to Banker’s Algorithm.