What is Critical Section Problem? Give the solution for critical...

Critical Section Problem: Definition, Requirements, and Solutions

The critical section problem in operating systems deals with coordinating multiple processes or threads that access shared data. The “critical section” is the part of a program where the shared resource is read or modified. If two or more processes enter their critical sections at the same time, it can cause race conditions and inconsistent results. The goal is to design a synchronization protocol so that shared data remains correct and the system remains efficient.

Conditions for a Correct Solution

Mutual Exclusion: At most one process is inside the critical section at any time.
Progress: If no process is in the critical section, one of the waiting processes should be able to enter soon; the decision cannot be postponed indefinitely.
Bounded Waiting: After a process requests entry, there is a limit on how many times other processes can enter before it gets a turn (prevents starvation).

Software Solution (Two Processes): Peterson’s Algorithm

Peterson’s algorithm is a classic software-only solution for two processes that ensures mutual exclusion, progress, and bounded waiting.

// Shared variables
boolean flag[2] = {false, false}; // intention to enter
int turn = 0;                     // whose turn it is (0 or 1)

// Code for Process i (i is 0 or 1; j = 1 - i)
flag[i] = true;        // I want to enter
turn = j;              // give turn to the other
while (flag[j] && turn == j) {
    // busy wait (spin) until it's safe to enter
}

// ----- Critical Section -----
// Access/modify shared data safely here

flag[i] = false;       // I'm leaving the critical section

// ----- Remainder Section -----

Works for two processes only.
Satisfies mutual exclusion, progress, and bounded waiting.

General Solution (N Processes): Semaphore-Based Mutex

Semaphores provide a general and practical solution for multiple processes or threads. A binary semaphore (mutex) controls entry to the critical section.

// Initialization (once)
semaphore mutex = 1;

// Code for each process/thread
wait(mutex);      // P() operation: request entry (decrement, may block)

// ----- Critical Section -----

signal(mutex);    // V() operation: release (increment, may wake one)

// ----- Remainder Section -----

Works for any number of processes.
Ensures mutual exclusion; with fair semaphore implementations, progress and bounded waiting are also achieved.
Typically avoids busy waiting by blocking threads while they wait.

Alternative Approach: Hardware Support (Test-and-Set Lock)

Many CPUs offer atomic instructions to build locks. A simple spinlock using Test-and-Set ensures mutual exclusion but may waste CPU while waiting.

// Shared lock
int lock = 0; // 0 = unlocked, 1 = locked

// Atomic instruction: returns old value and sets lock to 1
int TestAndSet(int *ptr);

// Code for each process/thread
while (TestAndSet(&lock) == 1) {
    // busy wait (spin)
}

// ----- Critical Section -----

lock = 0; // unlock

// ----- Remainder Section -----

Fast for short critical sections; can cause CPU spinning under contention.
Often combined with backoff or used inside higher-level primitives like semaphores and mutexes.

Summary

The critical section problem is about safely coordinating access to shared resources.
A correct solution must guarantee mutual exclusion, progress, and bounded waiting.
Peterson’s algorithm is a simple two-process software solution.
Semaphores (mutex locks) provide a scalable and practical solution for many processes and are widely used in operating systems.

Question Answer