Critical section problem and Peterson's software based solution

 

Critical Section and the Need for Synchronization

In a multiprogramming system, multiple processes execute concurrently and often share common data such as variables, files, or kernel data structures.

A critical section is a part of a program where a process accesses or updates shared data. Since shared data must remain consistent, only one process is allowed to execute in its critical section at any given time.

If two or more processes enter their critical sections simultaneously, it can lead to race conditions, where the result depends on the unpredictable order of execution.

Structure of a Process

A typical process is divided into four parts:

1. Entry Section – requests permission to enter the critical section

2. Critical Section – accesses shared resources

3. Exit Section – releases permission

4. Remainder Section – executes the rest of the code

while (true) {
    entry section
    critical section
    exit section
    remainder section
}

---

The Critical-Section Problem

The critical-section problem is to design a protocol that allows processes to cooperate safely while sharing data.

A correct solution must satisfy three requirements:

1. Mutual Exclusion

If one process is executing in its critical section, no other process may enter its critical section at the same time.

2. Progress

If no process is in the critical section and some processes want to enter, one of them must be selected without indefinite delay.

3. Bounded Waiting

There must be a limit on how long a process waits to enter its critical section after requesting access.

---

Critical Sections in the Operating System Kernel

The operating system kernel itself contains many critical sections. Examples include:

• Process lists

• Memory allocation tables

• Open-file lists

• Process ID (PID) assignment

Example: Race Condition in PID Allocation

If two processes call fork() simultaneously, both may read the same value of next_available_pid.

Without synchronization, both child processes could receive the same PID, which is incorrect.

This demonstrates why kernel-level synchronization is essential.

---

Preemptive vs Nonpreemptive Kernels

Nonpreemptive Kernel

• A process running in kernel mode cannot be preempted

• Only one kernel process runs at a time

• Naturally avoids race conditions

• Less responsive

Preemptive Kernel

• Kernel-mode processes can be preempted

• More responsive and better for real-time systems

• More complex to design

• Requires careful synchronization, especially on multiprocessor systems

Modern operating systems prefer preemptive kernels despite their complexity.

---

Peterson’s Solution

Peterson’s Solution is a classic software-based algorithm that solves the critical-section problem for two processes only.

Although it is not used in modern systems, it is important for understanding the principles of synchronization.

Shared Variables

int turn;
boolean flag[2];

• flag[i] → indicates whether process Pi wants to enter the critical section

• turn → indicates whose turn it is to enter the critical section

---

6. Algorithm (Process Pi)

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ;
    /* critical section */
    flag[i] = false;
    /* remainder section */
}

How It Works

1. Process Pi signals its intent by setting flag[i] = true

2. It gives the other process priority by setting turn = j

3. If the other process is not interested, Pi enters the critical section

4. If both want to enter, the value of turn decides who goes first

---

 Correctness of Peterson’s Solution

Mutual Exclusion

• Only one process can have the correct turn value

• Both processes cannot pass the while-loop at the same time

Progress

• If one process is not interested, the other can enter immediately

Bounded Waiting

• A process waits for at most one entry of the other process before entering

Thus, Peterson’s solution satisfies all three critical-section requirements.

---

 Limitations of Peterson’s Solution

Although logically correct, Peterson’s solution does not work reliably on modern hardware.

Reason: Instruction Reordering

• Compilers and processors may reorder instructions to improve performance

• This can violate the assumptions of the algorithm

Example Problem

A thread may see flag = true before the shared variable is updated, leading to incorrect behavior.

This reordering can cause:

• Race conditions

• Violation of mutual exclusion

---

 Why This Matters

Peterson’s solution shows:

• How difficult synchronization is

• Why hardware and OS-level synchronization tools (locks, atomic instructions, semaphores) are necessary

Modern systems rely on hardware-supported synchronization rather than pure software algorithms.

---

 Summary

• A critical section is where shared data is accessed

• Synchronization ensures correctness in concurrent execution

• The critical-section problem requires mutual exclusion, progress, and bounded waiting

• Peterson’s solution is a classic theoretical solution for two processes

• Modern systems use hardware-supported mechanisms due to instruction reordering