Process Synchronization: Race Conditions, Critical Sections & Synchronization Tools

Key Concepts and Definitions

What is Process Synchronization?

Process synchronization refers to the coordination of processes or threads to ensure that they execute in a controlled manner when they share resources. Without synchronization, processes may interfere with each other, leading to race conditions, inconsistent data, or system failures.

Why is Synchronization Needed?

Concurrent processes often share resources like:

• Shared memory (e.g., global variables, buffers).
• I/O devices (e.g., printers, network interfaces).
• Files (e.g., transaction logs in databases).

If two processes access a shared resource simultaneously, the outcome may be unpredictable. For example:

• A bank account balance might be incorrectly updated if two transactions (deposit and withdrawal) run concurrently.
• A printer queue might print garbled data if two processes send output at the same time.

Critical Section Problem

The critical section problem arises when multiple processes access a shared resource, and the order of execution affects the correctness of the program.

Components of a Process

Every process has three parts:

1. Entry Section: Code that requests access to the critical section.
2. Critical Section: The part of the process that accesses shared resources.
3. Exit Section: Code that releases the shared resource.
4. Remainder Section: The rest of the process that does not access shared resources.

Requirements for Solving the Critical Section Problem

To ensure correct synchronization, the following conditions must be met:

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

Synchronization Tools

1. Mutex Locks (Mutual Exclusion)

A mutex (mutual exclusion lock) is a synchronization primitive that ensures only one thread or process can access a resource at a time.

How Mutex Works:

• A process locks the mutex before entering the critical section.
• If the mutex is already locked, the process waits.
• The process unlocks the mutex after exiting the critical section.

Example: Bank Account Balance Update

Consider two processes updating a bank account balance:

mutex_lock(&balance_mutex);
balance += amount;  // Critical section
mutex_unlock(&balance_mutex);

Advantages:

• Simple to implement.
• Ensures mutual exclusion.

Disadvantages:

• Can lead to deadlocks if not managed properly.
• No built-in mechanism to prevent starvation.

2. Semaphores

A semaphore is a synchronization tool that maintains a counter to control access to a shared resource. It can be:

• Binary Semaphore: Acts like a mutex (0 or 1).
• Counting Semaphore: Allows multiple processes (value > 1).

Operations:

• wait() or P(): Decrements the semaphore. If the value is negative, the process waits.
• signal() or V(): Increments the semaphore. If processes are waiting, one is woken up.

Example: Printer Queue

Suppose a printer can handle only one job at a time. A semaphore printer is initialized to 1:

semaphore printer = 1;

```figure
{"type":"queue","values":["Job A","Job B","Job C"],"front":0,"rear":2,"caption":"Semaphore-controlled printer queue: Jobs wait in order (FIFO) for the printer resource."}

Process A: P(printer); // Locks the printer print_job(); // Critical section V(printer); // Releases the printer

Process B: P(printer); // Waits if printer is busy print_job(); V(printer);

Advantages:

• Flexible (can control access to multiple resources).
• Prevents deadlocks if used correctly.

Disadvantages:

• Complex to implement.
• Risk of priority inversion (low-priority process holds a resource needed by a high-priority process).

3. Monitors

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

Features:

• Only one process can execute a monitor procedure at a time.
• Uses condition variables to handle waiting and signaling.

Example: Producer-Consumer Problem

sequenceDiagram
    participant Producer
    participant Monitor
    participant Consumer

    Producer->>Monitor: Produce item (add to buffer)
    Monitor-->>Producer: Signal consumer
    Consumer->>Monitor: Consume item (remove from buffer)
    Monitor-->>Consumer: Signal producer

Advantages:

• Simplifies synchronization logic.
• Reduces risk of errors.

Disadvantages:

• Limited portability (not all languages support monitors natively).

Real-World Applications

1. eSewa and Khalti (Nepal)

• Shared Resource: Transaction logs in databases.
• Synchronization Tool: Mutex locks or semaphores ensure that only one transaction is processed at a time to prevent double-spending or incorrect balances.

2. Daraz Order Processing

• Shared Resource: Order queue and inventory database.
• Synchronization Tool: Monitors or semaphores coordinate between the order processing system and inventory updates to avoid overselling or inconsistent stock levels.

3. NTC Traffic Management System

• Shared Resource: Traffic signal timings and sensor data.
• Synchronization Tool: Semaphores ensure that traffic signals are updated atomically to prevent conflicts between different intersections.

Worked Example: Dining Philosophers Problem

Five philosophers sit at a round table with a bowl of spaghetti and five forks. Each philosopher alternates between thinking and eating. To eat, a philosopher needs two forks (one on each side). The problem arises if all philosophers pick the left fork simultaneously, leading to a deadlock.

Solution Using Semaphores

Implementation:

semaphore fork[5] = {1, 1, 1, 1, 1}; // Each fork is a semaphore

void philosopher(int id) {
    while (true) {
        think();
        P(fork[id]);       // Pick left fork
        P(fork[(id+1)%5]); // Pick right fork
        eat();
        V(fork[(id+1)%5]); // Put down right fork
        V(fork[id]);       // Put down left fork
    }
}

Deadlock Avoidance:

• Use a resource allocation graph to detect deadlocks.
• Implement a timeout mechanism to release forks if a philosopher waits too long.

Comparison of Synchronization Tools

Exam Tip

1. Understand the Critical Section Problem: Be able to explain the three requirements (mutual exclusion, progress, bounded waiting) and how they are satisfied by different tools.
2. Practice with Examples: Solve problems like the producer-consumer problem, dining philosophers, and readers-writers problem using semaphores or monitors.
3. Diagrams are Key: Draw state diagrams, resource allocation graphs, and sequence diagrams to explain synchronization mechanisms.
4. Real-World Scenarios: Relate synchronization to real-world systems like banking transactions, e-commerce order processing, or traffic management.
5. Common Pitfalls: Watch out for deadlocks, starvation, and priority inversion in your answers.

A monitor encapsulating shared data and procedures for the producer-consumer problem. (Image: Theodore.norvell (talk), CC BY 3.0, via Wikimedia Commons) Five philosophers sitting at a table with forks, illustrating deadlock scenarios. (Image: Benjamin D. Esham (bdesham), CC BY-SA 3.0, via Wikimedia Commons)