1. Introduction
In a multiprogramming or multitasking operating system, multiple processes and threads often execute concurrently. These processes frequently need to access shared resources such as memory locations, files, databases, buffers, printers, or other system resources.
When multiple processes access shared data simultaneously without proper coordination, the final result may depend on the order of execution. Since process execution order is unpredictable, this can lead to inconsistent, incorrect, or unexpected outcomes.
To prevent such problems, operating systems use synchronization mechanisms that regulate access to shared resources.
The Critical Section Problem is one of the most fundamental problems in process synchronization and forms the basis for synchronization techniques such as:
Mutex Locks
Semaphores
Monitors
Condition Variables
Read-Write Locks
The objective is to design a protocol that ensures processes access shared resources safely and correctly.
2. What is a Critical Section?
A Critical Section (CS) is a portion of a program where a process accesses shared resources or shared data that must not be simultaneously accessed by multiple processes.
Formally:
A critical section is the part of a program that accesses shared resources and therefore requires mutual exclusion.
Examples of critical sections include:
Updating a shared variable
Writing to a shared file
Modifying a shared data structure
Updating a database record
Accessing a printer queue
Example
// Shared variable
int balance = 1000;
balance = balance - 100;
The statement above modifies shared data.
Therefore:
Critical Section
because simultaneous access may corrupt the value.
3. Structure of a Process
To solve the Critical Section Problem, a process is conceptually divided into four sections.
Entry Section
↓
Critical Section
↓
Exit Section
↓
Remainder Section
Each section has a specific purpose.
3.1 Entry Section
The Entry Section contains code that requests permission to enter the critical section.
Responsibilities:
Acquire lock
Wait if resource is busy
Enforce synchronization rules
Example:
lock.acquire();
The process cannot proceed to the critical section until permission is granted.
3.2 Critical Section
The Critical Section contains code that accesses shared resources.
Examples:
balance = balance - 100;
counter++;
write(file, data);
Only one process should execute this section at a time.
3.3 Exit Section
The Exit Section releases ownership of the shared resource.
Responsibilities:
Release lock
Wake waiting processes
Allow others to enter
Example:
lock.release();
3.4 Remainder Section
The Remainder Section contains all code unrelated to shared resources.
Example:
printf("Processing Complete");
Synchronization is not required here.
4. Conceptual Visualization of Critical Section
Consider two processes:
Process P1
and
Process P2
A correct execution sequence is:
P1 Enters CS
↓
P1 Exits CS
↓
P2 Enters CS
↓
P2 Exits CS
Incorrect execution:
P1 Inside CS
↓
P2 Inside CS
at the same time.
This violates synchronization requirements.
5. The Core Problem
The Critical Section Problem arises because operations on shared data are often not atomic.
Example
Consider a shared variable:
int x = 0;
Two processes execute:
Process P1
x = x + 1;
Process P2
x = x + 1;
Expected Result
x = 2
because:
0 + 1 + 1 = 2
Actual Execution
The statement:
x = x + 1;
is not executed as a single operation.
Internally it involves:
Read x
↓
Add 1
↓
Write x
Suppose the execution occurs as follows:
Step 1
P1 reads:
x = 0
Step 2
P2 reads:
x = 0
Step 3
P1 computes:
0 + 1 = 1
and writes:
x = 1
Step 4
P2 computes:
0 + 1 = 1
and writes:
x = 1
Final Result
x = 1
instead of:
x = 2
This incorrect outcome occurs because the processes executed concurrently.
The problem is known as a:
Race Condition
and is one of the primary motivations for synchronization mechanisms.
6. Requirements of a Correct Solution
Any valid solution to the Critical Section Problem must satisfy three essential requirements.
6.1 Mutual Exclusion
Definition
At most one process can be inside the critical section at any given time.
Formally:
If one process is executing in its critical section, no other process may execute in its critical section simultaneously.
Illustration
Valid:
P1 In CS
↓
P1 Leaves
↓
P2 Enters
Invalid:
P1 In CS
P2 In CS
at the same time.
Importance
Without mutual exclusion:
Race conditions occur
Data corruption occurs
Results become unpredictable
This is the most fundamental requirement.
6.2 Progress
Definition
If no process is currently in the critical section and some processes wish to enter, the selection of the next process must not be postponed indefinitely.
Formally:
The system must eventually decide which waiting process enters next.
Example
Suppose:
Critical Section Empty
and:
P1 Wants Entry
P2 Wants Entry
A decision must be made.
The system cannot remain indefinitely in a state where:
Nobody Enters
despite the resource being available.
Importance
Progress prevents unnecessary delays and deadlocks.
6.3 Bounded Waiting
Definition
A process requesting entry into the critical section should not wait forever.
Formally:
There must exist a finite limit on the number of times other processes can enter the critical section before the waiting process is allowed to enter.
Example
Suppose:
P1 Requests Entry
Then:
P2 Enters
P2 Leaves
P2 Enters
P2 Leaves
P2 Enters
repeatedly.
If this continues forever:
P1 Starves
which violates bounded waiting.
Importance
Bounded waiting guarantees fairness.
It prevents starvation.
7. Conceptual Representation
A correct execution sequence appears as:
Time →
P1 Enters CS
↓
P1 Exits
↓
P2 Enters CS
↓
P2 Exits
or:
Time →
P2 Enters CS
↓
P2 Exits
↓
P1 Enters CS
What must never occur:
Time →
P1 Inside CS
P2 Inside CS
simultaneously.
This violates mutual exclusion.
8. Why This Problem is Important
The Critical Section Problem is the foundation of process synchronization.
Almost every synchronization mechanism exists to solve it.
Mutex Locks
Ensure only one process enters the critical section.
Semaphores
Provide controlled access to shared resources.
Monitors
Offer high-level synchronization.
Condition Variables
Coordinate process execution.
Read-Write Locks
Handle concurrent readers and exclusive writers.
Understanding the Critical Section Problem is essential before studying any synchronization primitive.
9. Race Condition
A race condition occurs when the outcome of a program depends on the order in which concurrent processes execute.
Example
Shared variable:
counter = 0;
Two processes execute:
counter++;
simultaneously.
Possible results:
counter = 1
or
counter = 2
depending on timing.
Because execution order is unpredictable:
Result Becomes Unpredictable
This is called a race condition.
The Critical Section Problem aims to eliminate race conditions.
10. Real-World Analogy
Imagine a public restroom with only one stall.
Shared Resource
Bathroom
Processes
People Waiting
Requirements
Mutual Exclusion
Only one person can use the bathroom at a time.
Progress
If the bathroom is empty, someone should be allowed to enter.
Bounded Waiting
Nobody should wait forever while others repeatedly enter.
This analogy closely matches the Critical Section Problem.