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​
-
Initial State:
counter = 0
-
Thread 1 reads:
counter_1 = 0
-
Thread 2 reads:
counter_2 = 0
-
Thread 1 increments:
counter_1 = 1
-
Thread 2 increments:
counter_2 = 1
-
Thread 1 writes back:
counter = 1
-
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​
-
Process P1 enters the entry section:
-
lock = false
-
while (lock);
- P1 exits the loop sincelock
is false. -
lock = true;
- P1 setslock
to true, entering the critical section.
-
-
Process P2 attempts to enter:
-
lock = true
(set by P1) -
while (lock);
- P2 is stuck in the loop sincelock
is true.
-
-
Process P1 exits the critical section:
-
lock = false;
-
P1 releases the lock.
-
-
Process P2 exits the busy-wait loop and enters the critical section.
Scenario 2: Failure Due to Preemption​
-
Process P1 enters the entry section, sees
lock = false
, and exits the busy-wait loop. -
P1 is preempted before setting
lock = true
. -
Process P2 enters, finds
lock = false
, and setslock = true
. -
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​
-
Process P1 checks
turn == 0
and enters the critical section. -
Process P2 checks
turn != 1
and waits. -
P1 sets
turn = 1
upon exit, allowing P2 to enter.
Scenario 2: Not Satisfying Progress​
-
Process P1 checks
turn == 0
and enters. -
P1 sets
turn = 1
upon exit. -
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​
-
P1 sets
flag[0] = true
indicating its intent to enter. -
Preemption happens, and P2 sets
flag[1] = true
. -
P2 sets
turn = 0
, allowing P1 to proceed if it wants. -
Preemption happens, and P1 sets
turn = 1
, allowing P2 to proceed if it wants. -
P1 is now stuck in a busy-wait since
flag[1] == true
andturn == 1
. -
P2 exits the busy-wait loop, executes its critical section, and then sets
flag[1] = false
. -
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.