What is the Critical Section Problem?
The critical section problem explained — mutual exclusion, progress, bounded waiting — with Peterson’s algorithm and a mutex code example.
Expected Interview Answer
The critical section problem is the challenge of designing a protocol that lets multiple concurrent processes or threads take turns using a shared resource safely, so that only one is ever inside the sensitive code section at a time.
A critical section is the part of a program that accesses shared data, such as a variable, file, or data structure, and any correct solution must guarantee three properties: mutual exclusion (only one process in the critical section at a time), progress (a process wanting to enter must eventually be allowed in if the section is free and there is no deadlock), and bounded waiting (there is a limit on how many times other processes can enter before a waiting process gets its turn, preventing starvation). Classic software solutions include Peterson’s algorithm for two processes, while practical operating systems rely on hardware-supported primitives like mutexes, semaphores, and atomic test-and-set instructions to enforce these guarantees efficiently. Getting the critical section wrong leads either to race conditions (no mutual exclusion) or to deadlock/starvation (no progress or bounded waiting).
- Defines the exact correctness criteria: mutual exclusion, progress, bounded waiting
- Foundation for understanding locks, semaphores, and monitors
- Prevents both race conditions and starvation when solved correctly
- Applies uniformly across threads, processes, and distributed systems
AI Mentor Explanation
A single practice net can only be used by one bowler at a time, so the team needs a fair sign-up sheet: only one bowler bowls at once, any bowler waiting for a free net must eventually get a turn, and no one can hog the net indefinitely while others wait. That sign-up protocol enforcing exclusive, fair, guaranteed access to the shared net is exactly the critical section problem.
Step-by-Step Explanation
Step 1
Identify the shared resource
Determine which code section touches data shared across threads or processes.
Step 2
Enforce mutual exclusion
Guarantee at most one process executes inside the critical section at any instant.
Step 3
Guarantee progress
If the section is free and someone wants in, the decision on who enters cannot be postponed forever.
Step 4
Guarantee bounded waiting
Cap how many times other processes can enter before a waiting process is finally let in, preventing starvation.
What Interviewer Expects
- Naming all three formal requirements: mutual exclusion, progress, bounded waiting
- At least one concrete mechanism that satisfies them (mutex, semaphore, Peterson’s algorithm)
- Distinguishing the critical section problem from a race condition (the problem vs the symptom)
- Mentioning that a broken solution risks either races or starvation/deadlock
Common Mistakes
- Naming only mutual exclusion and forgetting progress and bounded waiting
- Treating the critical section problem as identical to a race condition
- Assuming any lock automatically guarantees bounded waiting (fairness is not automatic)
- Not mentioning any real synchronization primitive as a solution
Best Answer (HR Friendly)
“The critical section problem is about making sure that when several parts of a program need to touch the same shared data, they take turns safely: only one at a time gets in, nobody who wants a turn is left out forever, and nobody unfairly cuts in line repeatedly.”
Code Example
#include <pthread.h>
#include <stdio.h>
int shared_balance = 100;
pthread_mutex_t balance_lock = PTHREAD_MUTEX_INITIALIZER;
void withdraw(int amount) {
pthread_mutex_lock(&balance_lock); /* enter critical section */
if (shared_balance >= amount) {
shared_balance -= amount; /* only one thread here at a time */
printf("Withdrew %d, balance now %d\n", amount, shared_balance);
} else {
printf("Insufficient funds for %d\n", amount);
}
pthread_mutex_unlock(&balance_lock); /* exit critical section */
}
int main(void) {
withdraw(40);
withdraw(90);
pthread_mutex_destroy(&balance_lock);
return 0;
}Follow-up Questions
- What is a race condition and how does it relate to the critical section problem?
- How does Peterson’s algorithm satisfy mutual exclusion for two processes?
- What is the difference between a mutex and a semaphore for solving this problem?
- What is priority inversion and how can it break bounded waiting guarantees?
MCQ Practice
1. Which is NOT one of the three required properties of a critical section solution?
The three required properties are mutual exclusion, progress, and bounded waiting — throughput is not a correctness guarantee.
2. Bounded waiting exists primarily to prevent?
Bounded waiting caps how long a process can be skipped over, preventing indefinite starvation.
3. A classic two-process software solution to the critical section problem is?
Peterson’s algorithm is a well-known software-only solution guaranteeing mutual exclusion for two processes.
Flash Cards
What is a critical section? — The part of code that accesses shared data and must run exclusively.
Name the three required properties. — Mutual exclusion, progress, and bounded waiting.
What does bounded waiting prevent? — Starvation — a process waiting forever while others repeatedly cut in.
Name one solution mechanism. — A mutex, semaphore, or Peterson’s algorithm for two processes.