Critical Section in Synchronization
When a process needs to read or modify something shared, whether that is a variable in memory, a file, a device, or a table, the piece of code where it does that is called a critical section. If two processes try to mess with the same shared resource at the same time without any coordination, you get a race condition, and the outcome becomes inconsistent or just plain wrong.
So the critical section problem is really about figuring out how to make processes take turns properly when they need to touch shared data.
How the Flow Works
Every process that needs to enter a critical section goes through a structured flow. First it hits the entry section, where it asks for permission. If granted, it goes into the critical section and does what it needs to do with the shared resource. Once done, it moves to the exit section, where it lets go of the resource and signals to other waiting processes that the coast is clear. Then it continues with whatever else it needs to do in the remainder section.
Three Things Any Solution Must Get Right
There are three conditions that any proper solution to this problem has to satisfy. All three must hold simultaneously.
| Requirement | What It Means | What Breaks Without It |
|---|---|---|
| Mutual Exclusion | One process in the critical section at a time. Everyone else waits. No exceptions. | Data corruption from simultaneous writes to shared resources. |
| Progress | If the critical section is empty and processes want in, one must be allowed to proceed. The decision cannot hang forever. | The system stalls in a deadlock where no process can enter. |
| Bounded Waiting | Every process that requests access must eventually get it. There is a limit on how many times others can cut in line. | Starvation: some processes wait indefinitely while others keep getting picked. |
Ways to Solve the Critical Section Problem
1. Peterson's Solution
A classic software-only approach for two processes. It uses a flag array to show that a process wants to enter and a turn variable to break ties when both want in at the same time. Simple and elegant, though limited to exactly two processes.
bool flag[2] = {false, false};
int turn;
void process_i(int i) {
int j = 1 - i;
flag[i] = true; // I want to enter
turn = j; // But you go first if we both want in
while (flag[j] && turn == j);
// --- Critical Section ---
flag[i] = false; // I'm done
}2. Test-and-Set
Uses a shared lock variable and an atomic hardware instruction to check and set it in one indivisible step. If the lock is already true, the process spins and waits. If not, it atomically sets it to true and enters. On exit, it resets the lock to false.
bool lock = false;
void process() {
while (test_and_set(&lock)); // Spin until lock is free
// --- Critical Section ---
lock = false; // Release the lock
}3. Compare-and-Swap
Works similarly to Test-and-Set but adds a conditional check. It only sets the lock if the current value matches an expected value, making it more controlled and suitable for building lock-free data structures.
int lock = 0;
void process() {
while (compare_and_swap(&lock, 0, 1) != 0);
// --- Critical Section ---
lock = 0;
}4. Semaphores
A more advanced tool that uses two atomic operations: wait() to request access and signal() to release it. They come in binary form (basically a 0 or 1 switch for mutual exclusion) or counting form for situations where more than one instance of a resource is available, like a pool of database connections.
semaphore S = 1; // Binary semaphore
void process() {
wait(S); // Decrement; block if S <= 0
// --- Critical Section ---
signal(S); // Increment; wake up a waiting process
}5. Mutex Locks
Built directly on the mutual exclusion concept. A process calls acquire() before entering and release() after exiting. Only one process holds the lock at a time, so only one gets through. Mutex locks are the most commonly used mechanism in modern application-level programming.
mutex m;
void process() {
m.acquire(); // Lock
// --- Critical Section ---
m.release(); // Unlock
}The Kernel Side of Things
The critical section problem does not only affect user-level processes. Inside the operating system kernel, many processes run concurrently and share kernel data structures like process lists, memory allocation tables, and interrupt handlers. Race conditions here are far more serious than in user space. A corrupted kernel data structure can bring down the entire system.
How a kernel handles this depends on whether it is preemptive or non-preemptive.
Non-Preemptive Kernels
Non-preemptive kernels sidestep the problem almost entirely. Once a process is running in kernel mode, nothing can pull it out until it finishes, blocks, or voluntarily gives up the CPU. Since only one kernel process runs at a time on a given processor, race conditions on kernel data simply do not happen.
The trade-off is responsiveness. If a kernel process takes too long, nothing else can run, making these kernels unsuitable for real-time applications.
Preemptive Kernels
Preemptive kernels are trickier. A running kernel process can be interrupted halfway through its execution, and another process can take over, potentially corrupting shared kernel data. But preemptive kernels are necessary for real-time systems where responsiveness matters, so they cannot just be swapped out for non-preemptive ones.
The common fix is spinlocks. When a kernel process grabs a spinlock, preemption and interrupts are disabled on that processor for the duration. The process runs through its critical section, then releases the spinlock, which re-enables interrupts.
Summary: Choosing the Right Tool
| Solution | Type | Best For | Limitation |
|---|---|---|---|
| Peterson's | Software | Two-process mutual exclusion | Does not scale beyond 2 processes |
| Test-and-Set | Hardware | Simple spinlocks | Busy waiting wastes CPU cycles |
| Compare-and-Swap | Hardware | Lock-free data structures | Complex to use correctly |
| Semaphores | OS-level | Resource pools with known capacity | Prone to misuse (forgetting signal()) |
| Mutex Locks | OS-level | General-purpose application locking | Cannot be used across processes without IPC |
| Spinlocks | Kernel | Very short kernel critical sections | Disables interrupts; must be held briefly |
Sort the Concepts
Classify each solution based on whether it operates at the Software/Application level or the Hardware/Kernel level.