Critical Section Problem

Consider a system consisting of $n$ processes {P_0, P_1, ..., P_{n-1}}. Each process has a segment of code, called a Critical Section, in which the process may be changing common variables, updating a table, writing a file, and so on.

The important feature of the system is that, when one process is executing in its critical section, no other process is allowed to execute in its critical section. That is, no two processes are executing in their critical sections at the same time.

1. The Structure of a Process

To enforce this, a process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section.

do {
    // Entry Section: Request permission
    acquire_lock();
    
        // CRITICAL SECTION
        // Access shared variables here
        
    // Exit Section: Release permission
    release_lock();
    
    // Remainder Section
} while (true);

2. Requirements for a Solution

Any valid solution to the critical-section problem must strictly satisfy the following three requirements:

1. Mutual Exclusion: If process $P_i$ is executing in its critical section, then no other processes can be executing in their critical sections.
2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.
3. Bounded Waiting: There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. (Prevents starvation).

3. Software Solutions

Historically, several software algorithms were developed to solve the critical section problem for two processes without relying on special hardware instructions.

Peterson's Solution

Peterson's solution is a classic software-based solution to the critical-section problem. It is restricted to two processes that alternate execution between their critical sections and remainder sections.

The algorithm uses two shared data variables:

• int turn; (Indicates whose turn it is to enter the critical section).
• boolean flag[2]; (Indicates if a process is ready to enter the critical section).

// Process P_i
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j) {
        // Wait (Busy Waiting / Spinlock)
    }
    
    // CRITICAL SECTION
    
    flag[i] = false;
    
    // REMAINDER SECTION
} while (true);

While Peterson's solution is theoretically correct and satisfies all three requirements (Mutual Exclusion, Progress, Bounded Waiting), it is not guaranteed to work on modern computer architectures due to CPU instruction reordering and caching mechanisms. Modern OS developers rely on hardware synchronization primitives (Mutexes and Semaphores) instead.