Critical Section Problem

What is a Critical Section?

A critical section is a part of a program where shared resources are accessed by various processes.

Critical sections are parts of the program where shared resources, like variables and data structures, are accessed. These sections must be executed in a controlled manner to prevent race conditions, which occur when multiple processes try to modify shared data simultaneously.

Key Components

• Entry Section: Prepares to enter the critical section, ensuring that no other process is inside.

• Exit Section: Signals that the critical section is no longer occupied.

• Non-Critical Section: Code that does not involve shared resources and can be executed concurrently.

Problem: Race Conditions

public class RaceConditionExample {
    private static int counter = 0; // Shared variable
 
    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new Thread(() -> incrementCounter());
        Thread thread2 = new Thread(() -> incrementCounter());
 
        thread1.start(); // Start thread1
        thread2.start(); // Start thread2
 
        thread1.join();  // Wait for thread1 to complete its execution
        thread2.join();  // Wait for thread2 to complete its execution
 
        System.out.println("Final counter value: " + counter);
    }
 
    private static void incrementCounter() {
        for (int i = 0; i < 100; i++) {
            counter++;
        }
    }
}

Output Example: Final counter value: 140

In the Java example above, two threads increment a shared counter. Although each thread is supposed to increment the counter 100 times, the final result may vary and often ends up being less than 200 due to the race condition. This happens because both threads access and modify the shared counter simultaneously.

How It Happens

1. Initial State: counter = 0

2. Thread 1 reads: counter_1 = 0

3. Thread 2 reads: counter_2 = 0

4. Thread 1 increments: counter_1 = 1

5. Thread 2 increments: counter_2 = 1

6. Thread 1 writes back: counter = 1

7. Thread 2 writes back: counter = 1

Both threads read the counter value simultaneously, increment it, and then write back, effectively losing one increment operation.

Requirements for a Solution

To solve the critical section problem, a solution must meet the following requirements:

• Mutual Exclusion: Only one process can be in the critical section at a time.

• Progress: If no process is in the critical section, any process that wishes to enter must be allowed to do so without unnecessary delay.

• Bounded Waiting: No process should have to wait indefinitely to enter the critical section, preventing starvation.

• No Assumptions About Speed or Number of CPUs: The solution should be platform-independent and work consistently across different hardware and operating systems.

Solution 1: Using Lock

Scenario 1: Proper Functioning

1. Process P1 enters the entry section:

   • lock = false

   • while (lock); - P1 exits the loop since lock is false.

   • lock = true; - P1 sets lock to true, entering the critical section.

2. Process P2 attempts to enter:

   • lock = true (set by P1)

   • while (lock); - P2 is stuck in the loop since lock is true.

3. Process P1 exits the critical section:

   • lock = false;

   • P1 releases the lock.

4. Process P2 exits the busy-wait loop and enters the critical section.

Scenario 2: Failure Due to Preemption

1. Process P1 enters the entry section, sees lock = false, and exits the busy-wait loop.

2. P1 is preempted before setting lock = true.

3. Process P2 enters, finds lock = false, and sets lock = true.

4. P1 resumes and sets lock = true, leading to both P1 and P2 being in the critical section simultaneously.

The failure here is due to non-atomic operations in the entry section. A potential fix could involve making the entry section atomic, but this might depend on specific hardware capabilities.

Solution 2: Using Turn

Scenario 1: Proper Functioning

1. Process P1 checks turn == 0 and enters the critical section.

2. Process P2 checks turn != 1 and waits.

3. P1 sets turn = 1 upon exit, allowing P2 to enter.

Scenario 2: Not Satisfying Progress

1. Process P1 checks turn == 0 and enters.

2. P1 sets turn = 1 upon exit.

3. P1 tries to enter again but is stuck since turn != 0.

This setup violates the progress requirement because P2 is unnecessarily postponed.

Solution 3: Peterson's Solution

Peterson's solution uses two flags and a turn variable to manage access to the critical section, overcoming issues seen in the previous solutions.

How It Works

1. P1 sets flag[0] = true indicating its intent to enter.

2. Preemption happens, and P2 sets flag[1] = true.

3. P2 sets turn = 0, allowing P1 to proceed if it wants.

4. Preemption happens, and P1 sets turn = 1, allowing P2 to proceed if it wants.

5. P1 is now stuck in a busy-wait since flag[1] == true and turn == 1.

6. P2 exits the busy-wait loop, executes its critical section, and then sets flag[1] = false.

7. P1 now exits the busy-wait loop and enters the critical section.

Benefits of Peterson's Solution

• Mutual Exclusion: Only one process can enter the critical section at a time.

• Progress: Processes can enter the critical section as soon as it is free.

• Bounded Waiting: Each process gets its turn without indefinite delay.

• Platform Independence: Works across various systems without specific hardware requirements.

Peterson's solution effectively handles mutual exclusion, progress, and bounded waiting, making it a robust method for solving the critical section problem in concurrent programming.