Understanding the Critical Section Problem in Operating Systems

When learning operating systems, the critical section problem in process management is one of the most challenging concepts to grasp. The critical section refers to a portion of code where processes access shared resources that must not be accessed simultaneously by multiple processes.

Any solution to the critical section problem must satisfy three essential requirements:

The Three Requirements

1. Mutual Exclusion

Only one process can execute in its critical section at any given time. This prevents race conditions and ensures data consistency.

2. Progress

The system must be able to make forward progress. If no process is currently in the critical section and there are processes waiting to enter, the system must quickly decide which process enters next. Processes that aren’t interested in entering their critical section (those in their remainder section) cannot indefinitely delay this decision. This requirement also ensures freedom from deadlock.

In simple terms: If no process is in the critical section, a waiting process must be allowed to enter.

3. Bounded Waiting

This requirement ensures fairness and prevents starvation. Once a process requests to enter the critical section, there must be a limit on how many other processes can enter before the requesting process gets its turn.

In simple terms: No process should wait indefinitely to enter the critical section.

Three Solutions to the Critical Section Problem

Let’s examine three possible solutions, assuming we have only two processes running in a single-threaded environment on a single processor core.

Solution 1: Simple Turn Variable

This approach uses one shared variable called turn:

while (true) {
    /* Entry Section */
    while (turn == j);
    /* Critical Section */
    turn = j;
    /* Remainder Section */
}

How it works:

• Initially, turn = 0
• Each process has a local variable j: Process 0 sets j = 1, Process 1 sets j = 0
• When both processes want to enter their critical section, only one can proceed based on the current value of turn
• After exiting the critical section, the process sets turn to allow the other process to enter

Analysis:

• ✅ Mutual Exclusion: Satisfied - only one process can enter at a time
• ❌ Progress: Not satisfied - if one process finishes and doesn’t want to re-enter, the other process gets stuck waiting forever
• ❌ Bounded Waiting: Not satisfied - a process might wait indefinitely if the other process doesn’t cooperate

The Problem: This solution creates a strict alternation that fails when one process no longer needs the critical section.

Solution 2: Peterson’s Solution

Peterson’s algorithm introduces a flag array to indicate each process’s intention to enter:

while(true) {
    flag[i] = true;        // Express intention to enter
    turn = j;              // Give priority to other process
    while (flag[j] == true && turn == j);  // Wait if necessary
    // Critical section
    flag[i] = false;       // No longer interested
    // Remainder section
}

How it works:

• Each process sets its flag to true when it wants to enter
• The process then sets turn to favor the other process
• It waits only if the other process also wants to enter AND has priority
• After exiting, the process sets its flag to false

Analysis:

• ✅ Mutual Exclusion: Satisfied - the combination of flags and turn variable ensures only one process enters
• ✅ Progress: Satisfied - if one process isn’t interested (flag is false), the other can enter immediately
• ✅ Bounded Waiting: Satisfied - a process waits at most one turn before entering

Why it works: Peterson’s algorithm elegantly balances intention (flags) with priority (turn variable).

Solution 3: Ticket Algorithm (Bakery Algorithm)

This solution can handle N processes using a ticket-based system:

while(true) {
    number[i] = max(number[0], ..., number[n-1]) + 1;  // Take a ticket
    for (j = 0; j < n; j++) {
        while (number[j] != 0 && (number[j],j) < (number[i],i));
    }
    // Critical section
    number[i] = 0;  // Return ticket
    // Remainder section
}

How it works:

• Each process takes a ticket number (highest current number + 1)
• Processes enter in ticket order (lowest number first)
• If two processes have the same ticket number, the one with the lower process ID goes first
• After finishing, the process resets its ticket to 0

Analysis:

• ✅ Mutual Exclusion: Satisfied - only the process with the smallest ticket (and ID) can enter
• ✅ Progress: Satisfied - processes with tickets will eventually get their turn
• ✅ Bounded Waiting: Satisfied - each process waits for at most N-1 other processes

Note: Due to concurrent execution, two processes might get the same ticket number, which is why we use the process ID as a tiebreaker.

Conclusion

The ticket algorithm provides the most robust solution as it’s fair, prevents starvation, and scales to multiple processes. While Peterson’s algorithm works well for two processes, the ticket algorithm demonstrates how we can extend synchronization concepts to handle more complex scenarios with multiple competing processes.